Skip to content

Instantly share code, notes, and snippets.

@rampion
Created April 7, 2012 00:09
Show Gist options
  • Save rampion/2324177 to your computer and use it in GitHub Desktop.
Save rampion/2324177 to your computer and use it in GitHub Desktop.
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 ()
@bradclawsie
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment