Project Euler — Problem 67 Solution

Problem

By start­ing at the top of the tri­an­gle below and mov­ing to adja­cent num­bers on the row below, the max­i­mum total from top to bot­tom is 23.

image

 

That is, 3 + 7 + 4 + 9 = 23.

Find the max­i­mum total from top to bot­tom in triangle.txt (right click and ‘Save Link/Target As…’), a 15K text file con­tain­ing a tri­an­gle with one-hun­dred rows.

NOTE: This is a much more dif­fi­cult ver­sion of Prob­lem 18. It is not pos­si­ble to try every route to solve this prob­lem, as there are 299 alto­geth­er! If you could check one tril­lion (1012) routes every sec­ond it would take over twen­ty bil­lion years to check them all. There is an effi­cient algo­rithm to solve it. ;o)

Solution

open System.IO

// cov­ers the data in the text to a tri­an­gle of ints, i.e. int list list
let tri­an­gle =
File.ReadAllLines(@“C:\TEMP\triangle.txt”)
|> Array.map (fun s -> s.Split(‘ ’) |> Array.map int32 |> Array.toList)
|> Array.toList

// func­tion to return all the com­bi­na­tions of n ele­ments from the sup­plied list
let rec comb n list =
match n, list with
| 0, _ -> [[]]
| _, [] -> []
| k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ (comb k xs)

// cal­cu­lates the next row in the T tri­an­gle giv­en the new row in R and the last row in T
let get­New­To­tal (row:int list) (total:int list) =
let head = total.Head
let tail = List.nth total (total.Length-1)
let body = total |> Seq.windowed 2 |> Seq.map (fun l -> Seq.max l) |> Seq.toList

List.map2 (+) row (List.concat [[head]; body; [tail]])

// recur­sive­ly tra­verse down the R tri­an­gle and return the last row in T
let rec tra­verse (raw:int list list) (total:int list) n =
let row = raw.[n]
let new­To­tal = get­New­To­tal row total

if n (raw.Length-1) then tra­verse raw new­To­tal (n+1) else new­To­tal let answer = List.max (tra­verse tri­an­gle [59] 1) [/code] See prob­lem 18 solu­tion for the full expla­na­tion of this solu­tion.