1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import Data.Array
import Data.HashMap.Strict (HashMap, fromListWith, toList)
transform :: Int -> Either Int (Int,Int)
transform n
| even (digits n) = Right $ halves n
| otherwise = Left $ n * 2024
digits :: Int -> Int
digits n = floor $ logBase 10 (fromIntegral n) + 1
halves :: Int -> (Int,Int)
halves n = ( floor $ fromIntegral n / 10^x
, n `mod` 10^x
)
where
x = digits n `div` 2
next :: Array Int (Either Int (Int,Int))
next = array (0, maxIdx)
$ (0, Left 1) : [ (n, transform n) | n <- [1..maxIdx] ]
maxIdx :: Int
maxIdx = 10^4
getNext :: Int -> Either Int (Int,Int)
getNext x | x <= maxIdx = next ! x
| otherwise = transform x
depth :: Int
depth = 75
evalList :: [(Int,Int)] -> [(Int,Int)]
evalList = go []
where
go :: [(Int,Int)] -> [(Int,Int)] -> [(Int,Int)]
go res [] = res
go res ((x,c):xs) = case getNext x of
Left y -> go ((y,c):res) xs
Right (y,z) -> go ((y,c):(z,c):res) xs
evalHM :: HashMap Int Int -> HashMap Int Int
evalHM = fromListWith (+) . evalList . toList
main :: IO ()
main = getLine
>>= print
. sum
. (!! depth)
. iterate evalHM
. fromListWith (+)
. map ((,1) . read)
. words
|
