jack's advent of code 2022 ramblings

given the sample 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

assuming input is the above as one big string,

raw_session =
  input
  |> String.split("$")
  |> tl
  |> Enum.map(&String.trim/1)
  |> Enum.map(&String.split(&1, "\n"))

split on $ breaks each command into its own (initially messy) chunk

also leaves an empty string in a list, so we pluck the tail via tl of the linked list to remove it

trim the lines, and split them on \n (because ls commands produce multiple lines below them)

[
  ["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"]
]

we are left with a nicer-to-parse list of commands, that i refer to as a session

session =
  raw_session
  |> Enum.map(fn raw_command ->
    case length(raw_command) do
      1 -> {:cd, raw_command |> Enum.at(0) |> String.split(" ") |> Enum.at(1)}
      _ -> {:ls, raw_command |> Enum.drop(1) |> Enum.map(&String.split(&1, " "))}
    end
  end)

we want to clean up this raw session into something nicer with atoms & lists, so go over each of the previously created commands, and depending on the length of them, create even nicer looking commands based on the 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"]]
]

look at that, so pretty

utils

defmodule DeviceFS do
  def dir_to_string(dir), do: "/#{dir |> Enum.reverse() |> tl |> Enum.join("/")}"

  def expand_contents(dir, contents) do
    Enum.map(contents, fn content ->
      case content do
        ["dir", name] -> ["dir", dir_to_string([name | dir])]
        _ -> content
      end
    end)
  end

  def generate_fs(fs, curdir, [{:cd, ".."} | session]) do
    generate_fs(fs, Enum.drop(curdir, 1), session)
  end

  def generate_fs(fs, curdir, [{:cd, dir} | [{:ls, contents} | session]]) do
    dir = [dir | curdir]
    fs = Map.put(fs, dir_to_string(dir), expand_contents(dir, contents))
    generate_fs(fs, dir, session)
  end

  def generate_fs(fs, _curdir, []), do: fs

  def generate_fs(session), do: generate_fs(%{}, [], session)
end

ah

so this is the day where i whip out [tail recursion], and [multiple clauses]

its time to get funky in here

but before explaining this, it would probably be first better to show what this does first

fs = DeviceFS.generate_fs(session)

pass in our session (the cleaned up list of commands) to generate_fs/1`

%{
  "/" => [["dir", "/a"], ["14848514", "b.txt"], ["8504156", "c.dat"], ["dir", "/d"]],
  "/a" => [["dir", "/a/e"], ["29116", "f"], ["2557", "g"], ["62596", "h.lst"]],
  "/a/e" => [["584", "i"]],
  "/d" => [["4060174", "j"], ["8033020", "d.log"], ["5626152", "d.ext"], ["7214296", "k"]]
}

and we get this!

now this isn’t a tree, but a mapping from each directory, to its contents

i’ll explain later how we use this, but first, how do we go from the commands to this map?

first, lets see how we even enter this module

def generate_fs(session), do: generate_fs(%{}, [], session)

this sneaky little one line function is our entrance into the recursive function, since generate_fs needs 4 arguments (and we initalize them all here instead of relying on the caller to set this up)

the first argument here will become our map of directories -> contents, but for now we make it an empty map

the second argument is what directory we are currently in (represented as a linked list), also assumed to be empty initially

and then, our sessions, untouched from the input

def generate_fs(fs, curdir, [{:cd, dir} | [{:ls, contents} | session]]) do
  dir = [dir | curdir]
  fs = Map.put(fs, dir_to_string(dir), expand_contents(dir, contents))
  generate_fs(fs, dir, session)
end

there are multiple definitions of generate_fs/3, and pattern matching is used to figure out which one to use

elixir will try each one in order, but this will end up being the first one hit, since the first line of the input data is cd /

we expect there to be a tupple {:cd, ...} as the head of the list, but since we need to handle any dir name, we leave that a variable named dir which will be an argument to the function

we then expect the tail of the linked list node in the session to be a linked node referencing a {:ls, ...} command

again, we don’t care whats associated with this command, so we set it as the variable contents

we also set the tail of this inner linked list node to be session, since after having ran through the body of this function we have consumed these commands, and can continue onto the next session operations after the next tail call

dir = [dir | curdir]

the first line of the function appends the dir we have cd‘d into to the dir we came from

fs = Map.put(fs, dir_to_string(dir), expand_contents(dir, contents))

we then update our fs variable (the map from filesystem path to contents, using two utility methods)

dir_to_string/1

def dir_to_string(dir), do: "/#{dir |> Enum.reverse() |> tl |> Enum.join("/")}"

dir_to_string/1 will take in a directory (which we represent as a linked list), reverse it, trim off the top, and join on /

# ...
  "/a/e" => [["584", "i"]],
# ...

this produced the key of the map we are generating

expand_contents/2

def expand_contents(dir, contents) do
  Enum.map(contents, fn content ->
    case content do
      ["dir", name] -> ["dir", dir_to_string([name | dir])]
      _ -> content
    end
  end)
end

expand contents

isn’t too busy, just need to ensure that when we save directories to our ‘filesystem’, that they are the full fat directories /a/b/c and not just c

the sample input doesn’t have any duplicate entries, but (at least my) puzzle input does

i didn’t have this function (or dir_to_string/1) initially, and it caused me to get the correct answer for the sample, but incorrect for part 1 .-.

def generate_fs(fs, curdir, [{:cd, ".."} | session]) do
  generate_fs(fs, Enum.drop(curdir, 1), session)
end

our second (first within the code order-wise) generate_fs/3 clause is the case where we go up a directory, so we simply drop one value from the current directory linked list

def generate_fs(fs, _curdir, []), do: fs

lastly, the final generate_fs/3 clause, both the final to be covered, the final order wise, and also the last clause before we’ve finished calculating fs, is when the session is empty

i.e. we’ve exuasted the commands, therefore just return fs

ok, back to the actual size bit

%{
  "/" => [["dir", "/a"], ["14848514", "b.txt"], ["8504156", "c.dat"], ["dir", "/d"]],
  "/a" => [["dir", "/a/e"], ["29116", "f"], ["2557", "g"], ["62596", "h.lst"]],
  "/a/e" => [["584", "i"]],
  "/d" => [["4060174", "j"], ["8033020", "d.log"], ["5626152", "d.ext"], ["7214296", "k"]]
}

reminder, we just generated this, as the variable fs

defmodule DeviceFSUtils do
  def get_size_of_dir(fs, dir) do
    dir = Map.get(fs, dir)

    sizes =
      for item <- dir do
        case item do
          ["dir", name] -> get_size_of_dir(fs, name)
          [number, _name] -> String.to_integer(number)
        end
      end

    Enum.sum(sizes)
  end

  def get_sizes_of_dirs(fs) do
    Map.keys(fs) |> Enum.map(&get_size_of_dir(fs, &1))
  end
end

another module! this one is just for figuring out the sizes of given directories, or all directories

i won’t explain this one, and leave it as exercise to the reader, if you wish

it uses recursion but its a lot less scary

part 1

DeviceFSUtils.get_sizes_of_dirs(fs)
|> Enum.filter(&(&1 <= 100_000))
|> Enum.sum() # -> 95437

use our new module to get the size of every dir

then filter them by values less than the threshold

then sum them

part 2

total_size_of_fs = 70_000_000
space_needed_to_update = 30_000_000

size_of_root_dir = DeviceFSUtils.get_size_of_dir(fs, "/")
# ^ 48381165 ^

define some specs of the fs we are on, the upgrade, and the size of the root dir (using our own util again)

space_to_free_up = size_of_root_dir + space_needed_to_update - total_size_of_fs
# ^ 8381165 ^

figure out the space we need to free up, based on the above calculations

DeviceFSUtils.get_sizes_of_dirs(fs)
|> Enum.filter(&(&1 >= space_to_free_up))
|> Enum.min() # -> 24933642

do more filtering, but this time get the min values

nice

the full solution can be found [here]