Computer Science Canada

2004 CCC S5 solution with memoization troubles
Author:  zylum [ Thu Aug 12, 2004 1:59 am ]
Post subject:  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:
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
Author:  wtd [ Thu Aug 12, 2004 7:20 pm ]
Post subject: 
Thank you for proving that obfuscated Java can be written. Wink

Cleaning it up so I can figure out just what the heck it actually does.
Author:  bugzpodder [ Thu Aug 12, 2004 9:17 pm ]
Post subject: 
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?
Author:  zylum [ Thu Aug 12, 2004 11:44 pm ]
Post subject: 
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.
Author:  wtd [ Fri Aug 13, 2004 12:33 am ]
Post subject: 
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.
Author:  bugzpodder [ Fri Aug 13, 2004 5:34 am ]
Post subject: 
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
Author:  wtd [ Mon Aug 16, 2004 12:28 am ]
Post subject: 
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.
Author:  bugzpodder [ Mon Aug 16, 2004 7:11 am ]
Post subject: 
you can use whatever for stage 1... for stage 2 you must use C/C++/Pascal, and maybe java depending on the year
Author:  wtd [ Wed Aug 18, 2004 2:20 pm ]
Post subject: 
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.
Author:  wtd [ Wed Aug 18, 2004 9:39 pm ]
Post subject: 
And after all this talking about how great a solution in O'Caml would be, I should probably offer one. Smile

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 ()
Author:  wtd [ Wed Aug 18, 2004 10:28 pm ]
Post subject: 
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.
Author:  wtd [ Wed Aug 18, 2004 10:49 pm ]
Post subject: 
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.)
Author:  bugzpodder [ Wed Aug 18, 2004 11:03 pm ]
Post subject: 
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
Author:  wtd [ Wed Aug 18, 2004 11:11 pm ]
Post subject: 
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.
Author:  wtd [ Thu Aug 19, 2004 2:44 am ]
Post subject: 
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.
Author:  wtd [ Thu Aug 19, 2004 5:51 am ]
Post subject: 
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. Smile
Author:  zylum [ Tue Aug 24, 2004 9:45 pm ]
Post subject: 
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.
Author:  wtd [ Tue Aug 24, 2004 9:55 pm ]
Post subject: 
zylum wrote:
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. Smile

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy