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

extension Collection where Index: Comparable {
    subscript(back i: Int) -> Iterator.Element {
        let backBy = i + 1
        return self[self.index(self.endIndex, offsetBy: -backBy)]
    }
}

extension Array {
  init(repeating: [Element], count: Int) {
    self.init([[Element]](repeating: repeating, count: count).flatMap{$0})
  }

  func repeated(count: Int) -> [Element] {
    return [Element](repeating: self, count: count)
  }
}

extension BinaryInteger {
    var digits: [Int] {
        return String(describing: self).compactMap { Int(String($0)) }
    }
}

func fft(_ input: [Int]) -> [Int] {
    var next:[Int] = Array.init(repeating: 0, count: input.count)
    var list: [Int] = input
    list.insert(0, at: 0)
    let pattern:[Int:Int] = [0:0, 1:1,2:0,3:-1]
    for i in (0 ..< input.count) {
        for j in (0 ..< list.count) {
            let value = (j / (i + 1)) % 4
            let y = pattern[value]!
            let x = list[j]
            next[i] += x * y
        }
    }
    next = next.map{ $0.digits.last! }
//    print(next)
    return next
}

func fft2(_ input: [Int]) -> [Int] {
    var next:[Int] = Array.init(repeating: 0, count: input.count)
    var ans = 0

    for i in (1 ... input.count/2) {
        ans += input[back: i]
        let index = next.index(next.endIndex, offsetBy: -(i+1))
        next[index] = ans
    }

    next = next.map{ abs($0)%10 }
    return next
}

func partOne() {
    var output: [Int] = input
    for a in (1 ... 100) {
        print("Processing \(a)")
        output = fft(output)
        print("ouput \(output[0...7])")
    }
    print("Part 1 answer is : \(output[0 ... 7])")
}



func partTwo() {
    var output: Array<Int> = Array.init(repeating: input, count: 10000)
    var offString = ""
    let array = output[0...6]
    _ = array.map{ a in offString = offString + "\(a)" }
    let offset = Int(offString)!
    for a in (1...100) {
        print("Processing \(a)")
        output = fft2(output)
        print("ouput \(output[0...7])")
    }
    print("Part 2 answer is : \(output[offset ... offset+7])")
}

partOne()
partTwo()

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

import arrow.core.extensions.sequence.applicative.replicate
import java.nio.file.Files
import java.nio.file.Paths
import java.util.stream.Collectors
import kotlin.math.abs
import kotlin.streams.asStream

object Day16 {
    private const val FILENAME = "src/main/resources/day16.txt"
    val fileData = Files.readAllLines(Paths.get(FILENAME)).first()

    val basePattern = sequenceOf(0, 1, 0, -1)
    fun generatePattern(n: Int): Sequence<Int> {
        return generateSequence { basePattern.flatMap { sequenceOf(it).replicate(n).flatten() } }.flatten().drop(1)
    }

    fun fft(input: Sequence<Int>, size: Int): Sequence<Int> {
        return (0 until size).asSequence().asStream().parallel().map { i ->
            abs(generatePattern(i + 1).zip(input.asSequence())
                .filterNot { (a, _) -> a == 0 }.asStream().parallel()
                .map { it.first * it.second }
                .reduce { t: Int, u: Int -> t + u }.orElseGet { 0 }) % 10
        }.collect(Collectors.toUnmodifiableList()).asSequence()
    }


    tailrec fun fftTimes(input: Sequence<Int>, size: Int, n: Int): Sequence<Int> {
        println("$n) " + input.take(8).joinToString(""))
        return when {
            n < 1 -> input
            else -> fftTimes(fft(input, size), size, n - 1)
        }
    }

    fun part1(): String {
        val list = fileData.map { it.toString().toInt() }
        return fftTimes(list.asSequence(), list.size, 100).take(8).joinToString("")
    }
}


fun main() {
    println(Day16.fftTimes("12345678".asSequence().map { it.toString().toInt() }, 8, 3).joinToString(""))
    println(Day16.part1())
}