Advent of Code 2022 - Day 7

Mix.install([:kino, {:kino_aoc, git: "https://github.com/ljgago/kino_aoc"}])

Input

test_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
"""

{:ok, puzzle_input} = KinoAOC.download_puzzle("2022", "7", System.fetch_env!("LB_AOC_SESSION"))

input_field =
  Kino.Input.select("input", [
    {test_input, "test_input"},
    {puzzle_input, "puzzle_input"}
  ])

Parse & Prep

Approach

We traverse the directory tree and keep track of directory sizes of the directory we are currently in and all their ancestors. This is represented by a stack of sizes where the size of the current directory is at the top of the stack and the ancestor’s sizes below.

If we are inside /a/b/c, the stack looks as follows:

|size_of_c|
|size_of_b|
|size_of_a|
|size_of_/|

Implementation

We can ignore $ ls instructions and dir x listings so we reject them. Finally, since after running our input we end up in some directory deep down the tree, we concatenate our stream with an infinite stream of $ cd .. instructions. The stream will be halted by the transformer later. We then transform the remaining input stream to a stream of directory sizes as follows:

initial accumulator

We begin our stack with an entry for the root directory (/) with size 0:

reducer

For the remaining items in our input stream, here is what we do:

• $ cd DIR - When entering a directory, we push a 0 on top of the stack.
• 312412 filename - When we see a filename listing, we add its size to the number on top of the stack, representing the size of the current directory.
• $ cd .. - When leaving a directory, we pop the leaving directory’s size from the stack, emit it and add it to the parent directory’s size which is now on top of the stack (again).

This transformation gives us a stream of directory sizes which we implicitely convert to a list in both parts later on.

all_dir_sizes =
  input_field
  |> Kino.Input.read()
  |> String.split("\n", trim: true)
  |> Stream.reject(&amp;(&amp;1 == "$ ls" || match?("dir " <> _, &amp;1)))
  |> Stream.concat(Stream.repeatedly(fn -> "$ cd .." end))
  |> Stream.transform(
    # initial accumulator
    [0],

    # reducer
    fn
      "$ cd ..", [_last] ->
        {:halt, nil}

      "$ cd ..", [leaving_size, parent_size | stack] ->
        {[leaving_size], [parent_size + leaving_size | stack]}

      "$ cd " <> _, stack ->
        {[], [0 | stack]}

      file, [size | stack] ->
        [filesize, _] = String.split(file, " ")
        {[], [size + String.to_integer(filesize) | stack]}
    end
  )
  |> Enum.to_list()
  |> Enum.reverse()

Part 1

all_dir_sizes
|> Enum.filter(&amp;(&amp;1 <= 100_000))
|> Enum.sum()

Part 2

disk_size_to_free_up = 30_000_000 + hd(all_dir_sizes) - 70_000_000
all_dir_sizes 
|> Enum.filter(&(&1 >= disk_size_to_free_up)) 
|> Enum.min()