/// --- 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:?}");
}