Candy Splitting

ProblemC.hs

import Control.Arrow
import Control.Monad
-- Using ByteString a little superfluously but thought my parser might slow me down.
import qualified Data.ByteString.Lazy.Char8 as QS
import Data.Bits
import Data.List
import Data.Maybe
import Data.Word

-- | A bag of sweeties is a list of unsigned integers
type Bag = [Word32]

-- | Given a bag of sweeties, I want to split it into two piles, calculating
-- how much Sean's is worth actually and how much patrick thinks each one is
-- worth. `choices` gives these for all possible subsets of a bag.
choices :: Bag -> [(Word32, (Word32, Word32))]
choices [] = return (0, (0, 0))
choices (x : xs) = do
  (sval_real, (pval, sval)) <- choices xs
  flg <- [True, False]
  return (if flg then (x + sval_real, (pval, sval `xor` x)) else (sval_real, (pval `xor` x, sval)))

-- | Is it possible to keep Patrick from crying?
check :: Bag -> Maybe Bag
check bag | foldr xor 0 bag == 0 = Just bag
          | otherwise = Nothing

-- | What is the first solution for which Patrick isn't going to cry?
solve :: Bag -> Maybe Word32
solve = listToMaybe . map fst . filter (uncurry (==) . snd)
      . tail . init . choices

combine :: [a] -> [(a, a)]
combine [] = []
combine (x:y:zs) = (x, y) : combine zs

parseLine :: (QS.ByteString, QS.ByteString) -> Bag
parseLine (n, sweeties) = sort
                        $ map (fromInteger . maybe undefined fst . QS.readInteger) 
                        $ take (maybe undefined fst $ QS.readInt n) $ QS.words sweeties

-- | Lazy interaction says it will apply a function from strings to strings on
-- an input, returning the output. So... given a input stream, split it up into
-- lines, chop the top of and pair up lines that relate to the same test-case.
-- Add a test-case index, parse each line and then check and solve it. Display
-- the output for each test-case and then merge into one output stream.
main = QS.interact (QS.unlines 
                   . map (display . second ((solve <=< check) . parseLine)) 
                   . zip [1..] . combine . tail . QS.lines)
  where display (n, out) = QS.pack $ "Case #" ++ show n ++ ": " ++ maybe "NO" show out