DEV Community

Cover image for Air Duct Spelunking
Robert Mion
Robert Mion

Posted on

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:
My maze

These are the locations of the numbers 0-7:
Numbers highlighted

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

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

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Then, I saw it: 3 to 6!

How did I miss it before?
Path from 3 to 6

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
Enter fullscreen mode Exit fullscreen mode

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

My shortest path, not the shortest path

Animation of the shortest path I could find

As a map:
Shortest path

Pulling my hair out to find a shorter path

I tried re-counting the path - same number:
Tracing my steps

I tried the only other viable path - higher number:
Trying an alternative

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.

Top comments (0)