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
- Another pathfinding puzzle...great.
- Shortest path? Or only path?
- Trying to connect the dots...err, portals
- 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.
Top comments (0)