Project Euler: Problems 18 and 67

Problem 18 


By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.


3
7 4
2 4 6
8 5 9 3


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


Find the maximum total from top to bottom of the triangle below:


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


NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)


Solution


By extension, this solves problem 67 as well.


This uses a tail-recursive function requiring the pyramid to be flattened into an array and reversed. Its 'intelligence' comes from calculating sums from the bottom-up, rather than top-down, and by flattening the pyramid into a binary heap. Since the recursion only keeps the higher sum between two (2) node comparisons, it reduces the calculations for a 100 hundred row pyramid, from the potential 2^99 routes, to fairly small number, 9950.


//calculates running sums up to the top node, which it then returns
let rec StripArray row (remainingList:array) (runningSums:array) =
    if row = 0 then
        //remainingList
        runningSums
    else
        //create next array up the pyramid
        let newList = [|for counterRow = row to (Array.length remainingList)-1 do
                        yield remainingList.[counterRow]|]


        //if running sum is empty, create the first array
        if Array.sum runningSums = 0 then
            let baseNums = [|for counterNew = 0 to row - 1 do
                                    yield remainingList.[counterNew]|]
            StripArray (row-1) newList baseNums
        else
            //compares sum of each node pair with its node value, and retains greater of the two
            let newSums = [|for counterNew = 0 to row - 1 do
                                let first = remainingList.[counterNew] + runningSums.[counterNew]
                                let second = remainingList.[counterNew] + runningSums.[counterNew + 1]
                                if first >= second then 
                                    yield first
                                else
                                    yield second|]
            StripArray (row - 1) newList newSums


let rec ItemsPerRowsOfArray row maxRows (arr:array) =
    if row > maxRows then
        arr
    else
        let lastValue = arr.[((Array.length arr) - 1)]
        let newValue = [|lastValue+row|]
        let newArr = Array.append arr newValue 
        ItemsPerRowsOfArray (row+1) maxRows newArr


//for a [pyramid converted to a binary heap, the number of rows
//this will throw an error if fed an array that is not a pyramid/binary heap
let FindNumberOfRows num = 
    let rowArray = ItemsPerRowsOfArray 1 (num/2) [|0|]
    let rowNum = rowArray |> Array.findIndex (fun x -> x = num)
    rowNum 


let FindMaxValuePath (flattenedArray:array) =
    let rows = FindNumberOfRows (Array.length flattenedArray)
    StripArray rows (Array.rev flattenedArray) [||]


//general proof to verify the code works, in this case a small pyramid
let generalProof = FindMaxValuePath [|1;2;3;4;5;6;7;8;9;10|]


//the array for problem #18
let flattenedArray =
[|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 Prob18Answer = FindMaxValuePath flattenedArray


//I created the array for problem #67 manually, but it is an intellectually trivial exercise to load the file provided into an array 
let prob67FlattenedArray = [|59;73;41;...removed values for display purposes...26;15;59;63;35|]



let Prob67Answer = FindMaxValuePath prob67FlattenedArray