Advent of Code 2022 - Day 7

Today’s challenge is quite interesting. I ended up using Zipper to solve this problem. Maybe I overengineered quite a bit.

The data structure

defmodule FSNode do
  @moduledoc """
  A node representing either a file or a dir.
  """

  @type filename :: String.t

  @type t :: %__MODULE__{
    dir?: boolean,
    size: non_neg_integer,
    children: %{optional(filename) => t}
  }

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

  @doc """
  Create a node representing an empty dir.
  """
  @spec dir() :: t
  def dir do
    %__MODULE__{dir?: true}
  end

  @doc """
  Create a node representing a file of a specific size.
  """
  @spec file(non_neg_integer) :: t
  def file(size) do
    %__MODULE__{dir?: false, size: size}
  end

  @doc """
  Adds a child to the current node if the current node is a dir.
  """
  @spec add_child!(current_node :: t, filename, child :: t) :: t
  def add_child!(%__MODULE__{dir?: true} = curr, name, %__MODULE__{} = child) do
    %{curr | size: curr.size + child.size , children: Map.put(curr.children, name, child)}
  end

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

  @doc """
  Pop the child of specific filename from the current node.
  """
  @spec pop_child!(dir :: t, filename) :: {child :: t, dir_without_child :: t}
  def pop_child!(%__MODULE__{dir?: true} = curr, name) do
    child = Map.fetch!(curr.children, name)
    {child, %{curr | children: Map.delete(curr.children, name), size: curr.size - child.size}}
  end

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

The zipper

defmodule FSZipper do
  @moduledoc """
  Zipper of FSNode tree.
  """

  @opaque t :: {
    focus :: FSNode.t,
    trail :: [{FSNode.t, FSNode.filename}]
  }

  @spec from_tree(FSNode.t) :: t
  def from_tree(tree) do
    {tree, []}
  end

  @spec cd(t, FSNode.filename) :: t
  def cd({%FSNode{dir?: true} = cwd, [{parent, name} | t]}, "..") do
    {FSNode.add_child!(parent, name, cwd), t}
  end

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

  @spec add_child(t, FSNode.filename, FSNode.t) :: t
  def add_child({%FSNode{dir?: true} = cwd, trail}, name, %FSNode{} = node) do
    {FSNode.add_child!(cwd, name, node), trail}
  end

  @spec to_tree(t) :: FSNode.t
  def to_tree({node, []}), do: node
  def to_tree(zipper), do: zipper |> cd("..") |> to_tree()
end

The parser

defmodule FSParser do
  @spec parse([String.t]) :: FSNode.t
  def parse(lines) do
    # `lines` should not contain \n and the end of each line.

    FSNode.dir()
    # 'Cuz there's no `dir /` in the input,
    # but there is `$ cd /`,
    # I just put it there by default.
    |> FSNode.add_child!("/", FSNode.dir())
    |> FSZipper.from_tree()
    |> parse(lines)
    |> FSZipper.to_tree()
  end

  @spec parse(FSZipper.t, [String.t]) :: FSZipper.t
  defp parse(zipper, []), do: zipper

  defp parse(zipper, [line | rest]) do
    case parse_line(line) do
      {:dir, name} ->
        zipper
        |> FSZipper.add_child(name, FSNode.dir())
        |> parse(rest)

      {:file, name, size} ->
        zipper
        |> FSZipper.add_child(name, FSNode.file(size))
        |> parse(rest)

      {:cd, dir} ->
        zipper
        |> FSZipper.cd(dir)
        |> parse(rest)

      _ ->
        parse(zipper, rest)
    end
  end

  @spec parse_line(String.t) ::
    :ls |
    {:cd, FSNode.filename} |
    {:dir, FSNode.filename} |
    {:file, FSNode.filename, size :: non_neg_integer} |
    :garbage
  defp parse_line("$ ls"), do: :ls

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

  defp parse_line("dir " <> name), do: {:dir, name}

  defp parse_line(<<char, _::binary>> = 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

The solution part

defmodule Day07 do
  @spec part1([String.t]) :: non_neg_integer
  def part1(input) do
    input
    |> FSParser.parse()
    |> filter1([])
    |> Enum.map(& &1.size)
    |> Enum.sum()
  end

  @total_capacity 70000000
  @target_free_capacity 30000000

  @spec part2([String.t]) :: non_neg_integer
  def part2(input) do
    fs = FSParser.parse(input)
    size_to_free = fs.size - (@total_capacity - @target_free_capacity)

    fs
    |> filter2(size_to_free, [])
    |> Enum.map(& &1.size)
    |> Enum.min()
  end

  @cap 100000

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

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

  defp filter1(%FSNode{dir?: false}, acc), do: acc

  defp filter2(%FSNode{dir?: false}, _size_to_free, acc), do: acc

  defp filter2(%FSNode{dir?: true, size: size}, size_to_free, acc)
       when size < size_to_free,
       do: acc

  defp filter2(%FSNode{dir?: true} = dir, size_to_free, acc) do
    case Enum.filter(Map.values(dir.children), & &1.size >= size_to_free) do
      [] -> [dir | acc]
      children -> Enum.reduce(children, acc, &filter2(&1, size_to_free, &2))
    end
  end
end