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

Can't stop the signal!

Day 16 - The Problem

Communication speed and quality has become a problem out here in the gas giants. Communication takes so long that we need to come up with a way to verify and repair the signals we receive to avoid having to have Control repeat itself.

Part 1 has us apply the "Flawed Frequency Transmission" algorithm supplied in the problem statement. We need to run it 100 times to get our solution.

If you brute forced your way through Part 1, Part 2 is a whole lot of hurt. The "actual" signal is 1000 times as long as in Part 1, so once again we need to find a good way to cheat.

Ongoing Meta

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Languages Seen On Day 15

Under construction

Comments

[Rizwan]

day 16 in swift - its slow but got answer though

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()

[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

[Jon Bristow]

Part 1 can be brute forced very easily.

Part 2 needs a way to cheat. I may noodle on this a while before resorting to hints.

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())
}

[Jon Bristow]

Woof, thanks to the hints contained in Rizwan's solution, I was able to construct a 3 second part 2:

import java.nio.file.Files
import java.nio.file.Paths
import kotlin.math.abs

object Day16r {
    private const val FILENAME = "src/main/resources/day16r.txt"
    val fileData = Files.readAllLines(Paths.get(FILENAME)).first().trim().map { it.toString().toLong() }
    private val basePattern = arrayOf(0, 1, 0, -1)

    fun part1(input: List<Long>) = nFft1(100, input).take(8).joinToString("").toInt()
    fun part2(input: List<Long>): Int =
        nFft2(
            n = 100,
            input = generateSequence { input }
                .take(10_000)
                .flatten()
                .drop(input.take(7).joinToString("").toInt())
                .toList()
        ).take(8).joinToString("").toInt()


    private fun fft(input: List<Long>): List<Long> {
        val half = input.size / 2
        val next = MutableList(input.size) { 0L }

        input.take(half).forEachIndexed { i, _ ->
            next[i] = input.mapIndexed { j, it -> j to it }
                .drop(i).filter { (j, _) ->
                    ((j + 1) / (i + 1)) % 2 != 0
                }
                .fold(0L) { acc, (j, c) ->
                    acc + c * basePattern[((j + 1) / (i + 1)) % 4]
                }
        }
        (1..half).asSequence().forEach {
            next[half + it - 1] = input.slice(half + it - 1 until input.size).sum()
        }
        return next.map { abs(it) % 10 }

    }

    private fun fft2(input: List<Long>): List<Long> {
        val next = MutableList(size = input.size, init = { 0L })
        var value = 0L
        for (i in (1 until input.size)) {
            value += input[input.lastIndex - i]
            next[next.lastIndex - i] = value
        }
        return next.map { abs(it) % 10 }
    }

    private tailrec fun nFft1(n: Int, input: List<Long>): List<Long> {
        return when {
            n < 1 -> input
            else -> nFft1(n - 1, fft(input))
        }
    }

    private tailrec fun nFft2(n: Int, input: List<Long>): List<Long> {
        return when {
            n < 1 -> input
            else -> nFft2(n - 1, fft2(input))
        }
    }
}

fun main() {
    println("part1: ${Day16r.part1(Day16r.fileData)}")
    println("part2: ${Day16r.part2(Day16r.fileData)}")
}