Skip to content

Instantly share code, notes, and snippets.

@AndrewNewcomb
Last active August 29, 2015 14:19
Show Gist options
  • Save AndrewNewcomb/5ca5442c9864612f823c to your computer and use it in GitHub Desktop.
Save AndrewNewcomb/5ca5442c9864612f823c to your computer and use it in GitHub Desktop.
FSharp solution to the biggest puddle problem
// F# solution to the biggest puddle problem posed at
// http://geekswithblogs.net/BlackRabbitCoder/archive/2015/04/07/little-puzzlersndashlargest-puddle-on-a-bar-chart.aspx
// April 2015
// This solution works in one pass of the array
open System
let heights = [|10; 20; 80; 70; 60; 90; 40; 30; 40; 70|]
//let heights = [|10; 5; 10; 4; 5; 10|]
//let heights = [|0; 20; 80; 70; 60; 90; 40; 30; 40; 70|]
//let heights = [|20;1;11|]
//let heights = [||]
let puddleState depth currentPuddleSize maxPuddleSize =
if depth > 0 then
currentPuddleSize + depth, maxPuddleSize
else
0, max currentPuddleSize maxPuddleSize
let rec move idxCurrentLeft idxCurrentRight currentHeightLeft currentHeightRight currentPuddleSize maxPuddleSize movingRight =
match idxCurrentLeft = idxCurrentRight with
| false ->
let depth, idxNewLeft, idxNewRight, newHeightLeft, newHeightRight =
let edgeHeight = min currentHeightLeft currentHeightRight
match movingRight with
| true ->
let idxNextLeft = idxCurrentLeft + 1
let newMaxLeft = max currentHeightLeft heights.[idxNextLeft]
edgeHeight - heights.[idxNextLeft], idxNextLeft, idxCurrentRight, newMaxLeft, currentHeightRight
| false ->
let idxNextRight = idxCurrentRight - 1
let newMaxRight = max currentHeightRight heights.[idxNextRight]
edgeHeight - heights.[idxNextRight], idxCurrentLeft, idxNextRight, currentHeightLeft, newMaxRight
let nextMoveIsToRight = heights.[idxNewLeft] <= heights.[idxNewRight]
let newPuddleState = puddleState depth currentPuddleSize maxPuddleSize
move idxNewLeft idxNewRight newHeightLeft newHeightRight (fst newPuddleState) (snd newPuddleState) nextMoveIsToRight
| true -> maxPuddleSize
let calcPuddleSize h =
match h with
| [||] -> 0
| _ -> move 0 (h.Length-1) h.[0] h.[h.Length-1] 0 0 true
let maxPuddleSize = calcPuddleSize heights
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment