Skip to content

Instantly share code, notes, and snippets.

@AndrewNewcomb
Last active August 29, 2015 14:19
Show Gist options
  • Save AndrewNewcomb/fb28621041ff3e3fc329 to your computer and use it in GitHub Desktop.
Save AndrewNewcomb/fb28621041ff3e3fc329 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 version will use three passes
open System
let heights = [|10; 20; 80; 70; 60; 90; 40; 30; 40; 70|]
type state1 = {Height:int; MaxLeft:int}
let getMaxLeft (state: state1 list) (item:int) =
match state with
| [] -> {Height=item; MaxLeft=item}::state
| _ when item > state.Head.MaxLeft -> {Height=item; MaxLeft=item}::state
| _ -> {Height=item; MaxLeft=state.Head.MaxLeft}::state
type state2 = {Height:int; MaxLeft:int; MaxRight:int}
let getMaxRight (state: state2 list) (item:state1) =
match state with
| [] -> {Height=item.Height; MaxLeft=item.MaxLeft; MaxRight=item.Height}::state
| _ when item.Height > state.Head.MaxRight -> {Height=item.Height; MaxLeft=item.MaxLeft; MaxRight=item.Height}::state
| _ -> {Height=item.Height; MaxLeft=item.MaxLeft; MaxRight=state.Head.MaxRight}::state
let depth column =
match column.MaxLeft > column.Height && column.Height < column.MaxRight with
| true -> (min column.MaxLeft column.MaxRight) - column.Height
| false -> 0
let puddleSize (currentPuddleSize, maxPuddleSize) depth =
if depth > 0 then
let newCurrent = currentPuddleSize + depth
newCurrent, max newCurrent maxPuddleSize
else
0, maxPuddleSize
let largestPuddleArea =
heights
|> Array.fold getMaxLeft []
|> List.fold getMaxRight []
|> Seq.map depth
|> Seq.fold puddleSize (0,0)
|> snd
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment