Maximum triangle path sum: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added racket implementation)
(Added Ada version)
Line 34: Line 34:


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|Ada}}==
<lang ada>with Ada.Text_Io; use Ada.Text_Io;
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;
with Ada.Containers.Vectors;


procedure Max_Sum is
package Integer_Vectors is new Ada.Containers.Vectors
(Positive, Integer);
Triangle : Integer_Vectors.Vector;
Data : String :=
" 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";
Num : Integer;
Last : Integer;
Index : Positive;
Tn : Integer := 1;
begin
Index := Data'First;
while Index < Data'Last loop
Get(Data(Index..Data'Last), Num, Last);
Triangle.Append(Num);
Index := Last+1;
end loop;
Last := Integer(Triangle.Length);
while (Tn * (Tn + 1) / 2) < Last loop
Tn := Tn + 1;
end loop;
for N in reverse 2 .. Tn loop
for I in 2 .. N loop
Triangle.Replace_Element
(Last - N, Triangle.Element(Last -N) +
Integer'Max(Triangle.Element(Last-1), Triangle.Element(Last)));
Last := Last - 1;
end loop;
Last := Last - 1;
end loop;
Put_Line(Integer'Image(Triangle.Element(1)));
end Max_Sum;
</lang>
Output:
<pre> 1320
</pre>
=={{header|D}}==
=={{header|D}}==
<lang d>void main() {
<lang d>void main() {

Revision as of 23:16, 9 March 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.

Ada

<lang ada>with Ada.Text_Io; use Ada.Text_Io; with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; with Ada.Containers.Vectors;

procedure Max_Sum is 

  package Integer_Vectors is new Ada.Containers.Vectors
    (Positive, Integer);
  
  Triangle : Integer_Vectors.Vector;
  
  Data : String :=
    "                          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";
  
  Num   : Integer;
  Last  : Integer;
  Index : Positive;
  Tn    : Integer := 1;

begin 

  Index := Data'First;
  while Index < Data'Last loop
     Get(Data(Index..Data'Last), Num, Last);
     Triangle.Append(Num);
     Index := Last+1;
  end loop;
  Last := Integer(Triangle.Length);
  while (Tn * (Tn + 1) / 2) < Last  loop
     Tn := Tn + 1;
  end loop;
  for N in reverse 2 .. Tn loop
     for I in 2 .. N loop

Triangle.Replace_Element (Last - N, Triangle.Element(Last -N) + Integer'Max(Triangle.Element(Last-1), Triangle.Element(Last))); Last := Last - 1; 

     end loop;
     Last := Last - 1;
  end loop;
  Put_Line(Integer'Image(Triangle.Element(1)));

end Max_Sum; </lang> Output: 

 1320

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

Go

<lang go>package main

import ( 

   "fmt"
   "strconv"
   "strings"

)

const t = ` 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`

func main() { 

   lines := strings.Split(t, "\n")
   f := strings.Fields(lines[len(lines)-1])
   d := make([]int, len(f))
   var err error
   for i, s := range f {
       if d[i], err = strconv.Atoi(s); err != nil {
           panic(err)
       }
   }
   d1 := d[1:]
   var l, r, u int
   for row := len(lines) - 2; row >= 0; row-- {
       l = d[0]
       for i, s := range strings.Fields(lines[row]) {
           if u, err = strconv.Atoi(s); err != nil {
               panic(err)
           }
           if r = d1[i]; l > r {
               d[i] = u + l
           } else {
               d[i] = u + r
           }
           l = r
       }
   }
   fmt.Println(d[0])

}</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

Perl 6

The Z+ and Zmax are examples of the zipwith metaoperator. We ought to be able to use [Z+]= as an assignment operator here, but rakudo has a bug. Note also we can use the Zmax metaoperator form because max is define as an infix in Perl 6. <lang perl6>my @rows = slurp("triangle.txt").lines.map: { [.words] }

while @rows > 1 { 

   my @last := @rows.pop;
   @rows[*-1] = @rows[*-1] Z+ (@last Zmax @last[1..*]);

}

say @rows;</lang>

Output:
1320

Here's a more FPish version with the same output. We define our own operator and the use it in the reduction metaoperator form, [op], which turns any infix into a list operator. <lang perl6>sub infix:<op>(@a,@b) { (@a Zmax @a[1..*]) Z+ @b }

say [op] slurp("triangle.txt").lines.reverse.map: { [.words] }</lang> Instead of using reverse, one could also define the op as right-associative. <lang perl6>sub infix:<op>(@a,@b) is assoc('right') { @a Z+ (@b Zmax @b[1..*]) }

say [op] slurp("triangle.txt").lines.map: { [.words] }</lang>

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>

Racket

<lang racket>#lang racket (require math/number-theory)

(define (trinv n) ; OEIS A002024 

 (exact-floor (/ (+ 1 (sqrt (* 1 (* 8 n)))) 2)))

(define (triangle-neighbour-bl n) 

 (define row (trinv n))
 (+ n (- (triangle-number row) (triangle-number (- row 1)))))

(define (maximum-triangle-path-sum T) 

 (define n-rows (trinv (vector-length T)))
 (define memo# (make-hash))
 (define (inner i)
   (hash-ref!
    memo# i
    (λ ()
      (+ (vector-ref T (sub1 i)) ; index is 1-based (so vector-refs need -1'ing)
         (cond [(= (trinv i) n-rows) 0]
               [else
                (define bl (triangle-neighbour-bl i))
                (max (inner bl) (inner (add1 bl)))])))))
 (inner 1))

(module+ main 

 (maximum-triangle-path-sum
  #(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)))

(module+ test 

 (require rackunit)
 (check-equal? (for/list ((n (in-range 1 (add1 10)))) (trinv n)) '(1 2 2 3 3 3 4 4 4 4))
 ;    1
 ;   2 3
 ;  4 5 6
 ; 7 8 9 10
 (check-eq? (triangle-neighbour-bl 1) 2)
 (check-eq? (triangle-neighbour-bl 3) 5)
 (check-eq? (triangle-neighbour-bl 5) 8)
 (define test-triangle
   #(55   94 48   95 30 96   77 71 26 67))
 (check-equal? (maximum-triangle-path-sum test-triangle) 321)
 )</lang>
Output:
1320

REXX

The method used is very efficient and performs very well for triangles that have thousands of rows (lines).
For an expanded discussion of the method's efficiency, see the discussion page. <lang rexx>/*REXX program finds the max sum of a "column" of numbers in a triangle.*/ @. = @.1 = 55 @.2 = 94 48 @.3 = 95 30 96 @.4 = 77 71 26 67 @.5 = 97 13 76 38 45 @.6 = 07 36 79 16 37 68 @.7 = 48 07 09 18 70 26 06 @.8 = 18 72 79 46 59 79 29 90 @.9 = 20 76 87 11 32 07 07 49 18 @.10 = 27 83 58 35 71 11 25 57 29 85 @.11 = 14 64 36 96 27 11 58 56 92 18 55 @.12 = 02 90 03 60 48 49 41 46 33 36 47 23 @.13 = 92 50 48 02 36 59 42 79 72 20 82 77 42 @.14 = 56 78 38 80 39 75 02 71 66 66 01 03 55 72 @.15 = 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36 @.16 = 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52 @.17 = 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15 @.18 = 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93 

        do r=1  while  @.r\==       /*build a version of the triangle*/
            do k=1  for words(@.r)    /*build a row, number by number. */
            #.r.k=word(@.r,k)         /*assign a number to an array num*/
            end   /*k*/
        end       /*r*/

rows=r-1 /*compute the number of rows. */ 

        do r=rows  by -1 to 2; p=r-1  /*traipse through triangle rows. */
            do k=1  for p;     kn=k+1 /*re-calculate the previous row. */
            #.p.k=max(#.r.k, #.r.kn)  +  #.p.k   /*replace previous #. */
            end   /*k*/
        end       /*r*/

say 'maximum path sum:' #.1.1 /*display the top (row 1) number.*/ 

                                      /*stick a fork in it, we're done.*/</lang>

output using the data within the REXX program: 

maximum path sum: 1320
Retrieved from "https://rosettacode.org/wiki/Maximum_triangle_path_sum?oldid=240276"