CODEWITHSUNDEEP
c++dynamic-programming
user15032639
user15032639

Reputation: 53

My implementation of the grid traveller problem only works for small grids

I am attempting this problem at 38:39 into this free code camp video: https://youtu.be/oBt53YbR9Kk?t=2361

The question is as follows:

Say that you are a traveller on a 2D grid. You begin in the top left corner and 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 to the goal on a grid with dimensions m*n

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

My attempt gives the correct answer for everything except the 18 by 18 grid, here is my code:

#include <iostream>
#include <map>


struct grid {
  unsigned long long int x,y;
  grid(unsigned long long int x_c, unsigned long long  int y_c):x(x_c),y(y_c){};

 bool operator< (const grid& rhs) const {
    return (x + y < rhs.x+rhs.y);

}
};



unsigned long long int grd_traveller(grid grd, std::map <grid,unsigned long long int> &mem){
  if (mem.count(grd) != 0){
    return mem[grd];
  }
  else if (grd.x ==1 || grd.y ==1){
    return 1;
  }

  else if (grd.x==0 || grd.y ==0){
    return 0;
  }
  else {
    grid iter1(grd.x-1,grd.y);
    grid iter2(grd.x,grd.y-1);

    unsigned long long int answer =  grd_traveller(iter1,mem) + grd_traveller(iter2,mem);
    mem[grd] = answer;
    return answer;
  }
}



int main(){
  std::map <grid,unsigned long long int> memory;
  std::cout << std::to_string(grd_traveller(grid(1,1),memory))<<"\n"; // Should give 1 and does
  std::cout << std::to_string(grd_traveller(grid(2,3),memory))<<"\n"; // Should give 3 and does
  std::cout << std::to_string(grd_traveller(grid(3,2),memory))<<"\n"; // Should give 3 and does
  std::cout << std::to_string(grd_traveller(grid(3,3),memory))<<"\n"; // Should give 6 and does
  std::map <grid,unsigned long long int> memory2;
  std::cout << grd_traveller(grid(18,18),memory2)<<"\n"; // Should give 2333606220, but doesn't 

}

At first I thought it might be memory issues so I increased everything to an unsigned long long int but that has not fixed it. What is even stranger is that for the 18 by 18 grid I get a different answer if I use the first map memory or the second map memory2. This is very weird and I am at a loss as to what is causing this behaviour. Does anyone have any ideas?

Upvotes: 0

Views: 387

Answers (2)

Feras Alnajjar
Feras Alnajjar

Reputation: 1

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long

//memoization.

ll grid(ll x, ll y) {
    static map<pair<ll, ll>, ll>memo;
    if (x == 0 || y == 0) return 0;
    if (x == 1 && y == 1) return 1;
    if (memo.count(make_pair(x, y)) > 0) return memo[make_pair(x, y)];
    memo[make_pair(x, y)] = grid(x - 1, y) + grid(x, y - 1);
    return memo[make_pair(x, y)];
    
}



int main() {
    cout << grid(18, 18);
    return 0;
}

Upvotes: -1

Cem
Cem

Reputation: 1296

The problem is in your comparison operator overload:

x + y < rhs.x+rhs.y

This check is not enough since it just compares the sum of coordinates. You should write one that checks the coordinates in a certain order:

x < rhs.x || x == rhs.x && y < rhs.y

Otherwise, for example, grids with coordinates (1, 5) and (2, 4) are considered to be equal by the std::map container since 1 + 5 == 2 + 4.

Upvotes: 3

Related Questions