Skip to content

Instantly share code, notes, and snippets.

@olajep olajep/rain_ordo_n.hs
Last active Aug 23, 2019

Embed
What would you like to do?
rainSolver = solve 0 . zipWithRightMax
zipWithRightMax xs = zip xs maxVals
where
rev = reverse xs
(maxVals, _) = foldl maxFold ([], head rev) rev
maxFold (acc, maxVal) x = (maxVal:acc,maxFromHere)
where
maxFromHere = max maxVal x
solve acc [] = acc
solve acc (x:xs)
| xs' == [] = solve acc xs -- no right border -> this x cannot be left border
| otherwise = solve (acc+area) xs'
where
(val, rightMax) = x
height = min val rightMax
(elems',xs') = span ((<height).fst) xs
elems = fst $ unzip elems'
area = (length elems * height) - (sum elems)
rainSolver = solve 0
solve acc [] = acc
solve acc (x:xs)
| xs' == [] = solve acc xs -- no right border -> this x cannot be left border
| otherwise = solve (acc+area) xs'
where
height = minimum [x, maximum xs]
(elems,xs') = span (<height) xs
area = (length elems * height) - (sum elems)
@qazwsxpawel

This comment has been minimized.

Copy link

qazwsxpawel commented Oct 30, 2013

Man, I need to learn Haskell :)

@Bontrey

This comment has been minimized.

Copy link

Bontrey commented Oct 30, 2013

This is O(n^2) without precomputing max of all the suffixes, isn't it

EDIT: Actually, more complicated than that. The span is also linear time =/

@olajep

This comment has been minimized.

Copy link
Owner Author

olajep commented Oct 30, 2013

@Bontrey: Yes, it is.

@olajep

This comment has been minimized.

Copy link
Owner Author

olajep commented Oct 30, 2013

@Bontrey: The span doesn't make it O(n^2).
Consider these extremes:
Take one elements n times.
Take all elements 1 time.

@Bontrey

This comment has been minimized.

Copy link

Bontrey commented Oct 30, 2013

Oh yeah. Good point. Each element is only segmented out once

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.