Maximum triangle path sum: Difference between revisions

From Rosetta Code
Content added Content deleted
(+ second Python entry)
(Better task description.)
Line 30: Line 30:
06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93</pre>
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93</pre>

Such numbers can be included in the solution code, or read from a "triangle.txt" file.


This task is derived from the [http://projecteuler.net/problem=18 Euler Problem #18].
This task is derived from the [http://projecteuler.net/problem=18 Euler Problem #18].


=={{header|D}}==
=={{header|D}}==
This solution assumes the triangle is in a "triangle.txt" file.

<lang d>void main() {
<lang d>void main() {
import std.stdio, std.algorithm, std.range, std.file, std.conv;
import std.stdio, std.algorithm, std.range, std.file, std.conv;
Line 49: Line 49:


=={{header|Haskell}}==
=={{header|Haskell}}==
This solution assumes the triangle is in a "triangle.txt" file.

<lang haskell>parse = map (map read . words) . lines
<lang haskell>parse = map (map read . words) . lines
f x y z = x + max y z
f x y z = x + max y z

Revision as of 13:03, 20 February 2014

Starting from the top of a pyramid of numbers like this, you can walk down going one step on the right or on the left, until you reach the bottom row:

                          55
                        94 48
                       95 30 96
                     77 71 26 67

One of such walks is 55 - 94 - 30 - 26. You can compute the total of the numbers you have seen in such walk, in this case it's 205.

Maximum triangle path sum is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it's 321.

Task: find the maximum total in the triangle below:

                          55
                        94 48
                       95 30 96
                     77 71 26 67
                    97 13 76 38 45
                  07 36 79 16 37 68
                 48 07 09 18 70 26 06
               18 72 79 46 59 79 29 90
              20 76 87 11 32 07 07 49 18
            27 83 58 35 71 11 25 57 29 85
           14 64 36 96 27 11 58 56 92 18 55
         02 90 03 60 48 49 41 46 33 36 47 23
        92 50 48 02 36 59 42 79 72 20 82 77 42
      56 78 38 80 39 75 02 71 66 66 01 03 55 72
     44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93

Such numbers can be included in the solution code, or read from a "triangle.txt" file.

This task is derived from the Euler Problem #18.

D

<lang d>void main() {

   import std.stdio, std.algorithm, std.range, std.file, std.conv;
   "triangle.txt".File.byLine.map!split.map!(to!(int[])).array.retro
   .reduce!((x, y) => zip(y, x, x.dropOne)
                      .map!(t => t[0] + t[1 .. $].max)
                      .array)[0]
   .writeln;

}</lang>

Output:
1320

Haskell

<lang haskell>parse = map (map read . words) . lines f x y z = x + max y z g xs ys = zipWith3 f xs ys $ tail ys solve = head . foldr1 g main = readFile "triangle.txt" >>= print . solve . parse</lang>

Output:
1320

Python

A simple mostly imperative solution: <lang python>def solve(tri):

   while len(tri) > 1:
       t0 = tri.pop()
       t1 = tri.pop()
       tri.append([max(t0[i], t0[i+1]) + t for i,t in enumerate(t1)])
   return tri[0][0]

def main():

   data = """\
                         55
                       94 48
                      95 30 96
                    77 71 26 67
                   97 13 76 38 45
                 07 36 79 16 37 68
                48 07 09 18 70 26 06
              18 72 79 46 59 79 29 90
             20 76 87 11 32 07 07 49 18
           27 83 58 35 71 11 25 57 29 85
          14 64 36 96 27 11 58 56 92 18 55
        02 90 03 60 48 49 41 46 33 36 47 23
       92 50 48 02 36 59 42 79 72 20 82 77 42
     56 78 38 80 39 75 02 71 66 66 01 03 55 72
    44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
  85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15

27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"""

   print solve([map(int, row.split()) for row in data.splitlines()])

main()</lang>

Output:
1320

A more functional version, similar to the Haskell entry (same output): <lang python>from itertools import imap

f = lambda x, y, z: x + max(y, z) g = lambda xs, ys: list(imap(f, ys, xs, xs[1:])) data = [map(int, row.split()) for row in open("triangle.txt")][::-1] print reduce(g, data)[0]</lang>