AoC 2022 Day 7

Mix.install([
  {:kino, "~> 0.7.0"},
  {:kino_vega_lite, "~> 0.1.6"},
  {:nimble_parsec, "~> 1.2"}
])

Input

input_field = Kino.Input.textarea("Puzzle input")

input = Kino.Input.read(input_field)

Part 1

defmodule Parser do
  import NimbleParsec

  filename = ascii_string([?a..?z, ?.], min: 1)
  newline = ignore(string("\n"))

  cd =
    ignore(string("$ cd "))
    |> choice([
      string("/"),
      string(".."),
      filename
    ])
    |> concat(newline)
    |> tag(:cd)

  file =
    integer(min: 1)
    |> ignore(string(" "))
    |> concat(filename)
    |> tag(:file)

  dir =
    ignore(string("dir "))
    |> concat(filename)
    |> tag(:dir)

  listing =
    ignore(string("$ ls\n"))
    |> repeat(
      choice([
        dir,
        file
      ])
      |> optional(newline)
    )
    |> tag(:listing)

  defparsec(:parse_tree, repeat(choice([listing, cd, newline])))
  defparsec(:debug, file)
end

{:ok, tree, "", _, _, _} = Parser.parse_tree(input)

defmodule TreeParser do
  defstruct [:current_path, :parsed_tree]

  defp add_path([_current | rest], ".."), do: rest
  defp add_path(path, dir), do: [dir | path]

  def add_entry({:dir, [name]}, folder), do: Map.put(folder, name, %{})
  def add_entry({:file, [size, name]}, folder), do: Map.put(folder, name, size)

  def parse([], %TreeParser{parsed_tree: parsed_tree}), do: parsed_tree

  def parse(
        [{:cd, [dir]} | tree],
        %TreeParser{current_path: current_path} = state
      ) do
    current_path = add_path(current_path, dir)
    parse(tree, %{state | current_path: current_path})
  end

  def parse(
        [{:listing, entries} | tree],
        %TreeParser{
          current_path: current_path,
          parsed_tree: parsed_tree
        } = state
      ) do
    access_path = Enum.reverse(current_path)

    folder = Enum.reduce(entries, %{}, &add_entry/2)
    new_parsed_tree = put_in(parsed_tree, access_path, folder)

    parse(tree, %{state | parsed_tree: new_parsed_tree})
  end

  def parse(tree) do
    parse(tree, %TreeParser{current_path: [], parsed_tree: %{}})
  end
end

parsed = TreeParser.parse(tree)

defmodule FolderEntry do
  defstruct [:name, :size, :children]

  def parse({name, children}) do
    children = children |> PathEntries.parse_children()
    size = sum_size(children)
    %FolderEntry{name: name, size: size, children: children}
  end

  def sum_size(children) do
    children
    |> Enum.map(fn child -> child.size end)
    |> Enum.sum()
  end
end

defmodule FileEntry do
  defstruct [:name, :size]

  def parse({name, size}) when is_integer(size), do: %FileEntry{name: name, size: size}
end

defmodule PathEntries do
  def parse_child({_, size} = entry) when is_integer(size), do: FileEntry.parse(entry)
  def parse_child(entry), do: FolderEntry.parse(entry)

  def parse_children(children) do
    children
    |> Enum.map(&parse_child/1)
  end

  def get_children_below_size(%FileEntry{size: s} = entry, size_lim) when s <= size_lim,
    do: [entry]

  def get_children_below_size(%FileEntry{size: _too_large}, _), do: []

  def get_children_below_size(%FolderEntry{size: s, children: c} = entry, size_lim) do
    case s do
      s when s <= size_lim -> [entry | Enum.flat_map(c, &amp;get_children_below_size(&amp;1, size_lim))]
      _ -> Enum.flat_map(c, &amp;get_children_below_size(&amp;1, size_lim))
    end
  end
end

folder = FolderEntry.parse({"/", parsed["/"]})

folder
|> PathEntries.get_children_below_size(100_000)
|> Enum.filter(&match?(%FolderEntry{}, &1))
|> Enum.map(& &1.size)
|> Enum.sum()

Part 2

defmodule PathEntries2 do
  def get_children_above_size(%FileEntry{size: s} = entry, size_lim) when s >= size_lim,
    do: [entry]

  def get_children_above_size(%FileEntry{size: _too_large}, _), do: []

  def get_children_above_size(%FolderEntry{size: s, children: c} = entry, size_lim) do
    case s do
      s when s >= size_lim -> [entry | Enum.flat_map(c, &get_children_above_size(&1, size_lim))]
      _ -> Enum.flat_map(c, &get_children_above_size(&1, size_lim))
    end
  end
end

total_disk = 70_000_000
needed_space = 30_000_000
curr_free_space = total_disk - folder.size
delete_min = needed_space - curr_free_space

PathEntries2.get_children_above_size(folder, delete_min)
|> Enum.map(& &1.size)
|> Enum.min()