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    <

# ... #         # ... #
. . . .         . . . .
.  .  .         .  .  .
. . . .         . . . .
# ... #         # ... #
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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript