Donut Maze

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

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

Example input

         A           
         A           
  #######.#########  
  #######.........#  
  #######.#######.#  
  #######.#######.#  
  #######.#######.#  
  #####  B    ###.#  
BC...##  C    ###.#  
  ##.##       ###.#  
  ##...DE  F  ###.#  
  #####    G  ###.#  
  #########.#####.#  
DE..#######...###.#  
  #.#########.###.#  
FG..#########.....#  
  ###########.#####  
             Z       
             Z       

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

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

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

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

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

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

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.