Advent of Code: Day 07

Helpers

defmodule Helpers do
  @spec read_file_contents(String.t()) :: binary()
  def read_file_contents(filename) do
    file_path = "/Users/charlie/github.com/charlieroth/advent-of-code/2022/#{filename}"

    case File.read(file_path) do
      {:ok, contents} -> contents
      {:error, _} -> raise("Failed to read file contents")
    end
  end
end

defmodule Tree do
  defstruct dir?: false, size: 0, children: %{}

  def dir(), do: %__MODULE__{dir?: true}
  def file(size), do: %__MODULE__{dir?: false, size: size}

  def add!(%__MODULE__{dir?: true} = cwd, name, %__MODULE__{} = child) do
    %{cwd | size: cwd.size + child.size, children: Map.put(cwd.children, name, child)}
  end

  def add!(%__MODULE__{dir?: false}, _, _) do
    raise ArgumentError, "Can't add children to a file"
  end

  def remove!(%__MODULE__{dir?: true} = cwd, path) do
    child = Map.fetch!(cwd.children, path)
    {child, %{cwd | size: cwd.size - child.size, children: Map.delete(cwd.children, path)}}
  end

  def remove!(%__MODULE__{dir?: false}, _name) do
    raise ArgumentError, "File has no children"
  end
end

defmodule Shell do
  def from_tree(node), do: {node, []}

  def to_tree({node, _}), do: node
  def to_tree(node), do: node |> cd("..") |> to_tree()

  def cd({%Tree{dir?: true} = cwd, [{parent, name} | t]}, "..") do
    {Tree.add!(parent, name, cwd), t}
  end

  def cd({%Tree{dir?: true} = cwd, trail}, name) do
    {%Tree{dir?: true} = child, cwd} = Tree.remove!(cwd, name)
    {child, [{cwd, name} | trail]}
  end

  def add({%Tree{dir?: true} = cwd, trail}, name, %Tree{} = node) do
    {Tree.add!(cwd, name, node), trail}
  end
end

defmodule Parser do
  def parse(cmds) do
    Tree.dir()
    |> Tree.add!("/", Tree.dir())
    |> Shell.from_tree()
    |> parse(cmds)
    |> Shell.to_tree()
  end

  def parse(shell, []), do: shell

  def parse(shell, [cmd | rest]) do
    case parse_line(cmd) do
      {:dir, name} ->
        shell
        |> Shell.add(name, Tree.dir())
        |> parse(rest)

      {:file, name, size} ->
        shell
        |> Shell.add(name, Tree.file(size))
        |> parse(rest)

      {:cd, path} ->
        shell
        |> Shell.cd(path)
        |> parse(rest)

      _ ->
        parse(shell, rest)
    end
  end

  defp parse_line("$ cd " <> path), do: {:cd, path}
  defp parse_line("$ ls"), do: {:ls}
  defp parse_line("dir " <> name), do: {:dir, name}

  defp parse_line(<> = line) when char in ?1..?9 do
    [size, name] = String.split(line, " ", parts: 2, trim: true)
    {:file, name, String.to_integer(size)}
  end

  defp parse_line(_), do: {:garbage}
end

Part 01

The device the Elves gave you has problems with more than just its communication system. You try to run a system update:

$ system-update --please --pretty-please-with-sugar-on-top
Error: No space left on device

Perhaps you can delete some files to make space for the update?

You browse around the filesystem to assess the situation and save the resulting terminal output (your puzzle 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

Given the commands and output in the example above, you can determine that the filesystem looks visually like this:

- / (dir)
  - a (dir)
    - e (dir)
      - 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)
    - j (file, size=4060174)
    - d.log (file, size=8033020)
    - d.ext (file, size=5626152)
    - k (file, size=7214296)

Since the disk is full, your first step should probably be to find directories that are good candidates for deletion. To do this, you need to determine the total size of each directory. The total size of a directory is the sum of the sizes of the files it contains, directly or indirectly. (Directories themselves do not count as having any intrinsic size.)

To begin, find all of the directories with a total size of at most 100000, then calculate the sum of their total sizes. In the example above, these directories are a and e; the sum of their total sizes is 95437 (94853 + 584). (As in this example, this process can count files more than once!)

Find all of the directories with a total size of at most 100000

What is the sum of the total sizes of those directories?

defmodule PartOne do
  @cap 100_000
  def solution(input) do
    input
    |> String.split("\n", trim: true)
    |> Parser.parse()
    |> filter([])
  end

  defp filter(%Tree{dir?: true, size: size, children: children}, acc) when size > @cap do
    children
    |> Map.values()
    |> Enum.filter(& &1.dir?)
    |> Enum.reduce(acc, &filter/2)
  end

  defp filter(%Tree{dir?: true} = node, acc) do
    node.children
    |> Map.values()
    |> Enum.filter(& &1.dir?)
    |> Enum.reduce([node | acc], &filter/2)
  end

  defp filter(%Tree{dir?: false}, acc), do: acc
end

~S"""
$ 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
"""
|> PartOne.solution()

Part 02

aasdf