Path sum: four ways

2015-09-12

Problem 083: Path sum: four ways

Description:

NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

131 673 234 103 018
201 096 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 037 331

Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.

Solution:

v                       4445 2697 5115 ... 5870
                        1096 0020 1318 ... 9377
         # ... #        9607 7385 0521 ... 9230
         . . . .        7206 3114 7760 ... 2187
         .  .  .        3620 8024 0577 ... 7505
         . . . .        1074 5438 9008 ... 6942
         # ... #        4295 1176 5596 ... 4757

>"d@"*>1-:::::"P"%5*"g"+\"P"/g"0"-\::"P"%5*"f"+\"P"/g"0"-\::"P"%5*"e"+\"P"/g"0"-\:  v
      |:p+"d"/"P"\+9%"P":\*:*"~~"p+2/"P"\+9%"P":\+*+55+*+55+*+55-"0"g/"P"\+"d"*5%"P"<                                                   >70g40g8+50g"d"+p  v
      >$120p92g9"d"p"Xdd"p>0>:40p   0>:50p40g"d"+50g"d"+g"X"-#v_820p"O"40g"d"+50g"d"+p 40g0`40g8+50g"d"+g40g9+50g"d"+g40g8+50g2+g+:70p`*|
                                     |-"P":+1                 <                       v                                                 <p+"d"g05+"c"g04"X"<
                    >     ^ |-"P":+1$<                                                                                                  >70g40g9+50g"c"+p  v
                            $                                                         >50g0`40g9+50g"c"+g40g9+50g"d"+g40g9+50g1+g+:70p`*|
                    |p070g07<                                                         v                                                 <p+"c"g05+"d"g04"X"<
                    >"O"9+"Od"+g.@                                                                                                            >70g40g55++50g"d"+pv
                                                                                      >40g"P"-40g55++50g"d"+g40g9+50g"d"+g40g55++50g2+g+:70p`*|
                                                                                      v                                                       <p+"d"g05+"e"g04"X"<
                                                                                                                                          >70g40g9+50g"e"+p"X"v
                                                                                      >50g"P"-40g9+50g"e"+g40g9+50g"d"+g40g9+50g3+g+:70p`*|
                                                              ^                                                                           <p+"e"g05+"d"g04    <

         # ... #         # ... #
         . . . .         . . . .
         .  .  .         .  .  .
         . . . .         . . . .
         # ... #         # ... #

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Now, after two pseudo-pathfinding problems we finally get a real one.

The right solution would proably be to search online for dijkstras algorithm, but I'm lazy and I kinda remember the essence - so I implement my own algorithm from what I remember about pathfinding :D.

The general idea is still the same - we generate a 80x80 grid where each cell contains the minimal distance to the node [0,0]. At the end we just have to look at the value of distance[79, 79]. Initially all distances are set to an absurdly high number.

Additionally we have a a 80x80 marker-grid where we mark cells either UNKNOWN (#), MARKED (0) or FINISHED (1). Initially all cells are Unknown.

We start our algorithm by setting distance[0, 0] = data[0, 0] and marker[0, 0] = MARKED

Then we execute the main loop until all cells are marked with FINISHED, in our main loop we do:

Search fo a MARKED cell
Calculate for all 4 directions the distance:
distance = distance[x, y] + data[x+1, y] (or x-1, y+1, y-1, depending on the direction)
If the calculated distance is less than the cached value (distance[x+1, y]) update the distance and set the updated cell to MARKED
Set our current cell to FINISHED (marker[x, y] = FINISHED)

Rinse and repeat until finished.

Interpreter steps:	11 718 762
Execution time (BefunExec):	1.75s (6.70 MHz)
Program size:	500 x 180
Solution:	425185
Solved at:	2015-09-12