Robert Mion

Posted on

# Donut Maze

## 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.