Sean McLemon | Advent of Code

2021-12-12 - Passage Pathing

(original .ipynb)

Day 12 puzzle input describes a collection of named caves (lower-case = small caves, and upper-case = big caves) and how they are connected (mine is here). Part 1 involves finding the number of possible paths from "start" to "end" with the restriction that you can only visit small caves once. Part 2 similarly involves finding the number of possible paths, but now you can visit one small cave twice in each run.

from collections import defaultdict

puzzle_input_str = open("puzzle_input/day12.txt").read()

test_input_str = """start-A
start-b
A-c
A-b
b-d
A-end
b-end"""


def parse_input(input_str):
    edges = [line.split("-") for line in input_str.split("\n")]
    graph = defaultdict(list)
    for src, dst in edges:
        graph[src].append(dst)
        graph[dst].append(src)
    return graph


def paths_to_target(graph, at, target, visited, can_visit):
    visited[at] += 1
    to_visit = [cave for cave in graph[at] if can_visit(cave, visited)]
    
    if at == "end":
        return 1
    elif len(to_visit) == 0:
        return 0
    else:
        return sum(paths_to_target(graph, cave, target, visited.copy(), can_visit) for cave in to_visit)

    
def can_visit_part_one(cave, visited):
    return cave.isupper() or not (cave in visited)
    
    
def part_one(input_str):
    graph = parse_input(input_str)
    visited = defaultdict(lambda:0)
    return paths_to_target(graph, "start", "end", visited, can_visit_part_one)
    

assert 10 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))

part one: 4549

def can_visit_part_two(cave, visited):
    if cave.isupper():
        return True
    if cave == "start":
        return False
    if visited[cave] == 0:
        return True
    
    return not any(count > 1 for cave,count in visited.items() if cave.islower())


def part_two(input_str):
    graph = parse_input(input_str)
    visited = defaultdict(lambda:0)
    return paths_to_target(graph, "start", "end", visited, can_visit_part_two)


assert 36 == part_two(test_input_str)
print("part two:", part_two(puzzle_input_str))

part two: 120535