Project Euler - Problems 18 and 67 - FSharp using Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Project Euler: Problems 18 and 67"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "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.\n",
    "\n",
    "\n",
    "3\n",
    "7 4\n",
    "2 4 6\n",
    "8 5 9 3\n",
    "\n",
    "\n",
    "That is, 3 + 7 + 4 + 9 = 23.\n",
    "\n",
    "\n",
    "Find the maximum total from top to bottom of the triangle below:\n",
    "\n",
    "\n",
    "75\n",
    "95 64\n",
    "17 47 82\n",
    "18 35 87 10\n",
    "20 04 82 47 65\n",
    "19 01 23 75 03 34\n",
    "88 02 77 73 07 63 67\n",
    "99 65 04 28 06 16 70 92\n",
    "41 41 26 56 83 40 80 70 33\n",
    "41 48 72 33 47 32 37 16 94 29\n",
    "53 71 44 65 25 43 91 52 97 51 14\n",
    "70 11 33 28 77 73 17 78 39 68 17 57\n",
    "91 71 52 38 17 14 91 43 58 50 27 29 48\n",
    "63 66 04 68 89 53 67 30 73 16 69 87 40 31\n",
    "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23\n",
    "\n",
    "\n",
    "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)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By extension, this solves problem 67 as well.\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[|1074|]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec StripArray row (remainingList:array<int>) (runningSums:array<int>) =\n",
    "    if row = 0 then\n",
    "        //remainingList\n",
    "        runningSums\n",
    "    else\n",
    "        //create next array up the pyramid\n",
    "        let newList = [|for counterRow = row to (Array.length remainingList)-1 do\n",
    "                        yield remainingList.[counterRow]|]\n",
    "\n",
    "\n",
    "        //if running sum is empty, create the first array\n",
    "        if Array.sum runningSums = 0 then\n",
    "            let baseNums = [|for counterNew = 0 to row - 1 do\n",
    "                                    yield remainingList.[counterNew]|]\n",
    "            StripArray (row-1) newList baseNums\n",
    "        else\n",
    "            //compares sum of each node pair with its node value, and retains greater of the two\n",
    "            let newSums = [|for counterNew = 0 to row - 1 do\n",
    "                                let first = remainingList.[counterNew] + runningSums.[counterNew]\n",
    "                                let second = remainingList.[counterNew] + runningSums.[counterNew + 1]\n",
    "                                if first >= second then \n",
    "                                    yield first\n",
    "                                else\n",
    "                                    yield second|]\n",
    "            StripArray (row - 1) newList newSums\n",
    "\n",
    "let rec ItemsPerRowsOfArray row maxRows (arr:array<int>) =\n",
    "    if row > maxRows then\n",
    "        arr\n",
    "    else\n",
    "        let lastValue = arr.[((Array.length arr) - 1)]\n",
    "        let newValue = [|lastValue+row|]\n",
    "        let newArr = Array.append arr newValue \n",
    "        ItemsPerRowsOfArray (row+1) maxRows newArr\n",
    "        \n",
    "let FindNumberOfRows num = \n",
    "    let rowArray = ItemsPerRowsOfArray 1 (num/2) [|0|]\n",
    "    let rowNum = rowArray |> Array.findIndex (fun x -> x = num)\n",
    "    rowNum \n",
    "    \n",
    "let FindMaxValuePath (flattenedArray:array<int>) =\n",
    "    let rows = FindNumberOfRows (Array.length flattenedArray)\n",
    "    StripArray rows (Array.rev flattenedArray) [||]\n",
    "\n",
    "let generalProof = FindMaxValuePath [|1;2;3;4;5;6;7;8;9;10|]\n",
    "\n",
    "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|]\n",
    "\n",
    "let Prob18Answer = FindMaxValuePath flattenedArray\n",
    "Prob18Answer"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "F#",
   "language": "fsharp",
   "name": "ifsharp"
  },
  "language": "fsharp",
  "language_info": {
   "codemirror_mode": "",
   "file_extension": ".fs",
   "mimetype": "text/x-fsharp",
   "name": "fsharp",
   "nbconvert_exporter": "",
   "pygments_lexer": "",
   "version": "4.3.1.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}