### 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|]

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