Path sum: two ways

2015-09-12

Problem 081: Path sum: two ways

Description:

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

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 top left to the bottom right by only moving right and down.

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"<
      $                                                                              >20g8+30g"d"v
      >0>:20p   0>:30p20g9+30g2+g20g9+30g"c"+g20g8+30g"d"+g20g30g+!#v_20g!#v_30g!#v_`|
                 |-"P":+1p+"d"g03+9g02                           <      <     <     <>20g9+30g"c"v
        |-"P":+1$<                                               ^$$<   ^+$<  ^+$\< ^         +g+<
        $
        >"O"9+"Od"+g.@

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

Download

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

Explanation:

Well, this is practically extremely simple path finding.

We generate an array where we remember the shortest distance from [0,0] to this node. Initially we can set distance[0, 0] = data[0,0]

The we got through our data row by row and column by column. The distance of every node we visit is the minimum of top-node-distance + own value and left-node-distance + own value.

Then after we iterated through every single node the result is written in the bottom right corner.