Day 7: No Space Left On Device

#!/usr/bin/env pypy3

import os.path
import re
import sys

SIZE_BOUND = 100000

def main():
    dirsizes = {}
    cwd = '/'
    for line in sys.stdin:
        if m := re.match(r'^\$ cd \.\.$', line):
            cwd, _ = os.path.split(cwd)
        elif m := re.match(r'^\$ cd (\S+)$', line):
            cwd = os.path.join(cwd, m.group(1))
            dirsizes[cwd] = 0
        elif m := re.match(r'^([0-9]+) (\S+)$', line):
            size = int(m.group(1))
            for d in filter(cwd.startswith, dirsizes):
                dirsizes[d] += size

    print(sum(v for v in dirsizes.values() if v <= SIZE_BOUND))

if __name__ == '__main__':
    main()

#!/usr/bin/env pypy3

import os.path
import re
import sys

SIZE_DISK = 70000000
SIZE_NEED = 30000000

def main():
    dirsizes = {}
    cwd = '/'
    for line in sys.stdin:
        if m := re.match(r'^\$ cd \.\.$', line):
            cwd, _ = os.path.split(cwd)
        elif m := re.match(r'^\$ cd (\S+)$', line):
            cwd = os.path.join(cwd, m.group(1))
            dirsizes[cwd] = 0
        elif m := re.match(r'^([0-9]+) (\S+)$', line):
            size = int(m.group(1))
            for d in filter(cwd.startswith, dirsizes):
                dirsizes[d] += size

    size_to_delete = SIZE_NEED - (SIZE_DISK - dirsizes['/'])
    print(min(v for v in dirsizes.values() if v >= size_to_delete))

if __name__ == '__main__':
    main()

#!/usr/bin/awk -f
/cd \// {
	p = 0
	s[p] = $3
}

/cd [a-z]/ { s[++p] = $3 }
/cd \.\./ { delete s[p--] }

/^[0-9]/ {
	str = ""
	for (i = 0; i <= p; ++i) {
		str = str "/" s[i]
		a[str] += $1
	}
}

END {
	for (i in a)
		if (a[i] <= 100000)
			sum += a[i]

	print(sum)
}

#!/usr/bin/awk -f
/cd \// {
	p = 0
	s[p] = $3
}

/cd [a-z]/ { s[++p] = $3 }
/cd \.\./ { delete s[p--] }

/^[0-9]/ {
	str = ""
	for (i = 0; i <= p; ++i) {
		str = str "/" s[i]
		a[str] += $1
	}
}

END {
	target = 30000000 - (70000000 - a["//"])
	min = a["//"]

	for (i in a)
		if (a[i] >= target && a[i] < min)
			min = a[i]

	print(min)
}

import { assertEquals } from "https://deno.land/std@0.167.0/testing/asserts.ts";
import { runPart } from "https://deno.land/x/aocd@v1.2.2/mod.ts";

type ParsedLine = Command | Output;

interface Command {
  type: "command";
  words: string[];
}

interface Output {
  type: "output";
  line: string;
}

function parse(input: string): ParsedLine[] {
  return input.trimEnd().split("\n").map((line) => {
    if (line.startsWith("$ ")) {
      return {
        type: "command",
        words: line.split(/\s+/).slice(1),
      };
    } else {
      return {
        type: "output",
        line,
      };
    }
  });
}

type Node = File | Directory;

interface File {
  type: "file";
  name: string;
  size: number;
}

interface Directory {
  type: "directory";
  name: string;
  nodes: Node[];
  parent: Directory | null;
}

function translateParsedLinesToFilesystem(
  parsedLines: ParsedLine[],
): Directory {
  const root: Directory = {
    type: "directory",
    name: "/",
    nodes: [],
    parent: null,
  };
  let currentDirectory = root;
  for (const parsedLine of parsedLines) {
    if (parsedLine.type === "command") {
      const [command, ...args] = parsedLine.words;
      if (command === "cd") {
        const [path] = args;
        if (path === "/") {
          currentDirectory = root;
        } else if (path === "..") {
          if (!currentDirectory.parent) {
            throw new Error("cannot cd .. from root");
          }
          currentDirectory = currentDirectory.parent;
        } else {
          for (const name of path.split("/")) {
            const node = currentDirectory.nodes.find((node) =>
              node.name === name
            );
            if (!node) {
              throw new Error(`could not find node ${name}`);
            }
            if (node.type !== "directory") {
              throw new Error(`node ${name} is not a directory`);
            }
            currentDirectory = node;
          }
        }
      } else if (command === "ls") {
        // do nothing
      } else {
        throw new Error(`unknown command ${command}`);
      }
    } else if (parsedLine.type === "output") {
      const { line } = parsedLine;
      const match = /^(dir|\d+)\s+(\S+)$/.exec(line);
      if (!match) {
        throw new Error(`line did not match expected format: ${line}`);
      }
      const [, dirLiteralOrSize, name] = match;
      if (dirLiteralOrSize === "dir") {
        currentDirectory.nodes.push({
          type: "directory",
          name,
          nodes: [],
          parent: currentDirectory,
        });
      } else {
        currentDirectory.nodes.push({
          type: "file",
          name,
          size: Number(dirLiteralOrSize),
        });
      }
    }
  }
  return root;
}

function calculateSizesOfAllDirectories(
  root: Directory,
): Map<Directory, number> {
  const sizes = new Map<Directory, number>();
  function calculateSizesOfAllDirectoriesHelper(
    directory: Directory,
  ): number {
    const size = directory.nodes.reduce((total, node) => {
      if (node.type === "file") {
        return total + node.size;
      } else {
        return total + calculateSizesOfAllDirectoriesHelper(node);
      }
    }, 0);
    sizes.set(directory, size);
    return size;
  }
  calculateSizesOfAllDirectoriesHelper(root);
  return sizes;
}

function part1(input: string): number {
  const parsedLines = parse(input);
  const root = translateParsedLinesToFilesystem(parsedLines);
  const sizes = calculateSizesOfAllDirectories(root);
  return Array.from(sizes.entries())
    .filter(([, size]) => size <= 100000)
    .reduce((sum, [, size]) => sum + size, 0);
}

function part2(input: string): number {
  const parsedLines = parse(input);
  const root = translateParsedLinesToFilesystem(parsedLines);
  const sizes = calculateSizesOfAllDirectories(root);

  const totalSize = sizes.get(root)!;
  const targetSize = 40_000_000;
  const needToDelete = totalSize - targetSize;

  return Math.min(
    ...Array.from(sizes.values()).filter((size) => size >= needToDelete),
  );
}

if (import.meta.main) {
  runPart(2022, 7, 1, part1);
  runPart(2022, 7, 2, part2);
}

const TEST_INPUT = `\
$ 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
`;

Deno.test("part1", () => {
  assertEquals(part1(TEST_INPUT), 95437);
});

Deno.test("part2", () => {
  assertEquals(part2(TEST_INPUT), 24933642);
});

(struct dir (contents) #:mutable #:transparent)
(struct file (size) #:transparent)
(define root (list "/"))

(define (part-01 input)
  (define disk (run-script null (mount-disk) input))
  (sum-dirs disk 100000))

(define (mount-disk)
  (make-hash `((,root . ,(dir null)))))

(define (run-script path disk out)
  (if (null? out)
      disk
      (match (string-split (first out))
        [(list _ "cd" "/")   (run-script root disk (rest out))]
        [(list _ "cd" "..")  (run-script (rest path) disk (rest out))]
        [(list _ "cd" subdir) (run-script (cons subdir path) disk (rest out))]
        [(list _ "ls")       (parse-listing path disk (rest out))]
        [_ (error 'execute-command "command expected: ~a" (first out))])))

(define (parse-listing path disk out)
  (cond [(null? out) disk]
        [else
         (match (string-split (first out))
           [(cons "$" _)  (run-script path disk out)]
           [(list "dir" name)  (add-directory path disk name out)]
           [(list size name)  (add-file path disk (string->number size) name out)]
           [_ (error 'parse-listing "unknown listing ~a" (first out))])]))

(define (add-directory path disk name out)
  (define new-dir (dir null))
  (define t (hash-ref disk path))
  (set-dir-contents! t (cons new-dir (dir-contents t)))
  (hash-set! disk (cons name path) new-dir)
  (parse-listing path disk (rest out)))

(define (add-file path disk size name out)
  (define new-path (cons name path))
  (define new-file (file size))
  (define t (hash-ref disk path))
  (set-dir-contents! t (cons new-file (dir-contents t)))
  (hash-set! disk new-path new-file)
  (parse-listing path disk (rest out)))

(define (sum-dirs disk limit)
  (for/sum ([(_ v) (in-hash disk)]
            #:when (dir? v))
    (define s (dir-size v))
    (if (> s limit) 0 s)))

(define (dir-size t)
  (match t
    [(dir contents) (apply + (map dir-size contents))]
    [(file size) size]))

(define (part-02 input)
  (define disk (execute-command null (mount-disk) input))
  (define used (dir-size (hash-ref disk (list "/"))))
  (define space-needed (- used 40000000))
  (for/fold ([smallest used])
            ([v (in-hash-values disk)]
             #:when (dir? v))
    (define size (dir-size v) )
    (if (>= size space-needed)
        (min size smallest)
        smallest)))

Both parts takes about 2.6ms.
As usual build up the data structures once and use it for both parts

Attempt 1: ~70% elapsed time
Breakdown:
~250 μs: read file
~ 1 ms: build the data structure
~270 μs: part 1
~230 μs: part 2

(define disk (run-script null (mount-disk) (read-input)))
(define (part-01 disk)
  (sum-dirs disk 100000))
(define (part-02 disk)
  (define used (dir-size (hash-ref disk (list "/"))))
  (define space-needed (- used 40000000))
  (for*/fold ([smallest used])
             ([(k v) (in-hash disk)]
              #:when (dir? v)
              [size (in-value (dir-size v))]
              #:unless (< size space-needed))
    (min size smallest)))
(list (part-01 disk)
      (part-02 disk))

Note: The example listing and my input (and being AoC I suspect everyone's input) are both a recursive dfs of the disk.

I have a truly marvelous demonstration of this proposition that this margin is too narrow to contain. I don't have time to write today :)

use std::error::Error;
use std::fs::File;
use std::io::Read;
use std::path::PathBuf;

type Entry = (PathBuf, u64, Type);

#[derive(PartialEq)]
enum Type {
    Dir,
    File,
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut file = File::open("input_7.txt")?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    let mut entries: Vec<Entry> = vec![("/".into(), 0, Type::Dir)];
    let mut current_entry = 0;
    for line in contents.lines() {
        if line.starts_with("$ cd ..") {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.pop();
            current_entry = add_dir(&mut entries, new_path);
        } else if line.starts_with("$ cd ") {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.push(line.split(" ").nth(2).unwrap());
            current_entry = add_dir(&mut entries, new_path);
        } else if line.starts_with("$ ls") {
            // do nothing
        } else if line.starts_with("dir ") {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.push(line.split(" ").nth(1).unwrap());
            add_dir(&mut entries, new_path);
        } else {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.push(line.split(" ").nth(1).unwrap());
            let size = line.split(" ").next().unwrap().parse::<u64>().unwrap();
            add_file(&mut entries, new_path, size);
        }
    }
    let total_size = entries
        .iter()
        .filter(|e| e.1 <= 100_000 && e.2 == Type::Dir)
        .fold(0, |acc, e| acc + e.1);
    println!("{total_size}");
    Ok(())
}

fn add_dir(entries: &mut Vec<Entry>, path: PathBuf) -> usize {
    let exists = entries.iter().position(|e| e.0 == path);
    if exists.is_some() {
        exists.unwrap()
    } else {
        entries.push((path, 0, Type::Dir));
        entries.len() - 1
    }
}

fn add_file(entries: &mut Vec<Entry>, path: PathBuf, size: u64) -> usize {
    let exists = entries.iter().position(|e| e.0 == path);
    if exists.is_some() {
        exists.unwrap()
    } else {
        entries
            .iter_mut()
            .filter(|e| path.starts_with(&e.0))
            .for_each(|e| e.1 += size);
        entries.push((path, size, Type::File));
        entries.len() - 1
    }
}

use std::error::Error;
use std::fs::File;
use std::io::Read;
use std::path::PathBuf;

type Entry = (PathBuf, u64, Type);

#[derive(PartialEq)]
enum Type {
    Dir,
    File,
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut file = File::open("input_7.txt")?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    let mut entries: Vec<Entry> = vec![("/".into(), 0, Type::Dir)];
    let mut current_entry = 0;
    for line in contents.lines() {
        if line.starts_with("$ cd ..") {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.pop();
            current_entry = add_dir(&mut entries, new_path);
        } else if line.starts_with("$ cd ") {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.push(line.split(" ").nth(2).unwrap());
            current_entry = add_dir(&mut entries, new_path);
        } else if line.starts_with("$ ls") {
            // do nothing
        } else if line.starts_with("dir ") {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.push(line.split(" ").nth(1).unwrap());
            add_dir(&mut entries, new_path);
        } else {
            let mut new_path = entries.get(current_entry).unwrap().0.clone();
            new_path.push(line.split(" ").nth(1).unwrap());
            let size = line.split(" ").next().unwrap().parse::<u64>().unwrap();
            add_file(&mut entries, new_path, size);
        }
    }
    let total_size = entries
        .iter()
        .filter(|e| e.2 == Type::File)
        .fold(0, |acc, e| acc + e.1);
    let need_to_clear = 30_000_000 - (70_000_000 - total_size);
    let smallest_suitable_dir_size = entries
        .iter()
        .filter(|e| e.1 >= need_to_clear)
        .min_by(|e1, e2| e1.1.cmp(&e2.1))
        .unwrap()
        .1;
    println!("{smallest_suitable_dir_size}");
    Ok(())
}

fn add_dir(entries: &mut Vec<Entry>, path: PathBuf) -> usize {
    let exists = entries.iter().position(|e| e.0 == path);
    if exists.is_some() {
        exists.unwrap()
    } else {
        entries.push((path, 0, Type::Dir));
        entries.len() - 1
    }
}

fn add_file(entries: &mut Vec<Entry>, path: PathBuf, size: u64) -> usize {
    let exists = entries.iter().position(|e| e.0 == path);
    if exists.is_some() {
        exists.unwrap()
    } else {
        entries
            .iter_mut()
            .filter(|e| path.starts_with(&e.0))
            .for_each(|e| e.1 += size);
        entries.push((path, size, Type::File));
        entries.len() - 1
    }
}

import collections, copy


def tree():
    return collections.defaultdict(tree)


filesystem = tree()
path = list()
dirs = set()


def add(keys, value=None, t=filesystem):
    for i, key in enumerate(keys):
        if i == len(keys) - 1 and value:
            continue
        t = t[key]

    if value:
        t[key] = value


def dirSize(keys):
    t = copy.deepcopy(filesystem)
    total = int()

    for k in keys:
        t = t[k]

    for k in t.keys():
        total += t[k] if type(t[k]) == int else dirSize(keys + tuple([k]))

    return total


for line in open("input.txt").read().splitlines():
    match line.split():
        case ["$", "cd", dir]:
            match dir:
                case "..":
                    path.pop()
                case "/":
                    path = ["/"]
                case _:
                    path.append(dir)
                    dirs.add(tuple(path))
                    add(path)
        case ["$", "ls"]:
            pass
        case ["dir", dir]:
            add(path + [dir])
            dirs.add(tuple(path + [dir]))
            pass
        case [size, file]:
            add(path + [file], int(size))


limit: int = 100_000
total_space: int = 70_000_000
need_space: int = 30_000_000
total = int()
for_delete = list()

need_space -= total_space - dirSize(tuple("/"))

for dir in dirs:
    size = dirSize(dir)
    if size < limit:
        total += size
    if size > need_space:
        for_delete.append(size)

print(total)  # Part One: 1325919
print(min(for_delete))  # Part Two: 2050735

/*
    Most of the heavy lifting is being done by my input parser, which builds
    out a hierarchical "filesystem" object I can traverse. In that structure
    I'm putting sizes on directories as I go, for convenience. Then for
    finding the actual solutions it's just a matter of reading what's there.
    Bit of recursion in the traversal functions, which is always fun.
*/

interface File {
  name: string;
  size: number;
  type: 'file';
}
interface Directory {
  children: (Directory | File)[];
  name: string;
  size: number;
  type: 'directory';
}
type Command = string;
type Path = string | undefined;
type Input = [Command, Path];

// parse the input file into a hierarchical object we can traverse
function formatInput(input: string): Directory {
  // declare the root node of the hierarchy we will be building out
  const filesystem = {
    children: [],
    name: '/',
    size: 0,
    type: 'directory',
  } as Directory;
  // pointer is used to track the path to the current node, it's an array of strings
  // each element is one level in the hierarchy (first should always be root, "/")
  let pointer = ['/'];
  // fetch the actual directory that a pointer references
  const resolvePointer = (pointerToResolve: string[]): Directory => {
    let currentDir = filesystem;
    if (pointerToResolve.length > 1) {
      for (const level of pointerToResolve) {
        if (level === '/') {
          continue;
        }
        currentDir = currentDir.children.filter(e => e.name === level)[0] as Directory;
      }
    }
    return currentDir;
  };

  // split input into separate "actions," each of which includes both a command and its output
  const actions = `${input}`.split('\n$ ');
  for (const action of actions) {
    // split by line; first is the command, any lines after are dirs or files in the ls output
    const output = action.split('\n');
    const [command, path] = output.shift().split(' ') as Input;

    // if the command was cd, move the pointer according to the path
    if (command === 'cd' && path) {
      if (path === '..') {
        pointer.pop();
      } else if (path === '/') {
        pointer = ['/'];
      } else {
        pointer.push(path);
      }
    }

    // if the command was ls, parse the output to populate the children of the current dir
    if (command === 'ls') {
      // get the actual directory represented by wherever the pointer is right now
      const currentDir = resolvePointer(pointer);
      for (const item of output) {
        const [meta, name] = item.split(' ');
        // hacky error handling yay
        if (!name) {
          break;
        }
        // if the listed item is a directory, add it to the children array
        if (meta === 'dir') {
          currentDir.children.push({
            children: [],
            name,
            size: 0,
            type: 'directory',
          });
        } else {
          // listed item must be a file, add it to the children array
          currentDir.children.push({
            name,
            size: Number(meta),
            type: 'file',
          });
          // now traverse up to root, adding this file size to each ancestor node
          const ancestorWalkPointer = [...pointer];
          while (ancestorWalkPointer.length > 0) {
            resolvePointer(ancestorWalkPointer).size += Number(meta);
            ancestorWalkPointer.pop();
          }
        }
      }
    }
  }
  return filesystem;
}

export function run(input: string): string[] {
  const filesystem = formatInput(input);

  const getTotalOfCandidateDirectorySizes = (fs: Directory): number => {
    let total = 0;
    const walk = (dir: Directory): void => {
      if (dir.size <= 100000) {
        total += dir.size;
      }
      for (const node of dir.children) {
        if (node.type === 'directory') {
          walk(node);
        }
      }
    };
    walk(fs);
    return total;
  };

  const findSmallestCandidateDirectory = (fs: Directory): number => {
    const spaceNeeded = 30000000 - (70000000 - fs.size);
    let smallestCandidateSize = 70000000;
    const walk = (dir: Directory): void => {
      if (dir.size >= spaceNeeded && dir.size < smallestCandidateSize) {
        smallestCandidateSize = dir.size;
      }
      for (const node of dir.children) {
        if (node.type === 'directory') {
          walk(node);
        }
      }
    };
    walk(fs);
    return smallestCandidateSize;
  };

  return [`${getTotalOfCandidateDirectorySizes(filesystem)}`, `${findSmallestCandidateDirectory(filesystem)}`];
}

I figured I'd just build a tree of inodes while parsing.

(struct inode (type name size parent children) #:mutable #:transparent)

(define (add-child! current-dir new-inode)
  (mappend! (inode-children current-dir) (mlist new-inode)))

(define (find-dir tree dirname)
  (for/first ([child (inode-children tree)]
              #:when (and (inode? child)
                          (eq? (inode-type child) 'dir)
                          (string=? (inode-name child) dirname)))
    child))


(define (sanitize-input input)
  (define lines (string-split input "\n"))

  (define tree (inode 'dir "/" 0 #f (mlist empty))) ; the (mlist empty) makes it so I need guards in all the for loops
                                                    ; but if I take it away, it breaks, so... ¯\\\_(ツ)\_/¯
  (define current-dir tree)

  (for ([line lines])
    (define parts (string-split line))
    (cond [(string=? (first parts) "$")
           (cond
             [(string=? (second parts) "cd")
              (match (third parts)
                ["/"  (set! current-dir tree)]
                [".." (set! current-dir (inode-parent current-dir))]
                [else
                 (define target-dir (find-dir current-dir (third parts)))
                 (when (not (inode? target-dir))
                   (error 'cd (~a "could not find" (third parts))))
                 (set! current-dir target-dir)])]
             [(string=? (second parts) "ls") 'ignore]
             [else 'unknown-command])]
          [(string=? (first parts) "dir")
           (define new-dir (inode 'dir (second parts) 0 current-dir (mlist empty)))
           (add-child! current-dir new-dir)]
          [else
           (define size (string->number (first parts)))
           (define filename (second parts))
           (define new-file (inode 'file filename size current-dir empty))
           (add-child! current-dir new-file)]))
  tree
  )

(define (size-calculator! tree)
  (define size
    (for/fold ([total-size 0])
              ([child (inode-children tree)]
               #:when (inode? child))
      (match (inode-type child)
        ['file (+ total-size (inode-size child))]
        ['dir
         (define sub-size (size-calculator! child))
         (set-inode-size! child sub-size)
         (+ total-size sub-size)])))
  (set-inode-size! tree size)
  size)

(define (solver tree compare-func target-size)
  (define subdirs
    (for/fold ([d empty])
              ([child (inode-children tree)]
               #:when (and (inode? child)
                           (eq? (inode-type child) 'dir)))
      (append d (solver child compare-func target-size))))
  (define dir (list (inode-name tree) (inode-size tree)))
  (if (compare-func (inode-size tree) target-size)
      (append (list dir) subdirs)
      subdirs))

(define (part-1 input)
  (define total-size  (size-calculator! input))
  (define out
    (solver input <= 100000))
  (apply + (map second out)))

(define (part-2 input)
  (define total-size  (size-calculator! input))

  (define target-size (- REQUIRED (- MAX total-size)))
  (define candidates (sort (map second (solver input >= target-size)) <))
  (first candidates))

class FilesystemObject:
    def __init__(self, parent, name: str):
        self.name = name
        self.parent = parent  # Want to hint this, but get not defined error?

    @property
    def size(self) -> int:
        raise NotImplementedError


class Directory(FilesystemObject):
    def __init__(
        self,
        parent,  # Want to hint this, but get not defined error?
        name: str,
        children: Optional[Dict[str, FilesystemObject]],
    ):  
        if children is None:
            self.children: Dict[str, FilesystemObject] = {}
        else:
            self.children = children
        super().__init__(parent, name)

    def add_child(self, child: FilesystemObject):
        self.children[child.name] = child

    @property
    def size(self) -> int:
        return sum((item.size for item in self.children.values()))


class File(FilesystemObject):
    def __init__(self, parent: Optional[Directory], name: str, size: int):
        self._size = size
        super().__init__(parent, name)

    @property
    def size(self) -> int:
        return self._size


def parse_commands(commands: List[str]) -> Directory:
    root = Directory(None, "/", None)
    cwd = root
    ls_mode = False

    for command in commands[1:]:
        breakdown = command.split()
        if breakdown[0] == "$":
            ls_mode = False
            if breakdown[1] == "cd":
                if breakdown[2] == "..":
                    cwd = cast(Directory, cwd.parent)
                    continue

                if breakdown[2] == "/" and root is not None:
                    cwd = root
                    continue

                if breakdown[2] == "/" and root is None:
                    root = Directory(cwd, "/", None)
                    cwd = root
                    continue

                cwd = cast(Directory, cwd.children[breakdown[2]])

            elif breakdown[1] == "ls":
                ls_mode = (
                    True  # I don't think I need this but if we expand this I might
                )

        elif ls_mode:

            if breakdown[0] == "dir":
                cwd.add_child(Directory(cwd, breakdown[1], None))
                continue

            cwd.add_child(File(cwd, breakdown[1], int(breakdown[0])))

        else:
            raise NotImplementedError

    return root


def find_small(current: FilesystemObject) -> List[int]:

    if isinstance(current, File):
        return []

    if current.size <= 100000:
        out = [current.size]
        for child in cast(Directory, current).children.values():
            out.extend(find_small(child))
        return out

    out = []
    for child in cast(Directory, current).children.values():
        out.extend(find_small(child))
    return out


def find_bigger(current: FilesystemObject, minimum: int) -> List[int]:

    if isinstance(current, File):
        return []

    if current.size >= minimum:
        out = [current.size]
        for child in cast(Directory, current).children.values():
            out.extend(find_bigger(child, minimum))
        return out

    return []


def main(filepath: str) -> Tuple[int, int]:

    inputs = load_file.load_cleaned_lines(filepath)
    root_dir = parse_commands(inputs)

    target = 30000000 - (70000000 - root_dir.size)

    return (sum(find_small(root_dir)), min(find_bigger(root_dir, target)))

A simple struct to store a directory node. The struct originally had more fields (I also had a separate struct for the file entries) since I didn't know what part 2 might ask for, but I've pared everything down to just what was ultimately needed to solve both parts.

defmodule Dir do
  @type t :: %__MODULE__{
          size: non_neg_integer(),
          dirs: %{String.t() => t()}
        }
  defstruct size: 0, dirs: %{}

  @spec sizes(t()) :: list(non_neg_integer())
  def sizes(%__MODULE__{} = d) do
    [d.size] ++ Enum.flat_map(Map.values(d.dirs), &sizes/1)
  end
end

The typespecs kind of clutter things up, but they might be helpful to explain what's going on?

defmodule Zipper.Context do
  @type t :: %__MODULE__{
          name: String.t(),
          siblings_size: non_neg_integer(),
          dir_siblings: %{String.t() => Dir.t()}
        }
  defstruct [:name, :siblings_size, :dir_siblings]
end

defmodule Zipper do
  alias Zipper.Context

  @type t :: %__MODULE__{
          focus: Dir.t(),
          context: list(Context.t())
        }
  defstruct focus: %Dir{}, context: []

  @spec to_dir(t()) :: Dir.t()
  def to_dir(%__MODULE__{} = z) do
    Enum.reduce(z.context, z.focus, &rebuild_parent/2)
  end

  @spec add_dir(t(), String.t()) :: t()
  def add_dir(%__MODULE__{} = z, name) do
    update_in(z.focus.dirs, &Map.put_new(&1, name, %Dir{}))
  end

  @spec add_size(t(), integer) :: t()
  def add_size(%__MODULE__{} = z, size) do
    update_in(z.focus.size, &(&1 + size))
  end

  @spec down(t(), String.t()) :: t()
  def down(%__MODULE__{} = z, name) do
    %__MODULE__{
      focus: Map.fetch!(z.focus.dirs, name),
      context: [make_context(z.focus, name) | z.context]
    }
  end

  @spec up(t()) :: t()
  def up(%__MODULE__{context: [context | rest]} = z) do
    %__MODULE__{context: rest, focus: rebuild_parent(context, z.focus)}
  end

  defp make_context(dir, cd_name) do
    %Context{
      name: cd_name,
      siblings_size: dir.size - dir.dirs[cd_name].size,
      dir_siblings: Map.delete(dir.dirs, cd_name)
    }
  end

  defp rebuild_parent(context, from_dir) do
    %Dir{
      size: context.siblings_size + from_dir.size,
      dirs: Map.put_new(context.dir_siblings, context.name, from_dir)
    }
  end
end

defmodule AdventOfCode.Solution.Year2022.Day07 do
  def part1(input) do
    input
    |> parse_fs()
    |> Dir.sizes()
    |> Enum.reject(&(&1 > 100_000))
    |> Enum.sum()
  end

  @capacity 70_000_000
  @min_needed 30_000_000

  def part2(input) do
    fs = parse_fs(input)

    unused_space = @capacity - fs.size
    min_to_delete = @min_needed - unused_space

    fs
    |> Dir.sizes()
    |> Enum.filter(&(&1 >= min_to_delete))
    |> Enum.min()
  end

  defp parse_fs(input) do
    input
    |> String.split("\n", trim: true)
    # Skip "$ cd /"
    |> Enum.drop(1)
    |> Enum.reduce(%Zipper{}, &process_line/2)
    |> Zipper.to_dir()
  end

  defp process_line("$ ls", z), do: z

  defp process_line("$ cd ..", z), do: Zipper.up(z)
  defp process_line("$ cd " <> dir_name, z), do: Zipper.down(z, dir_name)

  defp process_line("dir " <> dir_name, z) do
    Zipper.add_dir(z, dir_name)
  end

  defp process_line(file_line, z) do
    {size, _} = Integer.parse(file_line)
    Zipper.add_size(z, size)
  end
end

import std/[heapqueue, strutils, tables]

type
  MyFile = ref object
    name: string
    parentDir: MyFile
    case isDir: bool
    of true: files: TableRef[string, MyFile]
    of false: size: int

proc len(file: MyFile): int =
  if not file.isDir:
    return file.size
  var size = 0
  for subFile in file.files.values:
    size += subFile.len()
  return size

proc part1(file: MyFile): int =
  if not file.isDir:
    return file.size

  var size = 0
  for subFile in file.files.values:
    if subFile.isDir:
      if subFile.len <= 100000:
        size += subFile.len
      size += subFile.part1()
  return size

proc part2Rec(file: MyFile): (int, HeapQueue[int]) =
  var
    size = 0
    heap: HeapQueue[int]
  for subFile in file.files.values:
    if subFile.isDir:
      var (subDirSize, subDirHeap) = part2Rec(subFile)
      while subDirHeap.len > 0:
        heap.push(subDirHeap.pop())
      size += subDirSize
    else:
      size += subFile.size
  heap.push(size)
  return (size, heap)

proc part2(root: MyFile, capacity, goalFree: int): int =
  let outerSize = root.len
  var (_, heap) = root.part2Rec()
  while heap.len > 0:
    let size = heap.pop()
    if capacity - outerSize + size > goalFree:
      return size

  return -1

proc day07*() =
  var
    root: MyFile
    curDir: MyFile

  # Assumes the first input line is to root
  # `cd ..` from root is ignored
  for line in lines("inputs/day07.in"):
    let split = line.splitWhitespace()
    if split[0] == "$":
      if split[1] == "cd":
        let name = split[2]
        if name == "..":
          if curDir.parentDir != nil:
            curDir = curDir.parentDir
        else:
          if curDir == nil:
            # Create root
            root = MyFile(name: name, isDir: true)
            curDir = root
            continue # Done w/the rest of this if
          if curDir.files == nil:
            new curDir.files
          var dir = curDir.files.getOrDefault(name)
          if dir == nil:
            # This shouldn't happen but we can handle it just in case
            dir = MyFile(name: name, parentDir: curDir, isDir: true)
            curDir.files[name] = dir
          curDir = dir
      # We can ignore ls lines (at least for now)
      # elif split[1] == "ls":
      #   # Do other stuff
    else:
      let name = split[1]
      if curDir.files == nil:
        new curDir.files

      if split[0] == "dir":
        let newDir = MyFile(name: name, parentDir: curDir, isDir: true)
        curDir.files[name] = newDir
      else:
        curDir.files[name] = MyFile(name: name, parentDir: curDir, isDir: false,
            size: parseInt(split[0]))

  echo "Part 1: " & $(root.part1)
  echo "Part 2: " & $(root.part2(70_000_000, 30_000_000))