3 ms·
Off topic, but tangentially related: I was trying to use a modified Dijkstra / A* algorithm for this year’s Advent of Code Day 17 problem: https://adventofcod
by criddell 3y ago
Off topic, but tangentially related:
I was trying to use a modified Dijkstra / A* algorithm for this year’s Advent of Code Day 17 problem:
https://adventofcode.com/2023/day/17 https://adventofcode.com/2023/day/17
I never got the right answer though because there was some issue with the way I was tracking visited nodes. I was trying to use north, south, west, east rather than row and column direction values like other solutions I read, but I’m stubborn and it seems to me I should be able to get it work storing cell (as a (row, column) tuple)), direction, and distance travelled (1-3).
If you did this day, how did you do it?
- Cogito 3y agoMy search nodes were tuples of position, direction, and steps taken in the same direction. More or less a straight depth first search with a priority queue from there.
- criddell 3y agoHow were you storing direction? Was it a symbol for one of NORTH, EAST, SOUTH, WEST, or a symbol for one of FORWARD, LEFT, RIGHT, or a pair of values for row direction and column direction (i.e. +1, 0 or -1, 0 or 0, +1, or 0, -1)?
- Cogito 3y agoA tuple vector with row and column offset, your third option here, which happen to have symbol names of N, S, E, and W.
- criddell 3y agoThanks for replying. Maybe I just have a dumb bug in my logic and should take another crack at it.
- Cogito 3y agoI know I had issues keeping track of how many steps I’d taken, but making sure I was generating a good set of neighbours helped with that. Otherwise it was just making sure I got the rules right, like all AoC problems, and testing different cases to make sure my solution did the right thing.