Air Duct Spelunking

Advent of Code 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:

• 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:

These are the locations of the numbers 0-7:

After a few hours of careful navigation, these are the shortest paths I found:

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:

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?

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.

My shortest path, not the shortest path

As a map:

Pulling my hair out to find a shorter path

I tried re-counting the path - same number:

I tried the only other viable path - higher number:

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.