Done several tasks

[cses-programming-tasks.git] / app / cses1755.hs

diff --git a/app/cses1755.hs b/app/cses1755.hs
new file mode 100644 (file)
index 0000000..ff5d217
--- /dev/null
+++ b/app/cses1755.hs
@@ -0,0 +1,26 @@
+import qualified Data.Map.Strict as M
+import Data.Map.Strict ((!))
+
+type LetterCount = M.Map Char Int
+
+main :: IO ()
+main = do
+  line1 <- getLine
+  let counts = countLetters line1
+  if palindromable counts
+    then putStrLn $ showPalindrome counts
+    else putStrLn "NO SOLUTION"
+
+countLetters :: String -> LetterCount
+countLetters = foldr (\c m -> M.insertWith (+) c 1 m) M.empty  
+
+palindromable :: LetterCount -> Bool
+palindromable = (<= 1) . M.size . M.filter odd
+
+showPalindrome :: LetterCount -> String
+showPalindrome counts = showStart ++ showMid ++ showEnd
+  where 
+    (odds, evens) = M.partition odd counts
+    showStart = mconcat [replicate (n `div` 2) l | (l, n) <- M.toAscList evens]
+    showMid = mconcat [replicate n l | (l, n) <- M.toAscList odds]
+    showEnd = mconcat [replicate (n `div` 2) l | (l, n) <- M.toDescList evens]