Passage Pathing

Advent of Code 2021 Day 12

Solve for X where

X = number of paths that visit small caves N times

1. N = 1
2. N = 2

Our input is

• A multi-line string

The input represents

• Pairs of connected nodes
• start, end and 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?

1. Parse the input into an object representing linked nodes
2. 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.

• NullDev
• Totto16
• Pandicon

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.