Passage Pathing
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-02-03 14:41:11

## [Advent of Code 2021 Day 12](https://adventofcode.com/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](https://github.com/NullDev/Advent-of-Code/)
- [Totto16](https://github.com/Totto16/AOC-2021)
- [Pandicon](https://github.com/Pandicon/Advent-of-Code/)

### 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 `A`s 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
['b']:
  //
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.