no space left on device

approach

the terminal log is replayed into a tree of Nodes. a stack of directories follows the cd commands, and the lines after an ls create child directories or files with a size. a node with no children is a file.

part 1 is a depth-first search that returns two numbers per node: its total size and the sum of the sizes of the small directories inside it, counting itself if it's under the limit. part 2 computes how much space has to be freed, then runs a second search that returns the smallest directory size at least that big. the rust version is a port.

the trick

return a pair from the recursion, the subtree size and the running answer, so one pass does both.

def dfs(node, limit):
    if not node:
        return 0, node.file_weight
    ts = s = 0
    for nn in node:
        nnt, nns = dfs(nn, limit)
        ts += nnt
        s += nns
    return (0 if s > limit else s) + ts, s