advent16/src/advent16.hs

   1 import Data.Char (digitToInt, intToDigit)
   2
   3 main :: IO ()
   4 main = do
   5         text <- readFile "data/advent16.txt"
   6         let digits = parseDigits text
   7         -- print mem
   8         print $ part1 digits
   9         print $ part2 digits
  10         -- print $ part2 mem
  11
  12 part1 :: [Int] -> String
  13 part1 digits = map intToDigit $ take 8 $ (fft digits)!!100
  14
  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
  21
  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
  28
  29
  30 basePattern :: [Int]
  31 basePattern = [0, 1, 0, -1]
  32
  33 patternOf :: Int -> [Int]
  34 patternOf index = drop 1 $ cycle $ concatMap (replicate index) basePattern
  35
  36 elementAt :: [Int] -> Int -> Int
  37 elementAt digits index = (abs $ sum $ zipWith (*) digits $ patternOf index) `mod` 10
  38
  39 fftStep :: [Int] -> [Int]
  40 fftStep digits = map (elementAt digits) [1..(length digits)]
  41
  42 fft :: [Int] -> [[Int]]
  43 fft = iterate fftStep
  44
  45 fastFft :: [Int] -> [[Int]]
  46 fastFft = iterate fastFftStep
  47
  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
  51
  52
  53 parseDigits :: String -> [Int]
  54 parseDigits = map digitToInt
  55
  56
  57