2067d13996fd82c01ef22c7bf1b87a0341627d38
1 import Data.Char (digitToInt, intToDigit)
3 main :: IO ()
4 main = do
6 let digits = parseDigits text
7 -- print mem
8 print \$ part1 digits
9 print \$ part2 digits
10 -- print \$ part2 mem
12 part1 :: [Int] -> String
13 part1 digits = map intToDigit \$ take 8 \$ (fft digits)!!100
15 part2 :: [Int] -> String
16 part2 digits = map intToDigit signal
17 where offset = read @Int \$ map intToDigit \$ take 7 digits
18 fullDigits = concat \$ replicate 10000 digits
19 suffix = drop offset fullDigits
20 signal = take 8 \$ (fastFft suffix)!!100
22 part2naive :: [Int] -> String
23 part2naive digits = map intToDigit signal
24 where fullDigits = concat \$ replicate 10000 digits
25 result = (fft fullDigits)!!100
26 offset = read @Int \$ map intToDigit \$ take 7 digits
27 signal = take 8 \$ drop offset result
30 basePattern :: [Int]
31 basePattern = [0, 1, 0, -1]
33 patternOf :: Int -> [Int]
34 patternOf index = drop 1 \$ cycle \$ concatMap (replicate index) basePattern
36 elementAt :: [Int] -> Int -> Int
37 elementAt digits index = (abs \$ sum \$ zipWith (*) digits \$ patternOf index) `mod` 10
39 fftStep :: [Int] -> [Int]
40 fftStep digits = map (elementAt digits) [1..(length digits)]
42 fft :: [Int] -> [[Int]]
43 fft = iterate fftStep
45 fastFft :: [Int] -> [[Int]]
46 fastFft = iterate fastFftStep
48 fastFftStep :: [Int] -> [Int]
49 -- fastFftStep digits = map (\ds -> (sum ds) `mod` 10) \$ tails digits
50 fastFftStep digits = scanr (\d s -> (d + s) `mod` 10) 0 digits
53 parseDigits :: String -> [Int]
54 parseDigits = map digitToInt