diff options
Diffstat (limited to 'day07a/src')
| -rw-r--r-- | day07a/src/main.rs | 350 |
1 files changed, 350 insertions, 0 deletions
diff --git a/day07a/src/main.rs b/day07a/src/main.rs new file mode 100644 index 0000000..bfbbcd3 --- /dev/null +++ b/day07a/src/main.rs @@ -0,0 +1,350 @@ +/// --- Day 7: No Space Left On Device --- +/// +/// You can hear birds chirping and raindrops hitting leaves as the expedition proceeds. +/// Occasionally, you can even hear much louder sounds in the distance; how big do the +/// animals get out here, anyway? +/// +/// The device the Elves gave you has problems with more than just its communication system. You +/// try to run a system update: +/// +/// ``` +/// $ system-update --please --pretty-please-with-sugar-on-top +/// Error: No space left on device +/// ``` +/// +/// Perhaps you can delete some files to make space for the update? +/// +/// You browse around the filesystem to assess the situation and save the resulting terminal output +/// (your puzzle input). For example: +/// +/// ``` +/// $ cd / +/// $ ls +/// dir a +/// 14848514 b.txt +/// 8504156 c.dat +/// dir d +/// $ cd a +/// $ ls +/// dir e +/// 29116 f +/// 2557 g +/// 62596 h.lst +/// $ cd e +/// $ ls +/// 584 i +/// $ cd .. +/// $ cd .. +/// $ cd d +/// $ ls +/// 4060174 j +/// 8033020 d.log +/// 5626152 d.ext +/// 7214296 k +/// ``` +/// +/// The filesystem consists of a tree of files (plain data) and directories (which can contain +/// other directories or files). The outermost directory is called /. You can navigate around the +/// filesystem, moving into or out of directories and listing the contents of the directory you're +/// currently in. +/// +/// Within the terminal output, lines that begin with $ are commands you executed, very much like +/// some modern computers: +/// +/// cd means change directory. This changes which directory is the current directory, but the +/// specific result depends on the argument: +/// cd x moves in one level: it looks in the current directory for the directory named x +/// and makes it the current directory. +/// cd .. moves out one level: it finds the directory that contains the current directory, +/// then makes that directory the current directory. +/// cd / switches the current directory to the outermost directory, /. +/// ls means list. It prints out all of the files and directories immediately contained by the +/// current directory: +/// 123 abc means that the current directory contains a file named abc with size 123. +/// dir xyz means that the current directory contains a directory named xyz. +/// +/// Given the commands and output in the example above, you can determine that the filesystem looks +/// visually like this: +/// +/// ``` +/// - / (dir) +/// - a (dir) +/// - e (dir) +/// - i (file, size=584) +/// - f (file, size=29116) +/// - g (file, size=2557) +/// - h.lst (file, size=62596) +/// - b.txt (file, size=14848514) +/// - c.dat (file, size=8504156) +/// - d (dir) +/// - j (file, size=4060174) +/// - d.log (file, size=8033020) +/// - d.ext (file, size=5626152) +/// - k (file, size=7214296) +/// ``` +/// +/// Here, there are four directories: / (the outermost directory), a and d (which are in /), and e +/// (which is in a). These directories also contain files of various sizes. +/// +/// Since the disk is full, your first step should probably be to find directories that are good +/// candidates for deletion. To do this, you need to determine the total size of each directory. +/// The total size of a directory is the sum of the sizes of the files it contains, directly or +/// indirectly. (Directories themselves do not count as having any intrinsic size.) +/// +/// The total sizes of the directories above can be found as follows: +/// +/// The total size of directory e is 584 because it contains a single file i of size 584 and no +/// other directories. +/// The directory a has total size 94853 because it contains files f (size 29116), g (size +/// 2557), and h.lst (size 62596), plus file i indirectly (a contains e which contains i). +/// Directory d has total size 24933642. +/// As the outermost directory, / contains every file. Its total size is 48381165, the sum of +/// the size of every file. +/// +/// To begin, find all of the directories with a total size of at most 100000, then calculate the +/// sum of their total sizes. In the example above, these directories are a and e; the sum of +/// their total sizes is 95437 (94853 + 584). (As in this example, this process can count files +/// more than once!) +/// +/// Find all of the directories with a total size of at most 100000. What is the sum of the total +/// sizes of those directories? +use clap::Parser; +use nom::branch::alt; +use nom::bytes::streaming::tag; +use nom::character::streaming::{char, newline, not_line_ending, space1, u64}; +use nom::combinator::{map, peek}; +use nom::error::{context, ContextError, ErrorKind as NomErrorKind, ParseError}; +use nom::multi::many_till; +use nom::sequence::{delimited, preceded, terminated, tuple}; +use nom::IResult; + +use std::collections::HashMap; +use std::fs::File; +use std::io::prelude::*; +use std::io::BufReader; +use std::iter::*; +use std::path::PathBuf; + +pub type Input<'a> = &'a str; +pub type Result<'a, T> = IResult<Input<'a>, T, Error<Input<'a>>>; + +#[derive(Clone, Debug, PartialEq, Eq)] +pub enum ErrorKind { + Nom(NomErrorKind), + Context(&'static str), + Custom(String), +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct Error<I> { + pub errors: Vec<(I, ErrorKind)>, +} + +impl<I> ParseError<I> for Error<I> { + fn from_error_kind(input: I, kind: NomErrorKind) -> Self { + let errors = vec![(input, ErrorKind::Nom(kind))]; + Self { errors } + } + + fn append(input: I, kind: NomErrorKind, mut other: Self) -> Self { + other.errors.push((input, ErrorKind::Nom(kind))); + other + } +} + +impl<I> ContextError<I> for Error<I> { + fn add_context(input: I, ctx: &'static str, mut other: Self) -> Self { + other.errors.push((input, ErrorKind::Context(ctx))); + other + } +} + +const FILEPATH: &'static str = "examples/input.txt"; +const EOF_CHAR: char = '\0'; +const DIRMAXSIZE: u64 = 100000; + +#[derive(Parser, Debug)] +#[clap(author, version, about, long_about = None)] +struct Cli { + #[clap(short, long, default_value = FILEPATH)] + file: PathBuf, +} + +#[derive(Clone, Debug)] +enum Commands { + ChangeDir(String), + List(Vec<ListEntry>), +} + +#[derive(Clone, Debug)] +enum ListEntry { + File(FileEntry), + Folder(String), +} + +#[derive(Clone, Debug)] +struct FileEntry { + name: String, + size: u64, +} + +#[derive(Clone, Debug)] +struct Arena(Vec<Node>); + +#[derive(Clone, Debug)] +struct Node { + size: u64, + parent: Option<usize>, + children: HashMap<String, usize>, +} + +impl Node { + fn new() -> Self { + Node { + size: 0, + parent: None, + children: HashMap::new(), + } + } + + fn with_parent(idx: usize) -> Self { + Node { + size: 0, + parent: Some(idx), + children: HashMap::new(), + } + } +} + +impl Arena { + // NOTE: only call this once per node + fn consume(&mut self, idx: usize, ls: Vec<ListEntry>) { + for le in ls.into_iter() { + match le { + ListEntry::File(f) => { + let mut iteridx = idx; + loop { + self.0[iteridx].size += f.size; + iteridx = if let Some(pidx) = self.0[iteridx].parent { + pidx + } else { + break; + }; + } + } + ListEntry::Folder(f) => { + let fidx = self.0.len(); + self.0.push(Node::with_parent(idx)); + self.0[idx].children.insert(f, fidx); + } + } + } + } + + fn get(&mut self, idx: usize) -> &mut Node { + &mut self.0[idx] + } +} + +fn parse_cd(input: &str) -> Result<Commands> { + context( + "parse_cd", + map( + delimited(tuple((tag("cd"), space1)), not_line_ending, newline), + |s: &str| Commands::ChangeDir(s.to_string()), + ), + )(input) +} + +fn end_of_file_or_ls(input: &str) -> Result<char> { + alt((char(EOF_CHAR), peek(char('$'))))(input) +} + +fn parse_ls(input: &str) -> Result<Commands> { + let (input, _) = context("parse_ls", terminated(tag("ls"), newline))(input)?; + let (input, (lsv, _)) = many_till(parse_ls_entry, end_of_file_or_ls)(input)?; + Ok((input, Commands::List(lsv))) +} + +fn parse_ls_entry(input: &str) -> Result<ListEntry> { + context("parse_ls_entry", alt((parse_file, parse_folder)))(input) +} + +fn parse_file(input: &str) -> Result<ListEntry> { + map( + terminated(tuple((u64, preceded(tag(" "), not_line_ending))), newline), + |(size, name): (u64, &str)| { + ListEntry::File(FileEntry { + name: name.to_string(), + size, + }) + }, + )(input) +} + +fn parse_folder(input: &str) -> Result<ListEntry> { + map( + delimited(tag("dir "), not_line_ending, newline), + |s: &str| ListEntry::Folder(s.to_string()), + )(input) +} + +fn parse_cmd(input: &str) -> Result<Commands> { + context( + "parse_cmd", + preceded(tuple((tag("$"), space1)), alt((parse_cd, parse_ls))), + )(input) +} + +fn main() { + let args = Cli::parse(); + + let file = File::open(&args.file).unwrap(); + let mut reader = BufReader::new(file); + + let mut buf = String::new(); + let mut cmds = Vec::new(); + 'block: loop { + let len = reader.read_line(&mut buf).unwrap(); + if len == 0 { + buf.push(EOF_CHAR); + } + loop { + match parse_cmd(buf.as_str()) { + Ok((input, cmd)) => { + cmds.push(cmd); + if len == 0 && input.len() == 0 { + break 'block; + } + let _ = buf.drain(..(buf.len() - input.len())); + } + Err(err) => match err { + nom::Err::Incomplete(_) => continue 'block, + e @ _ => panic!("buf={} err={}", buf, e), + }, + } + } + } + + let mut loc = 0; + let mut arena = Arena(Vec::new()); + arena.0.push(Node::new()); + for cmd in cmds.into_iter() { + match cmd { + Commands::ChangeDir(dir) => match dir.as_str() { + "/" => loc = 0, + ".." => loc = arena.get(loc).parent.unwrap(), + _ => loc = arena.get(loc).children[&dir], + }, + Commands::List(lsv) => arena.consume(loc, lsv), + } + } + + let res: u64 = arena + .0 + .into_iter() + .filter(|n| n.size <= DIRMAXSIZE) + .map(|n| n.size) + .sum(); + println!("{res:?}"); +} |