Dynamic Programming Problem.

[Cinjection]

Today, I wrote the Dwite contest and tried to get #4 (http://dwite.org/questions/train_ride.html) complete, which I understand is a dynamic programming type problem. I've never written a solution to such a problem, but I gave it a go.

Here is what I got up to, in terms of a definition:

Let A[r][c] = The grid
Let D[r][c] = Least number of steps between [r][c] and 'S' (This is initialized to 999)
Let M(r, c) return the least number of steps to reach r,c

My recursive definition was:

M(r, c):
if (r || c are out of bounds) return 1000
if ( D[r][c] != 999) return D[r][c]
if ( A[r][c] = 'x' || ' ' ) return 1000;
if ( A[r][c] = 'S' ) return 0;
else:
return Min( M(r+1, c), M(r, c+1), M(r+1,c+1), M(r-1, c), M(r, c-1), M(r-1,c-1), M(r+1, c-1), M(r-1, c+1) ) + 1;

And I Fill the array (D) as such:
for (int i(0); i < 5; i++)
{
for(int j(0); j <10; j++)
D[i][j] = M(i,j);
}

And of course the final answer would be:

D[i][j], where i and j are the row and column positions of the ending point, respectively.

I really don't know if I'm going about this the correct way. I did not get to code to work for the contest, so I was wondering if someone could tell me if I'm at all close a valid DP solution.[/url]

[HeavenAgain]

its not really a DP problem, more of a BFS

[Cinjection]

HeavenAgain @ Tue Feb 12, 2008 6:57 pm wrote:

its not really a DP problem, more of a BFS

BFS? In any case, is this possible to do with DP? I research this for next time though.

[HeavenAgain]

http://en.wikipedia.org/wiki/Breadth-first_search
or
http://en.wikipedia.org/wiki/Depth-first_search

both can lead to your solution

[Cinjection]

HeavenAgain @ Tue Feb 12, 2008 6:59 pm wrote:

http://en.wikipedia.org/wiki/Breadth-first_search
or
http://en.wikipedia.org/wiki/Depth-first_search

both can lead to your solution

Yeah, I've read both of those already. I want a specific example to see how close I was to it.

[HeavenAgain]

first define a 2-d array, with default value thats very high
and get your starting position, and ending position, and just walk all the possible path, and take the shortest one
try download the top few submissions, and understand their code? Guppy Attack and kill -9 had a pretty clear solution (in my opinion, and for top 5 only, i didnt look at others yet)

[Cinjection]

HeavenAgain @ Tue Feb 12, 2008 8:32 pm wrote:

first define a 2-d array, with default value thats very high
and get your starting position, and ending position, and just walk all the possible path, and take the shortest one
try download the top few submissions, and understand their code? Guppy Attack and kill -9 had a pretty clear solution (in my opinion, and for top 5 only, i didnt look at others yet)

Hmm, we the process you described above seems more like a brute-force method, and I'd like to try to solve this with DP. As for checking out the other submissions, I have, but I really just want to see how close my particular solution is.

[OneOffDriveByPoster]

Hopefully a correct BFS implementation...

c++:

#include <cstdio> #include <cstring> #include <bitset> #include <deque> #include <utility> using namespace std; int const MAXN = 5; int const LINELEN = 10; int const NUMCASE = 5; int main(void) {     FILE *in = fopen("DATA4.txt", "r");     FILE *out = fopen("OUT4.txt", "w");     char lines[MAXN + 1][LINELEN + 2];     for (int caseno = 0; caseno < NUMCASE; ++caseno) {         int nn, sr, sc;         for (nn = 0; ; ++nn) {             fgets(lines[nn], LINELEN + 2, in);             lines[nn][LINELEN] = '\0';             if (strcmp("xxxxxxxxxx", lines[nn]) == 0) { break; }             for (int c = 0; c < LINELEN; ++c) {                 if (lines[nn][c] == 'S') { sr = nn; sc = c; }             }         }         int depth = 0;         deque<pair<int, int> > q;         bitset<MAXN * LINELEN> wasqueued;         q.push_back(make_pair(sr, sc) );         q.push_back(make_pair(-1, -1) );         wasqueued[sr * LINELEN + sc] = true;         while (!q.empty() ) {             int const r = q.front().first;             int const c = q.front().second;             q.pop_front();             if (r == -1 && c == -1) {                 ++depth;                 q.push_back(make_pair(-1, -1) );                 continue;             }             if (lines[r][c] == 'E') break;             for (int i = -1; i <= 1; ++i) {                 int const nr = r + i;                 if (nr < 0 || nr >= nn) continue;                 for (int j = -1; j <= 1; ++j) {                     int const nc = c + j;                     if (nc < 0 || nc >= LINELEN) continue;                     if (lines[r][c] == ' ') continue;                     if (wasqueued[nr * LINELEN + nc]) continue;                     q.push_back(make_pair(nr, nc) );                     wasqueued[nr * LINELEN + nc] = true;                 }             }         }         // assume 'E' reachable from 'S'         fprintf(out, "%d\n", depth);     }     return 0; }