2004 CCC S5 solution with memoization troubles

[zylum]

i was bored so i tried solving the S5 using memoization since the grid can be 100 by 100 and plane old recursion will take too long to solve the problem. so i first programmed my recursive solution but when i try to implement a memoization table it fails....

without memoization:

code:

class S5 {         static String[] map = { "      1",                                                         "  5    ",                                                         "  *    ",                                                         "  7    ",                                                         "       " };         static int width = map[0].length();         static int height = map.length;         public static void main(String[] args) {                         long time1 = System.currentTimeMillis();                         int ret = bestPath(1, 1, 0, 1);                         long time2 = System.currentTimeMillis();                         System.out.println(ret + " TIME: " + (time2 - time1));         }         static int bestPath(int x, int y, int amount, int dir) {                 if (x < 1 || x > width || y < 1 || y > height || map[y-1].charAt(x-1) == '*') return -Integer.MAX_VALUE;                 if (map[y-1].charAt(x-1) - '0' >= 0 && map[y-1].charAt(x-1) - '0'<= 9) amount += map[y-1].charAt(x-1) - '0';                 if (x == width && y == 1) return amount;                 return Math.max(Math.max(bestPath(x+1, y, amount, 0), dir == 1 ? -Integer.MAX_VALUE : bestPath(x, y-1, amount, -1)), dir == -1 ? -Integer.MAX_VALUE : bestPath(x, y+1, amount, 1));         } }

with memoization:

code:

class S5 {    static String[] map = {   "      1",                      "  5    ",                      "  *    ",                      "  7    ",                      "       " };    static int width = map[0].length();    static int height = map.length;    static int[][][] memo = new int[width][height][3];    public static void main(String[] args) {               //get initial time          long time1 = System.currentTimeMillis();          //initialize memo table          for (int i = 0; i < width; i++) for (int j = 0; j < height; j++) for (int k = 0; k < 3; k++) memo[i][j][k] = -Integer.MAX_VALUE;          //find best path          int ret = bestPath(1, 1, 0, 1);          //get final time          long time2 = System.currentTimeMillis();          //output best path and running time          System.out.println(ret + " TIME: " + (time2 - time1));    }    static int bestPath(int x, int y, int amount, int dir) {           //check if the coordinates are within the grid       if (x < 1 || x > width || y < 1 || y > height || map[y-1].charAt(x-1) == '*') return -Integer.MAX_VALUE;       //check if memo table has an answer to the current position       if (memo[x-1][y-1][dir+1] > -Integer.MAX_VALUE) return memo[x-1][y-1][dir+1];       //update the amount if the current location is an integer       if (map[y-1].charAt(x-1) - '0' >= 0 && map[y-1].charAt(x-1) - '0'<= 9) amount += map[y-1].charAt(x-1) - '0';       //if current position is final position, return amount       if (x == width && y == 1) return amount;       //update memo table while checking which direction you can go (up/down)       memo[x-1][y-1][dir+1] = Math.max(Math.max(bestPath(x+1, y, amount, 0), dir == 1 ? -Integer.MAX_VALUE : bestPath(x, y-1, amount, -1)), dir == -1 ? -Integer.MAX_VALUE : bestPath(x, y+1, amount, 1));       //return best path       return memo[x-1][y-1][dir+1];    } }

in the case that im using the answer should be 8

any help implementing would be great

[wtd]

Thank you for proving that obfuscated Java can be written.

Cleaning it up so I can figure out just what the heck it actually does.

[bugzpodder]

at the contest i wanted to use memoization but i used DP in the end, but i dont remember the reason. there may be some faulty logic (although i couldnt think of any now) although in theory most if not all DP problem can be done using memoization and vice versa.

in your program why did you initialize memo AFTER you call best path?
also, since memo stores the best amount, then you shouldnt keep amount as a variable right?

[zylum]

wtd > the code looks bad in the forum view, try copying it to you editor. also if you still dont follow, i updated the "with memo" version to include commenting.

bugz > oops, i didnt notice that i initialized the memo table after calling the function. it doesnt matter though since an integer is still greater than an integer variable which is not initialized.

[wtd]

The primary thing you need to do is factor out a lot of the code into methods. Like checking to see if x and y are within the proper bounds.

Being able to say:

code:

if (xInBounds(x)) { ... }

Rather than:

code:

if (x < 1 || x > width) { ... }

Would make your code far more readable.

[bugzpodder]

zylum, i assume that you have fixed the initialization error but it still doesnt work (im not sure how java initializes so if you say it doesnt matter...)
and what about the second point i've mentioned... i was wrong to say that you need to take out the amount variable, but i dont think you've updated it correctly. look into that

[wtd]

You mentioned the recursive solution being impractical for large datasets...

Can you implement in any language, or does the contest limit submissions to Java?

I ask because there are languages which do far more optimization for recursion. I'd reimplement in O'Caml for the heck of it, if you could provide a detailed explanation of exactly what the problem is. Even the CCC example doesn't provide much of an explanation of what's actually required.

[bugzpodder]

you can use whatever for stage 1... for stage 2 you must use C/C++/Pascal, and maybe java depending on the year

[wtd]

Ah. It's a shame you have to use one of those languages.

Using a functional language you could get an incredible speed-up. Consider this particular problem, for example. A functional language could essentially give you the "memoization" for free, without writing additional code.

Crazy you say?

Not really.

The reason Java, C++, etc. can't give you this is the presence of side-effects. A function called with the same arguments in these languages can't be guaranteed to have the same result. In many functional languages, this can be assumed.

If I have a map called my_map which takes a row number and a column number...

code:

best_path my_map 3 0

Will always return the same thing, assuming my_map stays the same. As a result, the compiler can cache the result of that expression. Any future occurrences of that expression will simply be replaced by a constant value. As with the memoization example you wrote, the best path for any given start point will only be calculated once, even if we use a recursive solution.

[wtd]

And after all this talking about how great a solution in O'Caml would be, I should probably offer one.

Yeah, it looks better with syntax highlighting, especially since O'Caml has a... robust... syntax. Highlighting is available for many editors, including popular ones like vim and Textpad on Windows.

All it needs is some logic to let it read in the map from a file.

code:

module S5 =         struct                 module StringUtils =                         struct                                 let rec string_chars s =                                         try (String.get s 0) :: string_chars (String.sub s 1 ((String.length s) - 1))                                         with _ -> [];;                         end                                                 let map = ["   1";" 5  ";" *  ";" 7  "]                                 let rec make_map = function                         [] -> []                         | first_row::others -> (StringUtils.string_chars first_row) :: make_map others                 let get_map_height map =                         List.length map                                         let get_map_width map =                         try List.length (List.hd map)                         with Failure "hd" -> 0                 exception Out_of_grid                 exception End_of_run                                 let get_map_cell map row column =                         try List.nth (List.nth map row) column                         with _ -> raise Out_of_grid                                                 let in_map map row column =                         try let temp = get_map_cell map row column in true                         with Out_of_grid -> false                                         let up_move_possible row =                         row > 0                                         let right_move_possible map column =                         let width = get_map_width map in                                 column < (width - 1)                                                 let acceptable_int i =                         i >= 0 && i <= 9                                         let filter_cell_char_to_int cell =                         let cell_int = (int_of_char cell) - (int_of_char '0') in                                 if acceptable_int cell_int then cell_int                                 else if cell = '*' then -1                                 else 0                                                 let rec best_path map row column =                         let current_cell = get_map_cell map row column in                                 let current_int_value = filter_cell_char_to_int current_cell in                                         if current_cell = '*' then                                                 0                                         else if (up_move_possible row) && (right_move_possible map column) then                                                 let up_cell = get_map_cell map (row - 1) column and                                                 right_cell = get_map_cell map row (column + 1) in                                                         let up_cell_int_value = filter_cell_char_to_int up_cell and                                                         right_cell_int_value = filter_cell_char_to_int right_cell in                                                                 if up_cell_int_value >= right_cell_int_value then                                                                         current_int_value + best_path map (row - 1) column                                                                                                                else                                                                         current_int_value + best_path map row (column + 1)                                         else if up_move_possible row then                                                 current_int_value + best_path map (row - 1) column                                         else if right_move_possible map column then                                                 current_int_value + best_path map row (column + 1)                                         else                                                 current_int_value         end open S5 let _ =         let std_map = S5.make_map S5.map and         start_row = 3 and start_column = 0 in                 let this_best_path = S5.best_path std_map start_row start_column in                         print_int this_best_path;                         print_newline ()

[wtd]

Attached is a solution I wrote that allows input files. I've added a .txt extension to the source file to make it possible to post here, since ".ml" seems to be blocked.

Using the same simple test:

code:

1  5   *   7

It gave the expected answer of 8.

Using a more complex example:

code:

8                  9       *5                4        3            2     7  1         9                              **  *                      9                     5  6       3 2    1   4  98                   1                                               9                        5****         **    4 5 67               *                         3 *       9 1 2 3

It gave me 19. I don't have a working reference implementation to compare this to, so I'll ask if someone can test it.

First thing I notice, though, is that both implementations seem to take virtually identical amounts of time, even though the level of recursion in the second example is far greater, even with all of the asterisks limiting potential paths.

[wtd]

And for fun I just sicced it on a file 990 lines long and 592 characters wide, randomly generated by this little Ruby program:

code:

cols = rand 1000 rows = rand 1000 def rand_line(len)         Array.new(len) {                 case rand(10)                         when 5, 6 then rand(9) + 1                         when 0 then "*"                         else " "                 end         }.join end puts Array.new(rows) { rand_line(cols) }.join("\n")

It had to think about this one, but computed the answer (whether correct or not, I don't know, though it should be) in a minute or two (I haven't been able to properly benchmark).

How long would a file of that size take your Java example? (I'm not gloating. I'm genuinely curious if standard Java is robust enough for this kind of recursion.)

[bugzpodder]

attach the file you used here and i'll happily compile my solution using java and give you the execution time using my PIII 660mHZ snail armed with XP

[wtd]

See attachment.

Oh, and I ran this example with O'Caml 3.07+2 on an AMD Athlon XP 1800+ with 256MB of RAM, 80GB HD, and Windows 2000 Professional. I'll give your time some leeway, considering the difference in computing power.

[wtd]

You know, I'm pretty sure there's an error in my algorithm. Working to correct it.

Edit: the correct version is included, along with Sys.time, which outputs the time the process has been running in seconds as a float. I'm on a very slow machine, so I'll test this against that huge file tomorrow.

Might also whip up a C version for comparison's sake.