328 lines
8.3 KiB
Rust
328 lines
8.3 KiB
Rust
#![feature(iterator_try_collect, absolute_path, hash_set_entry)]
|
|
|
|
use std::collections::HashMap;
|
|
use std::error::Error;
|
|
use std::fmt::Display;
|
|
use std::fs;
|
|
use std::hash::{Hash, Hasher};
|
|
use std::io::{self, BufRead};
|
|
use std::path::{Path, PathBuf};
|
|
|
|
mod parsing {
|
|
use nom::{
|
|
branch::alt,
|
|
bytes::complete::{is_not, tag},
|
|
character::complete::{digit1, multispace0},
|
|
combinator::{into, map, map_res},
|
|
sequence::{delimited, pair, preceded, separated_pair},
|
|
IResult,
|
|
};
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
pub enum Command {
|
|
Ls,
|
|
Cd(String),
|
|
}
|
|
|
|
fn cd(input: &str) -> IResult<&str, Command> {
|
|
let (input, dir) =
|
|
preceded(delimited(multispace0, tag("cd"), multispace0), filename)(input)?;
|
|
Ok((input, Command::Cd(dir)))
|
|
}
|
|
|
|
fn ls(input: &str) -> IResult<&str, Command> {
|
|
let (input, _) = tag("ls")(input)?;
|
|
Ok((input, Command::Ls))
|
|
}
|
|
|
|
fn command(input: &str) -> IResult<&str, Command> {
|
|
preceded(delimited(multispace0, tag("$"), multispace0), alt((cd, ls)))(input)
|
|
}
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
pub enum Listing {
|
|
Dir(String),
|
|
File(String, usize),
|
|
}
|
|
|
|
fn dir(input: &str) -> IResult<&str, Listing> {
|
|
let (input, f_name) = preceded(pair(tag("dir"), multispace0), filename)(input)?;
|
|
Ok((input, Listing::Dir(f_name)))
|
|
}
|
|
|
|
fn filename(input: &str) -> IResult<&str, String> {
|
|
map(is_not(" "), |r: &str| r.to_string())(input)
|
|
}
|
|
|
|
fn file(input: &str) -> IResult<&str, Listing> {
|
|
let (input, (f_size, f_name)) = separated_pair(
|
|
map_res(digit1, |s: &str| s.parse::<usize>()),
|
|
multispace0,
|
|
filename,
|
|
)(input)?;
|
|
Ok((input, Listing::File(f_name, f_size)))
|
|
}
|
|
|
|
fn listing(input: &str) -> IResult<&str, Listing> {
|
|
alt((dir, file))(input)
|
|
}
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
pub enum Line {
|
|
Result(Listing),
|
|
Command(Command),
|
|
}
|
|
|
|
impl From<Listing> for Line {
|
|
fn from(value: Listing) -> Self {
|
|
Self::Result(value)
|
|
}
|
|
}
|
|
|
|
impl From<Command> for Line {
|
|
fn from(value: Command) -> Self {
|
|
Self::Command(value)
|
|
}
|
|
}
|
|
|
|
pub fn line(input: &str) -> IResult<&str, Line> {
|
|
alt((into(listing), into(command)))(input)
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn test_command() {
|
|
assert_eq!(Ok(("", Command::Ls)), command("$ ls"));
|
|
assert_eq!(
|
|
Ok(("", Command::Cd("poo".to_string()))),
|
|
command("$ cd poo")
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn test_listing() {
|
|
assert_eq!(
|
|
Ok(("", Listing::Dir("cabbage".to_string()))),
|
|
listing("dir cabbage")
|
|
);
|
|
assert_eq!(
|
|
Ok(("", Listing::File("boob.txt".to_string(), 424242))),
|
|
listing("424242 boob.txt")
|
|
);
|
|
}
|
|
}
|
|
}
|
|
|
|
use parsing::{line, Command, Line, Listing};
|
|
use path_clean::clean;
|
|
|
|
#[derive(Debug)]
|
|
struct State {
|
|
cur_path: PathBuf,
|
|
filesystem: FileNode,
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
struct FileNode {
|
|
name: String,
|
|
children: HashMap<String, FileNode>,
|
|
size: Option<usize>,
|
|
}
|
|
|
|
impl Display for FileNode {
|
|
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
|
|
write!(f, "{} ", if self.is_dir() { "dir" } else { "file" })?;
|
|
if let Some(size) = self.size {
|
|
write!(f, "{} ", size)?;
|
|
}
|
|
write!(f, "{}", self.name)
|
|
}
|
|
}
|
|
|
|
impl PartialEq for FileNode {
|
|
fn eq(&self, other: &Self) -> bool {
|
|
self.name.eq(&other.name)
|
|
}
|
|
}
|
|
impl Eq for FileNode {}
|
|
|
|
impl Hash for FileNode {
|
|
fn hash<H: Hasher>(&self, state: &mut H) {
|
|
self.name.hash(state);
|
|
}
|
|
}
|
|
|
|
impl From<String> for FileNode {
|
|
fn from(value: String) -> Self {
|
|
FileNode::new(value)
|
|
}
|
|
}
|
|
|
|
impl<'a> IntoIterator for &'a FileNode {
|
|
type Item = &'a FileNode;
|
|
|
|
type IntoIter = std::vec::IntoIter<Self::Item>;
|
|
|
|
fn into_iter(self) -> Self::IntoIter {
|
|
fn append<'a>(tree: &'a FileNode, v: &mut Vec<&'a FileNode>) {
|
|
v.push(tree);
|
|
for child in tree.children.values() {
|
|
append(child, v);
|
|
}
|
|
}
|
|
|
|
let mut result = vec![];
|
|
append(self, &mut result);
|
|
result.into_iter()
|
|
}
|
|
}
|
|
|
|
impl FileNode {
|
|
fn is_dir(&self) -> bool {
|
|
!self.children.is_empty()
|
|
}
|
|
|
|
fn new(name: String) -> Self {
|
|
Self {
|
|
name,
|
|
children: HashMap::new(),
|
|
size: None,
|
|
}
|
|
}
|
|
|
|
fn calculate_size(&mut self) -> usize {
|
|
*self.size.get_or_insert_with(|| {
|
|
self.children
|
|
.iter_mut()
|
|
.fold(0, |acc, (_, v)| acc + v.calculate_size())
|
|
})
|
|
}
|
|
|
|
fn add(&mut self, path: String, size: Option<usize>) -> Result<(), Box<dyn Error>> {
|
|
let path = Path::new(&path);
|
|
if path.components().count() == 1 {
|
|
self.size = self.size.or(size);
|
|
return Ok(());
|
|
}
|
|
|
|
let path = path.strip_prefix(&self.name)?;
|
|
let first_comp = path
|
|
.components()
|
|
.next()
|
|
.ok_or("Expected at least one component")?
|
|
.as_os_str()
|
|
.to_string_lossy()
|
|
.to_string();
|
|
|
|
let path_str = path.as_os_str().to_string_lossy().to_string();
|
|
|
|
if let Some(child) = self.children.get_mut(&first_comp) {
|
|
child.add(path_str, size)?;
|
|
} else {
|
|
let mut child = FileNode::new(first_comp.clone());
|
|
child.add(path_str, size)?;
|
|
self.children.insert(first_comp, child);
|
|
}
|
|
|
|
Ok(())
|
|
}
|
|
}
|
|
|
|
impl State {
|
|
fn new() -> Self {
|
|
State {
|
|
cur_path: PathBuf::from("/"),
|
|
filesystem: FileNode::new("/".to_owned()),
|
|
}
|
|
}
|
|
|
|
fn from_lines(lines: &[String]) -> Result<Self, Box<dyn Error>> {
|
|
let mut state = State::new();
|
|
lines
|
|
.iter()
|
|
.flat_map(|l| line(l))
|
|
.try_for_each(|(_, l)| state.process(l))?;
|
|
Ok(state)
|
|
}
|
|
|
|
fn process(&mut self, line: Line) -> Result<(), Box<dyn Error>> {
|
|
match line {
|
|
Line::Command(cmd) => self.run(cmd),
|
|
Line::Result(listing) => self.process_result(listing)?,
|
|
}
|
|
Ok(())
|
|
}
|
|
|
|
fn run(&mut self, cmd: Command) {
|
|
if let Command::Cd(p) = cmd {
|
|
self.cur_path.push(p)
|
|
}
|
|
}
|
|
|
|
fn process_result(&mut self, res: Listing) -> Result<(), Box<dyn Error>> {
|
|
let (path, maybe_size) = match res {
|
|
Listing::File(path, size) => (path, Some(size)),
|
|
Listing::Dir(path) => (path, None),
|
|
};
|
|
|
|
let filename = clean(&self.cur_path.join(path).to_string_lossy());
|
|
self.filesystem.add(filename, maybe_size)?;
|
|
Ok(())
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
let filename = "etc/p07.txt";
|
|
let file = fs::File::open(filename).expect("Can't open file");
|
|
let lines: Vec<String> = io::BufReader::new(file).lines().flatten().collect();
|
|
|
|
println!("PART ONE ---------------");
|
|
part1(&lines);
|
|
println!("\n PART TWO ---------------");
|
|
part2(&lines);
|
|
}
|
|
|
|
fn part1(lines: &[String]) {
|
|
let mut state = State::from_lines(lines).unwrap();
|
|
let full_size = state.filesystem.calculate_size();
|
|
dbg!(full_size);
|
|
|
|
const MAX_DIR_SIZE: usize = 100_000;
|
|
dbg!(state
|
|
.filesystem
|
|
.into_iter()
|
|
.filter(|f| f.is_dir())
|
|
.flat_map(|f| f.size)
|
|
.filter(|&s| s < MAX_DIR_SIZE)
|
|
.sum::<usize>());
|
|
}
|
|
|
|
fn part2(lines: &[String]) {
|
|
let mut state = State::from_lines(lines).unwrap();
|
|
let full_size = state.filesystem.calculate_size();
|
|
dbg!(full_size);
|
|
|
|
const AVAILABLE_SPACE: usize = 70_000_000;
|
|
const DESIRED_AVAILABLE_SPACE: usize = 30_000_000;
|
|
const MAX_USED: usize = AVAILABLE_SPACE - DESIRED_AVAILABLE_SPACE;
|
|
|
|
let over_by = full_size - MAX_USED;
|
|
|
|
println!(
|
|
"Minimum dir to delete: {}",
|
|
state
|
|
.filesystem
|
|
.into_iter()
|
|
.filter(|f| f.is_dir()
|
|
&& match f.size {
|
|
Some(s) => s >= over_by,
|
|
_ => false,
|
|
})
|
|
.min_by(|a, b| a.size.cmp(&b.size))
|
|
.expect("Expect a minimum")
|
|
);
|
|
}
|