----------------------------------- zylum Thu Aug 12, 2004 1:59 am 2004 CCC S5 solution with memoization troubles ----------------------------------- 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: 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' 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' 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 Fri Aug 13, 2004 12:33 am ----------------------------------- 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: if (xInBounds(x)) { ... } Rather than: if (x < 1 || x > width) { ... } Would make your code far more readable. ----------------------------------- bugzpodder Fri Aug 13, 2004 5:34 am ----------------------------------- 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 Mon Aug 16, 2004 12:28 am ----------------------------------- 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 Mon Aug 16, 2004 7:11 am ----------------------------------- you can use whatever for stage 1... for stage 2 you must use C/C++/Pascal, and maybe java depending on the year ----------------------------------- wtd Wed Aug 18, 2004 2:20 pm ----------------------------------- 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... 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 Wed Aug 18, 2004 9:39 pm ----------------------------------- 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. 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 = 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 Wed Aug 18, 2004 10:28 pm ----------------------------------- 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: 1 5 * 7 It gave the expected answer of 8. Using a more complex example: 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 Wed Aug 18, 2004 10:49 pm ----------------------------------- And for fun I just sicced it on a file 990 lines long and 592 characters wide, randomly generated by this little Ruby program: 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 Wed Aug 18, 2004 11:03 pm ----------------------------------- 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 Wed Aug 18, 2004 11:11 pm ----------------------------------- 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 Thu Aug 19, 2004 2:44 am ----------------------------------- 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. ----------------------------------- wtd Thu Aug 19, 2004 5:51 am ----------------------------------- I hate to look like a fool, but I was wrong in this case. O'Caml doesn't provide automatic memoization of functions. In this case the only real benefit is the opportunity to apply the O'Caml optimizing compiler (which creates wickedly fast code), and the ability to work in a really nice language. :) ----------------------------------- zylum Tue Aug 24, 2004 9:45 pm ----------------------------------- i think your solution is wrong because the second test case you posted should return more than 19... remember the guy has to go from (0,0) to (width,0) and can move up/down/right and cannot go to places he's already been. ----------------------------------- wtd Tue Aug 24, 2004 9:55 pm ----------------------------------- i think your solution is wrong because the second test case you posted should return more than 19... remember the guy has to go from (0,0) to (width,0) and can move up/down/right and cannot go to places he's already been. Yeah. I fixed that. I was being a moron when I wrote that. :)