#2023 AoC Day 17
karmic dirge
pure copper
NOW it's pathfinding
last obsidian
Here we go
pure copper
which might well mean this one ends up on my backburner but oh well
pathfinding has historically been my ruin
yeah i'm not feeling it today, not even coding, straight to backburner
barren anvil
81/35
tawny lichen
I believe I have a solution for part 2, but it's currently grinding away...
105/95, which is a lot better than I deserved
barren anvil
nice
I honestly have no idea how people were doing this that the part 2 board took 6 minutes more than the part 1 board to fill up - it was a pretty trivial change for me
tawny lichen
I honestly have no idea how people were doing this that the part 2 board took 6 ...
||My solution for part A was Dijkstra's, where the "location" for each node included what direction you just came from, and how many steps you'd taken to get there... so in theory there could be as many as 12 copies of each location in the grid. For part B I thought that might be too much, and changed it so the "location" was just its location and what direction you came from, and now the "neighbours" of a given cell are all the cells between 4 and 10 steps away. Which is very similar, and wasn't a big change, but still not trivial.||
Runtimes were ||42s for part 1 using the first strategy, but dropping to 8s for part 1 using the second strategy, and 30s for part 2||
last obsidian
I salute those who know what the heck they are doing! 🫡
barren anvil
||My solution for part A was Dijkstra's, where the "location" for each node incl...
my part 2 code ||uses the former strategy and runs in about 5 seconds (timing by eye)||
curious what your impl looks like since my python code is not exactly optimized for speed
tranquil arrow
I know I'm sure as heck not gonna be able to do this before I need to leave for work, so not even gonna attempt it. Will be my first time doing a thing like this, and to have to incorporate extra route constraints means I'll need to have a good think about it (and probably still make a pretty suboptimal solution)
tawny lichen
yeah, it's not the ideal implementation
barren anvil
conveniently I "wrote" an implementation of ||a pqueue|| earlier today, so I had it handy
but yeah I can imagine if you have to do it that way it'd cause problems
honestly I think the techincally correct thing to do here is to just ||put them in a structure where you can look them up by weight (a dict or just an arraylist of some sort) and then just loop through possible weights||
normal patrol
Sweet, I got three-digit ranks for both parts this time
barren anvil
nice
normal patrol
target/release/d17p2 0.39s user 0.01s system 99% cpu 0.401 total -- not too bad for my only implementation of part 2
(||adapted only lightly from part 1||)
(marvel at how much structure code I wrote :P)
It turns out for these puzzles that ||std::collections::BinaryHeap is my friend (particularly combined with std::cmp::Reverse)||
also: hey, ||finally found the pathfinding puzzle||
normal patrol
||My solution for part A was Dijkstra's, where the "location" for each node incl...
oh. ||I did Dijkstra's for part 1 and just kept my whole Dijkstra's implementation for part 2, and changed the direction distance threshold||
karmic dirge
I || got to use my generic AStar class, main bit of code to write is the function to plug in for calculating moves and their costs. Part 2 runs a bit slower than I'ld like (10 seconds), not sure if that is because the heuristic function is bad or something else ||
barren anvil
curious ||what heuristic you used||
karmic dirge
just || grid distance/manhattan distance ||
barren anvil
I feel like ||that's not gonna do much better than plain dijkstra||
if you ||replace the heuristic with a function that always outputs 0||, how much does that change the runtime?
karmic dirge
It gets faster 🙂
barren anvil
that's not a great sign
karmic dirge
I got the time down by || reworking my node representation to only last direction + position (dropping consecutive moves), and changing move generation to add all valid moves in a direction together. Down to a little under 2 seconds for both parts together. ||
vernal garnet
last obsidian
I should come up with a way (if I'm going to keep using R) of converting that matrix into a graph properly... it keeps coming up!
vestal surge
|| Considering the path as a series of moves with each one having n..m steps in the same direction makes things much nicer... it means the shortest paths for direction stuff resolves to just two cases (either the next move is horizontal, or it's vertical). I did a very straightforward array based shortest path implementation, which fits this idea of moves nicely because the consecutive neighbours you're updating as part of a move are adjacent indexes and you can accumulate the heat value as you go. ||
vernal garnet
One thing that tripped me up on part two was ||the 4+ minumum also applying at the end (apparently I don't read parenthesizes text)||
floral skiff
one thing I wasn't clear on is if at the start ||you need to move 4 spaces right, or if you can start with a turn downwards||
As it turns out ||allowing a downwards turn got me the right answer, but I don't know if it was required for a right answer||
pure flicker
I predicted (almost correctly) that for part 2, it would be || increasing the maximum number of 'same-direction' steps, so I just had to adjust the next 'state' generation in dijkstra's to get the same result. Only thing that tripped me up was messing up the custom comparator for Java's PriorityQueue (stubbornly refused to use negative distance as the 'priority')||
lofty rampart
Now today is the path finding problem. Nice surprise to wake up to.
Well...nice eventuality, anyway.
vernal garnet
Heh, ||replacing the priority queue in my solution with a simple set just changed my runtime for part 2 from 10 seconds to six and a half minutes.||
regal dune
Thoroughly stucc today. Cannot even get an algorithm that halts on the example input. I tried implementing a heuristic search but it has no end case so it literally runs forever. But even so, after many iterations it cannot find the optimal answer. So I'm going to stop trying to be smart and just do DFS for part 1 I think. Throw my solution away and start again. Then I will be bussed for part 2 likely.
Search has always been a blind spot for me. The "at most three" rule is stopping me from doing any optimization I can think of.
I am considering cheating (looking at spoiler text) for this one if I can't even do part 1.
regal dune
Today's new-thing-I-hate-about-Python is that trying to append a tuple to a list tuple requires this weird-ass (x,) syntax.
velvet whale
ok, I finished it, with breaks. I am not proud of the code, but ||a*|| at least performed pretty well, ~1.5s for p1, 3s for p2, not going to bother improving this, or looking at it again anytime soon
regal dune
DFS isn't working the example for part 1, either. At least it finds the optimal value if I give it the right priorities to choose starting directions well, but it's not halted after 200 million iterations.
I could use ||A* || if I had some way of knowing whether I've visited a node optimally yet or not. Hm. Maybe I need to change the way I'm looking for loops to be less dumb.
normal patrol
one thing I wasn't clear on is if at the start ||you need to move 4 spaces right...
I ||forgot to put the start-in-any-direction exception in my part 2||, it looks like, and it got the right answer just fine.
Granted, that just means that ||my solution's optimal path starts going to the right||, but maybe the data point is helpful
barren anvil
Today's new-thing-I-hate-about-Python is that trying to append a tuple to a list...
what the heck does "append a tuple to a list tuple" mean
regal dune
That should be "tuple OF tuples", I think.
I wanted to take a tuple of tuples like ((a,b), (c,d)) and add (e,f) to the end of it. The syntax for doing this with + is atrocious.
tupleOfTuples + (newTuple,)
barren anvil
...honestly I didn't know you could add tuples like that
if you frequently need to append to it, why is the outer structure a tuple and not a list?
regal dune
I'm using it as a hash key, probably sillily.
Assume I'm doing everything wrong.
For example, trying to implement ||A* || from memory when I should have just looked it up, like I'm doing now.
wooden ore
ok, so a spoiler bar that short in the context of pathfinding isn't hiding much, just fyi
barren anvil
honestly I think that ||A* || is overrated
regal dune
Well I don't know how to solve this problem at all! Gotta try something.
barren anvil
fair
what I mean is that ||A* is just dijkstra with a heuristic added - but I've never actually encountered a situation where A* is satisfactorially fast but standard dijkstra isn't||
regal dune
Well, I think I have to because ||A* || didn't work. Gives the right answer for the example, at least, but the wrong answer for the real input for part 1. ||Disjkstra time|| At least that one I don't need to look up.
Wait, did I remember to implement the constraints?
vernal garnet
One of my long-time AoC opinions is that ||anyone using A* could just use Dijkstra|| and that ||half the time people using Dijkstra could just use BFS||.
normal patrol
what I mean is that ||A* is just dijkstra with a heuristic added - but I've neve...
yeah, ||I used Dijkstra this time and saw no reason to add a heuristic to it||
normal patrol
One of my long-time AoC opinions is that ||anyone using A* could just use Dijkst...
That's technically true, though ||Dijkstra helps quite a bit with managing different weights (in this case, different locations having different heat losses) -- with BFS you'd still need to run all of them for the min|| -- but it's true that ||without different weights, Dijkstra is basically just sparkling BFS||
vernal garnet
That's technically true, though ||Dijkstra helps quite a bit with managing diffe...
Oh, for today it's totally the right call. No contest. What I meant was, there were times in previous years where I've seen a group of people all talk about ||implementing Dijkstra or A* to solve some day|| where I was just thinking to myself ||"am I crazy? all these edges have the same weight."||. That's not to dump on anyone who does that, it's just something I noticed that in this particular area ||a lot more people than I'd expect tend to make things unnecessarily harder on themselves||
normal patrol
ah, yeah, makes sense
vernal garnet
(or literally everyone except me already has these implemented in their big bag of tricks, in which case do whatever you want 😄)
normal patrol
it's ||BFS with more steps|| at that point
normal patrol
(or literally everyone except me already has these implemented in their big bag ...
A ||priority queue|| gets you most of the way there, and that's in at least some standard libraries (in my case, ||std::collections::BinaryHeap, since I'm using Rust||) (though I still probably ||wouldn't reach for it if I didn't have to||)
vernal garnet
Oh, that reminds me of a thing I wanted to ask. For people who ||use a priority queue from a library||, does it support the ||decrease|| operation? And if not, how do you add it?
normal patrol
like, ||modifying a PQ key in-place||?
vernal garnet
exactly
regal dune
Part 2 seems to be specifically made to mess with my implementation for part 1... Damn it. At least I finally got part 1, ~3 hours in.
Time for a break.
last obsidian
Classic!
normal patrol
||In Rust, it's kinda not really a thing due to rules about mutability -- though it looks like it does expose a mutable reference of just the highest element through peek_mut , which would rebalance the tree somehow||
regal dune
Probably 12 nested loops is not a good strategy...
vernal garnet
You know what they say, if it's stupid but it works...
normal patrol
I wouldn't've
but, of course, in AoC it's about getting the right number, regardless of how you got there
wooden ore
about getting the right number one time for one input
last obsidian
Okay, full disclosure, I used other people's code, so feel free to disregard my score on the leaderboard. I found Python code and R code... and R gave me the wrong answer! Also, R does do queues and such, huzzah! ...no idea how to use them, but it does have them...
silk raft
I miss easy puzzles for dum-dums...
Don't the elves want to see me code a program to say "hello world"?
last obsidian
That would be something, "write hello world programs in increasingly weird languages each day"
silk raft
Watch as I use my awesome mental powers to add one number to another number! Creating a brand new number that is completely different from the two!
lofty rampart
My part 2 solution was quite slow, took a few minutes to execute.
Might come back to this one and optimize later for funsies
last obsidian
what's next after pathfinding? I would think grouping to get the right gears together, but that feels too easy...
lofty rampart
Maybe a pathfinding + "fix the smudge" situation? I feel like at this point in the year things start to build on each other
(Programming concept wise, that is)
regal dune
OK, I found a way to model the directional part of this thing without a 12-nested loop. Part 2 solved.
I implemented 4 different algorithms, either from memory or from Wikipedia, each with bugs that I don't know what they are. Ultimately it was a modified ||Dijkstra's big ol' algorithm|| that worked for me. I see how I can do even better now as well, but I've sunk way too much time into this today. 5s runtime isn't bad. I would not have expected it to be that fast for this large an input set.
vestal surge
|| Actually the real win performance wise with the array-like approach is just keeping the shortest path values in array like storage; even vanilla dijkstra's with stl priority_queue gets down into the same 20ms territory with the shortest path values in a vector<vector<vector<int>>>
What that looks like: https://gist.github.com/rakslice/32fe951fed89e3c0112e16bfde9b28ca#file-day17-cc-L59 ||
pure flicker
I feel like days like these are really just || knowledge gates; you either know dijkstra exists and just do one or two small modifications and get both stars relatively quick, or you just are stuck || like in previous years, where if you see some mention of some large modulo || it's probably some combinatorial problem with DP / CRT ||
floral skiff
||In Rust, it's kinda not really a thing due to rules about mutability -- though...
Thanks to interior mutability this is an issue for any key, the ||BinaryHeap|| docs have this disclaimer:
||It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the heap. This is normally only possible through interior mutability, global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified, but will be encapsulated to the BinaryHeap that observed the logic error and not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.||
which IIUC is similar to a lot of other "safe" rust behaviour that needs to uphold invariants, like Hash
"we guarentee an incorrect or even malicious implementation (as long as it's Safe) won't cause undefined behaviour; all other bets are off"