Advent of Rust // Day 7

//

I spent this morning trying to build a super generic directory tree structure using dynamic types and ended up being frustrated because I don’t get how ownership, lifetime, and all that jazz works in Rust. So I went to work and after eight hours of that I just slammed out the dumbest solution I could think of… and it worked right away.

In short, I just keep track of directories and their sizes. Each file from the input is added to the current directory and all parent directories. Everything is stored in a flat hash map. The rest is simple filtering. I’m not proud of it, but it works.

fn directory_sizes(input: &str) -> HashMap<String, u32> {  
    let mut tree: HashMap<String, u32> = HashMap::new();  
  
    let directory_regex = Regex::new(r"^\$ cd (.+)$").unwrap();  
    let file_regex = Regex::new(r"^(\d+) (.+)$").unwrap();  
  
    let mut path = vec![String::from(".")];  
  
    for line in input.lines() {  
        for directory in directory_regex.captures(line) {  
            match &directory[1] {  
                "/" => path.truncate(1),  
                ".." => { path.pop(); }  
                _ => path.push(String::from(&directory[1]))  
            };  
        }  
  
        for file in file_regex.captures(line) {  
            let file_size = file[1].parse::<u32>().unwrap();  
            for p in all_directories(&path) {  
                let new_size = tree.get(&p).unwrap_or(&0) + file_size;  
                tree.insert(p, new_size);  
            }  
        }  
    }  
  
    return tree;  
}

fn all_directories(path: &Vec<String>) -> Vec<String> {  
    return (0..path.len()).map(|i| path[0..i + 1].join("/")).collect();  
}

fn part_one(input: &str) -> u32 {  
    return directory_sizes(input).values().filter(|v| *v < &100000).sum();  
}  
  
fn part_two(input: &str) -> u32 {  
    let sizes = directory_sizes(input);  
  
    let total = 70000000;  
    let required = 30000000;  
  
    let unused = total - sizes.get(".").unwrap();  
    let missing = required - unused;  
  
    return *sizes.values().filter(|v| *v >= &missing).min().unwrap();  
}

The full source and solutions for the others puzzles of Advent of Code can be found in my GitHub repository.

See also in Advent of Rust

Comments

You can leave a comment by replying to this post on Mastodon.