alternate solution to https://b7j0c.org/blog/fb_interview_question.html

fb_interview_question.hs

module Main where

import Data.Bits

{- Note that, once completely reduced according to the rules,
 - the string will be homogeneous.  If it did contain two different
 - characters, there would be a place where two touched, and
 - they could be reduced.
 -
 - In fact, the order in which the reductions are done doesn't really matter,
 - since we'll always end up with the same thing.  So let's just work left to
 - right.
 -}
puzzleCount :: String -> Int
-- change a => 1, b => 2, c => 3 so we can take advantage of the fact that
--    1 xor 2 = 2 xor 1 = 3
--    1 xor 3 = 3 xor 1 = 2
--    2 xor 3 = 3 xor 2 = 1
-- which is precisely the reduction scheme
puzzleCount = check . map (\x -> fromEnum x - fromEnum 'a' + 1) 
  where check [] = 0
        -- we'll use the first two args to represent the homogeneous prefix
        -- we've already processed
        check (a:as) = collapse 1 a as
        collapse n a (b:bs) | a == b    = collapse (n+1) a bs       -- extend the current prefix
                            | odd n     = collapse 1 (a `xor` b) bs -- for an odd number of a's, a `xor` (a `xor (a ... `xor b)...) = a `xor` b
                            | otherwise = collapse 1 b bs           -- for an even number of a's, a `xor` (a `xor (a ... `xor b)...) = b
        collapse n _ [] = n   -- we're done when all the string is in the homogeneous prefix
        
main :: IO ()
main = do
  print $ puzzleCount "aab"
  print $ puzzleCount "bbcccccc"
  print $ puzzleCount "cab"
  print $ puzzleCount "bcab"
  print $ puzzleCount "aabcbccbaacaccabcbcab"
  print $ puzzleCount "ccaca"
  return ()

far better than mine. i learned some neat tricks reading this. thanks! -brad