From 992d24939100a6adb466b23449a62c36736b4249 Mon Sep 17 00:00:00 2001 From: tchojnacki Date: Sat, 13 Aug 2022 12:25:41 +0200 Subject: Finish day 20 --- aoc-2021-kotlin/README.md | 6 ++--- aoc-2021-kotlin/src/Day18.kt | 20 +++------------ aoc-2021-kotlin/src/Day20.kt | 60 ++++++++++++++++++++++++++++++++++++++++++++ aoc-2021-kotlin/src/Utils.kt | 11 ++++++++ 4 files changed, 77 insertions(+), 20 deletions(-) create mode 100644 aoc-2021-kotlin/src/Day20.kt (limited to 'aoc-2021-kotlin') diff --git a/aoc-2021-kotlin/README.md b/aoc-2021-kotlin/README.md index e2188a4..e8bad04 100644 --- a/aoc-2021-kotlin/README.md +++ b/aoc-2021-kotlin/README.md @@ -1,7 +1,7 @@ # Advent of Code 2021 in Kotlin ![Kotlin](https://img.shields.io/badge/Kotlin-grey?logo=Kotlin) -![41/50 stars](https://img.shields.io/badge/🌟%20stars-41/50-orange) -![21/25 days](https://img.shields.io/badge/📅%20days-21/25-blue) +![43/50 stars](https://img.shields.io/badge/🌟%20stars-43/50-orange) +![22/25 days](https://img.shields.io/badge/📅%20days-22/25-blue) Welcome to the Advent of Code Kotlin project created by [tchojnacki][github] using the [Advent of Code Kotlin Template][template] delivered by JetBrains. @@ -29,7 +29,7 @@ Welcome to the Advent of Code Kotlin project created by [tchojnacki][github] usi | Day 17: Trick Shot | 🌟 | 🌟 | | Day 18: Snailfish | 🌟 | 🌟 | | Day 19: Beacon Scanner | 🌟 | 🌟 | -| Day 20: Trench Map | | | +| Day 20: Trench Map | 🌟 | 🌟 | | Day 21: Dirac Dice | | | | Day 22: Reactor Reboot | | | | Day 23: Amphipod | | | diff --git a/aoc-2021-kotlin/src/Day18.kt b/aoc-2021-kotlin/src/Day18.kt index 84575b7..09c688a 100644 --- a/aoc-2021-kotlin/src/Day18.kt +++ b/aoc-2021-kotlin/src/Day18.kt @@ -100,15 +100,6 @@ object Day18 { ).also { it.reduce() } } - private fun combinations(items: Sequence): Sequence> = - sequence { - items.forEach { a -> - items.forEach { b -> - yield(a to b) - } - } - } - fun part1(input: List): Int = input .asSequence() @@ -116,14 +107,9 @@ object Day18 { .reduce(SnailfishNum::plus) .magnitude() - fun part2(input: List): Int = - combinations( - input - .asSequence() - .map(SnailfishNum::parse) - ) - .filter { it.first !== it.second } - .maxOf { (it.first + it.second).magnitude() } + fun part2(input: List): Int = combinations(input.map(SnailfishNum::parse)) + .filter { it.first !== it.second } + .maxOf { (it.first + it.second).magnitude() } } fun main() { diff --git a/aoc-2021-kotlin/src/Day20.kt b/aoc-2021-kotlin/src/Day20.kt new file mode 100644 index 0000000..9bc3b01 --- /dev/null +++ b/aoc-2021-kotlin/src/Day20.kt @@ -0,0 +1,60 @@ +object Day20 { + private class Enhancement private constructor( + private val algorithm: BooleanArray, + private val initialImage: Set + ) { + companion object { + fun fromString(string: String) = string.split("\n\n").let { (algorithm, image) -> + Enhancement( + algorithm.map { it == '#' }.toBooleanArray(), + image + .split("\n") + .withIndex() + .flatMap { (y, row) -> + row.withIndex().mapNotNull { (x, char) -> if (char == '#') Pos2D(x, y) else null } + } + .toSet() + ) + } + } + + private fun nextStateFor(currentImage: Set, pos: Pos2D) = combinations(1 downTo -1) + .map { (dy, dx) -> if (currentImage.contains(pos + Pos2D(dx, dy))) 1 else 0 } + .withIndex() + .sumOf { (index, value) -> value shl index } + .let { algorithm[it] } + + fun enhance(times: Int): Int { + return generateSequence(StepState.initial(initialImage)) { (image, topLeft, bottomRight) -> + StepState( + combinations(topLeft.y..bottomRight.y, topLeft.x..bottomRight.x) + .mapNotNull { (y, x) -> + Pos2D(x, y).let { if (nextStateFor(image, it)) it else null } + }.toSet(), + topLeft + Pos2D(1, 1), + bottomRight - Pos2D(1, 1) + ) + }.drop(times).first().image.size + } + } + + private data class StepState(val image: Set, val topLeft: Pos2D, val bottomRight: Pos2D) { + companion object { + fun initial(image: Set) = StepState(image, Pos2D(-100, -100), Pos2D(200, 200)) + } + } + + fun part1(input: String) = Enhancement.fromString(input).enhance(2) + + fun part2(input: String) = Enhancement.fromString(input).enhance(50) +} + +fun main() { + val testInput = readInputAsString("Day20_test") + check(Day20.part1(testInput) == 35) + check(Day20.part2(testInput) == 3351) + + val input = readInputAsString("Day20") + println(Day20.part1(input)) + println(Day20.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Utils.kt b/aoc-2021-kotlin/src/Utils.kt index 8fe3f75..4f78a1f 100644 --- a/aoc-2021-kotlin/src/Utils.kt +++ b/aoc-2021-kotlin/src/Utils.kt @@ -22,6 +22,8 @@ data class Pos2D(val x: Int, val y: Int) { } operator fun plus(other: Pos2D) = Pos2D(x + other.x, y + other.y) + + operator fun minus(other: Pos2D) = Pos2D(x - other.x, y - other.y) } fun parseToMap(input: List): Map = @@ -30,3 +32,12 @@ fun parseToMap(input: List): Map = Pos2D(x, y) to char.toString().toInt() } }.toMap() + +fun combinations(first: Iterable, second: Iterable = first): Sequence> = + sequence { + first.forEach { a -> + second.forEach { b -> + yield(a to b) + } + } + } -- cgit v1.2.3