DEV Community

Cover image for Donut Maze
Robert Mion
Robert Mion

Posted on

Donut Maze

#adventofcode #algorithms #computerscience #programming

Advent of Code 2019 Day 20

Task: Solve for X where...

Part 1 

X = the number of steps it takes to get from the open tile marked AA to the open tile marked ZZ
Enter fullscreen mode Exit fullscreen mode

Part 2 

X = the number of steps it takes to get from the open tile marked AA to the open tile marked ZZ, both at the outermost layer
Enter fullscreen mode Exit fullscreen mode

Example input 

 A A #######.######### #######.........# #######.#######.# #######.#######.# #######.#######.# ##### B ###.# BC...## C ###.# ##.## ###.# ##...DE F ###.# ##### G ###.# #########.#####.# DE..#######...###.# #.#########.###.# FG..#########.....# ###########.##### Z Z
Enter fullscreen mode Exit fullscreen mode

It represents:

  • A donut-shaped maze
  • #s are walls
  • .s are open spaces
  • Capital letter pairs are either start (AA), end (ZZ), or portals
  • Portals transport you from the tile before entering the portal to the tile after exiting the other side

Part 1

  1. Another pathfinding puzzle...great.
  2. Shortest path? Or only path?
  3. Trying to connect the dots...err, portals
  4. Referring to the rules for one last spark of motivation

Another pathfinding puzzle...great.

  • The last one was just two days ago!
  • Much like regular expressions, I feel like I really need to study pathfinding algorithms so I can start feeling more confident attempting these types of puzzles

Shortest path? Or only path?

  • The first example has two paths from AA to ZZ, one being shorter
  • The second example has one path
  • The challenge question doesn't mention 'shortest' path
  • Am I led to believe that there is only one path from AA to ZZ?
  • Perhaps through careful study and process of elimination I can find out!

Trying to connect the dots...err, portals

After cautious manual, visual traversal, I identified this path from AA to ZZ:

AA LU OP VR MU MH NH TJ KJ NI DR QC ME HK KA QN RB KM ZZ
Enter fullscreen mode Exit fullscreen mode

Now it's time to count the dots

Trying to count the dots...between the right portals

Attempt 1

AA +9 LU +55 OP +47 VR +51 MU +49 MH +69 NH +75 TJ +56 KJ +49 NI +68 DR +49 QC +59 ME +53 HK +61 KA +61 QN +85 RB +69 KM +65 ZZ 1030 TOO HIGH
Enter fullscreen mode Exit fullscreen mode

Attempt 2
Shorter path identified

ZZ +5 XF +49 HU +65 QL +57 QH +63 QD +63 CA +87 AO +7 MH +49 MU +51 VR +47 OP +55 LU +9 AA 607 TOO HIGH
Enter fullscreen mode Exit fullscreen mode

Attempt 3
Even shorter path identified

ZZ +5 XF +49 HU +65 QL +57 QH +63 QD +63 CA +87 AO +57 XB +63 WY +39 WC +47 AA 595 TOO HIGH
Enter fullscreen mode Exit fullscreen mode

I see no shorter path than the one outlined in Attempt 3.

Maybe I miscounted one of the sub-paths?

I counted again, in reverse order

AA +47 WC +39 WY +63 XB +57 AO +87 CA +63 QD +63 QH +57 QL +65 HU +49 XF +5 ZZ 595 SAME
Enter fullscreen mode Exit fullscreen mode

Well, shucks.

Referring to the rules for one last spark of motivation

  • It seems that the dot immediately in front of a portal is not counted
  • But the move from portal to portal is counted
  • This may mean that I'm just off by 1: counting the dot immediately in front of AA when I shouldn't be

Attempt 4

 AA +46 +1 WC +38 +1 WY +62 +1 XB +56 +1 AO +86 +1 CA +62 +1 QD +62 +1 QH +56 +1 QL +64 +1 HU +48 +1 XF +4 ZZ 594
Enter fullscreen mode Exit fullscreen mode

That was correct!

Part 2

Yikes. Recursion. And pathfinding.

No thanks.

Celebrating my accomplishment

  • I solved Part 1...even after 4 failed attempts!

It helps to study the rules.

Otherwise, you may be off-by-one.

Top comments (0)