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

[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)}")
}