summaryrefslogtreecommitdiffstats
path: root/day07a/src/main.rs
diff options
context:
space:
mode:
Diffstat (limited to 'day07a/src/main.rs')
-rw-r--r--day07a/src/main.rs350
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:?}");
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-16 08:44:42 +0000