Euler problems 18 and 67

Problems 18 and 67 differs in their size, where problem 67 is so large that a (naive) brute force algorithm would not end within reasonable time. A simple algorithm shows it self if we goes from the bottom up. The problem formulation displays the numbers such that one looks at the numbers from the top going down.

Look at one “sub-triangle” at the bottom such as (the very left one)

63
04  62

Simply replace 63 with the sum of 63 and the largest of its “children” in this case 62. That is we get

125
04   62

Do this for the “sub-triangles” on the last two rows. Next move up one row and rinse and repeat. When we reach the top we get the result in the top-most cell. In order to refresh functional programming I programmed the solution in F#:

let triag = [[75];
[95; 64];
[17; 47; 82];
[18; 35; 87; 10];
[20; 04; 82; 47; 65];
[19; 01; 23; 75; 03; 34];
[88; 02; 77; 73; 07; 63; 67];
[99; 65; 04; 28; 06; 16; 70; 92];
[41; 41; 26; 56; 83; 40; 80; 70; 33];
[41; 48; 72; 33; 47; 32; 37; 16; 94; 29];
[53; 71; 44; 65; 25; 43; 91; 52; 97; 51; 14];
[70; 11; 33; 28; 77; 73; 17; 78; 39; 68; 17; 57];
[91; 71; 52; 38; 17; 14; 91; 43; 58; 50; 27; 29; 48];
[63; 66; 04; 68; 89; 53; 67; 30; 73; 16; 69; 87; 40; 31];
[04; 62; 98; 27; 23; 09; 70; 98; 73; 93; 38; 53; 60; 04; 23]]

let rec addup (alist: int list) (blist: int list) =
    match (alist, blist) with
    | (ahead1 :: ahead2 :: asublist, bhead1 :: bsublist ) -> 
       let amax = if ahead1 > ahead2 then ahead1 else ahead2 in
           (amax + bhead1) :: (addup (ahead2::asublist) bsublist)
    | ([],[]) -> []
    | _ -> [];;
let rec compute (lists: int list list) =
    match lists with
    | alist :: blist :: sublist ->
      compute ((addup alist blist) :: sublist)
    | alist :: [] -> alist
    | [] -> [];;

printfn "Solution to Euler problem 18 : ";;
printlist (compute (List.rev triag));;

And using the .NET SteamReader class we can also compute the result for the larger problem #67

open System.IO;;
let rec parselines (file: StreamReader) =
    match file.EndOfStream with
    | true -> []
    | false ->
        let line = file.ReadLine() in
        let tokens = String.split [' '] line in
        let ints = List.map int.Parse tokens in
        ints :: parselines file;;

let diag2 = 
    let file = new StreamReader( "triangle.txt" ) in
    parselines file;;

printfn "Solution to Euler problem 67 : ";;
printlist (compute (List.rev diag2));;