Advent of Code 2021 Day 12
Solve for X where
X = number of paths that visit small caves N times
- N = 1
- N = 2
Our input is
- A multi-line string
The input represents
- Pairs of connected nodes
-
start,endand several alphabetical character nodes in between
Ugh, pathfinding...again?!
- I dreaded returning to the beginner-unfriendly, text-heavy articles that describe Dijkstra's algorithm
- I also recalled those articles referencing multi-dimensional arrays, or grids, which this puzzle doesn't indicate requiring
How far could I get without help?
- Parse the input into an object representing linked nodes
- Create a pathfinding algorithm
Parse the input into an object
Split the multi-line string at each new line character into an array of strings
Split each string at each space-dash-space character into an array of two strings: start, end
Create an object
For each array in the parsed input array:
Create a key in the object for any non-existent start or end character combination
Initialize its value as a new set, or list of unique values
Add the end value to the list of values stored in the start key
Add the start value to the list of values stored in the end key
Sadly, that's as far as I got.
Finding other solvers' pathfinding algorithms
Interestingly, three of the JavaScript solvers that I referenced the most thus far wrote almost identical algorithms.
This is pseudocode of their recursive pathfinding algorithm
Sub-routine that accepts two parameters with smart defaults:
1. Start character combination, defaulting to 'start'
2. Set of unique values visited thus far, defaulting to an empty set
If the start character combination is 'end':
Return 1
Make a copy of the set of unique values visited thus far
If the start character is lowercase:
Update the copy to reference a new set of values containing those from the second argument, plus the start character
Set count to 0
For each value in the array associated with the key in the object that matches the start character:
If the value is not in the (amended?) copy of the set of unique values visited thus far:
Set count to the sum of count and the result of calling this sub-routine, passing as arguments:
1. the value in the current iteration of this loop
2. the (amended?) copy of the set of unique values visited thus far
Return the final value of count
All of that in just 6 lines, at least in NullDev's code? Crazy!
I needed to see it working to fully understand it
- I inserted a line within the base-case check to log the path thus far
Using the example nodes: start,A,b,c,d,end
What I saw:
start,c,b,end
start,c,b,end
start,c,end
start,b,c,end
start,b,end
start,b,end
start,end
start,b,c,end
start,b,end
start,b,end
What the example shows:
start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,end
start,A,c,A,b,A,end
start,A,c,A,b,end
start,A,c,A,end
start,A,end
start,b,A,c,A,end
start,b,A,end
start,b,end
Where did the As go? What's happening in this recursive function?!
It seems unavoidable:
- I had to walk the path myself
pathfinder()
1.
pathfinder("start", {})
seen = {}
seen = {'start'}
count = 0
['A', 'b']:
count += pathfinder('A', {'start'})
count += pathfinder('b', {'start'})
2.
pathfinder('A', {'start'})
seen = {'start'}
count = 0
['start', 'c', 'b', 'end']:
count += pathfinder('c', {'start'}) // R: 3
count += pathfinder('b', {'start'}) // Not explored here
count += pathfinder('end', {'start'}) // Not explored here
3.
pathfinder('c', {'start'})
seen = {'start'}
seen = {'start', 'c'}
count = 0
['A']:
count += pathfinder('A', {'start', 'c'}) // S: 3
return 3 to R
4.
pathfinder('A', {'start', 'c'})
seen = {'start', 'c'}
count = 0
['start', 'c', 'b', 'end']:
count += pathfinder('b', {'start', 'c'}) // T: 2
count += pathfinder('end', {'start', 'c'}) // U: 1
return 3 to S
5.
pathfinder('b', {'start', 'c'})
seen = {'start', 'c'}
seen = {'start', 'c', 'b'}
count = 0
['start', 'A', 'd', 'end']:
count += pathfinder('A', {'start', 'c', 'b'}) // V: 1
count += pathfinder('d', {'start', 'c', 'b'}) // W: 0
count += pathfinder('end', {'start', 'c', 'b'}) // X: 1
return 2 to T
6.
pathfinder('A', {'start', 'c', 'b'})
seen = {'start', 'c'}
count = 0
['start', 'c', 'b', 'end']:
count += pathfinder('end', {'start', 'c'})
return 1 to X
7.
pathfinder('end', {'start', 'c', 'b'})
return 1 to V
8.
pathfinder('d', {'start', 'c', 'b'})
seen = {'start', 'c', 'b'}
seen = {'start', 'c', 'b', 'd'}
count = 0
return 0 to W
9.
pathfinder('end', {'start', 'c', 'b'})
return 1 to X
10.
pathfinder('end', {'start', 'c'})
return 1 to U
What walking through the initial branch of the algorithm revealed to me
- The importance of the check for a node being in the path
- The fact that the traveled path technically includes Capital-letter pairs, but in order for the algorithm to work, capital-letter pairs must be removed from the path being traveled in order to arrive at the base case
Celebrating small accomplishments in this challenge
- I forgot about
toLowerCase()as a way to see if characters are upper- or lowercase. I started by seeing if an array full of capital letters included either of the capital letters in the pair. - I learned another scenario for recursion: a gradually accumulating unique set of values. I have the habit of seeing recursion as a path from large data to 1 datum.
- I almost fully re-created the algorithm that I studied from scratch without having to debug or refer to it
- After careful analysis, I feel 100% confident in my understanding of how the algorithm operates
I opted not to run the algorithm on my input to generate a correct answer for part 1 and see part 2.
Each of the above accomplishments were reward enough.
Top comments (0)