aoc/year2022/
day07.rs

1//! # No Space Left On Device
2//!
3//! Some up-front analysis of the input data helps us develop an efficient solving algorithm (this
4//! is a regular theme in Advent of Code!). Looking at the directory commands shows 2 key insights:
5//! * We never return to a previously visited directory.
6//! * Directory traversal is only up or down in steps of one.
7//!
8//! This allows us to infer:
9//! * `$ ls` lines contain no useful information and can be ignored.
10//! * `dir foo` lines also contain no useful information and can be ignored.
11//! * Only the size in `12345 foo.bar` file listings is useful.
12//! * `cd foo` commands imply a "down" direction, but the name is not needed and can be ignored.
13//! * `cd ..` commands imply that we are finished with the current directory.
14//!
15//! For my input data this meant that 58% of it was unnecessary! Our algorithm will be:
16//! * If we encounter a file listing then add its size to the current running total.
17//! * Create a `vec` to function as a stack of incomplete directories. Anytime we encounter a `cd
18//!   foo` command, then we push the size of the current directory to this stack to save for later,
19//!   then reset our running total to 0.
20//! * Create a second `vec` to store the sizes of completed directories. Anytime we encounter a `cd
21//!   ..` then we can "complete" the current directory and add its size to this list. To find our
22//!   new running total we then pop the previous unfinished directory off the stack (and this is the
23//!   neat part) *add* the size of the just completed directory, since we know that it must have
24//!   been a child of the directory at the top of the stack.
25//!
26//!   Note that the end of the file is essentially a sequence of implicit `cd ..` commands
27//!   all the way to the root. Another nice side effect is that the root directory is always the
28//!   last element in our `vec`.
29//!
30//! For example, the sample input reduces to essentially only:
31//!
32//! `down 14848514 8504156 down 29116 2557 62596 down 584 up up down 4060174 8033020 5626152 7214296
33//! [implicit up up]`
34//!
35//! This means that the algorithm is extremely efficient and the data structures are very
36//! straightforward. For example, there's no need to store the current path names, or to recursively
37//! update upwards whenever a file is encountered.
38use crate::util::parse::*;
39
40/// Tokenize the input and return a `vec` of directory sizes.
41pub fn parse(input: &str) -> Vec<u32> {
42    let mut iter = input.split_ascii_whitespace();
43    let mut total = 0;
44    let mut stack = Vec::new();
45    let mut sizes = Vec::new();
46
47    while let Some(token) = iter.next() {
48        if token == "cd" {
49            if iter.next() == Some("..") {
50                sizes.push(total);
51                total += stack.pop().unwrap();
52            } else {
53                stack.push(total);
54                total = 0;
55            }
56        } else if token.as_bytes()[0].is_ascii_digit() {
57            total += token.unsigned::<u32>();
58        }
59    }
60
61    while let Some(prev) = stack.pop() {
62        sizes.push(total);
63        total += prev;
64    }
65
66    sizes
67}
68
69/// Sum all directories 100,000 bytes or less.
70pub fn part1(input: &[u32]) -> u32 {
71    input.iter().filter(|&&x| x <= 100_000).sum()
72}
73
74/// Find the smallest directory that can be deleted to free up the necessary space.
75pub fn part2(input: &[u32]) -> u32 {
76    let root = input.last().unwrap();
77    let needed = 30_000_000 - (70_000_000 - root);
78    *input.iter().filter(|&&x| x >= needed).min().unwrap()
79}
aoc/year2022/day07.rs

aoc/year2022/
day07.rs
