Finish day 20

4 files changed, 77 insertions, 20 deletions

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 <T> combinations(items: Sequence<T>): Sequence<Pair<T, T>> =
-        sequence {
-            items.forEach { a ->
-                items.forEach { b ->
-                    yield(a to b)
-                }
-            }
-        }
-
     fun part1(input: List<String>): Int =
         input
             .asSequence()
@@ -116,14 +107,9 @@ object Day18 {
             .reduce(SnailfishNum::plus)
             .magnitude()
 
-    fun part2(input: List<String>): Int =
-        combinations(
-            input
-                .asSequence()
-                .map(SnailfishNum::parse)
-        )
-            .filter { it.first !== it.second }
-            .maxOf { (it.first + it.second).magnitude() }
+    fun part2(input: List<String>): 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<Pos2D>
+    ) {
+        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<Pos2D>, 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<Pos2D>, val topLeft: Pos2D, val bottomRight: Pos2D) {
+        companion object {
+            fun initial(image: Set<Pos2D>) = 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<String>): Map<Pos2D, Int> =
@@ -30,3 +32,12 @@ fun parseToMap(input: List<String>): Map<Pos2D, Int> =
             Pos2D(x, y) to char.toString().toInt()
         }
     }.toMap()
+
+fun <T> combinations(first: Iterable<T>, second: Iterable<T> = first): Sequence<Pair<T, T>> =
+    sequence {
+        first.forEach { a ->
+            second.forEach { b ->
+                yield(a to b)
+            }
+        }
+    }