Passage Pathing - Advent of Code 2021 Day 12

 

Day 12 of this year's Advent of Code requires that we find all paths in a directed graph. The full details of the problem can be found here - https://adventofcode.com/2021/day/12

The data supplied by the problem describes all the connected small and big caves as shown in the diagram below

First Part

For the first part of the problem we need to find all the various paths the submarine can take from start to end while travelling through the small caves only once. The first part does allow multiple visits to large caves.

A standard approach to a problem that has multiple choices is that we consider all choices that are available to us. We can then either count or minimize based on the question asked in the problem

In this problem we also need to track all of the small caves that have been visited, so that they aren't repeated. We then use this list to eliminate choices that are no longer available to us. The choices that are available to us become the input into the recursive function. 

def travel(presentCave,smallCavesTravelled):

    count = 0

    if presentCave == "end":
        return 1

    if presentCave.islower():
        smallCavesTravelled.append(presentCave)

    for caveChoice in graph[presentCave]:
        if caveChoice not in smallCavesTravelled:
            count += travel(caveChoice,smallCavesTravelled.copy())

    return count

We keep considering choices until we reach the end cave.

The function above also accepts a cloned copy of the small caves that have been visited. In hindsight this could have probably also been a map as it would have simplified the second part of the problem

Second Part

The second part of the problem relaxes a rule placed in the first part - we can now visit a small cave twice. 

I decided to tweak the first function by simply tracking the caves that have been visited twice.

def travelOneSmallCaveTwice(presentCave,smallCavesTravelled,smallCaveTravelledTwice):

    c = 0

    if presentCave == "end":
        return 1

    if presentCave.islower():
        if presentCave in smallCavesTravelled:
            smallCaveTravelledTwice.append(presentCave)
        else:
            smallCavesTravelled.append(presentCave)

    for caveChoice in graph[presentCave]:
       
        if caveChoice not in smallCavesTravelled or\
            (caveChoice in smallCavesTravelled and len(smallCaveTravelledTwice) == 0):
            c += travelOneSmallCaveTwice(caveChoice,smallCavesTravelled.copy(),
                    smallCaveTravelledTwice.copy())

    return c

The full source code can be found there -

https://github.com/jasoncoelho/adventOfCode2021/blob/main/12/run.py