Donut Maze
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-05-20 18:23:08

## [Advent of Code 2019 Day 20](https://adventofcode.com/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.