Sean McLemon | Advent of Code

2022-12-07 - No Space Left On Device

(original .ipynb)

Day 7 puzzle input is a sequence of characters (mine is here). Part 1 involves reconstructing a file system hierarchy from the output of cd and ls commands, and finding the sum of all folder sizes under 100_000. Part 2 involves using this reconstructed file-system hierarchy to find which is the smallest folder to delete that allows our 70_000_000 (byte? megabyte?) filesystem to have at least 30_000_000 bytes/megabytes/units/sectors/whatever free.

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

test_input_str = """$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k"""


def parse_input(input_str):
    command, args = "", []
    output = []
    for line in input_str.splitlines():
        tokens = line.split(" ")
        if tokens[0] == "$":
            yield (command, args, output)
            command, args = tokens[1], tokens[2:]
            output = []
        else:
            output.append(tokens)
    yield (command, args, output)
        

def interpret_command(cwd, command, args, output):
    if command == "cd":
        return cwd[args[0]]
    elif command == "ls":
        for info, name in output:
            if info == "dir":
                if not (name in cwd):
                    cwd[name] = {"..": cwd}
            else:
                cwd[name] = int(info)
        return cwd


def calculate_size(cwd, path, sizes):
    local_total = 0
    for name in cwd:
        if name == "..":
            continue
        entry = cwd[name]
        if type(entry) == dict:
            size = calculate_size(entry, path + name + "/", sizes)
            local_total += size
            sizes[path + name] = size
        elif type(entry) == int:
            local_total += entry

    return local_total


def find_folder_sizes(input_str):
    root = {"/": {}}
    cwd = root

    shell_history = list(parse_input(input_str))
    for command, args, output in shell_history[1:]:
        cwd = interpret_command(cwd, command, args, output)
    
    sizes = {}
    total = calculate_size(root["/"], "/", sizes)
    return (sizes, total)

    
def part_one(input_str):
    max_size = 100_000
    (sizes, total) = find_folder_sizes(input_str)
    return sum(sizes[name] for name in sizes if sizes[name] < max_size)


assert 95437 == part_one(test_input_str)

print("part one:", part_one(puzzle_input_str))

part one: 1723892

def part_two(input_str):
    max_size = 100_000
    (sizes, total) = find_folder_sizes(input_str)
    free_size = 70_000_000 - total
    return min(size for size in sizes.values() if free_size + size >= 30_000_000)


assert part_two(test_input_str) == 24933642

print("part two:", part_two(puzzle_input_str))

part two: 8474158