Discussion on: Advent of Code 2019 Solution Megathread - Day 16: Flawed Frequency Transmission

[Neil Gall]

Brute forced part 1 in Haskell for its amazing list manipulations. But that's not going to work for part 2. Half the pattern is zeros in each row so clearly there are ways to optimise. Will need to mull it over.

import Data.Char (isSpace, ord)
import Data.List (dropWhileEnd, intercalate, transpose)
import Test.Hspec

basePattern = [0,1,0,-1]
zeroChar = ord '0'

strip :: String -> String
strip = dropWhile isSpace . dropWhileEnd isSpace

parseInput :: String -> [Int]
parseInput = map (flip (-) zeroChar . ord)

showOutput :: [Int] -> String
showOutput = intercalate "" . map show

patternForIndex :: Int -> [Int]
patternForIndex n = drop 1 $ concat $ repeat $ concat $ transpose $ replicate n basePattern

pairProduct :: (Int,Int) -> Int
pairProduct (x,y) = x * y

outputRow :: [Int] -> Int -> Int
outputRow input n = (abs $ sum $ map pairProduct $ zip input (patternForIndex n)) `mod` 10

-- extra parameter makes this useful in folds
fftPhase :: [Int] -> Int -> [Int]
fftPhase input _ = map (outputRow input) [1..length input]

runPhases :: Int -> String -> String
runPhases n input = showOutput $ foldl fftPhase (parseInput input) [1..n]

fftPhaseTests = do
  let phases = scanl fftPhase (parseInput "12345678") [1..4]
  map showOutput phases `shouldBe` ["12345678", "48226158", "34040438", "03415518", "01029498"]

largerTests = do
  runPhases 100 "80871224585914546619083218645595" `shouldStartWith` "24176176"
  runPhases 100 "19617804207202209144916044189917" `shouldStartWith` "73745418"
  runPhases 100 "69317163492948606335995924319873" `shouldStartWith` "52432133"

part1 input =
  let result = take 8 $ runPhases 100 input in
  putStrLn $ "Part 1 .. " ++ result

main = do
  fftPhaseTests
  largerTests

  input <- fmap strip $ readFile "input.txt"
  part1 input