aoc2022-day7.rs

aoc2022-day7.rs

use std::{collections::BTreeMap, str::FromStr};

type Error = String;
type Result<T> = std::result::Result<T, Error>;

const INPUT: &str = include_str!("./day7.txt");

#[derive(Debug)]
struct File(String);

macro_rules! from_str_impl {
    ($ty:ty, $impl_fn:expr) => {
        impl FromStr for $ty {
            type Err = Error;

            fn from_str(s: &str) -> Result<Self> {
                {
                    let impl_fn: fn(&str) -> Result<Self> = $impl_fn;
                    impl_fn(s)
                }
            }
        }
    };
}

from_str_impl! {
    File,
    |s| Ok(Self(s.to_owned()))
}

#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
struct NamedDirectory(String);

from_str_impl! {
    NamedDirectory,
    |s| Ok(Self(s.to_owned()))
}

#[derive(Debug, Default)]
enum Directory {
    #[default]
    Root,
    Parent,
    Named(NamedDirectory),
}

#[derive(Debug)]
struct DirectoryEntry(NamedDirectory);
from_str_impl! {
    DirectoryEntry,
    |s| s.split_once(' ')
        .ok_or_else(|| "directory entry contains a space".to_owned())
        .and_then(|line| match line {
            ("dir", name) => name.parse().map(Self),
            _ => Err("directory entry must start with a 'dir' keyword".to_owned()),
        })
}

from_str_impl! {
    Directory,
    |s| match s {
        ".." => Ok(Self::Parent),
        "/" => Ok(Self::Root),
        named => named.parse().map(Self::Named),
    }
}

#[derive(Debug)]
struct SizeEntry {
    size: u32,
    #[allow(dead_code)]
    file: File,
}

from_str_impl! {
    SizeEntry,
    |s| s.split_once(' ')
        .ok_or_else(|| "directory entry must have a space within".to_owned())
        .and_then(|(size, filename)| {
            size.parse::<u32>()
                .map_err(|_| format!("{size}: size must be an int"))
                .and_then(|size| filename.parse().map(|filename| (size, filename)))
                .map(|(size, file)| Self { size, file })
        })
}

#[derive(Debug)]
enum Command {
    Cd(Directory),
    Ls,
}

from_str_impl! {
    Command,
    |s| match &s.split(' ').collect::<Vec<_>>()[..] {
        &["$", "cd", directory] => directory.parse().map(Self::Cd),
        &["$", "ls"] => Ok(Self::Ls),
        other => Err(format!("'{other:?}' is not a valid command")),
    }
}

#[derive(Debug)]
enum OutputEntry {
    Size(SizeEntry),
    Directory(DirectoryEntry),
}

from_str_impl! {
    OutputEntry,
    |s| s.parse()
        .map(Self::Size)
        .or_else(|_| s.parse().map(Self::Directory))
}

#[derive(Debug)]
enum Line {
    Command(Command),
    Output(OutputEntry),
}

from_str_impl! {
    Line,
    |s| s.parse()
        .map(Self::Command)
        .or_else(|_| s.parse().map(Self::Output))
}

#[derive(Debug, Default)]
struct DirectoryCrawler {
    directories: BTreeMap<Vec<NamedDirectory>, Vec<OutputEntry>>,
    current_directory: Vec<NamedDirectory>,
}

impl DirectoryCrawler {
    pub fn load(&mut self, line: Line) {
        match line {
            Line::Command(command) => match command {
                Command::Cd(directory) => match directory {
                    Directory::Root => self.current_directory.clear(),
                    Directory::Parent => {
                        self.current_directory.pop();
                    }
                    Directory::Named(named) => self.current_directory.push(named),
                },
                Command::Ls => {}
            },
            Line::Output(output) => self
                .directories
                .entry(self.current_directory.clone())
                .or_default()
                .push(output),
        }
    }
}

fn main() -> Result<()> {
    let mut crawler = DirectoryCrawler::default();
    INPUT
        .lines()
        .map(Line::from_str)
        .collect::<Result<Vec<_>>>()?
        .into_iter()
        .map(|line| crawler.load(line))
        .for_each(drop);

    println!("{crawler:#?}");

    let directory_sizes = {
        let mut sizes = BTreeMap::<_, u32>::default();
        crawler
            .directories
            .iter()
            .rev()
            .map(|(path, entries)| {
                (0..path.len() + 1)
                    .map(|len| &path[0..len])
                    .for_each(|slice| {
                        *sizes.entry(slice.to_vec()).or_default() += entries
                            .iter()
                            .filter_map(|e| match e {
                                OutputEntry::Size(size) => Some(size),
                                OutputEntry::Directory(_) => None,
                            })
                            .map(|SizeEntry { size, .. }| *size)
                            .sum::<u32>()
                    })
            })
            .for_each(drop);
        sizes
    };

    println!("sizes: {directory_sizes:#?}");

    println!(
        "part 1: {}",
        directory_sizes
            .iter()
            .filter_map(|(_, &v)| (v < 100000).then_some(v))
            .sum::<u32>()
    );

    {
        let minimum_free_space = 30000000;
        let device_capacity = 70000000;
        let used_space = directory_sizes.get(&vec![]).ok_or("root not calculated")?;
        let free_space = device_capacity - used_space;

        println!("\nminimum_free_space: {minimum_free_space}");
        println!("device_capacity: {device_capacity}");
        println!("used_space: {used_space}");
        println!("free_space: {free_space}\n");

        let (size, directory) = directory_sizes
            .iter()
            .map(|(path, &size)| (size, path))
            .collect::<BTreeMap<u32, _>>()
            .into_iter()
            .find(|(size, _path)| (free_space + size) >= minimum_free_space)
            .ok_or("it is impossible to install update on this device")?;
        let directory_pretty = [
            "/",
            &directory
                .iter()
                .map(|NamedDirectory(dir)| dir.as_str())
                .collect::<Vec<_>>()
                .join("/"),
        ]
        .join("");
        println!("part 2: {size} ({directory_pretty})");
    }

    Ok(())
}