0

Given the input xm, ym,h I have to find all paths from point (1,0,1) to (xm, ym, 1) in a 3d grid such as:

  1. possible moves from (x,y,z) are (x+1, y, z), (x+1, y+1, z), (x+1, y-1, z)

  2. if z < h more possible moves are (x+1, y, z+1), (x+1, y+1, z+1), (x+1, y-1, z+1)

  3. if z > 1 more possible moves are also (x+1, y, z-1), (x+1, y+1, z-1),(x+1, y-1, z-1)

I figured out an algorithm that works for z = 1, but I am not sure how to make it work for other values of z. Any assistance will be appreciated.

llong countPaths3(int xm, int ym, int h) {
    std::pair<int,int> pair1 = {1,0};
    std::map<std::pair<int,int>, llong> map1;
    map1.insert({pair,1});
    int starty = -1;
    int endy = 1;
    llong value = 0;
        for(int x = 2; x <= xm; x++) {
            for(int y = starty; y <= endy; y++)
            {
                if (map1.count({x, y}) == 0) {
                    value = map1[{x - 1, y}] + map1[{x - 1, y + 1}] + map1[{x - 1, y - 1}];
                }

                map1[{x, y}] = value;
            }
            starty--;
            endy++;
        }
        return map1[{xm,ym}];
}
Cadey Lewis
  • 41
  • 6
  • permutation count seems enough. – Jarod42 Jun 11 '20 at 21:44
  • could you elaborate? – Cadey Lewis Jun 12 '20 at 09:03
  • Path length is `xm`. y/z are unrelated so you can multiplies numbers of ways to go from y0-ym and z0-zm. – Jarod42 Jun 12 '20 at 12:12
  • My idea was to count permutation of `n1 + ym` incrementation, `n1` decrementation, and `xm - 2 * n1` "noop". so IIRC, `(xm!)/(n1!*(n1+ym)!*(xm - 2 * n1)!`. – Jarod42 Jun 12 '20 at 12:19
  • what does n1 stand for? – Cadey Lewis Jun 12 '20 at 12:25
  • Number of decrement (considered) :), As example, to go from 0 to 3 in 5 step, we have `[(3+, 2=, 0-), (4+, 0=, 1-)]` first case `n1=0`, second case `n1=1`. First case has 10 (`5!/(3!*2!*0!)`) permutations, second case has 5 (`5!/(4!*0!*1!)`) permutations, so a total of 15 ways. whereas it should work for unbounded `y`, `z` seems more complicated... – Jarod42 Jun 12 '20 at 12:38
  • @Jarod42 How can you deal with decreasing lower than 0? – Yonlif Jun 13 '20 at 12:21
  • @Jarod42 I used that y/z are unrelated so I multiplied the numbers of ways, thanks! – Cadey Lewis Jun 13 '20 at 22:54

1 Answers1

0

While this problem can be solved combinatorially it can also be solved using Dynamic Programming, with a time and memory complexity of O(xm * ym * h).

Consider a 3d array where each point at index i, j, k in array represents the number of ways to get from (1, 0, 1) to (i, j, k), we would like to find the value at the index (xm, ym, 1).

We need to start filling the array,
First fill the x = 1 layer, there are 0 ways to get everywhere except for (1, 0, 1) which has the value of 1.
Second fill the x = 2 layer, there are 0 ways to get everywhere except for (2, 0, 1), (2, 1, 1), (2, 0, 2) which has the value of 1.
Than fill the next layer, and the one above it and so on until you reach the xmth layer - at this point you are done.
The general formula to fill up the index (i, j, k) is:

A[i, j, k] = 
A[i-1, j-1, k-1] + A[i-1, j-1, k-1] + A[i-1, j-1, k-1] + 
A[i-1, j, k]     + A[i-1, j, k]     + A[i-1, j, k]     + 
A[i-1, j+1, k+1] + A[i-1, j+1, k]   + A[i-1, j+1, k+1]

As mentioned - filling up the array using this formula takes time and memory complexity of O(xm * ym * h).

Don't forget to check edge cases and fill the first layer manually.

Good luck.

Yonlif
  • 1,770
  • 1
  • 13
  • 31
  • Some technical note: Which index represents the x layer is important in order to fully [utilize the cache of the computer](https://stackoverflow.com/questions/16699247/what-is-a-cache-friendly-code). – Yonlif Jun 13 '20 at 13:26
  • I thought about something like that but for x = 2 I get (2, 0, 1), (2, 1, 1), (2, -1, 1). How can I deal with the negative value? – Cadey Lewis Jun 13 '20 at 18:39
  • "Don't forget to check edge cases" Check for `y` and `z` out of range, if it is than remove the invalid element from the sum. – Yonlif Jun 13 '20 at 20:24
  • for xm = 3, ym = 0, h = 1 (3,0,1) I should get answer 3 - it can be derived from (2,0,1), (2,1,1) and (2,-1,1) so (2,-1,1) should be counted. – Cadey Lewis Jun 13 '20 at 20:42
  • Oh sorry now I understand what you are saying... It is a bit more difficult to handle now but nothing too serious, the `y` dimension should actually be at the size of `2 * xm` where the first `xm` are negative values and the right ones are positive. – Yonlif Jun 13 '20 at 20:50