Memoized Grid Travelling Solution Runs as a Regular Recursive Solution

Question

Problem Statement:

You are at the top left corner of an m by n grid. How many ways you can reach the bottom right box if you can only move Down or Right?

Observations:

Found a similar question (2D grid travel (Dynamic Programming) - recursive solution working but not memoized one) but I don't think it solves my problem
Upon debugging, I find that the memory map visited or v is not used
The code runs as a simple recursive solution to the GridTraversal problem that is, the memoised part does not run at all.

Code:

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

string find_target(string target, map<string, unsigned>& v) {
    if (v.find(target) != v.end()) {
        cout << v[target] <<endl;
        return target;
    }
    return "0";
}

int gridTraveller(unsigned m, unsigned n, map<string, unsigned>& v) {
    
    string a =  m + "," + n;
    a = find_target(a, v);

    // Debugging
    // cout << a << " ";

    if (strcmp(a.c_str(), "0")!=0) return v[a];
    if (m==1 && n==1) return 1;
    else if (m==0 || n==0) return 0;
    
    v[a] = gridTraveller(m-1, n, v) + gridTraveller(m, n-1, v);
    return v[a];
}

int main() {
    cout<<"Enter no of rows: ";
    unsigned row; cin >> row;
    cout<<"Enter no of columns: ";
    unsigned col; cin >> col;
    map <string, unsigned> visited;
    cout << gridTraveller(row, col, visited);
    return 0;
}

Regular Output:

Enter no of rows: 3
Enter no of columns: 2
3

Debug Output:

Enter no of rows: 3
Enter no of columns: 2
0 0 0 0 0 0 0 0 0 0 0 0 0 3

score 0 · Answer 1 · answered Apr 22 '22 at 08:00

Found the error! Turns out I had a problem with the map keys - I had to convert the int to string before concatenation. Also found a better way to check if the key is already present in the map

string int_to_str(int x) {
   stringstream s;
   s << x;
   return s.str();
}

unsigned gridTraveller(unsigned m, unsigned n, map<string, unsigned>& v) {
    string a = int_to_str(m) + "," + int_to_str(n);
    if (v.count(a)) return v[a];
    ...
}

Memoized Grid Travelling Solution Runs as a Regular Recursive Solution

1 Answers1