3 import Data.Char (digitToInt, intToDigit)
5 -- import qualified Data.Map.Strict as M
6 -- import Data.Map.Strict ((!))
8 -- import qualified Data.Set as S
14 text <- readFile "data/advent16.txt"
15 let digits = parseDigits text
21 part1 :: [Int] -> String
22 part1 digits = map intToDigit $ take 8 $ (fft digits)!!100
24 part2 digits = map intToDigit signal
25 where offset = read @Int $ map intToDigit $ take 7 digits
26 fullDigits = concat $ replicate 10000 digits
27 suffix = drop offset fullDigits
28 signal = take 8 $ (fastFft suffix)!!100
30 part2naive :: [Int] -> String
31 part2naive digits = map intToDigit signal
32 where fullDigits = concat $ replicate 10000 digits
33 result = (fft fullDigits)!!100
34 offset = read @Int $ map intToDigit $ take 7 digits
35 signal = take 8 $ drop offset result
39 basePattern = [0, 1, 0, -1]
41 patternOf :: Int -> [Int]
42 patternOf index = drop 1 $ cycle $ concatMap (replicate index) basePattern
44 elementAt :: [Int] -> Int -> Int
45 elementAt digits index = (abs $ sum $ zipWith (*) digits $ patternOf index) `mod` 10
47 fftStep :: [Int] -> [Int]
48 fftStep digits = map (elementAt digits) [1..(length digits)]
50 fft :: [Int] -> [[Int]]
53 fastFft :: [Int] -> [[Int]]
54 fastFft = iterate fastFftStep
56 fastFftStep :: [Int] -> [Int]
57 -- fastFftStep digits = map (\ds -> (sum ds) `mod` 10) $ tails digits
58 fastFftStep digits = scanr (\d s -> (d + s) `mod` 10) 0 digits
61 parseDigits :: String -> [Int]
62 parseDigits = map digitToInt