The day 7 challenge talks about trees! File trees that is.

The temptation to solve it before starting to write this article so I don't look silly is high, but I'm explicitly not doing so, so that we can bang our collective heads against any walls at the same time, and see how we can get out of it! Trees are serious business!

## Part 1

The sample input looks like this:

$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


And it represents a shell session from someone trying to find out which directories to delete to make space for a system upgrade.

The answer we're supposed to give is the sum of the total sizes of directories with a total size of at most 100000. In our example, e has size 584, and a has size 94853, and so the answer would be 95437.

Note that, yes, part 1 seems counterproductive when it comes to "saving space", since it finds "small enough" directories. It also does count some files twice, and it's important to note that directories themselves (or "empty directories", if you prefer to think of it that way) don't count towards the size total: only the files they contain.

So, confusing and a bit contrived, must be a coding puzzle!

## Parsing

Before we tackle any tree-like structures, let's first write a nom parser for the input.

Shell session
$cargo add nom@7 (cut)  Because we're parsing (utf-8) paths, let's pull in the camino crate so we can have its Utf8PathBuf type: Shell session $ cargo add camino
(cut)

Rust code
use camino::Utf8PathBuf;
use nom::{bytes::complete::take_while1, combinator::map, IResult};

fn parse_path(i: &str) -> IResult<&str, Utf8PathBuf> {
map(
take_while1(|c: char| "abcdefghijklmnopqrstuvwxyz./".contains(c)),
Into::into,
)(i)
}


Then we can parse our commands:

Rust code
#[derive(Debug)]
struct Ls;

fn parse_ls(i: &str) -> IResult<&str, Ls> {
map(tag("ls"), |_| Ls)(i)
}

#[derive(Debug)]
struct Cd(Utf8PathBuf);

fn parse_cd(i: &str) -> IResult<&str, Cd> {
map(preceded(tag("cd "), parse_path), Cd)(i)
}

#[derive(Debug)]
enum Command {
Ls(Ls),
Cd(Cd),
}

fn parse_command(i: &str) -> IResult<&str, Command> {
let (i, _) = tag("$")(i)?; alt((map(parse_ls, Command::Ls), map(parse_cd, Command::Cd)))(i) }  And entries: Rust code #[derive(Debug)] enum Entry { Dir(Utf8PathBuf), File(u64, Utf8PathBuf), } fn parse_entry(i: &str) -> IResult<&str, Entry> { let parse_file = map( separated_pair(nom::character::complete::u64, tag(" "), parse_path), |(size, path)| Entry::File(size, path), ); let parse_dir = map(preceded(tag("dir "), parse_path), Entry::Dir); alt((parse_file, parse_dir))(i) }  And finally, lines: Rust code #[derive(Debug)] enum Line { Command(Command), Entry(Entry), } fn parse_line(i: &str) -> IResult<&str, Line> { alt(( map(parse_command, Line::Command), map(parse_entry, Line::Entry), ))(i) }  And finally, let's see what this does on the sample input: Rust code use camino::Utf8PathBuf; use nom::{ branch::alt, bytes::complete::{tag, take_while1}, combinator::{all_consuming, map}, sequence::{preceded, separated_pair}, Finish, IResult, }; fn main() { let lines = include_str!("sample-input.txt") .lines() .map(|l| all_consuming(parse_line)(l).finish().unwrap().1); for line in lines { println!("{line:?}"); } }  Shell session $ cargo run
Compiling memchr v2.5.0
Compiling minimal-lexical v0.2.1
Compiling camino v1.1.1
Compiling nom v7.1.1
Compiling day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
Finished dev [unoptimized + debuginfo] target(s) in 2.89s
Running target/debug/day7
Command(Cd(Cd("/")))
Command(Ls(Ls))
Entry(Dir("a"))
Entry(File(14848514, "b.txt"))
Entry(File(8504156, "c.dat"))
Entry(Dir("d"))
Command(Cd(Cd("a")))
Command(Ls(Ls))
Entry(Dir("e"))
Entry(File(29116, "f"))
Entry(File(2557, "g"))
Entry(File(62596, "h.lst"))
Command(Cd(Cd("e")))
Command(Ls(Ls))
Entry(File(584, "i"))
Command(Cd(Cd("..")))
Command(Cd(Cd("..")))
Command(Cd(Cd("d")))
Command(Ls(Ls))
Entry(File(4060174, "j"))
Entry(File(8033020, "d.log"))
Entry(File(5626152, "d.ext"))
Entry(File(7214296, "k"))


That looks good to me, there's just... a little more wrapping than I'd want, let's address that:

Rust code
#[derive(Debug)]
enum Command {
Ls,
Cd(Utf8PathBuf),
}

impl From<Ls> for Command {
fn from(_ls: Ls) -> Self {
Command::Ls
}
}

impl From<Cd> for Command {
fn from(cd: Cd) -> Self {
Command::Cd(cd.0)
}
}

fn parse_command(i: &str) -> IResult<&str, Command> {
let (i, _) = tag("$")(i)?; alt((map(parse_ls, Into::into), map(parse_cd, Into::into)))(i) }  And... Shell session $ cargo run
Compiling day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
Finished dev [unoptimized + debuginfo] target(s) in 0.47s
Running target/debug/day7
Command(Cd("/"))
Command(Ls)
Entry(Dir("a"))
Entry(File(14848514, "b.txt"))
Entry(File(8504156, "c.dat"))
Entry(Dir("d"))
Command(Cd("a"))
Command(Ls)
Entry(Dir("e"))
Entry(File(29116, "f"))
Entry(File(2557, "g"))
Entry(File(62596, "h.lst"))
Command(Cd("e"))
Command(Ls)
Entry(File(584, "i"))
Command(Cd(".."))
Command(Cd(".."))
Command(Cd("d"))
Command(Ls)
Entry(File(4060174, "j"))
Entry(File(8033020, "d.log"))
Entry(File(5626152, "d.ext"))
Entry(File(7214296, "k"))


Yeah that's better!

## A naive tree

Now let's try and store that data into a tree-like structure.

Naively, we can try this:

Rust code
#[derive(Debug, Default)]
struct Node {
size: usize,
children: HashMap<Utf8PathBuf, Node>,
}


And then, for main:

Rust code
fn main() {
let lines = include_str!("sample-input.txt")
.lines()
.map(|l| all_consuming(parse_line)(l).finish().unwrap().1);

let mut node = Node::default();

for line in lines {
println!("{line:?}");
match line {
Line::Command(cmd) => match cmd {
Command::Ls => {
// just ignore those
}
Command::Cd(_) => todo!(),
},
Line::Entry(entry) => match entry {
Entry::Dir(dir) => {
node.children.entry(dir).or_default();
}
Entry::File(size, file) => {
node.children.entry(file).or_default().size = size as usize;
}
},
}
}
}


So far so good but.. the big one is cd isn't it?

We can try something like this:

Rust code
                Command::Cd(path) => match path.as_str() {
"/" => {
// this isn't strictly correct, but in practice, this
// only appears at the start of the input, so it works
// for this puzzle.
}
".." => {
todo!("how the heck do we find the parent?");
}
_ => {
node = node.children.entry(path).or_default();
todo!();
}
},


But it doesn't work:

Shell session
$cargo check Checking day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7) error[E0308]: mismatched types --> src/main.rs:40:32 | 23 | let mut node = Node::default(); | --------------- expected due to this value ... 40 | node = node.children.entry(path).or_default(); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct Node, found &mut Node For more information about this error, try rustc --explain E0308. error: could not compile day7 due to previous error  Mhh okay, what if we make node a &mut Node then? Rust code  let mut root = Node::default(); // ðŸ‘‡ let mut node = &mut root; for line in lines { println!("{line:?}"); match line { Line::Command(cmd) => match cmd { Command::Ls => { // just ignore those } Command::Cd(path) => match path.as_str() { "/" => { // ignore, we're already there } ".." => { todo!("how the heck do we find the parent?"); } _ => { node = node.children.entry(path).or_default(); } }, }, Line::Entry(entry) => match entry { Entry::Dir(dir) => { node.children.entry(dir).or_default(); } Entry::File(size, file) => { node.children.entry(file).or_default().size = size as usize; } }, } }  That actually works! But we still have a todo! in there so... Shell session $ cargo run
Compiling day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
Finished dev [unoptimized + debuginfo] target(s) in 0.67s
Running target/debug/day7
Command(Cd("/"))
Command(Ls)
Entry(Dir("a"))
Entry(File(14848514, "b.txt"))
Entry(File(8504156, "c.dat"))
Entry(Dir("d"))
Command(Cd("a"))
Command(Ls)
Entry(Dir("e"))
Entry(File(29116, "f"))
Entry(File(2557, "g"))
Entry(File(62596, "h.lst"))
Command(Cd("e"))
Command(Ls)
Entry(File(584, "i"))
Command(Cd(".."))
thread 'main' panicked at 'not yet implemented: how the heck do we find the parent?', src/main.rs:38:25
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace


Still, I'm curious what our tree looks like at this stage. If we break instead, we can print it afterwards:

Rust code
    // in the for loop, replace todo!() with break

// then, after the for loop
println!("{root:#?}");

Shell session
$cargo run Compiling day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7) Finished dev [unoptimized + debuginfo] target(s) in 0.60s Running target/debug/day7 Command(Cd("/")) (cut) Command(Cd("..")) Node { size: 0, children: { "c.dat": Node { size: 8504156, children: {}, }, "b.txt": Node { size: 14848514, children: {}, }, "a": Node { size: 0, children: { "f": Node { size: 29116, children: {}, }, "e": Node { size: 0, children: { "i": Node { size: 584, children: {}, }, }, }, "h.lst": Node { size: 62596, children: {}, }, "g": Node { size: 2557, children: {}, }, }, }, "d": Node { size: 0, children: {}, }, }, }  How fun! I love trees. So... how do we handle cd ..? Let's try several ideas that don't work. Here's something someone new to Rust might come up with after much fighting: Rust code #[derive(Debug, Default)] struct Node<'a> { size: usize, children: HashMap<Utf8PathBuf, Node<'a>>, parent: Option<&'a mut Node<'a>>, }  There is no happiness down that path. We're essentially trying to make a doubly-linked list happen, only worse. Still, let's give it our all: Rust code fn main() { let lines = include_str!("sample-input.txt") .lines() .map(|l| all_consuming(parse_line)(l).finish().unwrap().1); let mut root = Node::default(); let mut node = &mut root; for line in lines { println!("{line:?}"); match line { Line::Command(cmd) => match cmd { Command::Ls => { // just ignore those } Command::Cd(path) => match path.as_str() { "/" => { // ignore, we're already there } ".." => { node = node.parent.unwrap(); } _ => { node = node.children.entry(path).or_default(); } }, }, Line::Entry(entry) => match entry { Entry::Dir(dir) => { let entry = node.children.entry(dir).or_default(); entry.parent = Some(node); } Entry::File(size, file) => { let entry = node.children.entry(file).or_default(); entry.size = size as usize; entry.parent = Some(node); } }, } } println!("{root:#?}"); }  We are immediately met with a flurry of errors, signifying that no, we cannot do any of that, what were we thinking, who even dares try such a thing: Shell session $ cargo check
Checking day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
error[E0507]: cannot move out of node.parent which is behind a mutable reference
--> src/main.rs:40:32
|
40  |                         node = node.parent.unwrap();
|                                ^^^^^^^^^^^ -------- node.parent moved due to this method call
|                                |
|                                help: consider calling .as_ref() or .as_mut() to borrow the type's contents
|                                move occurs because node.parent has type Option<&mut Node<'_>>, which does not implement the Copy trait
|
note: this function takes ownership of the receiver self, which moves node.parent
--> /home/amos/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/option.rs:772:25
|
772 |     pub const fn unwrap(self) -> T {
|                         ^^^^

error[E0505]: cannot move out of node.parent because it is borrowed
--> src/main.rs:40:32
|
40 |                         node = node.parent.unwrap();
|                                ^^^^^^^^^^^
|                                |
|                                move out of node.parent occurs here
|                                borrow later used here
...
55 |                     entry.parent = Some(node);
|                                         ---- borrow of *node occurs here

error[E0499]: cannot borrow node.children as mutable more than once at a time
--> src/main.rs:43:32
|
43 |                         node = node.children.entry(path).or_default();
|                                ^^^^^^^^^^^^^^^^^^^^^^^^^
|                                |
|                                second mutable borrow occurs here
|                                first borrow later used here
...
55 |                     entry.parent = Some(node);
|                                         ---- first mutable borrow occurs here

error[E0499]: cannot borrow node.children as mutable more than once at a time
--> src/main.rs:49:33
|
49 |                     let entry = node.children.entry(dir).or_default();
|                                 ^^^^^^^^^^^^^^^^^^^^^^^^
|                                 |
|                                 second mutable borrow occurs here
|                                 first borrow later used here
...
55 |                     entry.parent = Some(node);
|                                         ---- first mutable borrow occurs here

error[E0499]: cannot borrow *node as mutable more than once at a time
--> src/main.rs:50:41
|
50 |                     entry.parent = Some(node);
|                                         ^^^^
|                                         |
|                                         second mutable borrow occurs here
|                                         first borrow later used here
...
55 |                     entry.parent = Some(node);
|                                         ---- first mutable borrow occurs here

error[E0499]: cannot borrow node.children as mutable more than once at a time
--> src/main.rs:53:33
|
53 |                     let entry = node.children.entry(file).or_default();
|                                 ^^^^^^^^^^^^^^^^^^^^^^^^^
|                                 |
|                                 second mutable borrow occurs here
|                                 first borrow later used here
54 |                     entry.size = size as usize;
55 |                     entry.parent = Some(node);
|                                         ---- first mutable borrow occurs here

error[E0499]: cannot borrow *node as mutable more than once at a time
--> src/main.rs:55:41
|
53 |                     let entry = node.children.entry(file).or_default();
|                                 ------------------------- first mutable borrow occurs here
54 |                     entry.size = size as usize;
55 |                     entry.parent = Some(node);
|                     --------------------^^^^-
|                     |                   |
|                     |                   second mutable borrow occurs here
|                     first borrow later used here

error[E0502]: cannot borrow root as immutable because it is also borrowed as mutable
--> src/main.rs:60:16
|
25 |     let mut node = &mut root;
|                    --------- mutable borrow occurs here
...
60 |     println!("{root:#?}");
|                ^^^^
|                |
|                immutable borrow occurs here
|                mutable borrow later used here
|
= note: this error originates in the macro $crate::format_args_nl which comes from the expansion of the macro println (in Nightly builds, run with -Z macro-backtrace for more info) Some errors have detailed explanations: E0499, E0502, E0505, E0507. For more information about an error, try rustc --explain E0499. error: could not compile day7 due to 8 previous errors  Most of the errors boil down to "cannot borrow X as mutable more than once at a time". And that's... the crust of Rust. You can only ever have one mutable reference to something at a time. Anything else is insta-UB. And that rules keeps us safe. Let's look at different ways to get out of it! ## Using Rc/RefCell Just like in day 5, we can push the borrow checking from compile-time to run-time with RefCell. After all, we're not actually mutating more than one node at a time! Rust code #[derive(Debug, Default)] struct Node { size: usize, children: HashMap<Utf8PathBuf, RefCell<Node>>, parent: Option<RefCell<Node>>, }  This already fails, though: Shell session $ cargo check
Checking day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
error[E0072]: recursive type Node has infinite size
--> src/main.rs:13:1
|
13 | struct Node {
| ^^^^^^^^^^^ recursive type has infinite size
...
16 |     parent: Option<RefCell<Node>>,
|             --------------------- recursive without indirection
|
help: insert some indirection (e.g., a Box, Rc, or &) to make Node representable
|
16 |     parent: Option<Box<RefCell<Node>>>,
|                    ++++             +

For more information about this error, try rustc --explain E0072.
error: could not compile day7 due to previous error


This happens because when you do something like this in Rust:

Rust code
struct Foo {
bar: Bar,
}


Foo doesn't have a pointer/reference to Bar, Bar is embedded directly into Foo. So, if you embed Foo into Foo... it's of potentially infinite size.

Rust code
struct Foo {
// boom, infinite recursion
foo: Foo,
}


It works if you have an actual reference to Foo:

Rust code
struct Foo<'a> {
// boom, infinite recursion
foo: &'a Foo,
}


(It's worth nothing you cannot build a type as declared here, though)

Or a smart pointer to some heap-allocated Foo value:

Rust code
struct Foo {
foo: Box<Foo>,
}


(Again, this is unbuildable afaict).

Or a heap-allocated collection of Foo, like we did earlier:

Rust code
struct Foo {
foo: Vec<Foo>,
}


Point is: we cannot store the parent as merely RefCell<Foo>, because it's slightly larger than Foo - it's just a wrapper around Foo that applies borrow-checking rules at runtime.

There's another reason why we don't want to do that anyway: RefCell<Foo> has ownership of the Foo inside. But we don't want exclusive ownership. Consider a file tree like this:

- a
- b
- c


Both b and c have a as a parent: neither can "own" a, they have to share ownership of it. And, for single-threaded problems, we can achieve that with Rc, which stands for "Reference-Counting pointer".

For convenience, let's introduce a type alias:

Rust code
type NodeHandle = Rc<RefCell<Node>>;

#[derive(Debug, Default)]
struct Node {
size: usize,
children: HashMap<Utf8PathBuf, NodeHandle>,
parent: Option<NodeHandle>,
}


With that, we can painstakingly adjust our code, sprinkling .borrow() and .borrow_mut(), and .clone() to increase the reference count:

Rust code
fn main() {
let lines = include_str!("sample-input.txt")
.lines()
.map(|l| all_consuming(parse_line)(l).finish().unwrap().1);

let root = Rc::new(RefCell::new(Node::default()));
let mut node = root.clone();

for line in lines {
println!("{line:?}");
match line {
Line::Command(cmd) => match cmd {
Command::Ls => {
// just ignore those
}
Command::Cd(path) => match path.as_str() {
"/" => {
}
".." => {
let parent = node.borrow().parent.clone().unwrap();
node = parent;
}
_ => {
let child = node.borrow_mut().children.entry(path).or_default().clone();
node = child;
}
},
},
Line::Entry(entry) => match entry {
Entry::Dir(dir) => {
let entry = node.borrow_mut().children.entry(dir).or_default().clone();
entry.borrow_mut().parent = Some(node.clone());
}
Entry::File(size, file) => {
let entry = node.borrow_mut().children.entry(file).or_default().clone();
entry.borrow_mut().size = size as usize;
entry.borrow_mut().parent = Some(node.clone());
}
},
}
}
println!("{root:#?}");
}


I advise against running this program though: because of cyclic data structures, it will generate infinitely recursive output.

We should probably take care of that Debug output:

Rust code
#[derive(Default)]
struct Node {
size: usize,
children: HashMap<Utf8PathBuf, NodeHandle>,
parent: Option<NodeHandle>,
}

impl fmt::Debug for Node {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Node")
.field("size", &self.size)
.field("children", &self.children)
.finish()
}
}

Shell session
$cargo run Compiling day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7) Finished dev [unoptimized + debuginfo] target(s) in 0.63s Running target/debug/day7 Command(Cd("/")) Command(Ls) Entry(Dir("a")) Entry(File(14848514, "b.txt")) Entry(File(8504156, "c.dat")) Entry(Dir("d")) Command(Cd("a")) Command(Ls) Entry(Dir("e")) Entry(File(29116, "f")) Entry(File(2557, "g")) Entry(File(62596, "h.lst")) Command(Cd("e")) Command(Ls) Entry(File(584, "i")) Command(Cd("..")) Command(Cd("..")) Command(Cd("d")) Command(Ls) Entry(File(4060174, "j")) Entry(File(8033020, "d.log")) Entry(File(5626152, "d.ext")) Entry(File(7214296, "k")) RefCell { value: Node { size: 0, children: { "c.dat": RefCell { value: Node { size: 8504156, children: {}, }, }, "d": RefCell { value: Node { size: 0, children: { "k": RefCell { value: Node { size: 7214296, children: {}, }, }, "j": RefCell { value: Node { size: 4060174, children: {}, }, }, "d.log": RefCell { value: Node { size: 8033020, children: {}, }, }, "d.ext": RefCell { value: Node { size: 5626152, children: {}, }, }, }, }, }, "a": RefCell { value: Node { size: 0, children: { "f": RefCell { value: Node { size: 29116, children: {}, }, }, "g": RefCell { value: Node { size: 2557, children: {}, }, }, "e": RefCell { value: Node { size: 0, children: { "i": RefCell { value: Node { size: 584, children: {}, }, }, }, }, }, "h.lst": RefCell { value: Node { size: 62596, children: {}, }, }, }, }, }, "b.txt": RefCell { value: Node { size: 14848514, children: {}, }, }, }, }, }  This might be correct, but it's too much text for me to look at. Let's provide a Debug implementation on NodeHandle instead: Rust code type NodeHandle = Rc<RefCell<Node>>; impl fmt::Debug for NodeHandle { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("Node") .field("size", &self.size) .field("children", &self.children) .finish() } }  Shell session $ cargo check
Checking day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
error[E0117]: only traits defined in the current crate can be implemented for types defined outside of the crate
--> src/main.rs:14:1
|
14 | impl fmt::Debug for NodeHandle {
| ^^^^^^^^^^^^^^^^^^^^----------
| |                   |
| |                   Rc is not defined in the current crate
| impl doesn't use only types from inside the current crate
|
= note: define and implement a trait or new type instead

For more information about this error, try rustc --explain E0117.
error: could not compile day7 due to previous error


Oh no, we can't! That's "orphan rules", mentioned briefly in A half-hour to learn Rust.

However, we can define it on a newtype:

Rust code
struct PrettyNode<'a>(&'a NodeHandle);

impl<'a> fmt::Debug for PrettyNode<'a> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let this = self.0.borrow();
if this.size == 0 {
writeln!(f, "(dir)")?;
} else {
writeln!(f, "(file, size={})", this.size)?;
}

for (name, child) in &this.children {
// not very efficient at all, but shrug
for (index, line) in format!("{:?}", PrettyNode(child)).lines().enumerate() {
if index == 0 {
writeln!(f, "{name} {line}")?;
} else {
writeln!(f, "  {line}")?;
}
}
}
Ok(())
}
}


Which we can then use like so:

Rust code
    println!("{:#?}", PrettyNode(&root));


And generates output like that one:

Shell session
$cargo run (cut) (dir) b.txt (file, size=14848514) a (dir) g (file, size=2557) h.lst (file, size=62596) e (dir) i (file, size=584) f (file, size=29116) d (dir) j (file, size=4060174) d.ext (file, size=5626152) k (file, size=7214296) d.log (file, size=8033020) c.dat (file, size=8504156)  This doesn't quite match the sample output yet, because they keep keys sorted. We could sort children in the Debug impl, or we could use a data structure that keeps keys sorted all the time, like a BTreeMap: Rust code #[derive(Default)] struct Node { size: usize, children: BTreeMap<Utf8PathBuf, NodeHandle>, parent: Option<NodeHandle>, }  And then our output: Shell session $ cargo run
(cut)
(dir)
a (dir)
e (dir)
i (file, size=584)
f (file, size=29116)
g (file, size=2557)
h.lst (file, size=62596)
b.txt (file, size=14848514)
c.dat (file, size=8504156)
d (dir)
d.ext (file, size=5626152)
d.log (file, size=8033020)
j (file, size=4060174)
k (file, size=7214296)


Matches theirs:

- / (dir)
- a (dir)
- e (dir)
- i (file, size=584)
- f (file, size=29116)
- g (file, size=2557)
- h.lst (file, size=62596)
- b.txt (file, size=14848514)
- c.dat (file, size=8504156)
- d (dir)
- j (file, size=4060174)
- d.log (file, size=8033020)
- d.ext (file, size=5626152)
- k (file, size=7214296)


Or does it? They have j, d.log, etc. Whereas for us, d.ext comes first. Maybe they don't sort keys, maybe they merely retain insertion order!

We can achieve that with the indexmap crate:

Shell session
$cargo add indexmap (cut)  Rust code #[derive(Default)] struct Node { size: usize, children: IndexMap<Utf8PathBuf, NodeHandle>, parent: Option<NodeHandle>, }  Our output is now: (dir) a (dir) e (dir) i (file, size=584) f (file, size=29116) g (file, size=2557) h.lst (file, size=62596) b.txt (file, size=14848514) c.dat (file, size=8504156) d (dir) j (file, size=4060174) d.log (file, size=8033020) d.ext (file, size=5626152) k (file, size=7214296)  Which matches theirs, modulo some dashes. Now that we have a working version, we should probably explore tree traversal: ie., how do we actually answer their question. First let's define some methods on Node: Rust code impl Node { fn is_dir(&self) -> bool { self.size == 0 && !self.children.is_empty() } fn total_size(&self) -> u64 { self.children .values() .map(|child| child.borrow().total_size()) .sum::<u64>() + self.size as u64 } }  And then... it would be really convenient if we could iterate over all directories, let's try that: Rust code impl Node { fn all_dirs(&self) -> impl Iterator<Item = &Node> + '_ { std::iter::once(self).chain( self.children .values() .cloned() .filter_map(|c| { if c.borrow().is_dir() { Some(c.borrow().all_dirs()) } else { None } }) .flatten(), ) } }  That doesn't work: Shell session $ cargo run
Compiling day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
error[E0515]: cannot return value referencing temporary value
--> src/main.rs:69:25
|
69 |                         Some(c.borrow().all_dirs())
|                         ^^^^^----------^^^^^^^^^^^^
|                         |    |
|                         |    temporary value created here
|                         returns a value referencing data owned by the current function

error[E0515]: cannot return value referencing function parameter c
--> src/main.rs:69:25
|
69 |                         Some(c.borrow().all_dirs())
|                         ^^^^^----------^^^^^^^^^^^^
|                         |    |
|                         |    c is borrowed here
|                         returns a value referencing data owned by the current function

For more information about this error, try rustc --explain E0515.
error: could not compile day7 due to 2 previous errors


We can try defining it against NodeHandle instead (as a freestanding function, since we can't define methods on Rc<RefCell<Node>>, since Rc is a foreign type):

Rust code
fn all_dirs(n: NodeHandle) -> impl Iterator<Item = NodeHandle> {
std::iter::once(n.clone()).chain(
n.borrow()
.children
.values()
.cloned()
.filter_map(|c| {
if c.borrow().is_dir() {
Some(all_dirs(c))
} else {
None
}
})
.flatten(),
)
}


But...

Shell session
$cargo run Compiling day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7) error[E0275]: overflow evaluating the requirement <Flatten<FilterMap<Cloned<indexmap::map::Values<'_, Utf8PathBuf, Rc<RefCell<Node>>>>, [closure@src/main.rs:67:25: 67:28]>> as Iterator>::Item == Rc<RefCell<Node>> --> src/main.rs:62:5 | 62 | / std::iter::once(n.clone()).chain( 63 | | n.borrow() 64 | | .children 65 | | .values() ... | 74 | | .flatten(), 75 | | ) | |_____^ | = note: required for std::iter::Chain<std::iter::Once<Rc<RefCell<Node>>>, Flatten<FilterMap<Cloned<indexmap::map::Values<'_, Utf8PathBuf, Rc<RefCell<Node>>>>, [closure@src/main.rs:67:25: 67:28]>>> to implement Iterator For more information about this error, try rustc --explain E0275. error: could not compile day7 due to previous error  ...that's infinite recursion. Luckily, I've written about recursive iterators years ago Rust code fn all_dirs(n: NodeHandle) -> Box<dyn Iterator<Item = NodeHandle>> { Box::new( std::iter::once(n.clone()).chain( n.borrow() .children .values() .cloned() .filter_map(|c| { if c.borrow().is_dir() { Some(all_dirs(c)) } else { None } }) .flatten(), ), ) }  Unluckily, this still doesn't work: Shell session $ cargo check
Checking day7 v0.1.0 (/home/amos/bearcove/aoc2022/day7)
error[E0515]: cannot return value referencing temporary value
--> src/main.rs:62:5
|
62 | /     Box::new(
63 | |         std::iter::once(n.clone()).chain(
64 | |             n.borrow()
| |             ---------- temporary value created here
65 | |                 .children
...  |
76 | |         ),
77 | |     )
| |_____^ returns a value referencing data owned by the current function
|
= help: use .collect() to allocate the iterator

error[E0515]: cannot return value referencing function parameter n
--> src/main.rs:62:5
|
62 | /     Box::new(
63 | |         std::iter::once(n.clone()).chain(
64 | |             n.borrow()
| |             ---------- n is borrowed here
65 | |                 .children
...  |
76 | |         ),
77 | |     )
| |_____^ returns a value referencing data owned by the current function
|
= help: use .collect() to allocate the iterator

For more information about this error, try rustc --explain E0515.
error: could not compile day7 due to 2 previous errors


The compiler's suggestion isn't totally off the mark, since this compiles:

Rust code
fn all_dirs(n: NodeHandle) -> Box<dyn Iterator<Item = NodeHandle>> {
// clippy is wrong and should feel bad
#[allow(clippy::needless_collect)]
let children = n.borrow().children.values().cloned().collect::<Vec<_>>();

Box::new(
std::iter::once(n).chain(
children
.into_iter()
.filter_map(|c| {
if c.borrow().is_dir() {
Some(all_dirs(c))
} else {
None
}
})
.flatten(),
),
)
}


It's not... great. But it compiles. Let's try to use it:

Rust code
    let sum = all_dirs(root)
.map(|d| d.borrow().total_size())
.filter(|&s| s <= 100_000)
.inspect(|s| {
dbg!(s);
})
.sum::<u64>();
dbg!(sum);

Shell session
$cargo run (cut) [src/main.rs:128] s = 94853 [src/main.rs:128] s = 584 [src/main.rs:131] sum = 95437  This awful, awful code gets us through part 1. We'll want to revisit it, though. ## Part 2 Before we bikeshed our tree code, let's solve Part 2 real quick. The problem states that our disk is of size 70000000 and we want to delete the smallest directory that'll give us 30000000 of space for the upgrade. Time for more iterators! Rust code  let total_space = 70000000_u64; let used_space = root.borrow().total_size(); let free_space = total_space.checked_sub(dbg!(used_space)).unwrap(); let needed_free_space = 30000000_u64; let minimum_space_to_free = needed_free_space.checked_sub(free_space).unwrap(); let removed_dir_size = all_dirs(root) .map(|d| d.borrow().total_size()) .filter(|&s| s >= minimum_space_to_free) .inspect(|s| { dbg!(s); }) .min(); dbg!(removed_dir_size);  With the sample input, we get: Shell session $ cargo run
(cut)
[src/main.rs:127] used_space = 48381165
[src/main.rs:135] s = 48381165
[src/main.rs:135] s = 24933642
[src/main.rs:138] removed_dir_size = Some(
24933642,
)


And that gets us the second star.

Now for the fun part!

## Using the id_tree crate

One pattern that's commonly used in Rust when tackling a problem that the borrow checker doesn't quite understand, is to put everything in a big Vec and use indices.

That's exactly the strategy employed by the id_tree crate.

Let's see how it would work for us.

Shell session
$cargo add id_tree (cut)  We'll keep only the parsing part and re-do everything else from scratch: gone are the all_nodes function, our old Node and NodeHandle types, etc. A bunch of id_tree operations are fallible, and I don't want to sprinkle unwrap() everywhere, so: Shell session $ cargo add color-eyre
(cut)


Replacing our Node struct, let's make an FsEntry struct (since id_tree already has a type called Node):

Rust code
#[derive(Debug)]
struct FsEntry {
path: Utf8PathBuf,
size: u64,
}


Note that we don't need to track the children or the parent.

We can build the tree like so:

Rust code
fn main() -> color_eyre::Result<()> {
color_eyre::install().unwrap();

let lines = include_str!("sample-input.txt")
.lines()
.map(|l| all_consuming(parse_line)(l).finish().unwrap().1);

let mut tree = Tree::<FsEntry>::new();
let root = tree.insert(
Node::new(FsEntry {
path: "/".into(),
size: 0,
}),
InsertBehavior::AsRoot,
)?;
let mut curr = root;

for line in lines {
println!("{line:?}");
match line {
Line::Command(cmd) => match cmd {
Command::Ls => {
// just ignore those
}
Command::Cd(path) => match path.as_str() {
"/" => {
}
".." => {
curr = tree.get(&curr)?.parent().unwrap().clone();
}
_ => {
let node = Node::new(FsEntry {
path: path.clone(),
size: 0,
});
curr = tree.insert(node, InsertBehavior::UnderNode(&curr))?;
}
},
},
Line::Entry(entry) => match entry {
Entry::Dir(_) => {
// ignore, we'll do that when we cd into them
}
Entry::File(size, path) => {
let node = Node::new(FsEntry { size, path });
tree.insert(node, InsertBehavior::UnderNode(&curr))?;
}
},
}
}

let mut s = String::new();
tree.write_formatted(&mut s)?;
println!("{s}");

Ok(())
}


The output of this program looks like this:

Shell session
$cargo run (cut) FsEntry { path: "/", size: 0 } â”œâ”€â”€ FsEntry { path: "b.txt", size: 14848514 } â”œâ”€â”€ FsEntry { path: "c.dat", size: 8504156 } â”œâ”€â”€ FsEntry { path: "a", size: 0 } â”‚ â”œâ”€â”€ FsEntry { path: "f", size: 29116 } â”‚ â”œâ”€â”€ FsEntry { path: "g", size: 2557 } â”‚ â”œâ”€â”€ FsEntry { path: "h.lst", size: 62596 } â”‚ â””â”€â”€ FsEntry { path: "e", size: 0 } â”‚ â””â”€â”€ FsEntry { path: "i", size: 584 } â””â”€â”€ FsEntry { path: "d", size: 0 } â”œâ”€â”€ FsEntry { path: "j", size: 4060174 } â”œâ”€â”€ FsEntry { path: "d.log", size: 8033020 } â”œâ”€â”€ FsEntry { path: "d.ext", size: 5626152 } â””â”€â”€ FsEntry { path: "k", size: 7214296 }  Which seems correct! Now, we have to implement total_size as a freestanding function: Rust code fn total_size(tree: &Tree<FsEntry>, node: &Node<FsEntry>) -> color_eyre::Result<u64> { let mut total = node.data().size; for child in node.children() { total += total_size(tree, tree.get(child)?)?; } Ok(total) }  We can then iterate our whole tree in.. whichever order really, doesn't matter, and answer part 1 again: Rust code  let sum = tree .traverse_pre_order(tree.root_node_id().unwrap())? .map(|n| total_size(&tree, n).unwrap()) .filter(|&s| s <= 100_000) .inspect(|s| { dbg!(s); }) .sum::<u64>(); dbg!(sum);  With the sample input, we get: Shell session $ cargo run
(cut)
[src/main.rs:80] s = 94853
[src/main.rs:80] s = 29116
[src/main.rs:80] s = 2557
[src/main.rs:80] s = 62596
[src/main.rs:80] s = 584
[src/main.rs:80] s = 584
[src/main.rs:83] sum = 190290


Woops, this one returns files, too!

Let's fix it:

Rust code
    let sum = tree
.traverse_pre_order(tree.root_node_id().unwrap())?
// only consider folders:
.filter(|n| !n.children().is_empty())
.map(|n| total_size(&tree, n).unwrap())
.filter(|&s| s <= 100_000)
.inspect(|s| {
dbg!(s);
})
.sum::<u64>();
dbg!(sum);


And now it works!

As for part 2:

Rust code
    let total_space = 70000000_u64;
let used_space = total_size(&tree, tree.get(tree.root_node_id().unwrap())?)?;
let free_space = total_space.checked_sub(dbg!(used_space)).unwrap();
let needed_free_space = 30000000_u64;
let minimum_space_to_free = needed_free_space.checked_sub(free_space).unwrap();

let size_to_remove = tree
.traverse_pre_order(tree.root_node_id().unwrap())?
.filter(|n| !n.children().is_empty())
.map(|n| total_size(&tree, n).unwrap())
.filter(|&s| s >= minimum_space_to_free)
.inspect(|s| {
dbg!(s);
})
.min();
dbg!(size_to_remove);


Note that, at this point, we're not using path at all: the compiler says so:

Shell session
$cargo check --quiet warning: field path is never read --> src/main.rs:13:5 | 12 | struct FsEntry { | ------- field in this struct 13 | path: Utf8PathBuf, | ^^^^ | = note: #[warn(dead_code)] on by default = note: FsEntry has a derived impl for the trait Debug, but this is intentionally ignored during dead code analysis  So, if we were going for a fast solution, we could remove that path altogether, and not even parse it (having parse_path return a () instead). ## Using a stack I have another idea. Let's get rid of id_tree: Shell session $ cargo rm id_tree
Removing id_tree from dependencies


And have a node type with children, once again:

Rust code
#[derive(Debug)]
struct FsEntry {
path: Utf8PathBuf,
size: u64,
children: Vec<FsEntry>,
}


Once again, we can have total_size directly on that type:

Rust code
impl FsEntry {
fn total_size(&self) -> u64 {
self.size + self.children.iter().map(|c| c.total_size()).sum::<u64>()
}

fn all_dirs(&self) -> Box<dyn Iterator<Item = &FsEntry> + '_> {
Box::new(
std::iter::once(self).chain(
self.children
.iter()
.filter(|c| !c.children.is_empty())
.flat_map(|c| c.all_dirs()),
),
)
}
}


Ooh would you look at that, that's much more elegant!

And then main becomes:

Rust code
fn main() -> color_eyre::Result<()> {
color_eyre::install().unwrap();

let lines = include_str!("input.txt")
.lines()
.map(|l| all_consuming(parse_line)(l).finish().unwrap().1);

let mut stack = vec![FsEntry {
path: "/".into(),
size: 0,
children: vec![],
}];

for line in lines {
println!("{line:?}");
match line {
Line::Command(cmd) => match cmd {
Command::Ls => {
// just ignore those
}
Command::Cd(path) => match path.as_str() {
"/" => {
}
".." => {
let child = stack.pop();
stack.last_mut().unwrap().children.push(child.unwrap());
}
_ => {
let node = FsEntry {
path: path.clone(),
size: 0,
children: vec![],
};
stack.push(node);
}
},
},
Line::Entry(entry) => match entry {
Entry::Dir(_) => {
// ignore, we'll do that when we cd into them
}
Entry::File(size, path) => {
let node = FsEntry {
size,
path,
children: vec![],
};
stack.last_mut().unwrap().children.push(node);
}
},
}
}

let root = stack.pop().unwrap();
dbg!(&root);

// solving part 1 because it's the same difficulty as part 2, just less code
let sum = root
.all_dirs()
.map(|d| d.total_size())
.filter(|&s| s <= 100_000)
.sum::<u64>();
dbg!(sum);

Ok(())
}

Shell session
\$ cargo run
(cut)
[src/main.rs:72] &root = FsEntry {
path: "d",
size: 0,
children: [
FsEntry {
path: "j",
size: 4060174,
children: [],
},
FsEntry {
path: "d.log",
size: 8033020,
children: [],
},
FsEntry {
path: "d.ext",
size: 5626152,
children: [],
},
FsEntry {
path: "k",
size: 7214296,
children: [],
},
],
}
[src/main.rs:80] sum = 0


Woops! The root is not the root, and our answer is wrong. Let's make sure we pop that whole stack.

Rust code
    // after that big for

let mut root = stack.pop().unwrap();
while let Some(mut next) = stack.pop() {
next.children.push(root);
root = next;
}
dbg!(&root);


And now it works!

I like that solution a lot, but I have... one more idea!

## Using the stack

Wait, haven't we done that one already?

No bear, the stack. Calling a function pushes a frame on the stack, and returning pops a frame, and so, behold:

Rust code
impl FsEntry {
fn build(mut self, it: &mut dyn Iterator<Item = Line>) -> Self {
while let Some(line) = it.next() {
match line {
Line::Command(Command::Cd(sub)) => match sub.as_str() {
"/" => {
// muffin,
}
".." => break,
_ => self.children.push(
FsEntry {
path: sub.clone(),
size: 0,
children: vec![],
}
.build(it),
),
},
Line::Entry(Entry::File(size, path)) => {
self.children.push(FsEntry {
path,
size,
children: vec![],
});
}
_ => {
// ignore other commands
}
}
}
self
}
}


And with that, main simply becomes:

Rust code
fn main() {
let mut lines = include_str!("input.txt")
.lines()
.map(|l| all_consuming(parse_line)(l).finish().unwrap().1);

let root = FsEntry {
path: "/".into(),
size: 0,
children: vec![],
}
.build(&mut lines);
dbg!(&root);

// solving part 1 because it's the same difficulty as part 2, just less code
let sum = root
.all_dirs()
.map(|d| d.total_size())
.filter(|&s| s < 100_000)
.sum::<u64>();
dbg!(sum);
}


That's my favorite of all the solutions I've presented so far, but I have to add a couple notes:

• It only works because we never cd into the same directory twice. If we did, it wouldn't be a problem, we'd just have to merge the children: but the code as-is doesn't handle that.
• For large datasets (with deep directory structures), this code will make the stack overflow, whereas the Vec-based approach won't (provided the data fits in the heap..)

Nevertheless, I'm happy I was able to show that the code doesn't have to be awful, given that this puzzle has nice properties :) I would probably reach out for id_tree again if I had more complicated tree-like problems to solve.

Similarly, if I had graph problems, I would reach out for a crate like petgraph, which powers guppy, which in turns powers cargo-nextest, which we used in the day 6 problem. Welcome to the Rain cinematic universe!