Grid Traveler – Tabulation

It is another nice and hot spring day in the Twin Cities of Minneapolis and St. Paul. Yesterday after work my wife and I headed to the bank. On our way back I noticed that the temperature had gone up to 99F.

Earlier today after breakfast my wife and I went out on our daily walk. There were more people than usual. We stopped to talk with a neighbor that was also out and about. She likes to walk at a good pace. She was covered in sweat.

The forecasted temperatures for the next couple weeks will are in the mid 80s to the mid 90s. During lunch time the temperature went up to 93F. In general the high temperature for the day occurs around 05:00 PM.

A couple weeks ago we were talking with a couple of neighbors. They mentioned that some of our plants in the front yard were dead. Today during lunch the company that handles plants and lawns stopped by to remove and replace all the dead shrubs.

On a separate note, things are not going well with the vote counting process. There seems to be a lot of cheating going on. It seems that the candidate that represents communism and terrorism will get elected president. The economy has come to a standstill. The Peruvian currency is devaluating.

In addition the candidate from the left is instigating people to go after the upper and middle classes. Hope this things is resolved peacefully in the next few days.

I continue to watch and experiment with the materials presented in the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges.

Say that you are a traveler on a 2D grid. You begin in the
top-left corner and your goal is to travel to the bottom-right
corner. You may only move down or right.

In how many ways can you travel to the goal on a grid with
dimensions m * n?

Write a function `grdTraveler(m, n) that calculates this.

We saw this problem earlier in the course. Last time we solved it using recursion and had to optimize it using memoization. Today we are supposed to solve the problem using the tabulation technique.

The course uses JavaScript. We will be using Java and the VSCode IDE on a Windows 10 computer. Of course any portable programming language should do.

int gridTraveler(int m, int n) {
}

The signature for the function in question is the same as before. We are given a table / matrix and we need to find out how many different paths can be used to traverse the grid from the top-left to the bottom-right corners moving down and right.

If interested on the comments and solution using recursion and memoization, you can find it in the Grid Traveler or Unique Paths post in this blog.

0,0
main <<< m: 0 n: 0
main <<< gridTraveler: 0


1,0
main <<< m: 1 n: 0
main <<< gridTraveler: 0


0,1
main <<< m: 0 n: 1
main <<< gridTraveler: 0


1,1
main <<< m: 1 n: 1      
main <<< gridTraveler: 1


2,3
main <<< m: 2 n: 3
gridTraveler <<< table:
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 2, 3]
main <<< gridTraveler: 3


3,2
main <<< m: 3 n: 2
gridTraveler <<< table:
[0, 0, 0]
[0, 1, 1]
[0, 1, 2]
[0, 1, 3]
main <<< gridTraveler: 3


3,3
main <<< m: 3 n: 3
gridTraveler <<< table:
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 2, 3]
[0, 1, 3, 6]
main <<< gridTraveler: 6


6,6
main <<< m: 6 n: 6
gridTraveler <<< table:
[0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 3, 6, 10, 15, 21]
[0, 1, 4, 10, 20, 35, 56]
[0, 1, 5, 15, 35, 70, 126]
[0, 1, 6, 21, 56, 126, 252]
main <<< gridTraveler: 252


18,18
main <<< m: 18 n: 18
gridTraveler <<< table:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171]
[0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140]
[0, 1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985]
[0, 1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568, 11628, 15504, 20349, 26334]
[0, 1, 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, 18564, 27132, 38760, 54264, 74613, 100947]
[0, 1, 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, 31824, 50388, 77520, 116280, 170544, 245157, 346104]    
[0, 1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 43758, 75582, 125970, 203490, 319770, 490314, 735471, 1081575]
[0, 1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92378, 167960, 293930, 497420, 817190, 1307504, 2042975, 3124550]
[0, 1, 11, 66, 286, 1001, 3003, 8008, 19448, 43758, 92378, 184756, 352716, 646646, 1144066, 1961256, 3268760, 5311735, 8436285]
[0, 1, 12, 78, 364, 1365, 4368, 12376, 31824, 75582, 167960, 352716, 705432, 1352078, 2496144, 4457400, 7726160, 13037895, 21474180]
[0, 1, 13, 91, 455, 1820, 6188, 18564, 50388, 125970, 293930, 646646, 1352078, 2704156, 5200300, 9657700, 17383860, 30421755, 51895935]
[0, 1, 14, 105, 560, 2380, 8568, 27132, 77520, 203490, 497420, 1144066, 2496144, 5200300, 10400600, 20058300, 37442160, 67863915, 119759850]
[0, 1, 15, 120, 680, 3060, 11628, 38760, 116280, 319770, 817190, 1961256, 4457400, 9657700, 20058300, 40116600, 77558760, 145422675, 265182525]
[0, 1, 16, 136, 816, 3876, 15504, 54264, 170544, 490314, 1307504, 3268760, 7726160, 17383860, 37442160, 77558760, 155117520, 300540195, 565722720]
[0, 1, 17, 153, 969, 4845, 20349, 74613, 245157, 735471, 2042975, 5311735, 13037895, 30421755, 67863915, 145422675, 300540195, 601080390, 1166803110]
[0, 1, 18, 171, 1140, 5985, 26334, 100947, 346104, 1081575, 3124550, 8436285, 21474180, 51895935, 119759850, 265182525, 565722720, 1166803110, 2333606220]
main <<< gridTraveler: 2333606220

The input arguments are provided in a single line. The first is the number of rows `m` and the second the number of columns `n` in the 2D grid.

After our test code reads the input line it generated and displays the two variables with the specified values.

Our code seems to call the function in question, compute the answer and display the returned value.

The first four test cases are intended to check the simple cases.

Starting with the fifth test case our code seems to display the updated grid. The result is located at the lower-right corner. The value is then displayed after calling the function in question.

Take a few seconds and look at the test cases in the Grid Traveler or Unique Paths post. In that case we used memoization and stored the values in a 2D grid. The values are the same as the ones we obtain using the tabulation technique. The difference is that in this case we loop through the grid instead of calling recursively a function.

**** Tabulation Recipe ****

1. Visualize the problem as a table
2. Size the table based on the inputs
3. Initialize the table with some values
4. Seed the trivial answer into the table
5. Iterate through the table
6. Fill further positions based on the current position

The tabulation steps can be well defined. The implementation of some requires some insights into the specific problem.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read m and n ****
        int[] mn = Arrays.stream(br.readLine().trim().split(","))
                    .mapToInt(Integer::parseInt)
                    .toArray();

        // **** close buffered reader ****
        br.close();

        // **** create and set m and n ****
        int m = mn[0];
        int n = mn[1];

        // ???? ????
        System.out.println("main <<< m: " + m + " n: " + n);

        // **** generate and display answer ****
        System.out.println("main <<< gridTraveler: " + gridTraveler(m, n));
    }

Our test code is quite simple. We read the input line and extract the values for `m` and `n`.

We then call the function in question with the specified arguments and display the result. The code seems to match very close the previous description on the test cases.

    /**
     * Say that you are a traveler on a 2D grid. You begin in the
     * top-left corner and your goal is to travel to the bottom-right
     * corner. You may only move down or right.
     * 
     * In how many ways can you travel to the goal on a grid with
     * dimensions m * n?
     * 
     * Use tabulation.
     * 
     * Time: O(m * n) - Space: O(m * n)
     */
    static long gridTraveler(int m, int n) {

        // **** sanity checks ****
        if (m == 0 || n == 0) return 0;
        if (m == 1 && n == 1) return 1;

        // **** initialization ****
        long[][] table = new long[m + 1][n + 1];
        table[1][1] = 1;

        // **** traverse each row in table ****
        for (int r = 0; r < table.length; r++) {

            // **** traverse each column in this row in table ****
            for (int c = 0; c < table[r].length; c++) {

                // **** fill lower cell in table (if possible) ****
                if (r < m)
                    table[r + 1] += table[r];

                // **** fill right cell in table (if possible) ****
                if (c < n)
                    table[r] += table[r];
            }
        }

        // ???? ????
        System.out.println("gridTraveler <<< table: ");
        for (int i = 0; i < table.length; i++)
            System.out.println(Arrays.toString(table[i]));

        // **** return answer ****
        return table[m][n];
    }

We start by adding a couple sanity tests.

In the initialization we create a 2D table and initialize one element. This is all that is needed to start traversing the table while updating entries.

We then have two loops. The outer traverses the rows while the second the columns in the 2D table.

For each location in the table we update the lower and right cells if needed.

We display the final contents of the table so we can compare them with the matrix we generated in the recursive implementation with memoization.

Finally we return the value of the lower-right cell in the table.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John