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.

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.




 
(ns clojure.examples.rosetta
	(:gen-class)
        (:require [clojure.string :as string]))
 
(def rosetta                     "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")
 
;; The technique is described here in more detail http://mishadoff.com/blog/clojure-euler-problem-018/
;; Most of the code converts the string data to a nested array of integers.
;; The code to calculate the max sum is then only a  single line
 
;; First convert string data to nested list
;;  with each inner list containing one row of the triangle
;;   [[55] [94 48] [95 30 96] ... [...10 69 93]
(defn parse-int [s]
    " Convert digits to a number (finds digits when could be surrounded by non-digits"
  (Integer. (re-find #"\d+" s)))
 
(defn data-int-array [s]
  " Convert string to integer array"
  (map parse-int (string/split (string/trim s) #"\s+")))
 
(defn nested-triangle [s]
  " Convert triangle to nested vector, with each inner vector containing one triangle row"
  (loop [lst s n 1 newlist nil]
    (if (empty? lst) (reverse newlist)
                     (recur (drop n lst) (inc n) (cons (take n lst) newlist)))))
; Create nested list
(def nested-list (nested-triangle (data-int-array rosetta)))
 
;; Function to compute maximum path sum
(defn max-sum [s]
  " Compute maximum path sum using a technique described here: http://mishadoff.com/blog/clojure-euler-problem-018/"
  (reduce (fn [a b] (map + b (map max a (rest a)))) (reverse s)))
 
; Print result
(println (max-sum nested-list))
 
 