Aetherus

Aetherus

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

Most Liked

LostKobrakai

LostKobrakai

Reading part 1 this morning I didn’t want to deal with trees or whatever, so I just didn’t bother. Now in the evening I noticed I don’t need to deal with half of the stuff in the input. Just go the S3 route of a KV storage of {path, size} and the rest can be computed from there. I did a second pass to calculate all the directory sizes, which made answering the puzzle questions rather simple operations. In the end I was really surprised by how expressive the resulting code turned out to be.

Solution
defmodule Day7 do
  defstruct prefix: nil, files: %{}, dirs: %{}

  def parse_files(text) do
    state =
      text
      |> String.split("\n")
      |> Enum.reject(&(&1 == ""))
      |> Enum.reduce(%__MODULE__{}, fn
        "$ cd /", state ->
          %__MODULE__{state | prefix: "/"}

        "$ cd ..", state ->
          %__MODULE__{state | prefix: Path.dirname(state.prefix)}

        "$ cd " <> dir, state ->
          %__MODULE__{state | prefix: Path.join(state.prefix, dir)}

        "$ ls", state ->
          state

        "dir " <> _, state ->
          state

        file_info, state ->
          [size, filename] = String.split(file_info, " ", parts: 2)
          files = Map.put(state.files, Path.join(state.prefix, filename), String.to_integer(size))
          %__MODULE__{state | files: files}
      end)

    Enum.reduce(state.files, state, fn {path, size}, state ->
      path
      |> stream_of_parent_directories()
      |> Enum.reduce(state, fn dir, state ->
        update_in(state, [Access.key!(:dirs), Access.key(dir, 0)], &(&1 + size))
      end)
    end)
  end

  defp stream_of_parent_directories(path) do
    Stream.unfold(path, fn
      nil ->
        nil

      path ->
        case Path.dirname(path) do
          "/" -> {"/", nil}
          dir -> {dir, dir}
        end
    end)
  end

  def find_sum_of_small_folders(text) do
    text
    |> parse_files()
    |> Map.fetch!(:dirs)
    |> Map.values()
    |> Enum.filter(fn size -> size < 100_000 end)
    |> Enum.sum()
  end

  def find_size_of_smallest_directory_to_delete(text) do
    dirs =
      text
      |> parse_files()
      |> Map.fetch!(:dirs)

    total_space = 70_000_000
    total_used = dirs["/"]
    total_free = total_space - total_used
    size_update = 30_000_000
    size_to_be_freed = size_update - total_free

    dirs
    |> Map.values()
    |> Enum.filter(fn size -> size >= size_to_be_freed end)
    |> Enum.min()
  end
end
mruoss

mruoss

I went with Stream.transform/5 keeping track of a stack of directory_sizes.

Day 7 Livebook

adamu

adamu

This is the first day that broke me :exploding_head:

Not happy with my answer as I’ve clearly over-complicated it and will definitely be reading through everyone else’s. It does complete in less that 1ms though.

I did:

  1. Build up the file tree as a %{path => node} map
  2. Depth-first search to find the directories in order of fewest descendants
  3. Walk the list from 2, updating the dir sizes

https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2022/day7.exs

Where Next?

Popular in Challenges Top

Aetherus
This topic is about Day 3 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/le...
New
bismark
Took me a minute to remember my binary math :smile: :grimacing:.. import Bitwise __DIR__ |&gt; Path.join("puzzle.txt") |&gt; File.strea...
New
jkwchui
Monkeys fitted squarely as GenServers in my head. My initial problem was using cast instead of call; I imagine impolite monkeys slinging...
New
bjorng
This topic is about Day 5 of the Advent of Code 2021. We have a private leaderboard (shared with users of Erlang Forums ): https://adve...
New
bjorng
Here is my solution for day 1 of Advent of Code: defmodule Day01 do def part1(input) do all = parse(input) {first, second} = E...
New
bjorng
This topic is about Day 2 of the Advent of Code 2021. We have a private leaderboard (shared with users of Erlang Forums): https://adven...
New
bjorng
Note: This topic is to talk about Day 16 of the Advent of Code 2019. There is a private leaderboard for elixirforum members. You can joi...
New
Aetherus
I tried to use combinatorial to solve today’s puzzles but failed (my brain burned out :exploding_head:). In the end I just used brute for...
New
Aetherus
Today’s challenge is quite interesting. I ended up using Zipper to solve this problem. Maybe I overengineered quite a bit. The data stru...
New
christhekeele
Thought I’d kick today’s thread off! Parsing Enum rocks, so most of my code was actually in parsing input. ▶ Preprocessing input Part 1...
New

Other popular topics Top

New
AstonJ
Posting this to see if we can make things easier for people to get into Neovim. If you use Neovim and have a favourite distro please let ...
New
albydarned
Hello all! I am typing this post from my new MacBook Pro with the M1 chip. I’m loving it so far, and will probably use it as my daily dr...
New
shahryarjb
Hello, I have map which I want to convert it to string like this: the map: %{last_name: "tavakkoli", name: "shahryar"} the string I ne...
New
josevalim
Hi everyone, One of the features added to Elixir early on to help integration with Erlang code was the idea of overridable function defi...
New
dokuzbir
I want to highlight html closing tags when i click a html tag. That works in .html files but doesnt work for html.eex templates. How can...
New
aalberti333
As the title describes, I’m trying to run Enum.map() over a list of key/value pairs, where the value is a map. My data looks like this: ...
New
Qqwy
Original source of discussion: This topic on the Pragmatic Programmers’ Functional Web Development with Elixir, OTP, and Phoenix forum. ...
New
klo
Got a question about when to concat vs. prepending items to list then reversing to achieve appending. So i know lists boil down to [1 | ...
New
dogweather
I wrote this comment on r/haskell, and it’s not popular there. :wink: But I think I’m on to something… Haskell reminds me of Java, and e...
New

We're in Beta

About us Mission Statement