advent16/src/advent16.hs

   1 import Debug.Trace
   2
   3 import Data.Char (digitToInt, intToDigit)
   4
   5 -- import qualified Data.Map.Strict as M
   6 -- import Data.Map.Strict ((!))
   7 import Data.List
   8 -- import qualified Data.Set as S
   9
  10
  11
  12 main :: IO ()
  13 main = do
  14         text <- readFile "data/advent16.txt"
  15         let digits = parseDigits text
  16         -- print mem
  17         print $ part1 digits
  18         print $ part2 digits
  19         -- print $ part2 mem
  20
  21 part1 :: [Int] -> String
  22 part1 digits = map intToDigit $ take 8 $ (fft digits)!!100
  23
  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
  29
  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
  36
  37
  38 basePattern :: [Int]
  39 basePattern = [0, 1, 0, -1]
  40
  41 patternOf :: Int -> [Int]
  42 patternOf index = drop 1 $ cycle $ concatMap (replicate index) basePattern
  43
  44 elementAt :: [Int] -> Int -> Int
  45 elementAt digits index = (abs $ sum $ zipWith (*) digits $ patternOf index) `mod` 10
  46
  47 fftStep :: [Int] -> [Int]
  48 fftStep digits = map (elementAt digits) [1..(length digits)]
  49
  50 fft :: [Int] -> [[Int]]
  51 fft = iterate fftStep
  52
  53 fastFft :: [Int] -> [[Int]]
  54 fastFft = iterate fastFftStep
  55
  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
  59
  60
  61 parseDigits :: String -> [Int]
  62 parseDigits = map digitToInt
  63
  64
  65