Day 6: Guard Gallivant
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 1 point
*
I’m not proud of it.
I have a conjecture though, that any looping solution, obtained by adding one obstacle, would eventually lead to a rectangular loop. That may lead to a non brute-force solution. It’s quite hard to prove rigorously though. (Maybe proving, that the loop has to be convex, which is an equivalent statement here, is easier? You can also find matrix representations of the guard’s state changes, if that helps.)
Maybe some of the more mathematically inclined people here can try proving or disproving that.
Anyways, here is my current solution in Kotlin:
fun main() {
fun part1(input: List<String>): Int {
val puzzleMap = PuzzleMap.fromPuzzleInput(input)
puzzleMap.simulateGuardPath()
return puzzleMap.asIterable().indicesWhere { it is MapObject.Visited }.count()
}
fun part2(input: List<String>): Int {
val puzzleMap = PuzzleMap.fromPuzzleInput(input)
puzzleMap.simulateGuardPath()
return puzzleMap.asIterable().indicesWhere { it is MapObject.Visited }.count {
val alteredPuzzleMap = PuzzleMap.fromPuzzleInput(input)
alteredPuzzleMap[VecNReal(it)] = MapObject.Obstacle()
alteredPuzzleMap.simulateGuardPath()
}
}
val testInput = readInput("Day06_test")
check(part1(testInput) == 41)
check(part2(testInput) == 6)
val input = readInput("Day06")
part1(input).println()
part2(input).println()
}
enum class Orientation {
NORTH, SOUTH, WEST, EAST;
fun rotateClockwise(): Orientation {
return when (this) {
NORTH -> EAST
EAST -> SOUTH
SOUTH -> WEST
WEST -> NORTH
}
}
fun asVector(): VecNReal {
return when (this) {
NORTH -> VecNReal(listOf(0.0, 1.0))
SOUTH -> VecNReal(listOf(0.0, -1.0))
WEST -> VecNReal(listOf(-1.0, 0.0))
EAST -> VecNReal(listOf(1.0, 0.0))
}
}
}
class PuzzleMap(objectElements: List<List<MapObject>>): Grid2D<MapObject>(objectElements) {
private val guard = Grid2D(objectElements).asIterable().first { it is MapObject.Guard } as MapObject.Guard
companion object {
fun fromPuzzleInput(input: List<String>): PuzzleMap = PuzzleMap(
input.reversed().mapIndexed { y, row -> row.mapIndexed { x, cell -> MapObject.fromCharAndIndex(cell, x to y) } }
).also { it.transpose() }
}
fun guardStep() {
if (guardScout() is MapObject.Obstacle) guard.orientation = guard.orientation.rotateClockwise()
else {
guard.position += guard.orientation.asVector()
}
}
fun simulateGuardPath(): Boolean {
while (true) {
markVisited()
val scouted = guardScout()
if (scouted is MapObject.Visited && guard.orientation in scouted.inOrientation) return true
else if (scouted is MapObject.OutOfBounds) return false
guardStep()
}
}
fun guardScout(): MapObject = runCatching { this[guard.position + guard.orientation.asVector()] }.getOrElse { MapObject.OutOfBounds }
fun markVisited() {
val previousMapObject = this[guard.position]
if (previousMapObject is MapObject.Visited) this[guard.position] = previousMapObject.copy(previousMapObject.inOrientation.plus(guard.orientation))
else this[guard.position] = MapObject.Visited(listOf(guard.orientation))
}
}
sealed class MapObject {
class Empty: MapObject()
class Obstacle: MapObject()
object OutOfBounds: MapObject()
data class Visited(val inOrientation: List<Orientation>): MapObject()
data class Guard(var position: VecNReal, var orientation: Orientation = Orientation.NORTH): MapObject()
companion object {
fun fromCharAndIndex(c: Char, index: Pair<Int, Int>): MapObject {
return when (c) {
'.' -> Empty()
'#' -> Obstacle()
'^' -> Guard(VecNReal(index))
else -> throw IllegalArgumentException("Unknown map object $c")
}
}
}
}
I also have a repo.
