[Advent Of Code 2022] Day 7: No Space Left On Device [SPOILERS]

Programming
1

AoC 2022/07

This one was a bit of a surprise! I didn’t expect to need to break out the parser. I did enjoy it, though! And, after solving it, I realized there’s some parsing shortcuts I could take and some info which doesn’t actually require tracking.

Python Solution 
class DirectoryEntry:
    def __init__(self, pwd: pathlib.Path, data: dict[pathlib.Path, DirectoryEntry]):
        self.pwd = pwd
        self.dirs: set[str] = set()
        self.size = 0
        self.data = data

    def rsize(self) -> int:
        return self.size + sum(self.data[self.pwd / child].rsize() for child in self.dirs)

class Solution:
    def directory_data(self, stdout: list[str]) -> dict[pathlib.Path, DirectoryEntry]:
        dirs: dict[pathlib.Path, DirectoryEntry] = {}
        pwd = ROOT
        for line in stdout:
            if line == "$ cd /":
                pwd = ROOT
            elif line == "$ cd ..":
                pwd = pwd.parent
            elif line.startswith("$ cd"):
                pwd /= line.split()[-1]
            elif line == "$ ls":
                dirs[pwd] = DirectoryEntry(pwd, dirs)
            else:  # ls output
                type_or_size, name = line.split()
                if type_or_size == "dir":
                    dirs[pwd].dirs.add(name)
                else:
                    dirs[pwd].size += int(type_or_size)
        return dirs

    def part1(self, parsed_input: InputType) -> int:
        dirs = self.directory_data(parsed_input)
        return sum(
            directory.rsize()
            for directory in dirs.values()
            if directory.rsize() <= 100000
        )

    def part2(self, parsed_input: InputType) -> int:
        dirs = self.directory_data(parsed_input)
        to_free = 30000000 - 70000000 + dirs[ROOT].rsize()
        return min(
            directory.rsize()
            for directory in dirs.values()
            if directory.rsize() >= to_free
        )
2
Ruby Solution 
filesystem = Hash.new(0)
current_path = ['/']

File.readlines('inputs/07.txt', chomp: true).each do |line|
  case line.split
  in ['$', 'cd', '/']
    current_path = ['/']
  in ['$', 'cd', '..']
    current_path.pop
  in ['$', 'cd', dir]
    current_path.push(dir)
  in [filesize, *] if filesize =~ /\d+/
    path = current_path.dup

    while path.any?
      filesystem[path.join('/')] += filesize.to_i
      path.pop
    end
  else
    next
  end
end

a = filesystem.values.select { |size| size <= 100_000 }.sum
b = filesystem.values.select { |size| 70_000_000 - filesystem['/'] + size >= 30_000_000 }.min
3

I realized I was way overcomplicating things…

Summary 
, puzzle_input: str) -> InputType:
        dirs = collections.defaultdict(int)
        pwd = ROOT
        for line in puzzle_input.splitlines():
            match (words := line.split()):
                case ["$", "cd", ".."]:
                    pwd = pwd.parent
                case ["$", "cd", _]:
                    pwd /= line.split()[-1]
                case _ if words[0].isdigit():
                    size = int(words[0])
                    dirs[pwd] += size
                    for p in pwd.parents:
                        dirs[p] += size
        return dirs

   def part1(self, dirs: InputType) -> int:
        return sum(
            size
            for size in dirs.values()
            if size <= 100000
        )

    def part2(self, dirs: InputType) -> int:
        to_free = 30000000 - 70000000 + dirs[ROOT]

        return min(
            size
            for size in dirs.values()
            if size >= to_free
        )
4

Ugliest code so far this year for me. Not totally happy with the strategy I used and with my use of Typescript itself. But it has been a busy day and tiring day, so I’ll probably call it good enough for now and revise this solution in later days.

Discussion about strategy used (spoilers)

Representing the filesystem as a hashmap is a good idea. In the end, I took advantage of the fact the input is basically traversing directories depth-first, which meant that my code would only need to keep track of a stack and when a cd .. came, I would only need to pop from the stack and update the size of the parent directory, doing the computations for part 1 when that pop happens. My idea in doing this was to keep only in memory what I absolutely needed. Then part 2 kinda threw all of that under the bus by encouraging to keep track of every directory and by making me dealing with with values leftover in the stack.

Typescript solution 
type Dir = [name: string, size: number];

const FILESYSTEM_TOTAL_SPACE = 70000000;
const TARGET_UNUSED_SPACE = 30000000;

export function parse(input: string): State {
  const lines = nonEmptyLines(input).map((l) => l.split(" "));

  const stack = new Array<Dir>();
  stack.push(["/", 0]);

  let total_used = 0;
  const dirs = new Array<Dir>();

  let sumUnder100k = 0;
  for (const line of lines) {
    const fst = line[0];

    switch (fst) {
      // deno-lint-ignore no-case-declarations
      case "$":
        const [cmd, arg] = line.slice(1);
        if (cmd == "cd" && arg == "/") {
          // ignore root
          continue;
        } else if (cmd == "cd" && arg == "..") {
          // we know we are done with this directory
          const [name, size] = stack.pop()!;
          dirs.push([name, size]);

          // update parent size with the size of
          // the directory we just visited
          stack[stack.length - 1][1] += size;
          if (size <= 100000) {
            sumUnder100k += size;
          }
          continue;
        } else if (cmd == "cd") {
          stack.push([arg, 0]);
          continue;
        }
        break;
      case "dir":
        continue;
      // deno-lint-ignore no-case-declarations
      default:
        // line representing a file in the current directory
        const size = parseInt(line[0], 10);
        stack[stack.length - 1][1] += size;
        total_used += size;
    }
  }

  // deal with items still in the stack
  let rest = 0;
  for (const [name, size] of stack.reverse()) {
    dirs.push([name, size + rest]);
    rest += size;
  }

  const actual_unused = FILESYSTEM_TOTAL_SPACE - total_used;
  const space_to_free = TARGET_UNUSED_SPACE - actual_unused;

  const minDir = dirs
    .filter(([_, size]) => size >= space_to_free)
    .sort((a, b) => a[1] - b[1]);

  return { part1: sumUnder100k, part2: minDir[0][1] };
}