Robot in grid - unique paths

Problem

A robot is located at the top-left corner of a NXN grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

Approach

UniquePaths(row, column) = 0 if row > N or column > N

                                                1 if row ==N and column == N

                                                 UniquePaths(row+1, column) + UniquePaths(row, column+1)

i.e, the recursive method has optimal substructure and overlapping sub problems. So, the problem can be solved using Dynamic Programming.

Code Snippet

97. private int GetNumberOfUniquePaths(int row, int column, int N)
98.         {
99.             if ((row == N) && (column == N))
100.             {
101.                 return 1;
102.             }
103.             if ((row > N) || (column > N))
104.             {
105.                 return 0;
106.             }
107.             int uniquePathsByMovingDown = this.GetNumberOfUniquePaths(row + 1, column, N);
108.             int uniquePathsByMovingRight = this.GetNumberOfUniquePaths(row, column + 1, N);
109.             return uniquePathsByMovingDown + uniquePathsByMovingRight;
110.         }
111.         int GetNumberOfUniquePaths(int N)
112.         {
113.             int r = this.GetNumberOfUniquePaths(1, 1, N);
114.             return r;
115.         }

DP - Memoization (Top-Down - Lazy)

Code Snippet

14. int GetUniquePaths_DP_Memoization_Lazy(int N)
15.         {
16.             int?[][] DP_Memoization_Lazy_Cache = new int?[N + 1][];
17.             for(int i =0;i<=N;i++)
18.             {
19.                 DP_Memoization_Lazy_Cache[i] = new int?[N + 1];
20.                 for(int j=0;j<=N;j++)
21.                 {
22.                     DP_Memoization_Lazy_Cache[i][j] = null;
23.                 }
24.             }
25.             this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache, row: 1, column: 1);
26.             return DP_Memoization_Lazy_Cache[1][1].Value;
27.         }
28.         private int GetUniquePaths_DP_Memoization_Lazy(int?[][] DP_Memoization_Lazy_Cache, int row,
29.             int column)
30.         {
31.             int N = DP_Memoization_Lazy_Cache.Length - 1;
32.             if (row > N)
33.             {
34.                 return 0;
35.             }
36.             if (column > N)
37.             {
38.                 return 0;
39.             }
40.             if(DP_Memoization_Lazy_Cache[row][column] != null)
41.             {
42.                 return DP_Memoization_Lazy_Cache[row][column].Value;
43.             }
44.             if((row == N) && (column == N))
45.             {
46.                 DP_Memoization_Lazy_Cache[N][N] = 1;
47.                 return 1;
48.             }
49.             int pathsWhenMovedDown = this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache,
50.                 row + 1, column);
51.             int pathsWhenMovedRight = this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache,
52.                 row, column + 1);
53.             DP_Memoization_Lazy_Cache[row][column] = pathsWhenMovedDown + pathsWhenMovedRight;
54.             return DP_Memoization_Lazy_Cache[row][column].Value;
55.         }

Getting Paths

Code Snippet

56. Tuple<int, int>[][] GetUniquePaths(int N)
57.         {
58.             var r = this.GetUniquePaths(1, 1, N);
59.             return r;
60.         }
61.         private Tuple<int, int>[][] GetUniquePaths(int row, int column, int N)
62.         {
63.             if ((row == N) && (column == N))
64.             {
65.                 var r = new Tuple<int, int>[1][];
66.                 r[0] = new Tuple<int, int>[] { new Tuple<int,int>(row, column) };
67.                 return r;
68.             }
69.             if ((row > N) || (column > N))
70.             {
71.                 return new Tuple<int, int>[0][];
72.             }
73.             var uniquePathsByMovingDown = this.GetUniquePaths(row + 1, column, N);
74.             var uniquePathsByMovingRight = this.GetUniquePaths(row, column + 1, N);
75.             List<Tuple<int, int>[]> paths = this.MergePaths(uniquePathsByMovingDown,
76.                 row, column).ToList();
77.             paths.AddRange(this.MergePaths(uniquePathsByMovingRight, row, column));
78.             return paths.ToArray();
79.         }
80.         private Tuple<int, int>[][] MergePaths(Tuple<int, int>[][] paths,
81.             int row, int column)
82.         {
83.             Tuple<int, int>[][] mergedPaths = new Tuple<int, int>[paths.Length][];
84.             if (paths.Length > 0)
85.             {
86.                 Assert.IsTrue(paths.All(p => p.Length > 0));
87.                 for (int i = 0; i < paths.Length; i++)
88.                 {
89.                     List<Tuple<int, int>> mergedPath = new List<Tuple<int, int>>();
90.                     mergedPath.Add(new Tuple<int, int>(row, column));
91.                     mergedPath.AddRange(paths[i]);
92.                     mergedPaths[i] = mergedPath.ToArray();
93.                 }
94.             }
95.             return mergedPaths;
96.         }

DP - Bottom-Up

Code Snippet

97. int DP_BottomUp_GetNumberOfUniquePaths(int N)
98.         {
99.             int[][] DP_BottomUp_Tabular_Eager_Cache = new int[N + 1][];
100.             for (int row = 0; row <= N; row++)
101.             {
102.                 DP_BottomUp_Tabular_Eager_Cache[row] = new int[N + 1];
103.                 for (int column = 0; column <= N; column++)
104.                 {
105.                     if ((row == N)
106.                         || (column == N))
107.                     {
108.                         DP_BottomUp_Tabular_Eager_Cache[row][column] = 1;
109.                     }
110.                 }
111.             }
112.             for (int row = N - 1; row >= 1;row--)
113.             {
114.                 for (int column = N - 1; column >= 1; column--)
115.                 {
116.                     DP_BottomUp_Tabular_Eager_Cache[row][column] =
117.                         DP_BottomUp_Tabular_Eager_Cache[row + 1][column]
118.                         + DP_BottomUp_Tabular_Eager_Cache[row][column + 1];
119.                 }
120.             }
121.             return DP_BottomUp_Tabular_Eager_Cache[1][1];
122.         }

Unit Tests

Code Snippet

142. [TestMethod]
143.         [TestCategory(Constants.DynamicProgramming)]
144.         public void RobotInGridTests()
145.         {
146.             int p = this.DP_BottomUp_GetNumberOfUniquePaths(3);
147.             Assert.AreEqual(p, 6);
148.             p = GetNumberOfUniquePaths(3);
149.             Assert.AreEqual(p, 6);
150.             int p1 = this.GetUniquePaths_DP_Memoization_Lazy(3);
151.             Assert.AreEqual(p, p1);
152.             var p2 = this.GetUniquePaths(3);
153.             Assert.AreEqual(p1, p2.Length);
154.             foreach (var path in p2)
155.             {
156.                 Debug.WriteLine("===================================================================");
157.                 foreach (Tuple<int, int> t in path)
158.                 {
159.                     Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2));
160.                 }
161.             }
162.             p = this.DP_BottomUp_GetNumberOfUniquePaths(4);
163.             Assert.AreEqual(p, 20);
164.             p = GetNumberOfUniquePaths(4);
165.             Assert.AreEqual(p, 20);
166.             p1 = this.GetUniquePaths_DP_Memoization_Lazy(4);
167.             Assert.AreEqual(p, p1);
168.             p2 = this.GetUniquePaths(4);
169.             Assert.AreEqual(p1, p2.Length);
170.             foreach (var path in p2)
171.             {
172.                 Debug.WriteLine("===================================================================");
173.                 foreach (Tuple<int, int> t in path)
174.                 {
175.                     Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2));
176.                 }
177.             }
178.         }

Finding the number of paths mathematically

Say, if the grid is 4X4 => i.e, the number of unique paths is nothing but all possible permutations of RRRDDD where R represents right and D represents Down. For details, please see the attached image:

Related Links

http://leetcode.com/2010/11/unique-paths.html

http://stackoverflow.com/questions/10468779/calculating-number-of-moves-from-top-left-corner-to-bottom-right-with-move-in-an/25095898#25095898

http://stackoverflow.com/questions/9105699/algorithm-for-finding-all-paths-in-a-nxn-grid/25095973#25095973