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)
}

really fun, first one that felt like a legit challenge.

tricky part of parsing is that you have two "modes" of consuming lines, one looking for cd and ls commands and one for consuming ls output. I solved that by treating the lines as a queue rather than just iterating them in a foreach loop, and having a 2nd nested loop to consume ls output from the line queue. important subtlety here is when you encounter the first non-matching line, to make sure to put it back into its place at the front of the queue (the appendleft call).

for computing the total sizes I implemented a "normal" recursive algorithm; for finding directories matching what the problem wanted I did the "recursive algorithm as an iterative loop" trick. if you're not very comfortable with recursion it can be useful to study both approaches, because every recursive algorithm can be implemented non-recursively, and often the iterative implementation is easier to think about / debug.

from collections import deque
import re


CD_RE = re.compile(r'\$ cd (.+)')
LS_RE = re.compile(r'\$ ls')
DIR_RE = re.compile(r'dir (.+)')
FILE_RE = re.compile(r'(\d+) (.+)')


class Directory:
	def __init__(self, name, parent):
		self.name = name
		self.parent = parent
		self.entries = {}
		self.total_size = 0

	def prettyprint(self, pad=''):
		print(f'{pad}- {self.name} (dir, total_size={self.total_size})')
		for name, entry in sorted(self.entries.items()):
			child_padding = pad + '  '
			if isinstance(entry, int):
				print(f'{child_padding}- {name} (file, size={entry})')
			else:
				entry.prettyprint(child_padding)

	@staticmethod
	def parse(lines):
		root_dir = Directory(name='/', parent=None)
		current_dir = root_dir

		lines = deque(lines)
		while lines:
			line = lines.popleft()

			cd_match = CD_RE.match(line)
			ls_match = LS_RE.match(line)
			if cd_match:
				target = cd_match.group(1)
				if target == '/':
					current_dir = root_dir
				elif target == '..':
					current_dir = current_dir.parent
				else:
					current_dir = current_dir.entries[target]

			elif ls_match:
				while lines:
					line = lines.popleft()
					dir_match = DIR_RE.match(line)
					file_match = FILE_RE.match(line)
					if dir_match:
						name = dir_match.group(1)
						new_dir = Directory(name=name, parent=current_dir)
						current_dir.entries[name] = new_dir
					elif file_match:
						size, name = int(file_match.group(1)), file_match.group(2)
						current_dir.entries[name] = size
					else:
						lines.appendleft(line)
						break

		return root_dir

	def assign_total_sizes(self):
		total = 0
		for name, entry in self.entries.items():
			if isinstance(entry, int):
				total += entry
			else:
				entry.assign_total_sizes()
				total += entry.total_size

		self.total_size = total


with open('07.txt') as input_file:
	lines = input_file.readlines()

root_directory = Directory.parse(lines)
root_directory.assign_total_sizes()
root_directory.prettyprint()

total = 0

pending = deque()
pending.append(root_directory)

while pending:
	item = pending.popleft()
	if isinstance(item, Directory):
		pending.extend(item.entries.values())

		if item.total_size < 100000:
			total += item.total_size

print(total)

for shits and giggles I also implemented a recursive prettyprint function that matches the output from the problem statement, and adds in the total computed size of each directory:

- / (dir, total_size=48381165)
  - a (dir, total_size=94853)
    - e (dir, total_size=584)
      - i (file, size=584)
    - f (file, size=29116)
    - g (file, size=2557)
    - h.lst (file, size=62596)
  - b.txt (file, size=14848514)
  - c.dat (file, size=8504156)
  - d (dir, total_size=24933642)
    - d.ext (file, size=5626152)
    - d.log (file, size=8033020)
    - j (file, size=4060174)
    - k (file, size=7214296)

--- aoc07a.py   2022-12-06 22:05:34.232327237 -0800
+++ aoc07b.py   2022-12-06 22:05:17.718218543 -0800
@@ -81,7 +81,13 @@
 root_directory.assign_total_sizes()
 root_directory.prettyprint()
 
-total = 0
+disk_size = 70_000_000
+required_free_space = 30_000_000
+
+target_disk_size = disk_size - required_free_space
+to_be_deleted = root_directory.total_size - target_disk_size
+
+best_directory = disk_size
 
 pending = deque()
 pending.append(root_directory)
@@ -91,7 +97,7 @@
        if isinstance(item, Directory):
                pending.extend(item.entries.values())
 
-               if item.total_size < 100000:
-                       total += item.total_size
+               if to_be_deleted < item.total_size < best_directory:
+                       best_directory = item.total_size
 
-print(total)
+print(best_directory)

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))