Skip to content

Instantly share code, notes, and snippets.

@faiface
Created December 11, 2022 14:56
Show Gist options
  • Save faiface/fa4fff324cebf1395342ef3ff3bd22dd to your computer and use it in GitHub Desktop.
Save faiface/fa4fff324cebf1395342ef3ff3bd22dd to your computer and use it in GitHub Desktop.
use std::collections::HashMap;
#[derive(Default, Debug)]
struct Dir {
name_and_parent: Option<(String, Box<Dir>)>,
files: HashMap<String, usize>,
subdirs: HashMap<String, Box<Dir>>,
total_size: usize,
}
impl Dir {
fn move_up(mut self: Box<Self>) -> Box<Self> {
let Some((name, mut parent)) = self.name_and_parent.take() else {
return self;
};
parent.total_size += self.total_size;
parent.subdirs.insert(name, self);
parent
}
fn move_to_root(self: Box<Self>) -> Box<Self> {
if self.name_and_parent.is_none() { return self; }
self.move_up().move_to_root()
}
fn move_down(mut self: Box<Self>, dir_name: &str) -> Box<Self> {
let (name, mut subdir) = self.subdirs.remove_entry(dir_name).unwrap();
self.total_size -= subdir.total_size;
subdir.name_and_parent = Some((name, self));
subdir
}
fn add_file(&mut self, name: String, size: usize) {
self.files.insert(name, size);
self.total_size += size;
}
fn add_dir(&mut self, name: String) {
if !self.subdirs.contains_key(&name) {
self.subdirs.insert(name, Box::default());
}
}
}
fn count_sum_of_sizes_up_to_100000(dir: &Dir) -> usize {
let subdirs_result = dir.subdirs.values()
.map(|subdir| count_sum_of_sizes_up_to_100000(subdir))
.sum::<usize>();
if dir.total_size <= 100000 {
dir.total_size + subdirs_result
} else {
subdirs_result
}
}
fn best_dir_to_delete(dir: &Dir, need_space: usize) -> Option<usize> {
let best_from_subdirs = dir.subdirs.values()
.filter_map(|subdir| best_dir_to_delete(subdir, need_space))
.min();
if best_from_subdirs.is_some() {
best_from_subdirs
} else if dir.total_size >= need_space {
Some(dir.total_size)
} else {
None
}
}
fn main() {
let mut dir = Box::new(Dir::default());
for line in std::io::stdin().lines().map(Result::unwrap) {
let parts = line.split_whitespace().collect::<Vec<_>>();
match (parts[0], parts[1]) {
("$", "cd") => match parts[2] {
"/" => dir = dir.move_to_root(),
".." => dir = dir.move_up(),
subdir => dir = dir.move_down(subdir),
},
("$", _) => {},
("dir", dir_name) => dir.add_dir(dir_name.to_string()),
(size_str, file_name) => {
let size = size_str.parse::<usize>().unwrap();
dir.add_file(file_name.to_string(), size);
},
}
}
dir = dir.move_to_root();
println!("{:?}", best_dir_to_delete(&dir, 30000000 - (70000000 - dir.total_size)));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment