https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 20> (spoilers) :thread:
# advent-of-code
a
m
That was a fun one! For part 2 (and now also part1) I'm looking for path nodes with a manhattan distance <= allowed cheat distance. Saved distance then is the difference in the original path distances of the selected nodes minus manhattan distance between these nodes. Day20.kt Performance is not yet great (several seconds for both parts)
m
• generate path from start to end • for each point on path, take all points on the path that are within the cheat time manhatten distance • calculate cheated cost to that point • count all who save at least 100
Day 20 Michael
a
A simple but effective optimization: For point 
[i, j]
, only check 
[max(0, i - cheatTime)..min(sizeX - 1, i + cheatTime), max(0, j - cheatTime)..min(sizeY - 1, j + cheatTime)]
.
b
this one hurt
my solution was pretty dumb, almost brute force
p
My solution is to flood the puzzle with the distance from the start, flood the puzzle with the distance from the end and for each tile look if possible jumps would save the required amount of picoseconds. (~250ms for part 2 cold start) Errors I've made on the way: • counted just the best jump from one possition instead of all possible jumps • forget to count in the cost of the jump itself https://github.com/glubo/adventofcode/blob/main/src/main/kotlin/cz/glubo/adventofcode/y2024/day20/Day20.kt
k
Spent a lot of time debugging my part 1 as I had a wrong understanding of what distinct start and end positions of the cheat meant. This came back to hunt me again in part 2. I ended up using a double flood fill for part 2, which I have now tidied up and used for part 1 as well. Solution
Runtime:
Copy code
Part 1: ~4ms. Part 2: ~83ms
d
OMG I had a very dumb off by 1 error that had me convinced I had a different logic error
I was computing cheat 21 instead of 20
same 1
So then I zoomed in on “If cheat mode is active when the end position is reached, cheat mode ends automatically”, thinking about the case where you cheat in a straight line through the end and past it — that that case should be omitted (e.g. S = (0, 0), E = (19, 0), Cheat point = (20, 0) — there’s no path to the cheat point that does not go through the end)
It’s not required to handle that
Anyway I used Dijkstra to compute the cost map, then did the manhattan distance thing on the cost map. I used the cost map for part 1 as well but a different strategy to generate the candidate points.
💯 1
I don’t want to spend any more time on this so here’s my code
and the off by one error worked on the test input because the input size is small… so the savings for 21 steps and 20 steps is exactly the same
j
I thought you could only move through walls during cheating, and that the cheat ended when you were on normal track. So I tried to find a path through the walls. Cost me a lot of time to build a complicated program, and then figuring out why it gave a different answer for the test problem.
d
oh yeah i started down that road as well
m
Me too but luckily I noticed quite quickly that the cheat in the second example crossed the path
👀 1
d
The very first thing I did was the simple thing, but off by 1 cost me a couple hours
w
I misunderstood what “at the end of the cheat” meant. I thought two picoseconds would mean two steps on ‘#’ point were allowed after which you had to end up on a valid point in the 3rd second basically. Found out with the example that I was misinterpreting.
d
Yes I had that problem in part 1 also
The description is not very precise
j
I had at first an algorithm that computed the correct answer for the real input, but the example was wrong it computed 2 cheats fewer, than was expected, took me hours and a pause to solve
j
Creating two dictionaries first: for each point the distance to start and to end. (Also precalculating the "diamond" of points reachable by a cheat , that isn't really big improvement, but makes the solution cleaner imo). Then it's just simple sum of counts.
JakubG.kt.pas
h
🤦‍♂️ 🤦‍♂️ (because a single face palm isn't enough)... I've just spent the better part of 2.5 hours trying to work out why my perfectly logical Part 2 algorithm (for each point on the path, find other points on the path with Manhatten distance <= 20, calculate the savings etc), was returning very low counts compared to the samples And then I found it...
Copy code
val longShortcuts = mutableSetOf<Point>()
🤦‍♂️🤦‍♂️
p
Another fine day - gather the route, then find pairs within "cheat" distance that are forward in the route by more than the distance (by indices).
Day20.kt
e
slowest part is finding all pairs of points within manhattan on the path, which I'm slightly speeding up by keeping them all in lexicographical sorted order, but that still feels like it should be faster with a proper k-d tree or something
also had a fun off-by-one where I forgot to add the E to the path, so everything was correct except the final shortcut in the example
j
If I understand your approach, for each position you’re testing all other nodes to see if they are within cheat range?
e
not quite all: starting from (y1, x1), I'm testing all points on the path between (y1, x1 + 1) up to (y1 + cheats, x1) where the points are sorted by y then x
that will include some points like (y1 + 1, 0) which are definitely out of range, but still skips a good number of them. I want to be able to skip more though
d
I ended up checking all coordinates in range to see if they are on the path -- I think you check fewer nodes (800 each time) that way given the path length (around 7500 IIRC)
But I don't actually store the path per se, I have the standard Map<Point, Int> of cost to end from Dijkstra
j
I found it way faster to test only a diamond od 20 manhattan max
same 1
d
Yes exactly
e
maybe it doesn't help for much for Kotlin but it did speed up some of my other language solutions, because even if it's more points, it's contiguous memory
j
Yeah that way i was able to get to c.a. 1/8 seconds
e
https://github.com/ephemient/aoc2024/actions/runs/12434913212/job/34719739782#step:6:846
Copy code
Day20Bench.part1  avgt    5    13019.992 ±    258.033  us/op
Day20Bench.part2  avgt    5   106876.438 ±    811.870  us/op
Day20Bench.solve  avgt    5   117218.934 ±   2002.563  us/op
roughly 100ms on shared runners
d
I tried it with and without the map of point to index, without turns out to be faster for me
422.864375ms vs 295.158750ms
Alright ended up with
p
I didn't bother with a map to distance, as the index of the point in the path list is the picoseconds into the route - find the two indices and subtract to get the improvement (and add in the cost of the shortcut)
Copy code
Warming up 1 puzzles over 10s for year 2024 day 20...
Warmup finished after 10.020018375s with 115 iterations
year 2024 day 20 part 1
	 Default took 41.456125ms 👑: 1426
year 2024 day 20 part 2
	 Default took 43.142458ms 👑: 1000697
I'd be interested in how much different inputs impact the solve duration
you can also optimize the initial route discovery as it's a single-track route without any branches - you're either moving in the same direction or you're turning left or right - saves on checking all the neighbours and filtering out backtracking
w
@ephemient There is a way to only process the candidates: • index the nodes by y: O(1) lookup • for each y store the sorted nodes by x corresponding with that y coordinate • while traversing the coordinates ensure the sum of x + y remains smaller than the max cheat length you should only be traversing the actual candidate nodes that way. It requires a binary search to locate the current coordinate by x in the sorted x array. I’m not sure if this makes sense, but for reference here is my implementation: https://github.com/werner77/AdventOfCode/blob/master/src/main/kotlin/com/behindmedia/adventofcode/year2024/day20/Day20.kt
I only use arrays, little bit over-optimized
e
I was considering doing a morton encoding to flatten the representation while retaining some locality
might have to implement both to evaluate the difference
but that'll take more brainpower than I have to spare right now, so maybe some other day blob sweat smile
m
Parallelized solution using a kd-tree: Day20Kd.kt
Copy code
Part 1 median:     2.303 ms  (2174 benchmark iterations)
Part 2 median:     7.595 ms  (647 benchmark iterations)
🙌 1
And on a machine with more cores:
Copy code
Part 1 median:     2,032 ms  (2460 benchmark iterations)
Part 2 median:     3,768 ms  (1328 benchmark iterations)
n
That was fun until it wasn't, then it was fun again. As usual with these hard problems, I'm so much better at figuring out what's wrong when I'm out walking the dog or taking a shower or trying to sleep. I'll leave the fast solutions to you guys. I'm going to have to be content with 250ms until at least after Christmas break. Off to Mexico! Feliz Navidad!
Actually, I lied. I had put in some optimizations but had forgotten to take out the slow stuff it was supposed to replace. Now I have a conundrum. Single-threaded, it's 90ms cold and 30ms warmed up. Multi-threaded, it's 190ms cold and 7ms warmed up. Which should I keep? Also weirdly, each core maxes out at 66% usage. Could it be that the individual unit of work is so small that it gets bogged down with scheduling and can't put the core to full use?
44 Views
Open in Slack
PreviousNext
Powered by