1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

//! # No Space Left On Device
//!
//! Some up-front analysis of the input data helps us develop an efficient solving algorithm (this
//! is a regular theme in Advent of Code!). Looking at the directory commands shows 2 key insights:
//! * We never return to a previously visited directory
//! * Directory traversal is only up or down in steps of one.
//!
//! This allows us to infer:
//! * `$ ls` lines contain no useful information and can be ignored.
//! * `dir foo` lines also contain no useful information and can be ignored.
//! * Only the size in `12345 foo.bar` file listings is useful.
//! * `cd foo` commands imply a "down" direction, but the name is not needed and can be ignored.
//! * `cd ..` commands imply that we are finished with the current directory.
//!
//! For my input data this meant that 58% of it was unnecessary! Our algorithm will be:
//! * If we encounter a file listing then add its size to the current running total.
//! * Create a `vec` to function as a stack of incomplete directories. Anytime we encounter a
//!   `cd foo` command, then we push the size of the current directory to this stack to save for
//!   later, then reset our running total to 0.
//! * Create a second `vec` to store the sizes of completed directories. Anytime we encounter
//!   a `cd ..` then we can "complete" the current directory and add its size to this list. To find
//!   our new running total we then pop the previous unfinished directory off the stack
//!   (and this is the neat part) *add* the size of the just completed directory, since we know
//!   that it must have been a child of the directory at the top of the stack.
//!
//!   Note that the end of the file is essentially an sequence of implicit `cd ..` commands
//!   all the way to the root. Another nice side effect is that the root directory is always the
//!   last element in our `vec`.
//!
//! For example, the sample input reduces to essentially only:
//!
//! `down 14848514 8504156 down 29116 2557 62596 down 584 up up down 4060174 8033020 5626152 7214296 [implicit up up]`
//!
//! This means that the algorithm is extremely efficient and the data structures are very
//! straightforward. For example there's no need to store the current path names, or to recursively
//! update upwards whenever a file is encountered.
use crate::util::parse::*;

/// Tokenize the input and return a `vec` of directory sizes.
pub fn parse(input: &str) -> Vec<u32> {
    let mut cd = false;
    let mut total = 0;
    let mut stack = Vec::new();
    let mut sizes = Vec::new();

    for token in input.split_ascii_whitespace() {
        if cd {
            if token == ".." {
                sizes.push(total);
                total += stack.pop().unwrap();
            } else {
                stack.push(total);
                total = 0;
            }
            cd = false;
        } else if token == "cd" {
            cd = true;
        } else if token.as_bytes()[0].is_ascii_digit() {
            total += token.unsigned::<u32>();
        }
    }

    while !stack.is_empty() {
        sizes.push(total);
        total += stack.pop().unwrap();
    }

    sizes
}

/// Sum all directories 100,000 bytes or less.
pub fn part1(input: &[u32]) -> u32 {
    input.iter().filter(|&&x| x <= 100_000).sum()
}

/// Find the smallest directory that can be deleted to free up the necessary space.
pub fn part2(input: &[u32]) -> u32 {
    let root = input.last().unwrap();
    let needed = 30_000_000 - (70_000_000 - root);
    *input.iter().filter(|&&x| x >= needed).min().unwrap()
}