10
votes

# Day 17: Clumsy Crucible

## Today's problem description: https://adventofcode.com/2023/day/17

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python`

with any of the "short names" listed in this page of supported languages):

```
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
```

A pathfinding puzzle! My wish from yesterday was granted! :D

## Algorithm

This is a very straightforward application of pathfinding (Dijkstra, A*, etc.), but the state transition function was a little more complicated than usual for grid pathfinding.

I wanted to experiment with a search algorithm called

Anytime Focal Search(PDF), which doesn't really improve over plain A* a lot here, but there was no way of knowing that without trying it. (Edit: I just realized that the version of AFS I implemented is exactly equivalent to A* here, because I don't have a more sophisticated heuristic than the manhattan distance).Anytime Focal Search is good when there are many paths of similar cost, or when you need an answer quickly, even if it is sub-optimal. Giving the algorithm more time to run then successively improves the path found, until it is optimal.

I'm also using a RadixHeap, a monotone priority queue useful for pathfinding problems, because that's slightly faster than the BinaryHeap that comes with the standard library.

## Rust

## Performance

My solution was really slow at first, because I forgot to filter out duplicate states, but now it is reasonably fast:

I pair programmed this with a friend because we were both like "omg wtf." At first we tried to not use Dijkstra, and we actually had something that worked on the test input, but it was not a correct solution in general and also helplessly slow. Then we used Dijkstra pretty much the same way as the other comments here. He typed the code so eventually I want to come back and write my own version of the algorithm.

Golang solution

Ugh, this one took far too long given that I knew exactly how to solve it.

## Discussion

Pathfinding search problem -- I knew this wanted something like Dijkstra's algorithm. I wanted the data in a grid to manage the directional aspects of it, but the actual graph to search is the location in the grid + the state of how you go there.

Simple implementation got the tests in part 1, but was pretty slow for the full input. However, it finished before I could implement a priority queue to speed up. :)

Picking up part 2, the different rules just dictate a different case for how neighbors are found in the grid, so

I cased both into may algorithm. I was able to get the tests for part 2, but needed the priority queue implementation before I could get a solution for the whole input.

Partly I blame how long the PQ implementation took on the way the heap is implemented in go -- I needed to write a wrapper around it, and there were bugs in the integration of it in my algorithm.

In the end, it's pretty messy, but I have spent far too long on it already.

Forgot to post this last night. It could've been a lot faster if I'd used another algorithm like A*, but I was lazy and Djikstra was fast enough that I didn't think I needed to bother implementing anything else. I was glad to finally see this year's requisite pathfinding problem, though I thought it wasn't an especially interesting example of one.

## Solution