### re: AoC Day 18: Settlers of The North Pole VIEW POST

Yawn. It was a relief to get something solvable after the problems from Saturday and Monday which were incredibly hard, but another Conway's Game of Life, with another huge iteration count? Just cranking the handle here, nothing new to solve.

I modelled it with a 2D array. Getting more familiar with Kotlin arrays and sequences now.

enum class Acre(val symbol: Char) {
OPEN('.'),
TREES('|'),
LUMBERYARD('#')
}

data class Pos(val x: Int, val y: Int)

val Pos.neighbours: Sequence<Pos> get() = sequence {
(-1..1).flatMap { dy ->
(-1..1).map { dx ->
if (dy != 0 || dx != 0) yield(Pos(x+dx,y+dy))
}
}
}

class Landscape(val width: Int, val height: Int) {
val acres: Array<Array<Acre>> = Array<Array<Acre>>(height) { Array<Acre>(width) { Acre.OPEN }}

val positions: Sequence<Pos> get() = sequence {
(0..height-1).flatMap { y -> (0..width-1).map { x -> yield(Pos(x, y)) }}
}

fun validPos(p: Pos): Boolean = 0 <= p.y && p.y < height && 0 <= p.x && p.x < width

fun neighbourCount(p: Pos, a: Acre): Int =
p.neighbours.count { n -> this[n] == a }

fun totalCount(a: Acre): Int = positions.count { pos -> this[pos] == a }

fun resourceValue(): Int = totalCount(Acre.TREES) * totalCount(Acre.LUMBERYARD)
}

operator fun Landscape.get(p: Pos): Acre = if (validPos(p)) acres[p.y][p.x] else Acre.OPEN
operator fun Landscape.set(p: Pos, a: Acre) { if (validPos(p)) acres[p.y][p.x] = a }

I made an infinite sequence of states again:

fun Landscape.tick(): Landscape {
val next = Landscape(width, height)
positions.forEach { pos ->
val neighbours = pos.neighbours.map(this::get).toList()
next[pos] = when (this[pos]) {
Acre.OPEN ->
if (neighbourCount(pos, Acre.TREES) >= 3)
Acre.TREES
else
Acre.OPEN

Acre.TREES ->
if (neighbourCount(pos, Acre.LUMBERYARD) >= 3)
Acre.LUMBERYARD
else
Acre.TREES

Acre.LUMBERYARD ->
if (neighbourCount(pos, Acre.LUMBERYARD) >= 1 && neighbourCount(pos, Acre.TREES) >= 1)
Acre.LUMBERYARD
else
Acre.OPEN
}
}
return next
}

fun Landscape.timeline(): Sequence<Landscape> = sequence {
var next = this@timeline
while (true) {
yield(next)
next = next.tick()
}
}

So part 1 was trivial:

fun part1(input: Landscape): Int =
input.timeline().drop(10).first().resourceValue()

For part 2 I made a generic loop finder:

inline fun <reified T> findLoop(ts: Sequence<T>): Pair<Int, Int> {
val seen = mutableMapOf<T, Int>()
val firstRepeat = ts.zip(indices).dropWhile { (t, i) ->
if (seen.containsKey(t))
false
else {
seen[t] = i
true
}
}.first()

return Pair(seen[firstRepeat.first]!!, firstRepeat.second)
}

Then used this to do the old find-loop-run-last-few-iterations dance:

fun part2(input: Landscape): Int {
val (loopStart, loopEnd) = findLoop(input.timeline())
val iterations = 1000000000
val loops = (iterations - loopStart) / (loopEnd - loopStart)
val lastLoop = (iterations - loopStart) % loops
val lastLoopTimeline = input.timeline().drop(loopStart)
val lastIteration = lastLoopTimeline.drop(lastLoop).first()
return lastIteration.resourceValue()
}
code of conduct - report abuse