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
18//!   `cd foo` command, then we push the size of the current directory to this stack to save for
19//!   later, then reset our running total to 0.
20//! * Create a second `vec` to store the sizes of completed directories. Anytime we encounter
21//!   a `cd ..` then we can "complete" the current directory and add its size to this list. To find
22//!   our new running total we then pop the previous unfinished directory off the stack
23//!   (and this is the neat part) *add* the size of the just completed directory, since we know
24//!   that it must have been a child of the directory at the top of the stack.
25//!
26//!   Note that the end of the file is essentially an 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 [implicit up up]`
33//!
34//! This means that the algorithm is extremely efficient and the data structures are very
35//! straightforward. For example there's no need to store the current path names, or to recursively
36//! update upwards whenever a file is encountered.
37use crate::util::parse::*;
38
39/// Tokenize the input and return a `vec` of directory sizes.
40pub fn parse(input: &str) -> Vec<u32> {
41    let mut cd = false;
42    let mut total = 0;
43    let mut stack = Vec::new();
44    let mut sizes = Vec::new();
45
46    for token in input.split_ascii_whitespace() {
47        if cd {
48            if token == ".." {
49                sizes.push(total);
50                total += stack.pop().unwrap();
51            } else {
52                stack.push(total);
53                total = 0;
54            }
55            cd = false;
56        } else if token == "cd" {
57            cd = true;
58        } else if token.as_bytes()[0].is_ascii_digit() {
59            total += token.unsigned::<u32>();
60        }
61    }
62
63    while !stack.is_empty() {
64        sizes.push(total);
65        total += stack.pop().unwrap();
66    }
67
68    sizes
69}
70
71/// Sum all directories 100,000 bytes or less.
72pub fn part1(input: &[u32]) -> u32 {
73    input.iter().filter(|&&x| x <= 100_000).sum()
74}
75
76/// Find the smallest directory that can be deleted to free up the necessary space.
77pub fn part2(input: &[u32]) -> u32 {
78    let root = input.last().unwrap();
79    let needed = 30_000_000 - (70_000_000 - root);
80    *input.iter().filter(|&&x| x >= needed).min().unwrap()
81}
aoc/year2022/day07.rs

aoc/year2022/
day07.rs
