Advent of Code 2022 - Day 07
Tags: rust, programming, adventofcode
Published: 2022-12-09 01:47:03

---
title: Advent of Code 2022 - Day 07
published: true
date: 2022-12-07 00:00:00 UTC
tags: rust, programming, adventofcode
canonical_url: https://www.ericburden.work/blog/2022/12/07/advent-of-code-2022-day-07/
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vqgw1ymlkraii9y0krci.png
---

It’s that time of year again! Just like last year, I’ll be posting my solutions to the [Advent of Code](https://adventofcode.com/) puzzles. This year, I’ll be solving the puzzles in [Rust](https://www.rust-lang.org/). I’ll post my solutions and code to [GitHub](https://github.com/ericwburden/advent_of_code_2022) as well. After finishing last year (and 2015-2019) in [Julia](https://julialang.org/), I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 07 - No Space Left on Device

Find the problem description [HERE](https://adventofcode.com/2022/day/7).

## The Input - Parse Me Twice

Well, well, well. Today’s puzzle had me longing for Julia again, just a _bit_. Mostly because building tree-based structures in Rust is **not** my forte. Which, I guess makes today a valuable learning opportunity, but it was still a bit of a slog. Today’s input parsing comes in two parts. First, we read in the input file and parse the lines into a series of `Cmd` structs that are a bit easier to work with for the second step, which is building an object to hold our file tree structure.

```rust
use anyhow::{anyhow, bail, Error, Result};
use std::fmt::{Display, Formatter, Result as FmtResult};
use std::{cell::RefCell, collections::HashMap, rc::Rc};

/// Represents a directory in the file tree, including the directory label,
/// a list of the contained directories, a list of the contained files, and
/// the total size of all the files contained in the directory and all
/// sub-directories.
#[derive(Debug, Clone)]
struct Dir<'a> {
    label: &'a str,
    dirs: Vec<DirRef<'a>>,
    files: Vec<File<'a>>,
    size: u32,
}

/// A type alias for a Dir wrapped in Rc, which allows for the Dir to have multiple
/// owners, and RefCell, which allows for runtime-checked mutable borrows of the Dir.
/// Together, these two properties allow us to recursively nest `Dir`s within `Dir`s.
pub type DirRef<'a> = Rc<RefCell<Dir<'a>>>;

/// Represents a file in the file tree, including its name and file size
#[derive(Debug, Clone)]
struct File<'a> {
    label: &'a str,
    size: u32,
}

/// Enum to allow both types of items to be stored in a single vector. Both types
/// are in Rc<RefCell<T>> wrappers to TODO
#[derive(Debug, Clone)]
enum FileSystemObj<'a> {
    Dir(DirRef<'a>),
    File(File<'a>),
}

/// Represents a command from the input file. Commands come in one of four flavors.
#[derive(Debug, Clone)]
enum Cmd<'a> {
    MoveIn(Dir<'a>),
    MoveUp,
    MoveRoot,
    List(Vec<FileSystemObj<'a>>),
}

/// Module to wrap the parsers needed to parse the input file into commands
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::{tag, take_until},
        character::complete::{alpha1, space1, u32},
        combinator::map,
        multi::separated_list1,
        sequence::{preceded, separated_pair},
        Finish, IResult,
    };

    /// Nom parser for "dir bacon" -> Rc<RefCell<Dir { label: "bacon" }>>
    fn dir(s: &str) -> IResult<&str, DirRef> {
        let (s, label) = preceded(tag("dir "), alpha1)(s)?;
        let dir = Dir::from(label);
        Ok((s, Rc::new(RefCell::new(dir))))
    }

    /// Nom parser for "123 eggs.txt" -> File { size: 123, label: "eggs.txt" } 
    fn file(s: &str) -> IResult<&str, File> {
        let (s, (size, label)) = separated_pair(u32, space1, take_until("\n"))(s)?;
        let file = File { size, label };
        Ok((s, file))
    }

    /// Nom parser for parsing one of the file objects listed from an `ls` command
    fn fs_obj(s: &str) -> IResult<&str, FileSystemObj> {
        alt((map(dir, FileSystemObj::Dir), map(file, FileSystemObj::File)))(s)
    }

    /// Nom parser for a list of newline separated results from an `ls` command 
    fn contents(s: &str) -> IResult<&str, Vec<FileSystemObj>> {
        separated_list1(tag("\n"), fs_obj)(s)
    }

    /// Nom parser for the various `cd` commands
    fn cd_cmd(s: &str) -> IResult<&str, Cmd> {
        let (s, cmd_str) = preceded(tag("$ cd "), take_until("\n"))(s)?;
        let cmd = match cmd_str {
            "/" => Cmd::MoveRoot,
            ".." => Cmd::MoveUp,
            _ => Cmd::MoveIn(Dir::from(cmd_str)),
        };
        Ok((s, cmd))
    }

    /// Nom parser for the `ls` command. Grabs the command line and the lines
    /// that follow listing the files and directories.
    fn ls_cmd(s: &str) -> IResult<&str, Cmd> {
        let (s, listed) = preceded(tag("$ ls\n"), contents)(s)?;
        Ok((s, Cmd::List(listed)))
    }

    /// Nom parser for either a `cd` or `ls` command
    fn command(s: &str) -> IResult<&str, Cmd> {
        alt((cd_cmd, ls_cmd))(s)
    }

    /// Nom parser to parse all commands from the input into a list of Cmd
    pub fn commands(s: &str) -> Result<Vec<Cmd>> {
        let result = separated_list1(tag("\n"), command)(s).finish();
        let (_, cmds) = result.map_err(|_| anyhow!("Could not parse commands!"))?;
        Ok(cmds)
    }
}

```

That’s right. _All_ of that code is just for creating a list of parsed commands that will be _used_ to produce the actual input structure that we’re going to be operating on. Speaking of which…

```rust
/// These functions make building the file structure slightly less painful.
impl<'a> Dir<'a> {
    /// Create an empty directory with the given label
    fn from(label: &'a str) -> Self {
        let dirs = Vec::new();
        let files = Vec::new();
        let size = 0;
        Dir {
            label,
            dirs,
            files,
            size,
        }
    }

    /// Search the contents of a file system object and return the child object
    /// indicated by `label`.
    fn get_child(&self, label: &str) -> Option<DirRef<'a>> {
        self
           .dirs
           .iter()
           .find(|c| c.borrow().label == label)
           .cloned()
    }

    /// Add a nested directory to this directory
    fn add_dir(&mut self, dir: Dir<'a>) {
        let dir_ref = Rc::new(RefCell::new(dir));
        self.dirs.push(dir_ref);
    }
}

/// Represents the entire filesystem, which is a linked tree of all the filesystem
/// objects. Contains the root node.
#[derive(Debug, Clone)]
pub struct FileSystem<'a>(pub DirRef<'a>);

impl<'a> TryFrom<Vec<Cmd<'a>>> for FileSystem<'a> {
    type Error = Error;

    fn try_from(commands: Vec<Cmd<'a>>) -> Result<Self, Self::Error> {
        // Create a new DirRef for the root node and use it to initialize the 
        // list of open directories.
        let root = Rc::new(RefCell::new(Dir::from("/")));
        let mut open_dirs = vec![root.clone()];

        for command in commands {
            // This is safe, there's nothing in the loop that would cause us to
            // empty `open_dirs` that isn't already handled.
            let current_dir = open_dirs.last_mut().unwrap();

            // Based on the command we're looking at...
            match command {
                // Move into a new directory by getting that directory's reference
                // from the current directory's contents and pushing that reference
                // to the end of the list of open directories.
                Cmd::MoveIn(dir) => {
                    let dir = current_dir.borrow_mut().get_child(dir.label).unwrap();
                    open_dirs.push(dir);
                }

                // Move up out of the current directory by dropping the last directory
                // from the list of open directories.
                Cmd::MoveUp => {
                    open_dirs
                        .pop()
                        .ok_or(anyhow!("Cannot 'cd ..' out of root!"))?;
                }

                // Move to the root directory by dropping all but the first (root)
                // directory from the list of open directories.
                Cmd::MoveRoot => open_dirs.truncate(1),

                // Process a command to list contents by adding all the files and
                // directories listed as children of the currently open directory.
                Cmd::List(mut objs) => for obj in objs.drain(..) {
                    match obj {
                        FileSystemObj::Dir(d) => current_dir.borrow_mut().dirs.push(d),
                        FileSystemObj::File(f) => current_dir.borrow_mut().files.push(f),
                    }
                },
            }
        }
        Ok(FileSystem(root))
    }
}

impl FileSystem<'_> {
    /// Fill in the sizes of all the directories in the file system by recursively
    /// walking the file system.
    fn calculate_directory_sizes(&self) {

        // Recursively walk the file system tree and fill in the sizes for
        // each directory.
        fn size(dir: DirRef) -> u32 {
            let mut total = 0;

            // Add the sizes of all the files in this directory
            for file in dir.borrow().files.iter() {
                total += file.size;
            }

            // Add (and fill in) recursively all the sub-directories in this
            // directory
            for child_dir in dir.borrow().dirs.iter() {
                total += size(child_dir.clone());
            }

            // Update this directory
            dir.borrow_mut().size = total;

            total
        }

        // Perform the walk
        size(self.0.clone());
    }
}

const INPUT: &str = include_str!("../../input/07/input.txt");

/// Read the input by first parsing all the commands from the input file, then
/// following those commands to build up a tree structure for the file system, 
/// finally filling in all the directory sizes and returning the file system struct.
fn read<'a>() -> Input<'a> {
    let commands = parser::commands(INPUT).expect("Could not parse input!");
    let mut fs = FileSystem::try_from(commands).expect("Could not build filesystem!");
    fs.calculate_directory_sizes();
    fs
}

```

That was a _lot_ of parsing and converting, but it will all be worth it now, since we’ve got a pretty good representation of the file system structure to work on the actually puzzle with.

## Part One - Count Me Out

It seems like the elf AI knows us _too_ well, because now we’re **thoroughly** distracted by this communications device. Now we can’t run a system update because we’re out of disk space. For part one, we need to identify which directories are smaller than some very rounded limit in what is an unfortunately familiar exercise.

```rust
/// Solve Day 7, Part 1
pub fn solve(input: &Input) -> u32 {
    // From the list of directory sizes, keep only the sizes less than 100_000
    // and return the total of those directory sizes.
    input
        .get_directory_sizes()
        .iter()
        .filter(|x| **x <= 100_000)
        .sum::<u32>()
}

impl FileSystem<'_> {
    /// Pull the sizes of each directory in the file system into a vector
    pub fn get_directory_sizes(&self) -> Vec<u32> {
        let mut sizes = Vec::new();

        // Walk the file system tree structure, adding directory sizes to `sizes`
        fn walk(dir: DirRef, sizes: &mut Vec<u32>) {
            sizes.push(dir.borrow().size);
            for item in dir.borrow().dirs.iter() {
                walk(item.clone(), sizes);
            }
        }

        // Do the walk!
        walk(self.0.clone(), &mut sizes);
        sizes
    }
}

```

Recursive search for the win! Since we updated all the directories with their sizes during input parsing, it’s just a regular old recursive walk through the file system to get the list of directory sizes.

## Part Two - Give Me Some Space

Time to clear out some storage space. Given all the work we’ve put in so far, it’s nice that this part is mostly just a bit of math.

```rust
/// Solve Day 7, Part 2 
pub fn solve(input: &Input) -> Output {
    // Calculate the space we need to free up as described by the puzzle
    let space_remaining = 70_000_000 - input.total_size();
    let space_needed = 30_000_000 - space_remaining;

    // Iterate through the directory sizes and find the ones whose size is at least
    // as large as the amount of space we need, and take the smallest size of those.
    input
        .get_directory_sizes()
        .into_iter()
        .filter(|x| *x >= space_needed)
        .min()
        .unwrap()
        .into()
}

impl FileSystem<'_> {
    /// Get the size of the root directory, which is the total size of the files
    /// in our file system.
    fn total_size(&self) -> u32 {
        self.0.borrow().size
    }
}

```

Not much going on here, but it got us a star!

## Wrap Up

I feel a bit like I _asked_ for this. Given how loud and out there I’ve been with my desire to get better at text parsing, I also feel like I’m supposed to be_happy_ about the somewhat intense amount of input parsing we’ve seen so far, particularly given that we’re only seven days in. In addition, I got to spend a good amount of time in the Rust docs today figuring out how to do the linked-tree structure. There was a lot of unfamiliar syntax for me today, which probably means that today was an excellent day for learning. I’ll probably be happy about it tomorrow. Until then, Happy Holidays!