Posted at

第17回オフラインリアルタイムどう書くの参考問題をHaskellで書いた

More than 5 years have passed since last update.

実行効率は考慮せず素朴な方法で書きました。


base.hs

import Control.Applicative

--基数変換
convertBase :: Int -> Int -> [Int]
convertBase n b = convertBase' n b []
where
convertBase' :: Int -> Int -> [Int] -> [Int]
convertBase' 0 _ ns = ns
convertBase' n b ns = let q = n `div` b
r = n `mod` b
in convertBase' q b (r:ns)
--回文かチェック
isPalindrome :: [Int] -> Bool
isPalindrome ns = ns == reverse ns

solve :: Int -> String
solve n = let base = concatMap (\b -> if isPalindrome $ convertBase n b then [b] else []) [2..n]
in if null base
then "-"
else listToString base
where
listToString (n:[]) = show n
listToString (n:ns) = show n ++ "," ++ listToString ns

main = do
tests <- lines <$> readFile "test.txt"
mapM (\t -> print $ runTest solve t) tests
where
runTest :: (Int -> String) -> String -> Bool
runTest f t = let [input, output] = words t
in f (read input :: Int) == output



test.hs

17301   5,38,100,218,236,5766,17300

2 -
1 -
3 2
4 3
5 2,4
6 5
10 3,4,9
101 10,100
1001 10,25,76,90,142,1000
10001 10,24,30,42,80,100,136,10000
1212 22,100,201,302,403,605,1211
123412 62,100,205,215,30852,61705,123411
5179 5178
4919 4918
5791 5790
5498 2748,5497
453 150,452
134 66,133
8489 27,652,8488
1234 22,616,1233
5497 41,238,5496
4763 19,35,432,4762
3974 17,27,1986,3973
3521 44,55,502,3520
5513 20,38,53,148,5512
8042 23,29,60,4020,8041
7442 37,60,121,3720,7441
4857 25,1618,4856
22843 49,69,91,141,430,22842
194823 84,121,21646,64940,194822
435697 160,169,235,626,1822,435696
142 3,7,70,141
886 5,14,442,885
3102 7,65,93,140,281,516,1033,1550,3101
17326 11,28,99,105,8662,17325
32982 13,72,238,477,716,1433,5496,10993,16490,32981
36 5,8,11,17,35
37 6,36
251 8,250
252 5,10,17,20,27,35,41,62,83,125,251
253 12,14,22,252
6643 2,3,9,81,90,510,948,6642
5040 71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039
9240 23,38,62,104,109,119,131,139,153,164,167,209,219,230,263,279,307,329,384,419,439,461,615,659,769,839,923,1154,1319,1539,1847,2309,3079,4619,9239