Give or Take!?

Today I'll write about "Give" and "Take" in programming.

"Give" literally means that a module gives some information to other modules to calculate some value. While "take" means that a module takes some information from other modules.

Let's go over it more detail.

A simplest example would be recursion v.s. tail recursion.

Consider the problem below:

http://www.topcoder.com/stat?c=problem_statement&pm=10095&rd=13516

This problem can be solved with an easy DFS.

A "giving" solution to the problem would be as follows:

class CrazyBot {
public:
   double _e, _w, _s, _n;
   double ret;
   char passed[100][100];

   double getProbability(int n, int east, int west, int south, int north) {

       _e = east/100.;
       _w = west/100.;
       _s = south/100.;
       _n = north/100.;

       ret = 0.;
       memset(passed, 0, sizeof(passed));

       passed[50][50] = 1;
       solve(n, 1., 50, 50);

       return ret;
   }

   void solve(int n, double prb, int x, int y) {
       if (!n) {
           ret += prb;
           return;
       }

       passed[x][y] = 1;
       if (!passed[x-1][y]) solve(n-1, _w*prb, x-1, y);
       if (!passed[x+1][y]) solve(n-1, _e*prb, x+1, y);
       if (!passed[x][y-1]) solve(n-1, _n*prb, x, y-1);
       if (!passed[x][y+1]) solve(n-1, _s*prb, x, y+1);
       passed[x][y] = 0;

   }
};

I think the solution above is like what they call "tail recursion." But I would rather call this kind of recursive function "giving recursion." You can see that the function call itself and give the probability to it!

Another solution would be "taking" solution.

class CrazyBot {
public:
    double _e, _w, _s, _n;
    char passed[100][100];

    double getProbability(int n, int east, int west, int south, int north) {

        _e = east/100.;
        _w = west/100.;
        _s = south/100.;
        _n = north/100.;

        memset(passed, 0, sizeof(passed));
        passed[50][50] = 1;

        return solve2(n, 50, 50);
    }

    double solve2(int n, int x, int y) {
        if (!n)
            return 1.;

        double prb = 0.;
        passed[x][y] = 1;
        if (!passed[x-1][y]) prb += _w*solve2(n-1, x-1, y);
        if (!passed[x+1][y]) prb += _e*solve2(n-1, x+1, y);
        if (!passed[x][y-1]) prb += _n*solve2(n-1, x, y-1);
        if (!passed[x][y+1]) prb += _s*solve2(n-1, x, y+1);
        passed[x][y] = 0;

        return prb;
    }
};

This is a general recursive function you are familiar with.

Taking some information from the invoked functions, and calculate the return value.

Which type of recursion do you like?

I think I like the former because it's easy to think how things going on.

Aside from recursive functions, there are giving DP and taking DP.

Let' say you want to count how many pattern there exist to move P, the left below point of a rectangle, to Q, the right upper point.

You would solve the problem by constructing a two-dimensional matrix and doing the DP.

In this case, there could be two different coding -- giving and taking--.

Something like this:

e.g.) Giving DP

dp[x][y] = dp[x-1][y] + dp[x][y-1];

e.g.) Taking DP

dp[x+1][y] += dp[x][y];

dp[x][y+1] += dp[x][y];

Also, when solving DP problems regarding string manipulations, you can choose "giving" or "taking."

I think there's no big difference in speed and memory consumption between these two coding style. It's matter of taste.

But it's good to be able to write both styles and tactically use them depending on situations.