Day 07
Mix.install([
{:kino, "~> 0.8.0"}
])
Puzzle Input
area = Kino.Input.textarea("Puzzle Input")
puzzle_input = Kino.Input.read(area)
example_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
"""
Common
defmodule TerminalParser do
def parse_node(node) do
case node do
"dir " <> name ->
{:directory, name}
file ->
[size, name] = String.split(file, " ", parts: 2)
{:file, name, size |> Integer.parse() |> elem(0)}
end
end
def parse_command(lines) do
case lines do
["cd " <> destination] ->
{:cd, destination}
["ls" | nodes] ->
{:scan, Enum.map(nodes, &parse_node/1)}
end
end
end
ExUnit.start(autorun: false)
defmodule TerminalParserTests do
use ExUnit.Case, async: true
test "parse dir" do
assert TerminalParser.parse_node("dir a") == {:directory, "a"}
end
test "parse file" do
assert TerminalParser.parse_node("14848514 b.txt") == {:file, "b.txt", 14_848_514}
end
test "parse cd" do
assert TerminalParser.parse_command(["cd /"]) == {:cd, "/"}
end
test "parse ls" do
assert TerminalParser.parse_command([
"ls",
"dir a",
"14848514 b.txt",
"8504156 c.dat",
"dir d"
]) ==
{:scan,
[
{:directory, "a"},
{:file, "b.txt", 14_848_514},
{:file, "c.dat", 8_504_156},
{:directory, "d"}
]}
end
end
ExUnit.run()
commands =
puzzle_input
|> String.split("$ ", trim: true)
|> Enum.map(fn command ->
command |> String.split("\n", trim: true) |> TerminalParser.parse_command()
end)
defmodule FileSystem do
defstruct pwd: [], content: %{}
def new(), do: %FileSystem{}
def execute(fs, cmd) do
case cmd do
{:cd, dir} ->
cd(fs, dir)
{:scan, nodes} ->
scan(fs, nodes)
end
end
def size(fs, {:directory, _} = dir) do
fs
|> cd(dir)
|> size()
end
def size(_fs, {:file, _name, size}) do
size
end
def size(fs) do
fs
|> ls()
|> Enum.reduce(0, fn node, bytes ->
bytes + size(fs, node)
end)
end
def scan(fs, nodes) do
%{fs | content: Map.put(fs.content, {:directory, fs.pwd}, nodes)}
end
def cd(fs, dir) do
case dir do
"/" ->
%{fs | pwd: []}
{:directory, []} ->
%{fs | pwd: []}
".." ->
pwd =
case fs.pwd do
[_ | tail] -> tail
[] -> []
end
%{fs | pwd: pwd}
{:directory, path} when is_list(path) ->
%{fs | pwd: path ++ fs.pwd}
{:directory, name} when is_binary(name) ->
%{fs | pwd: [name | fs.pwd]}
name ->
%{fs | pwd: [name | fs.pwd]}
end
end
def ls(fs) do
Map.get(fs.content, {:directory, fs.pwd}, [])
end
def dirs(fs) do
Map.keys(fs.content)
end
end
ExUnit.start(autorun: false)
defmodule FileSystemTests do
use ExUnit.Case, async: true
describe "execute" do
test "cd" do
fs =
%FileSystem{}
|> FileSystem.execute({:cd, "a"})
assert fs == %FileSystem{content: %{}, pwd: ~w(a)}
end
test "scan" do
fs =
%FileSystem{}
|> FileSystem.execute({:cd, "a"})
|> FileSystem.execute(
{:scan,
[
{:directory, "a"},
{:file, "b.txt", 14_848_514},
{:file, "c.dat", 8_504_156},
{:directory, "d"}
]}
)
assert fs == %FileSystem{
content: %{
{:directory, ["a"]} => [
{:directory, "a"},
{:file, "b.txt", 14_848_514},
{:file, "c.dat", 8_504_156},
{:directory, "d"}
]
},
pwd: ["a"]
}
end
end
describe "cd" do
test "moves to directory" do
fs =
%FileSystem{}
|> FileSystem.cd("a")
|> FileSystem.cd({:directory, "b"})
|> FileSystem.cd({:directory, ["c", "e"]})
assert fs == %FileSystem{content: %{}, pwd: ~w(c e b a)}
end
test "pops from directory" do
fs =
%FileSystem{}
|> FileSystem.cd({:directory, ["b", "a"]})
|> FileSystem.cd("..")
assert fs == %FileSystem{content: %{}, pwd: ~w(a)}
end
test "pops to root" do
fs =
%FileSystem{}
|> FileSystem.cd({:directory, ["b", "a"]})
|> FileSystem.cd("/")
assert fs == %FileSystem{content: %{}, pwd: []}
end
end
test "scans contens" do
fs =
%FileSystem{}
|> FileSystem.cd("a")
|> FileSystem.scan([
{:directory, "a"},
{:file, "b.txt", 14_848_514},
{:file, "c.dat", 8_504_156},
{:directory, "d"}
])
assert fs == %FileSystem{
content: %{
{:directory, ["a"]} => [
{:directory, "a"},
{:file, "b.txt", 14_848_514},
{:file, "c.dat", 8_504_156},
{:directory, "d"}
]
},
pwd: ["a"]
}
end
test "dirs" do
fs = %FileSystem{
pwd: [],
content: %{
{:directory, []} => [
{:directory, "a"},
{:file, "b.txt", 14_848_514},
{:file, "c.dat", 8_504_156},
{:directory, "d"}
],
{:directory, ["a"]} => [
{:directory, "e"},
{:file, "f", 29116},
{:file, "g", 2557},
{:file, "h.lst", 62596}
],
{:directory, ["d"]} => [
{:file, "j", 4_060_174},
{:file, "d.log", 8_033_020},
{:file, "d.ext", 5_626_152},
{:file, "k", 7_214_296}
],
{:directory, ["e", "a"]} => [{:file, "i", 584}]
}
}
assert FileSystem.dirs(fs) == [
{:directory, []},
{:directory, ["a"]},
{:directory, ["d"]},
{:directory, ["e", "a"]}
]
end
test "dir size" do
fs = %FileSystem{
pwd: [],
content: %{
{:directory, []} => [
{:directory, "a"},
{:file, "b.txt", 14_848_514},
{:file, "c.dat", 8_504_156},
{:directory, "d"}
],
{:directory, ["a"]} => [
{:directory, "e"},
{:file, "f", 29116},
{:file, "g", 2557},
{:file, "h.lst", 62596}
],
{:directory, ["d"]} => [
{:file, "j", 4_060_174},
{:file, "d.log", 8_033_020},
{:file, "d.ext", 5_626_152},
{:file, "k", 7_214_296}
],
{:directory, ["e", "a"]} => [{:file, "i", 584}]
}
}
assert FileSystem.size(fs, {:directory, ["e", "a"]}) == 584
assert FileSystem.size(fs, {:directory, ["a"]}) == 94853
assert FileSystem.size(fs, {:directory, ["d"]}) == 24_933_642
assert FileSystem.size(fs, {:directory, []}) == 48_381_165
end
end
ExUnit.run()
fs =
commands
|> Enum.reduce(FileSystem.new(), &FileSystem.execute(&2, &1))
|> FileSystem.cd("/")
Part One
fs
|> FileSystem.dirs()
|> Stream.map(&FileSystem.size(fs, &1))
|> Stream.filter(fn size -> size <= 100_000 end)
|> Enum.sum()
Part Two
total_size = 70_000_000
update_size = 30_000_000
current_size = FileSystem.size(fs)
reclaim_size = update_size + current_size - total_size
fs
|> FileSystem.dirs()
|> Stream.map(&FileSystem.size(fs, &1))
|> Enum.sort()
|> Enum.find(fn size -> size >= reclaim_size end)
