Advent of Code 2024 - Day 6 - Guard Gallivant

[@aaronperl]

My solution for Part B is still running so I don't know yet if it works.... it looks like I'm taking a mostly-similar approach to you, but instead of just tracking the visited positions, I'm also tracking the direction that the guard travelled through each position. Then, if the guard moves into a visited position in the same direction as before, the guard should be entering a loop, so I increase the counter and move on to the next attempt.
I still feel like there should be a better way to do this, because it always seems like "the right" algorithm to every AoC problem ends up giving the result in milliseconds.
... And now it looks like my code just got stuck, so I guess there is still more for me to figure out....

[@DanielPersson]

Hi Aaron.
This one was something that stumped me. And I think there is a really elegant solution if you know more about AI, math or graphics I guess. But I think making the guard run is kinda a good solution.
The map is really small; maybe you could load it into a graphics card and use the thousands of cores there to do small, quick calculations.
Thank you for being a part of this event every year and the community at large.
Best regards
Daniel

[@aaronperl]

@@DanielPersson As I thought about the problem a bit more, I realized my error: it's possible to cross the same spot in different directions, so my simple loop detection didn't work; I needed to track all the directions at each visited position. Once I did that, I was able to get the correct solution (but it still took a few minutes to run .... but it's good enough for AoC :) )

[@WayneBagguley]

SPOILER: Don't read this if you haven't figured it out yet but it looks like you are always moving forward after hitting an obstacle and turning, so if you have another obstacle immediately in front of you after turning it will move to that position and you will get an incorrect result. To detect a loop you need to keep a set of visited position-direction pairs, if your current position and direction pair is in the set then it's a loop.

[@DanielPersson]

Hi Wayne.
Thank you for the hint, I was totally stumped and the simple thing I missed was that I could turn multiple times and that is in hindsight obvious.
Best regards
Daniel

[@WayneBagguley]

Part 1:
fun calc(input: List): Int {
var current = '^'
var direction = 0 to -1
var position = input.flatMapIndexed { y, s -> s.mapIndexed { x, c -> x to c }.filter { it.second == '^' }.map { it.first to y } }.first()
val visited: MutableSet = mutableSetOf(position)

while (current != 'X') {
val next = input.getOrNull(position.second + direction.second)?.getOrNull(position.first + direction.first) ?: 'X'
when (next) {
'.', '^' -> {
position = position.first + direction.first to position.second + direction.second
visited.add(position)
current = next
}
'#' -> direction = -direction.second to direction.first
else -> current = 'X'
}
}
return visited.size
}

[@WayneBagguley]

Part 2:
fun calc(input: List): Int {
val start = input.flatMapIndexed { y, s -> s.mapIndexed { x, c -> x to c }.filter { it.second == '^' }.map { it.first to y } }.first()
val dots = input.flatMapIndexed { y, s -> s.mapIndexed { x, c -> x to c }.filter { it.second == '.' }.map { it.first to y } }
return dots.map { d -> input.toMutableList().apply { this[d.second] = StringBuilder(this[d.second])
.also { it.setCharAt(d.first, '#') }.toString() } }.count { !doesExit(it, start) }
}
private fun doesExit(input: List, start: Pair): Boolean {
var position = start
var current = '^'
var direction = 0 to -1
val visited: MutableSet = mutableSetOf((0 to -1) to start)
while (current != 'X') {
val next = input.getOrNull(position.second + direction.second)?.getOrNull(position.first + direction.first) ?: 'X'
when (next) {
'.', '^' -> {
position = position.first + direction.first to position.second + direction.second
if (position to direction in visited) return false
visited.add(position to direction)
current = next
}
'#' -> direction = -direction.second to direction.first
else -> current = 'X'
}
}
return true
}