https://kotlinlang.org logo
Join SlackCommunities
Powered by
<Advent of Code 2024 day 16> (spoilers) :thread:
# advent-of-code
a
Advent of Code 2024 day 16 (spoilers) šŸ§µ
m
While waiting for the puzzle to unlock I thought "I should add Dijkstra to my utils, it might be needed in the coming days". Maybe next year I will be ready. šŸ˜„
advent of code intensifies 5
b
i always forget how to use my util dijkstra function so i end up just implementing it myself
p2 solved in 15 min, i should probably optimize that
m
Part 1
Part 2
p2 solved in 15 min, i should probably optimize that
I wanted to say 15 min is a very good time, but I think that's not what you meant. šŸ˜„
d
That was a fun one, I was waiting for Dijkstra
Track all paths is a nice extension
b
problems like these make me miss python, 
import networkx
ā˜ļø 1
d
Code cleaning time
p
This took me too much effort to debug, but finally part 2 in ~15 s runtime https://github.com/glubo/adventofcode/blob/main/src/main/kotlin/cz/glubo/adventofcode/y2024/day16/Day16.kt
d
Yeah I was failing to clear the "previous" set when I found a cheaper path
šŸ‘ 1
k
Had a literal off by 1 error in part 1 (was adding 1000 instead of 1001). And spent a lot of time on part 2 (was back on track after a bit of help figuring out the best way to track the path). Tidied up my solution
j
Priority Queue FTW, part1 ~6ms, part2 ~996ms.
d
30ms to solve both parts (single pass)
very nice 1
j
Good enough it isā€¦ I was happy that I didnā€™t run into memory problems when storing all the visited positions in every item in my queue
d
For ā€œfind one pathā€ you can store reverse links in a map. Then you walk from end to start to get the path. For all paths you can store them in a multimap and fill to get all paths.
Funny, if I switch from:
Copy code
val frontier = mutableSetOf(startReindeer)
// loop
val reindeer = frontier.minBy { minScores.getValue(it) }
frontier.remove(reindeer)
to
Copy code
val frontier = java.util.PriorityQueue<Pair<Reindeer, Int>>() { a, b -> a.second.compareTo(b.second)}
// loop
val (reindeer, score) = frontier.poll()!!
it gets slower by 5-7ms
j
Oh man I messed up the way finding so hard, I had a way a few seconds after solving part 1 but computing all with dijkstra I messed up.
p
Had so many brain farts with part 2, finally got it solved in 37sec runtime. I want to improve but have to deal with Christmas prep.
m
@Dan Fingal-Surma
it gets slower by 5-7ms
Possibly because the 
frontier
has to grow a lot more as you are not removing elements from it. Try 
remove()
instead of 
poll()
.
d
poll removes
šŸ‘ 1
If I make the set a list instead time goes up to 1s from 30ms šŸ™‚ linked list 2s
Lol nevermind, thatā€™s because in the List case you need to do
Copy code
while (frontier.remove(reindeer)) {}
if you do that then itā€™s basically the same
My max frontier size is 
161
m
For me the same change (from set to PriorityQueue) changes the run time from 3.3s to 120ms in part 2.
d
Another oddity, using 
mutableHashSetOf
is faster that 
HashSet
, I thought the former was 
LinkedHashSet
which Iā€™d expect to have more overhead
I imagine 
PriorityQueue
benefits you more as the frontier gets bigger
Iā€™m doing aggressive path pruning
m
I'm not doing any pruning, so it grows bigger.
d
Pruning rules are basically: (1) donā€™t generate turn if it makes you face a wall, (2) donā€™t add a neighbor to the Q if thereā€™s already a shorter path there.
Dropping rule (a) moves runtime from 30ms to 300ms
if I drop rule (b) it doesnā€™t complete
OOM
also (c) donā€™t add to the Q if it would be worse than the known shortest path
Oh also I compute the paths totally differently that you do, I donā€™t have the paths in the Q
that will likely be a constant factor difference
Screenshot 2024-12-16 at 2.13.54ā€ÆAM.png,Screenshot 2024-12-16 at 2.14.04ā€ÆAM.png,Screenshot 2024-12-16 at 2.14.13ā€ÆAM.png
j
I'm keeping the paths in priority queue for part2, but overall I have same principles as Dan above. I'd add one more: caching of possible exits from a 
Pair<Pos,Dir>
allowed me to come to:
Copy code
Parsing took 669.75us
Part 1 took 4.437250ms, result is 109516
Part 2 took 26.895375ms, result is 568
which is probably not yet optimal, but good enough to stop and start working on the visualization šŸ™‚
also I'm having my own PriorityQueue from previous years when I tried multiplatform, but from performance point of view it is not any different from the java.util's version:
Copy code
class PriorityQueue<E : Any>(val comparator: Comparator<E>, vararg initial: E) {

    private var backingList = mutableListOf<E>().apply { addAll(initial) }

    val size get() = backingList.size
    fun isNotEmpty(): Boolean = size > 0

    fun poll(): E {
        check(size > 0)
        return backingList.removeAt(0)
    }

    fun offer(e: E) {
        val index = backingList.binarySearch(e, comparator).let {
            if (it < 0) -it - 1 else it
        }
        backingList.add(index, e)
    }

    override fun toString(): String = backingList.toString()
}
m
I feel like the 'end' check isn't needed because the puzzle is constructed in such a way you barely skip over paths. but it runs very fast. frontier consists of only a pair of points and my visited set is actually a map that I do my combination logic on.
Day 16 Michael.cpp
n
I have no idea what is wrong with my code. After 2 hours pulling my hair I just got someone else's solution and it's off by 4 šŸ¤Æ Would appreciate if you have time to have a look to see if there is anything glaring obvious I am missing
D16P1.cpp
d
Oh yeah, you can skip enqueueing a node to the frontier if youā€™ve re-joined a previously explored path. But it doesnā€™t actually save any steps for me. 100% of the time in my input that node is already in the frontier (and frontier.add returns false)
b
@nerses you're adding the wrong distance on turns
d
heā€™s turning and moving in one step
b
oh
d
oh WOW, that optimization cuts my runtime in half
b
seems like that would eliminate possible paths with multiple turns in one place, but those are probably not optimal
d
vs turning without moving
if you ever turn and face a wall, itā€™s never an optimal path. and you canā€™t turn twice in one spot either and still be on an optimal path, then youā€™re backtracking
30ms to 15ms
this is wrong
.filterNot { it.p in settled.map { it.p } }
b
that would only be true if you can turn anywhere, not just at walls
d
(p, dir) is what gets settled, not p
b
i can think of an example where backtracking gets you the best path, but i don't know if any of the real inputs are that way
d
I donā€™t see how that would be true
b
the easiest one is if the best path is behind where you started
hard to explain, i'd have to draw it out
d
I think thatā€™s the only case
if you have to turn 180 at the start to get to the best path. But we start in a corner.
.filterNot { it.p to it.dir in settled.map { it.p to it.dir } }
is the correct expression
In any other case if you have to turn around you went the wrong way
b
i didn't look at the input, didn't know you start in a corner
d
w.r.t the code, the issue is that you may thing Point p is settled coming via direction d, but you may later discover that coming to point p via direction dā€™ is cheaper
because in that first case, you may need to turn to continue, which is quite costly
I mean thatā€™s the only case. You think itā€™s settled but you need to turn to continue. So coming at the point straight on is cheaper.
in general the vertexes in the abstract graph are (p, d)
n
hmmm you mean in situations like T intersections?
Copy code
#.####
#.....
#.####
#...##
###.##
d
No
Let me see if I can draw one
n
in the above if I am coming from the left on row index 1 at point(1, 1) I might later come from the bottom up which might be cheaper
d
Oh sorry yes
if the exit is up or down, thatā€™s the case
if the exit is right then itā€™s symmetric
n
but because the bottom one is waiting as it is on a turn. point(1.1) will be set as settled but it's wrong as at the next step it needs to turn
d
Correct
n
damn
thanks! let me add it
d
Does it fail on the test input or the real input?
Iā€™m actually having a hard time coming up with an input where this holds
I think you also have
Copy code
val existing = unsettled.firstOrNull { it.p == n.p }
donā€™t you need to consider dir here as well?
n
aaand it worked! Thanks a lot @Dan Fingal-Surma I was thinking that if you reached a point it doesn't matter from which side you came as it is always going 1 step from the cheapest side. But obviously i missed that because even if it comes to same point one of the paths might need to turn to continue adding huge penalty
šŸŽ‰ 1
I think unsettled is fine like that as there is only going one for each point and it is going to be the cheapest It was passing both test inputs, but failing the real input by 4. I was getting 102508 instead of 102504
d
Yeah if I introduce that bug into my code itā€™s also off by 4
Now I want to find the minimal maze that causes thisā€¦
Ah I can just print the path with/without and examine the section
n
Copy code
#######
#....E#
#.#####
#.....#
#.###.#
#...#.#
###.#.#
#S....#
#######
4018 instead of 4014 šŸ™‚
d
OK yes thatā€™s it. In the real input itā€™s a very windy difference.
Correct path vs incorrect path:
Copy code
OOOOO
 O
 O
 O
 OOO
   O
 OOO
vs
Copy code
OOOOO
 O
 OOOOO
     O
     O
     O
 OOOOO
n
yeah exactly
d
Same # of turns, #2 is longer in total, but it gets to its 3rd turn point before #1 gets there
šŸ‘Œ 1
m
@Jakub GwĆ³ÅŗdÅŗ Regarding timing solutions, it looks like different inputs require a dramatically different amount of work. My solution completes in 80ms on my input, but takes 5 seconds on someone elses input.
true 1
d
@Marcin Wisniowski DM me the expensive input?
j
It's visualization time! My reindeer goes funny path.
Day16.mov
šŸ˜‚ 7
šŸ™Œ 7
kodee naughty 5
d
Someone on the expensive input provided my runtime gets better, 15ms -> 13ms
ok yes 13186 nodes dequeued vs 16460
OK I can get this down to 6-7ms on all 3 inputs I have by putting the cost information directly in the frontier instead of looking it up in the map
Copy code
val frontier = mutableSetOf(startReindeer to 0)
// loop
val (reindeer, score) = frontier.minBy { it.second }
frontier.remove(reindeer to score)
instead of
Copy code
val frontier = mutableSetOf(startReindeer)
// loop
val reindeer = frontier.minBy { minScores.getValue(it) }
frontier.remove(reindeer)
val score = minScores.getValue(reindeer)
Aww my input doesnā€™t make a funny picture
m
Got my solution to finish down from 
80ms
to 
0.5ms
šŸŽ‰ 1
d
what was the key?
m
Not adding pointless moves to the 
unvisited
list, meaning not adding turns that end up facing a wall.
šŸ‘ 1
d
Do you turn and move at the same time? I found that cut my runtime in half
j
pls share this expensive output šŸ™‚ somehow my "kodee input" (which I though would be hard for queue) got me from 5+25ms on real input to 2+10ms
m
It seems to depend on the solution though if it's actually more expensive or not.
input_expensive.txt
j
wooooho! On this expensive one:
Copy code
Parsing took 1.253125ms
Part 1 took 5.480791ms, result is 73432
Part 2 took 5.328513417s, result is 496
Daaamn
šŸ˜µ 1
d
Weird, removing the optimization to skip pointless turns only takes me from 6ms to 45ms on the expensive input
r
Today's visualization!
K 2
kotlin notebook 1
advent of code intensifies 1
p
@Marcin Wisniowski interestingly that expensive input is identical to my input šŸ¤”
p
https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day16.kt Made it šŸ˜… This stuff is getting really challenging for me. How do I even call this? Part 1: Dijkstraā€™s Part 2: Is that still Dijkstraā€™s? Using a priority queue I managed to get part 2 down to 150ms
n
I was behind on Day 15 because a) it was hard for me; and b) I went skiing yesterday and was totally bushed. But luckily Day 16 was fast (by my standards; just under an hour). Not that my solution was fast, about 1s cold start. Applying some low-hanging fruit optimizations brings it down to ~250ms cold start, half that warm. I'm pretty unhappy with my solution, which is just Dijkstra with a ballooned out "visited" map so that I can keep track of the multiple paths. I'll have to think about whether there's a more efficient way to store the paths. EDIT: Thought of a more efficient way to store the paths. Not efficient, mind you, just more efficient. Total time now 120ms cold, 27ms warmed up.
e
Day16.kt probably could optimize but I'm still catching up
o
BFS with Priority Queue, not exactly Djikstra but works fast enough
Copy code
import common.Direction
import utils.Point
import java.io.File
import java.util.PriorityQueue

fun main() {
    val input =
        File("input.txt").readText().split("\n")
    val points = input.mapIndexed { x, s ->
        s.mapIndexed { y, c ->
            Point(x, y)
        }
    }
    val start = points.flatten().single { input[it.x][it.y] == 'S' }
    val queue = PriorityQueue<State>()
    val directionMap = mutableMapOf(
        Direction.Right to listOf(
            Point(0, 1),
            Point(-1, 0),
            Point(1, 0)
        ), Direction.Up to listOf(
            Point(-1, 0),
            Point(0, 1),
            Point(0, -1)
        ), Direction.Left to listOf(
            Point(0, -1),
            Point(-1, 0),
            Point(1, 0)
        ), Direction.Down to listOf(
            Point(1, 0),
            Point(0, 1),
            Point(0, -1)
        )
    )

    val visited = mutableSetOf<Pair<Point, Direction>>()
    val result = mutableSetOf<Pair<Point, Direction>>()
    queue.offer(State(start, Direction.Right, 0, 0).apply {
        this.points.add(start to Direction.Right)
    })
    visited.add(start to Direction.Right)
    while (queue.isNotEmpty()) {
        val top = queue.poll()
        visited.add(top.point to top.direction)

        if (input[top.point.x][top.point.y] == 'E') {
                println(top.score())
                result.addAll(top.points)
        } else {
            directionMap[top.direction]!!.map {
                top.point.copy(x = top.point.x + it.x, y = top.point.y + it.y) to getNewDirection(it)
            }.filter {
                it.first.x in points.indices && it.first.y in points.first().indices && input[it.first.x][it.first.y] != '#'
            }.forEach {
                val state = State(
                    it.first,
                    it.second,
                    top.steps + 1,
                    if (it.second == top.direction) top.turns else top.turns + 1,
                ).apply {
                    this.points.addAll(top.points + (it.first to it.second))
                }
                if (!visited.contains(it.first to it.second)) {
                    queue.offer(
                        state
                    )
                }
            }
        }
    }
    println(result.map { it.first }.toSet().size)
}


fun getNewDirection(point: Point): Direction {
    return when {
        point.x == 1 -> Direction.Down
        point.x == -1 -> Direction.Up
        point.y == 1 -> Direction.Right
        point.y == -1 -> Direction.Left
        else -> error("")
    }
}

private data class State(val point: Point, val direction: Direction, val steps: Int, val turns: Int) :
    Comparable<State> {
    fun score() = this.turns * 1000 + this.steps
    override fun compareTo(other: State) =
        (this.score()).compareTo(other.score())

    val points = mutableSetOf<Pair<Point, Direction>>()
}
k
I am still confused what to store where šŸ™‚ but got my solution to run around 2ms on expensive one posted here https://github.com/bukajsytlos/aoc-kotlin/blob/master/2024/src/main/kotlin/Day16.kt
49 Views
Open in Slack
PreviousNext
Powered by