app/cses1755.hs

   1 import qualified Data.Map.Strict as M
   2 import Data.Map.Strict ((!))
   3
   4 type LetterCount = M.Map Char Int
   5
   6 main :: IO ()
   7 main = do
   8   line1 <- getLine
   9   let counts = countLetters line1
  10   if palindromable counts
  11     then putStrLn $ showPalindrome counts
  12     else putStrLn "NO SOLUTION"
  13
  14 countLetters :: String -> LetterCount
  15 countLetters = foldr (\c m -> M.insertWith (+) c 1 m) M.empty
  16
  17 palindromable :: LetterCount -> Bool
  18 palindromable = (<= 1) . M.size . M.filter odd
  19
  20 showPalindrome :: LetterCount -> String
  21 showPalindrome counts = showStart ++ showMid ++ showEnd
  22   where
  23     (odds, evens) = M.partition odd counts
  24     showStart = mconcat [replicate (n `div` 2) l | (l, n) <- M.toAscList evens]
  25     showMid = mconcat [replicate n l | (l, n) <- M.toAscList odds]
  26     showEnd = mconcat [replicate (n `div` 2) l | (l, n) <- M.toDescList evens]