You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
189 lines
3.4 KiB
Rust
189 lines
3.4 KiB
Rust
static INPUT: &str = include_str!("inputs/day7.txt");
|
|
|
|
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
|
|
struct FileID(usize);
|
|
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
|
|
struct DirID(usize);
|
|
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
|
|
enum DirEntryKind {
|
|
File(FileID),
|
|
Dir(DirID),
|
|
}
|
|
#[derive(Debug)]
|
|
struct DirEntry {
|
|
name: String,
|
|
kind: DirEntryKind,
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
struct File {
|
|
size: usize,
|
|
}
|
|
#[derive(Debug)]
|
|
struct Dir {
|
|
parent: DirID,
|
|
children: Vec<DirEntry>,
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
struct Fs {
|
|
files: Vec<File>,
|
|
dirs: Vec<Dir>,
|
|
}
|
|
impl Fs {
|
|
fn new() -> Self {
|
|
Self {
|
|
files: vec![],
|
|
dirs: vec![Dir {
|
|
parent: DirID(0),
|
|
children: vec![],
|
|
}],
|
|
}
|
|
}
|
|
|
|
fn root(&self) -> DirID {
|
|
DirID(0)
|
|
}
|
|
|
|
fn mkdir(&mut self, target: DirID, name: &str) -> DirID {
|
|
let new_id = DirID(self.dirs.len());
|
|
self.dirs.push(Dir {
|
|
parent: target,
|
|
children: vec![],
|
|
});
|
|
self.dirs[target.0].children.push(DirEntry {
|
|
name: name.to_string(),
|
|
kind: DirEntryKind::Dir(new_id),
|
|
});
|
|
|
|
new_id
|
|
}
|
|
|
|
fn mkfile(&mut self, target: DirID, name: &str, size: usize) -> FileID {
|
|
let new_id = FileID(self.files.len());
|
|
self.files.push(File { size });
|
|
self.dirs[target.0].children.push(DirEntry {
|
|
name: name.to_string(),
|
|
kind: DirEntryKind::File(new_id),
|
|
});
|
|
|
|
new_id
|
|
}
|
|
|
|
fn entry(&self, target: DirID, name: &str) -> DirEntryKind {
|
|
let dir = &self.dirs[target.0];
|
|
|
|
dir.children
|
|
.iter()
|
|
.find(|e| e.name == name)
|
|
.map(|e| e.kind)
|
|
.unwrap()
|
|
}
|
|
|
|
fn parent(&self, target: DirID) -> DirID {
|
|
self.dirs[target.0].parent
|
|
}
|
|
|
|
fn dirsz(&self, target: DirID) -> usize {
|
|
let dir = &self.dirs[target.0];
|
|
|
|
dir.children
|
|
.iter()
|
|
.map(|c| match c.kind {
|
|
DirEntryKind::File(fid) => self.files[fid.0].size,
|
|
DirEntryKind::Dir(did) => self.dirsz(did),
|
|
})
|
|
.sum()
|
|
}
|
|
}
|
|
|
|
fn make_fs(s: &str) -> Fs {
|
|
let mut lines = s.split('\n').filter(|s| !s.is_empty()).peekable();
|
|
|
|
let mut fs = Fs::new();
|
|
let mut current_dir = fs.root();
|
|
|
|
while let Some(line) = lines.next() {
|
|
assert!(line.starts_with('$'));
|
|
let mut parts = line.split(' ').skip(1);
|
|
|
|
match parts.next().unwrap() {
|
|
"cd" => {
|
|
let arg = parts.next().unwrap();
|
|
|
|
current_dir = match arg {
|
|
"/" => fs.root(),
|
|
".." => fs.parent(current_dir),
|
|
_ => {
|
|
let entry = fs.entry(current_dir, arg);
|
|
match entry {
|
|
DirEntryKind::Dir(d) => d,
|
|
_ => panic!(),
|
|
}
|
|
}
|
|
};
|
|
}
|
|
"ls" => {
|
|
while let Some(data_line) = lines.peek() {
|
|
if data_line.starts_with('$') {
|
|
break;
|
|
}
|
|
|
|
let mut parts = data_line.split(' ');
|
|
let ty = parts.next().unwrap();
|
|
let name = parts.next().unwrap();
|
|
|
|
match ty {
|
|
"dir" => {
|
|
fs.mkdir(current_dir, name);
|
|
}
|
|
_ => {
|
|
let sz: usize = ty.parse().unwrap();
|
|
fs.mkfile(current_dir, name, sz);
|
|
}
|
|
}
|
|
|
|
lines.next();
|
|
}
|
|
}
|
|
_ => panic!(),
|
|
}
|
|
}
|
|
|
|
fs
|
|
}
|
|
|
|
pub fn part1() {
|
|
let fs = make_fs(INPUT);
|
|
|
|
println!(
|
|
"{}",
|
|
fs.dirs
|
|
.iter()
|
|
.enumerate()
|
|
.map(|(did, _)| fs.dirsz(DirID(did)))
|
|
.filter(|sz| sz <= &100000)
|
|
.sum::<usize>()
|
|
);
|
|
}
|
|
|
|
pub fn part2() {
|
|
let fs = make_fs(INPUT);
|
|
let total = 70_000_000;
|
|
let needed_free = 30_000_000;
|
|
let used = fs.dirsz(fs.root());
|
|
let free = total - used;
|
|
let diff = needed_free - free;
|
|
|
|
println!(
|
|
"{}",
|
|
fs.dirs
|
|
.iter()
|
|
.enumerate()
|
|
.map(|(did, _)| fs.dirsz(DirID(did)))
|
|
.filter(|sz| sz >= &diff)
|
|
.min()
|
|
.unwrap()
|
|
);
|
|
}
|