Juha-Matti Santala
Community Builder. Dreamer. Adventurer.

Advent of Code - 2021

This is a solution to Day 12 of Advent of Code 2021.

Day 12 - Passage Pathing

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

Read input

This time, in addition to reading the input, we also create an undirected graph.

An undirected graph is a graph where you can go from node A to node B and from node B to node A, hence there's no direction. That's how this cave system works: you can move between two caves in either direction.

from utils import read_input
from collections import defaultdict


def transformer(line):
    return line.split('-')

paths = read_input(12, transformer)

caves = defaultdict(set)
for a, b in paths:
    caves[a].add(b)
    caves[b].add(a)

Part 1

In one of the previous puzzles, we had to work with breadth-first search and this time we're working with depth-first search and finding all possible routes from start to finish (with some extra rules).

The extra rules are codified in can_enter function. In this part 1, if the name of the cave is in lower case, we can only enter it once.

def can_enter(cave, path):
    return not (cave.islower() and cave in path)

To make a map, we start from start cave and recursively find all the paths for each of the caves you can access from.

Once we reach an end, we return our path so far and we collect these paths into a map (a_map is called that instead of map because map is a built-in function in Python and I don't want to override that).

If we reached a cave that is not end, we find all caves it is connected to, check if we can enter them by rules and if we can, we find all the paths from those towards the end.

def make_a_map(caves):
    a_map = []
    for next_cave in caves['start']:
        paths = find_all_paths(next_cave, caves, ['start'])
        a_map.extend(paths)
    return a_map


def find_all_paths(cave, caves, path):
    path = path[:]
    path.append(cave)
    if cave == 'end':
        return [path]
    all_paths = []
    for next_cave in caves[cave]:
        if can_enter(next_cave, path):
            paths = find_all_paths(next_cave, caves, path)
            all_paths.extend(paths)

    return all_paths


a_map = make_a_map(caves)
result = len(a_map)
print(f'Solution: {result}')
assert result == 3495

Solution: 3495

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.

The only thing that changes for part 2 is the rule for when a cave can be re-entered. So we only need to change our can_enter function.

Since make_a_map and find_all_paths are otherwise exactly the same, in a non Advent of Code environment, I would pass the can_enter validation function as a parameter to make_a_map so I'd only need to have that piece of code once. However, since I don't generally like to introduce unnecessary bits in part 1 code, I'm keeping it like this.

def can_enter(cave, path):
    if cave.islower() and path.count(cave) == 2:
        return False
    if cave.islower() and cave in path and any(c.islower() and path.count(c) == 2 for c in path):
        return False
    if cave == 'start':
        return False
    return True

def make_a_map(caves):
    a_map = []
    for next_cave in caves['start']:
        paths = find_all_paths(next_cave, caves, ['start'])
        a_map.extend(paths)
    return a_map

def find_all_paths(cave, caves, path):
    path = path[:]
    path.append(cave)
    if cave == 'end':
        return [path]
    all_paths = []
    for next_cave in caves[cave]:
        if can_enter(next_cave, path):
            paths = find_all_paths(next_cave, caves, path)
            all_paths.extend(paths)

    return all_paths


a_map = make_a_map(caves)
result = len(a_map)
print(f'Solution: {result}')
assert result == 94849

Solution: 94849

Wrap up

Graphs are hard for me. I really really struggled with the breadth-first search in Day 9 but I managed to solve today's puzzle all on my own without any help! It took me a good pondering though since I had trouble finding the right combination of returning out of the function and being able to collect all the paths.

And then I missed the "and the remaining small caves can be visited at most once" part of the rules in second part and was so confused for why certain paths were not allowed. Once I realized that, everything fell in place nicely.

This might be my most proud achievement in Advent of Code ever. I guess my skills are improving!

PS. If you wanna learn something new and see solutions that your friends very likely did not reach, check out Tess Ferrandez's Twitter and her solutions. Whether it's using complex numbers to deal with 2D coordinate system, a region merge system instead of breadth-first search or dynamic programming, her solutions are ones that I haven't seen anywhere else (and they're in Python!) and I've been learning so much from her this year.