Path sum: three ways

2015-09-12

Problem 082: Path sum: three ways

Description:

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

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

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"<
      $
      >"P">1-::9\2+gv
          |:p+"d"\9\<                                                             >$$v                                                          >v
          >$1>:20p0>:30p20g8+30g"d"+g40p30g>:50p40g20g9+50g2+g+::40p20g9+50g"d"+g`|  >20g8+30g"d"+g40p30g>:50p40g20g9+50g2+g+::40p20g9+50g"d"+g`|
                   ^  <                    |-"P":+1                  p+"d"g05+9g02<  $                   |+1:-1                    p+"d"g05+9g02<
                      |-"P":+1             >#                                        ^#                 $<$                                      <
             |-"P":+1$<                            >70v
             >$"O"9+"Od"+g70p"O">1-:"X"\"d"+g:70g`!|
                                |:                $<0p<
                                >$70g.@

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

Download

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

Explanation:

As the problem description states this is similar to problem-081.

Again we generate an node-array where we remark the minimal distance from the left side to this node. Initially we can initialize the left column with its input values. (distance[0, y] = data[0, y]) and all the other nodes with an absurdly high number.

Then we iterate through all remaining columns:

For each column x we go all possible ways from the previous column. That means:

Choose the start-row y (and do this for all possible start rows)
Get the distance to reach this row by calculating distance[x-1, y] + data[x, y]
Then go all the way up and down and calculate the distance on the way distance[x-1, y] + data[x, y] + data[x, y - 1] + data[x, y - 2] ...
For each node where this distance is lesser than the current one we update distance array.
Optimization node: Once we find a node where the distance is greater than a previous calculated we can stop further traversing the column (in this direction)

At the end we have an distance array where each node is the minimal distance to reach this node from the left side. Our result is then the minimal value of the most-right column.

Note: While problem-081 hat an time complexity of O(n) this one has one of O(n^2). But for an 80x80 array that's still fast enough and really not an problem.

Interpreter steps:	13 777 233
Execution time (BefunExec):	2.11s (6.54 MHz)
Program size:	500 x 180
Solution:	260324
Solved at:	2015-09-12