[Advent of Code 2021] Day 12 | Passage Pathing

Part 1

With your submarine's subterranean subsystems subsisting suboptimally, the only way you're getting out of this cave anytime soon is by finding a path yourself. Not just a path - the only way to know if you've found the best path is to find all of them.

Fortunately, the sensors are still mostly working, and so you build a rough map of the remaining caves (your puzzle input). For example:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

This is a list of how all of the caves are connected. You start in the cave named start, and your destination is the cave named end. An entry like b-d means that cave b is connected to cave d - that is, you can move between them.

So, the above cave system looks roughly like this:

    start
    /   \
c--A-----b--d
    \   /
     end

Your goal is to find the number of distinct paths that start at start, end at end, and don't visit small caves more than once. There are two types of caves: big caves (written in uppercase, like A) and small caves (written in lowercase, like b). It would be a waste of time to visit any small cave more than once, but big caves are large enough that it might be worth visiting them multiple times. So, all paths you find should visit small caves at most once, and can visit big caves any number of times.

Given these rules, there are _10_ paths through this example cave system:

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

(Each line in the above list corresponds to a single path; the caves visited by that path are listed in the order they are visited and separated by commas.)

Note that in this cave system, cave d is never visited by any path: to do so, cave b would need to be visited twice (once on the way to cave d and a second time when returning from cave d), and since cave b is small, this is not allowed.

Here is a slightly larger example:

dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc

The 19 paths through it are as follows:

start,HN,dc,HN,end
start,HN,dc,HN,kj,HN,end
start,HN,dc,end
start,HN,dc,kj,HN,end
start,HN,end
start,HN,kj,HN,dc,HN,end
start,HN,kj,HN,dc,end
start,HN,kj,HN,end
start,HN,kj,dc,HN,end
start,HN,kj,dc,end
start,dc,HN,end
start,dc,HN,kj,HN,end
start,dc,end
start,dc,kj,HN,end
start,kj,HN,dc,HN,end
start,kj,HN,dc,end
start,kj,HN,end
start,kj,dc,HN,end
start,kj,dc,end

Finally, this even larger example has 226 paths through it:

fs-end
he-DX
fs-he
start-DX
pj-DX
end-zg
zg-sl
zg-pj
pj-he
RW-he
fs-DX
pj-RW
zg-RW
start-pj
he-WI
zg-he
pj-fs
start-RW

How many paths through this cave system are there that visit small caves at most once?

Proposed solution: since this is a graph with only the unique name of the nodes as attributes we can represent this as a dictionary of node names to a list of connections; then breadth-first search while using memoization to keep track of unique paths until running out of unique paths

Time complexity: O(E + V) where E is the number of edges and V is the number of vertices

Space complexity: O(N) where N is the number of unique valid paths from start to end

#!/usr/bin/env python3
from collections import defaultdict, deque
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

connections = defaultdict(list)
for line in file_input:
    first, second = line.split("-")
    connections[first].append(second)
    connections[second].append(first)

paths = set()
queue = deque()
queue.append("start")
while len(queue) != 0:
    check = queue.popleft()
    last_node = check.split(",")[-1]
    if last_node == "end":
        paths.add(check)
        continue
    for move in connections[last_node]:
        if "{},".format(move) not in check or move.isupper():
            queue.append("{},{}".format(check, move))

print("Total Unique Paths: {}".format(len(paths)))

Let's break this down. The first part is just taking each line and populating the graph being represented by a dictionary. Each key is an individual node's name e.g. "start", "dc", "end", etc. And the corresponding values are lists of connections to other nodes.

connections = defaultdict(list)
for line in file_input:
    first, second = line.split("-")
    connections[first].append(second)
    connections[second].append(first)

Next, make a data structure for the final unique paths (already visited) and a queue for unique paths being traversed. We can populate the queue beginning with start.

paths = set()
queue = deque()
queue.append("start")
while len(queue) != 0:
    check = queue.popleft()

For each working path in the queue, we are representing them by the string delimited by commas (exactly like they are represented in the description of the problem). If the last visited node is "end" then it's a valid path and we can add it to the unique paths. Otherwise, iterate through the possible connections to the last node. Valid moves for part 1 are those that are not already in the working path or the connection is back to a big cave (uppercase).

    last_node = check.split(",")[-1]
    if last_node == "end":
        paths.add(check)
        continue
    for move in connections[last_node]:
        if "{},".format(move) not in check or move.isupper():
            queue.append("{},{}".format(check, move))

Our final paths set contains all unique paths represented as comma-delimited strings.

❯ python3 solution12.py example
Total Unique Paths: 10
❯ python3 solution12.py example2
Total Unique Paths: 19
❯ python3 solution12.py example3
Total Unique Paths: 226
❯ python3 solution12.py input12
Total Unique Paths: 5104

Part 2

After reviewing the available paths, you realize you might have time to visit a single small cave twice. Specifically, big caves can be visited any number of times, a single small cave can be visited at most twice, and the remaining small caves can be visited at most once. However, the caves named start and end can only be visited exactly once each: once you leave the start cave, you may not return to it, and once you reach the end cave, the path must end immediately.

Now, the 36 possible paths through the first example above are:

start,A,b,A,b,A,c,A,end
start,A,b,A,b,A,end
start,A,b,A,b,end
start,A,b,A,c,A,b,A,end
start,A,b,A,c,A,b,end
start,A,b,A,c,A,c,A,end
start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,d,b,A,c,A,end
start,A,b,d,b,A,end
start,A,b,d,b,end
start,A,b,end
start,A,c,A,b,A,b,A,end
start,A,c,A,b,A,b,end
start,A,c,A,b,A,c,A,end
start,A,c,A,b,A,end
start,A,c,A,b,d,b,A,end
start,A,c,A,b,d,b,end
start,A,c,A,b,end
start,A,c,A,c,A,b,A,end
start,A,c,A,c,A,b,end
start,A,c,A,c,A,end
start,A,c,A,end
start,A,end
start,b,A,b,A,c,A,end
start,b,A,b,A,end
start,b,A,b,end
start,b,A,c,A,b,A,end
start,b,A,c,A,b,end
start,b,A,c,A,c,A,end
start,b,A,c,A,end
start,b,A,end
start,b,d,b,A,c,A,end
start,b,d,b,A,end
start,b,d,b,end
start,b,end

The slightly larger example above now has 103 paths through it, and the even larger example now has 3509 paths through it.

Given these new rules, how many paths through this cave system are there?

Proposed solution: the same solution except the rules for a valid move have changed slightly; I abstract this into a function to check if another small cave has already been moved to twice in the current path being checked

Time complexity: O(E + V)

Space complexity: O(N)

def valid_path(check, move):
    if move == "start":
        return False
    double_small = None
    frequencies = {name:check.count("{}".format(name)) for name in check.split(",")}
    for name, frequency in frequencies.items():
        if frequency == 2 and name.islower():
            double_small = name
    if double_small is not None and (double_small == move or move in frequencies):
        return False
    return True

paths = set()
queue = deque()
queue.append("start")
while len(queue) != 0:
    check = queue.popleft()
    last_node = check.split(",")[-1]
    if last_node == "end":
        paths.add(check)
        continue
    for move in connections[last_node]:
        if valid_path(check, move) or move.isupper():
            queue.append("{},{}".format(check, move))

print("Total Unique Paths: {}".format(len(paths)))

There are optimizations to be made here but the results speak for themselves.

❯ python3 solution12.py example
Total Unique Paths: 36
❯ python3 solution12.py example2
Total Unique Paths: 103
❯ python3 solution12.py example3
Total Unique Paths: 3509
❯ time python3 solution12.py input12
Total Unique Paths: 149220
python3 solution12.py input12  6.79s user 0.06s system 98% cpu 6.950 total