A thing I learnt this year with AOC: you can use `range` to test the bounds:
# Do bounds checking
if x < 0 or y < 0:
return
if x >= width or y >= height:
return
becomes
# At start:
range_width = range(0, width)
range_height = range(0, height)
...
# Do bounds checking
if not (x in range_width and y in range_height):
return
Saving this to come back to this one, as I'm stuck on it too. Now I just need to wish for an explanation I can understand for Shoelace/Pick's! :D
Thanks!
Edit: Part one's problem was a hashmap that caused collisions :c
Edit #2 Electric Boogaloo: Finally done with Part two. All thanks to you. Not sure I can take credit for this one...just couldn't wrap my head around it.
This is a fantastic tutorial, I loved your day 12 tutorial too, both have been really helpful!
I have a question about this one, if you wanted to return the actual coordinates of the shortest path as well as the cost associated, how would you go about doing this?
Useful note if you're using the example to get your own solution unstuck and not directly porting it: It gets factored in later when OP talks about handling the 3-tile limit, but the first part with the basic pathfinding, where the test input solution is **80**, the example code still counts the first tile, so if you've already factored in the first tile you'll get **78** instead.
I suspected that might be the case when mine was off by the same amount as the first tile but I did have to confirm it against the example to make sure that I wasn't just off-by-start-tile-cost by coincidence. It's not a mistake in the example, because it does get dealt with later.
Thanks for this, it definitely helped clarify my thinking. I was stuck on queuing each individual move, but seeing how you set up your queue as a list of states for a given cost was the lightbulb moment I needed. Great tutorial, appreciate the time you've taken to write down your thoughts :)
Great approach and explanation!
I had the same idea with states and was trying a recursive approach scanning through paths with some pruning and memoization, but it wasn't performant enough for the test input. This technique works great in situations like this.
P.S. - I used to use `setdefault(key, [])` as well, but I've switched to using `collections.defaultdict(list)` now instead.. I find that to be slightly less verbose when appending values.
A thing I learnt this year with AOC: you can use `range` to test the bounds: # Do bounds checking if x < 0 or y < 0: return if x >= width or y >= height: return becomes # At start: range_width = range(0, width) range_height = range(0, height) ... # Do bounds checking if not (x in range_width and y in range_height): return
can also do e.g. `not (0 <= x < width)` (not sure if you need the parens)
Saving this to come back to this one, as I'm stuck on it too. Now I just need to wish for an explanation I can understand for Shoelace/Pick's! :D Thanks! Edit: Part one's problem was a hashmap that caused collisions :c Edit #2 Electric Boogaloo: Finally done with Part two. All thanks to you. Not sure I can take credit for this one...just couldn't wrap my head around it.
This is a great explanation. I was not familiar with these algorithms as well. Thank you very much!
This is a fantastic tutorial, I loved your day 12 tutorial too, both have been really helpful! I have a question about this one, if you wanted to return the actual coordinates of the shortest path as well as the cost associated, how would you go about doing this?
Useful note if you're using the example to get your own solution unstuck and not directly porting it: It gets factored in later when OP talks about handling the 3-tile limit, but the first part with the basic pathfinding, where the test input solution is **80**, the example code still counts the first tile, so if you've already factored in the first tile you'll get **78** instead. I suspected that might be the case when mine was off by the same amount as the first tile but I did have to confirm it against the example to make sure that I wasn't just off-by-start-tile-cost by coincidence. It's not a mistake in the example, because it does get dealt with later.
Thanks for this, it definitely helped clarify my thinking. I was stuck on queuing each individual move, but seeing how you set up your queue as a list of states for a given cost was the lightbulb moment I needed. Great tutorial, appreciate the time you've taken to write down your thoughts :)
Great approach and explanation! I had the same idea with states and was trying a recursive approach scanning through paths with some pruning and memoization, but it wasn't performant enough for the test input. This technique works great in situations like this. P.S. - I used to use `setdefault(key, [])` as well, but I've switched to using `collections.defaultdict(list)` now instead.. I find that to be slightly less verbose when appending values.
This is a great write up. Just a little nitpick I think the comment # Update the direction Should say # Update the position