## DEV Community is a community of 722,735 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Jon Bristow

Posted on

# Advent of Code 2019 Solution Megathread - Day 24: Planet of Discord

We're nearly there! And it's Conway with a late entry!

### Day 24 - The Problem

Hail Eris! We're on the last planet before we get to Santa!

Unfortunately, we also have a bug problem.

In Part 1, we need to apply some generative rules to a field of points where critters magically live and die based upon the status of their neighbors. We also need to calculate a score based upon their position at the first sign of a loop in their lifecycle!

Those Plutoers (Plutesians? Plutannescos?) must have been here, though... It turns out these critters are generating in recursive space! In Part 2 we need to simulate 200 ticks of the infinitely recursive plane.

### Ongoing Meta

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

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.

## Discussion (1) Jon Bristow • Edited

All-in-all, this wasn't too bad if you've done a Conway's Game of Life simulation before.

Part 1 was deceptively easy, which made way to a deceptively easily brute-forceable part 2. I'll try to make this more elegant, but it probably won't be until after Christmas.

Kotlin Solution:

``````import java.math.BigInteger
import java.nio.file.Files
import java.nio.file.Paths

data class RecursivePoint(val level: Int, val point: Point) {
override fun toString(): String {
return "\$level:(\${point.x},\${point.y})"
}
}

private val middle = Point(2, 2)

object Day24 {
private const val FILENAME = "src/main/resources/day24.txt"
val fileData: List<String> get() = Files.readAllLines(Paths.get(FILENAME)).filter { it.isNotEmpty() }

private fun parseMap(input: List<String>): Map<Point, Boolean> {
return (input.indices).flatMap { y ->
(input.indices).map { x ->
Point(x, y) to (input[y][x] == '#')
}
}.toMap()
}

private fun shouldLive(self: Boolean, neighbors: List<Boolean>) =
neighbors.count { it }.let { (!self && it == 2) || (it == 1) }

private fun neighbors(rp: RecursivePoint) = when {
rp.point == Point(0, 0) ->
listOf(
RecursivePoint(rp.level - 1, Point(2, 1)),
RecursivePoint(rp.level - 1, Point(1, 2))
) + rp.right() + rp.below()
rp.point == Point(4, 4) ->
listOf(
RecursivePoint(rp.level - 1, Point(2, 3)),
RecursivePoint(rp.level - 1, Point(3, 2))
) + rp.left() + rp.above()
rp.point == Point(0, 4) ->
listOf(
RecursivePoint(rp.level - 1, Point(2, 3)),
RecursivePoint(rp.level - 1, Point(1, 2))
) + rp.right() + rp.above()
rp.point == Point(4, 0) ->
listOf(
RecursivePoint(rp.level - 1, Point(2, 1)),
RecursivePoint(rp.level - 1, Point(3, 2))
) + rp.left() + rp.below()

rp.point == Point(1, 2) ->
rp.aboveAndBelow() + rp.left() + (0..4).map {
rp.copy(level = rp.level + 1, point = Point(x = 0, y = it))
}
rp.point == Point(2, 1) ->
rp.leftAndRight() + rp.above() + (0..4).map {
rp.copy(level = rp.level + 1, point = Point(x = it, y = 0))
}
rp.point == Point(2, 3) ->
rp.leftAndRight() + rp.below() + (0..4).map {
rp.copy(level = rp.level + 1, point = Point(x = it, y = 4))
}
rp.point == Point(3, 2) ->
rp.aboveAndBelow() + rp.right() + (0..4).map {
rp.copy(level = rp.level + 1, point = Point(x = 4, y = it))
}            // top
rp.point.y == 0 && rp.point.x > 0 && rp.point.x < 4 ->
rp.leftAndRight() + rp.below() + RecursivePoint(rp.level - 1, Point(2, 1))
// bottom
rp.point.y == 4 && rp.point.x > 0 && rp.point.x < 4 ->
rp.leftAndRight() + rp.above() + RecursivePoint(rp.level - 1, Point(2, 3))
//left
rp.point.x == 0 && rp.point.y > 0 && rp.point.y < 4 ->
rp.aboveAndBelow() + rp.right() + RecursivePoint(rp.level - 1, Point(1, 2))
//right
rp.point.x == 4 && rp.point.y > 0 && rp.point.y < 4 ->
rp.aboveAndBelow() + rp.left() + RecursivePoint(rp.level - 1, Point(3, 2))
else -> rp.allDirections()
}

fun part1(input: List<String>) {

val bugMap = parseMap(input)
val neighborMap = bugMap.mapValues { (k, _) ->
(allDirections().map(k::inDirection).filter(bugMap::containsKey))
}

fun step(bm: Map<Point, Boolean>): Map<Point, Boolean> {
return bm.mapValues { (k, v) -> shouldLive(v, neighborMap[k]!!.mapNotNull { bm[it] }) }
}

tailrec fun stepUntilRepeat(bm: Map<Point, Boolean>, seen: Set<String>): Map<Point, Boolean> {
return when (val prev = bm.printOut()) {
in seen -> bm
else -> stepUntilRepeat(step(bm), seen + prev)
}
}

println(stepUntilRepeat(bugMap, emptySet()).calculateDiversity())
}

private fun Map<Point, Boolean>.calculateDiversity(): BigInteger {
val inline = (0 until 5).flatMap { y ->
(0 until 5).map { x ->
this[Point(x, y)] ?: false
}
}
return inline.withIndex().fold(BigInteger.ZERO) { acc, curr ->
if (curr.value) {
acc + BigInteger.TWO.pow(curr.index)
} else {
acc
}
}

}

fun part2(input: List<String>) {
val bugMap = (parseMap(input) - middle).mapKeys { RecursivePoint(0, it.key) }

fun step(bm: Map<RecursivePoint, Boolean>): Map<RecursivePoint, Boolean> {
return bm.mapValues { (k, v) ->
val ns = neighbors(k)
shouldLive(v, ns.map { bm[it] ?: false })
}
}

fun addLevelBelow(minLevel: Map.Entry<Int, Int>) = when {
minLevel.value > 0 -> addEmptyLevel(minLevel.key - 1)
else -> emptyMap()
}

fun addLevelAbove(maxLevel: Map.Entry<Int, Int>) = when {
maxLevel.value > 0 -> addEmptyLevel(maxLevel.key + 1)
else -> emptyMap()
}

tailrec fun stepN(count: Int, bm: Map<RecursivePoint, Boolean>): Map<RecursivePoint, Boolean> = when (count) {
0 -> bm
else -> {
val (minLevel, maxLevel) =
bm.asSequence()
.groupBy { it.key.level }
.mapValues { it.value.count(Map.Entry<RecursivePoint, Boolean>::value) }.asSequence()
.sortedBy { it.key }
.let { it.first() to it.last() }
stepN(count - 1, step(expanded))
}
}

println(stepN(200, bugMap).count(Map.Entry<RecursivePoint, Boolean>::value))
}

(0 until 5).flatMap { y ->
(0 until 5).map { x -> RecursivePoint(i, Point(x, y)) to false }
}.toMap() - RecursivePoint(i, middle)
}

private fun RecursivePoint.above() = copy(point = point.copy(y = point.y - 1))
private fun RecursivePoint.below() = copy(point = point.copy(y = point.y + 1))
private fun RecursivePoint.aboveAndBelow() = listOf(above(), below())
private fun RecursivePoint.left() = copy(point = point.copy(x = point.x - 1))
private fun RecursivePoint.right() = copy(point = point.copy(x = point.x + 1))
private fun RecursivePoint.leftAndRight() = listOf(left(), right())
private fun RecursivePoint.allDirections() = aboveAndBelow() + leftAndRight()

fun Map<Point, Boolean>.printOut(): String {
return (0 until 5).joinToString("\n") { y ->
(0 until 5).joinToString("") { x ->
when (this[Point(x, y)] ?: false) {
true -> '#'
false -> '.'
}.toString()
}
}
}

fun main() {
Day24.part1(Day24.fileData)
Day24.part2(Day24.fileData)
}

``````