Air Duct Spelunking
Tags: adventofcode, algorithms, programming, computerscience
Published: 2022-08-14 01:34:18

## [Advent of Code 2016 Day 24](https://adventofcode.com/2016/day/24)

## Part 1
1. This seems familiar...
2. It may be doable visually!
3. Uncovering shorter and shorter paths
4. Counting the steps
5. Guessing...again and again
6. My shortest path, not *the* shortest path
7. Pulling my hair out to find a shorter path

### This seems familiar...
...to [2019 Day 18: Many-Worlds Interpretation](https://adventofcode.com/2019/day/18):
- Designated starting spot: `0` here instead of `@` there
- An elaborate maze
- Markers to pass through or collect
- In search of the shortest path from start to collecting or passing through all markers

### It may be doable visually!
- Many-Worlds featured dozens of keys and doors in a large square maze
- The number of possible routes seemed endless
- Here, however, there are only seven markers
- And the maze is relatively smaller - though no less elaborate

It is definitely worth my time analyzing the maze and attempting to identify some shortest paths between a few of the numbers `0-7`.

### Uncovering shorter and shorter paths
This is my puzzle input:
![My maze](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yzrtrb2rxj7uw1o60nx3.jpg)

These are the locations of the numbers `0-7`:
![Numbers highlighted](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3jn2nadjgt4oul38nl47.jpg)

After a few hours of careful navigation, these are the shortest paths I found:
![A few paths between numbers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qwn0bwsdbloeibd3hvvd.jpg)

Before attempting to count each step between numbers, these are the paths that seem viable:
- 01376542
- 01352467
- 01732456
- 01765423

### Counting the steps
- I've done it before
- It's not fun
- But it's all I can do

At least it makes for a cool GIF:
![A few short paths](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r6i2mzjqpzu80j8nvg6h.gif)

### Guessing...again and again
My initial tallies:
```
0:1 22
1:3 64
1:7 54
7:3 79
5:6 20
4:5 80
2:4 32
```

I decided to try the most promising path first:
```
01732456

0:1 22
1:7 54
7:3 79
3:2 216
2:4 32
4:5 80
5:6 20
-------
    503: too high
```

Thankfully, the website told me `too high`.

Sadly, I wasted a guess hoping for dumb luck:
- I submitted 500, seeing if I was one off
- Still too high

Even worse, I wasted another guess!
- I submitted 495
- Still too high

Time to try another path:
```
01765423

0:1 22
1:7 54
7:6 198
6:5 20
5:4 80
4:2 32
2:3 216
-------
    over 503, yikes
```

Then, I saw it: `3` to `6`!

How did I miss it before?
![Path from 3 to 6](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lx706elm6w4yr46ovecz.jpg)

I have no idea if this is the shortest path, but it's definitely an optimization:
```
01736542

0:1 22
1:7 54
7:3 79
3:6 147
6:5 20
5:4 80
4:2 32
-------
    434: wrong
```

Bummer.

Even worse, I submitted too many guesses to get the direction I should be headed.

I must assume that there's a shorter path.

First, I'll try to find one between 3 and 6.

I tried. Couldn't find any that are shorter.
![Exploring alternative paths](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rd0ymve57f5wrqqxg980.jpg)

### My shortest path, not *the* shortest path
![Animation of the shortest path I could find](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bg2og27onbjq2blzzxnr.gif)

As a map:
![Shortest path](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ov1hmth42yhe4gnydlpc.jpg)

### Pulling my hair out to find a shorter path
I tried re-counting the path - same number:
![Tracing my steps](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/crbxkwvg1u8orzvolrao.jpg)

I tried the only other viable path - higher number:
![Trying an alternative](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i17zj2ipfn1q501o1rfx.jpg)

No matter what I found, nothing beat my shortest path.

Grrr.

## An admirable attempt
- I tried to solve this puzzle visually
- After hours of hunting, I couldn't find the shortest path

To anyone reading this:
- What am I not seeing?

Anyway, time to move on.