DailyProgrammer Challenge #213h Solution (Stepstring Discrepancy)

c-stepstring.hs

import Control.Arrow
import Data.Char
import Data.List
import Data.Ord
import Text.Printf

(c0, c1) = ('a', 'b')

accum s = 0 : accumR 0 s where
    accumR _ []     = []
    accumR a (c:cs) = a' : accumR a' cs where
        a' | c == c0   = a - 1
           | c == c1   = a + 1
           | otherwise = a

minMax = (maximumBy (comparing snd) &&& minimumBy (comparing snd)) . zip [0..]

intoRange ((li, l), (hi, h)) st = (abs $ h - l, range) where
    range | li <= hi = (li * st, hi * st, st)
          | li >  hi = (hi * st, li * st, st)

leap _ []     = []
leap n (x:xs) = x : leap n xs' where xs' = drop (n - 1) xs

discr o st s = intoRange (minMax $ accum $ leap st $ drop o s) st
maxDiscr s = maximumBy (comparing $ fst) $
             concatMap (\st -> map (\o -> discr o st s) [0..st - 1]) [1..length s - 1]

main :: IO ()
main = interact (unlines . map (show . maxDiscr) . lines)