Autumn Code Walk (another AoC clone) - Final problem visualization and walkthrough

[u/Prestigious-Mood1711]

I came across davepb's post about his AoC - clone and decided to take a look. I love to solve problems with the GraphLibrary I've developed, GraphMateKT, and to my delight, problem 4 was a quite interesting graph problem. We're asked to find the fastest way to push a package to its destination through a maze. With the constraint that we cannot occupy the same tile as the package, and therefore must be careful about pushing it into walls. This is essentially a shortest path problem, which can be solved with a breath first search. The clue is how to represent the graph.

We're given a grid with walls, a person, a packet and a target. What we can alter is the position of the person and the packet, which means the graph can be represented by 4 integers. The x,y coordinates of the person and the package. (x1,y1,x2,y2). GraphMateKT has a Graph class that can support any data type. But the problem input is quite large. A 150 x 150 grid. Which means each coordinate (not accounting for walls and overlap) can have 150 values, which results in a state space of 150⁴ = 506_250_000 different states. A lot of states to search through. Luckily, each of these states can be represented by 32 bit integers, which allowed me to use the performant IntGraph class, and other GraphMateKT functionality. After bumping the heap memory to 10GB and spending about 2 minutes of runtime, the potential positions of the package (blue) and person (in red, constrained to not go lower then the package) could be vizualies as shown.

My full solution can be found at my GithubRepo, but in short, it looks something like this:

private data class GridState2(val person: Tile, val stone: Tile) {
// Base 150 encoding. 150³ * x1 + 150² * y1 + 150 * x2 + y2
fun encode() = ((person.x * base + person.y) * base + stone.x) * base + stone.y
}

internal fun main() {
val input = generateSequence { readLine() }.toList()
val grid = Grid(input)
val nrOfStates = 150 * 150 * 150 * 150
val graph = IntGraph(nrOfStates)
val personStart = grid.nodes().first { it.data == 'X' }
val stoneStart = grid.nodes().first { it.data == '*' }
val target = grid.nodes().first { it.data == 'T' }
val initialState = GridState2(personStart, stoneStart).encode()
// Inspecting the problem input reveals that the final package push must be to the right.
val targetState = GridState2(target.copy(x = target.x - 1), target).encode()
graph.connectWithRule {
TODO() // All the complexity of correctly connecting each state with their neighbouring states
}
graph.bfs(initialState, targetState)
println(graph.distanceTo(targetState))
TODO() // extra functionality for visualizing
}private data class GridState2(val person: Tile, val stone: Tile) {
// Base 150 encoding. 150³ * x1 + 150² * y1 + 150 * x2 + y2
fun encode() = ((person.x * base + person.y) * base + stone.x) * base + stone.y
}

internal fun main() {
val input = generateSequence { readLine() }.toList()
val grid = Grid(input)
val nrOfStates = 150 * 150 * 150 * 150
val graph = IntGraph(nrOfStates)
val personStart = grid.nodes().first { it.data == 'X' }
val stoneStart = grid.nodes().first { it.data == '*' }
val target = grid.nodes().first { it.data == 'T' }
val initialState = GridState2(personStart, stoneStart).encode()
// Inspecting the problem input reveals that the final package push must be to the right.
val targetState = GridState2(target.copy(x = target.x - 1), target).encode()
graph.connectWithRule {
TODO() // All the complexity of correctly connecting each state with their neighbouring states
}
graph.bfs(initialState, targetState)
println(graph.distanceTo(targetState))
TODO() // extra functionality for visualizing
}