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

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.

Comments

[Jon Bristow]

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[0].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() }
                val expanded = bm + addLevelBelow(minLevel) + addLevelAbove(maxLevel)
                stepN(count - 1, step(expanded))
            }
        }

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

    private fun addEmptyLevel(i: Int) =
        (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)
}