import Prelude
-- Rule 110 replaces the center value of 111, 100, and 000 with 0, otherwise 1
repl110 :: String -> String
repl110 s | (length s < 3) = s
repl110 s | take 3 s `elem` ["111","100","000"] = '0' : repl110 (tail s)
repl110 s = '1' : repl110 (tail s)
rule110 :: String -> String
rule110 s = trim0s (repl110 ("000" ++ s ++ "000"))
drop0s :: String -> String
drop0s ('0':s) = drop0s s
drop0s s = s
trim0s :: String -> String
trim0s s = drop0s (reverse (drop0s s))
countUntil :: (Eq a) => a -> [a] -> Integer
countUntil x [] = -1
countUntil x (y:ys) | x==y = 0
countUntil x (_:xs) = 1+countUntil x xs
-- the Collatz sequence computes 3n+1 for odd values, n/2 for even values, and stops at 1
collatzStep :: Integer -> Integer
collatzStep n =
if n<=1 then 1
else if odd n then 3*n+1
else n `div` 2
collatz :: Integer -> Integer
collatz n = countUntil 1 (iterate collatzStep n)
select (True:bs) (x:xs) = x:select bs xs
select (False:bs) (x:xs) = select bs xs
select [] _ = []
select _ [] = []
highWatermarks0 :: (Ord a) => Integer -> a -> [a] -> [Integer]
highWatermarks0 i m [] = []
highWatermarks0 i m (x:xs)
| x>m = i : highWatermarks0 (i+1) x xs
| otherwise = highWatermarks0 (i+1) m xs
highWatermarks :: (Ord a) => [a] -> [Integer]
highWatermarks l@(x:xs) = highWatermarks0 0 x l
highWatermarks1 s =
let maximum = scanl1 max s
bigger = map (uncurry (>=)) (zip s maximum)
in select bigger [0..]