#![allow(clippy::same_item_push)]
use std::{
    fs::File,
    io::{BufRead, BufReader},
    path::Path,
};

#[derive(Debug, Clone)]
struct FS {
    blocks: Vec<FSBlock>,
}

impl FS {
    fn _print_blocks(&self) {
        for b in &self.blocks {
            match b {
                FSBlock::File(id, size) => print!("{}", id.to_string().repeat(*size)),
                FSBlock::Free(size) => print!("{}", ".".repeat(*size)),
            }
        }
        println!();
    }

    fn from_disk_map(disk_map: Vec<usize>) -> Self {
        let mut fs = FS { blocks: vec![] };
        let mut current_id = 0;
        for (i, n) in disk_map.iter().enumerate() {
            if i % 2 == 0 {
                fs.blocks.push(FSBlock::File(current_id, *n));
                current_id += 1;
            } else {
                fs.blocks.push(FSBlock::Free(*n));
            }
        }
        fs
    }

    fn compact(&mut self) {
        let mut ignore_list = vec![];
        loop {
            let self_tmp = self.clone();
            let last_file_block = match self_tmp
                .blocks
                .iter()
                .enumerate()
                .filter_map(|(i, b)| match b {
                    FSBlock::File(id, _) => {
                        if ignore_list.contains(id) {
                            None
                        } else {
                            Some((i, b))
                        }
                    }
                    _ => None,
                })
                .last()
            {
                Some(b) => b,
                None => break,
            };
            let (last_file_block_pos, FSBlock::File(last_file_block_id, last_file_block_size)) =
                last_file_block
            else {
                unreachable!()
            };

            let first_free_block = match self_tmp
                .blocks
                .iter()
                .enumerate()
                .filter_map(|(i, b)| match b {
                    FSBlock::Free(size) => {
                        if size >= last_file_block_size {
                            Some((i, b))
                        } else {
                            None
                        }
                    }
                    _ => None,
                })
                .rev()
                .last()
            {
                Some(b) => b,
                None => {
                    ignore_list.push(*last_file_block_id);
                    continue;
                }
            };
            let (first_free_block_pos, FSBlock::Free(_)) = first_free_block else {
                unreachable!()
            };

            ignore_list.push(*last_file_block_id);
            if last_file_block_pos > first_free_block_pos {
                if let Some(b) = self.blocks.get_mut(first_free_block_pos) {
                    match b {
                        FSBlock::Free(size) => *size -= last_file_block_size,
                        _ => unreachable!(),
                    }
                }

                let file_block = self.blocks.remove(last_file_block_pos);
                self.blocks.insert(first_free_block_pos, file_block);
                self.blocks
                    .insert(last_file_block_pos, FSBlock::Free(*last_file_block_size));

                //self.print_blocks();
            }
        }
    }

    fn checksum(&self) -> usize {
        let mut a = vec![];
        for b in &self.blocks {
            match b {
                FSBlock::File(id, size) => {
                    for _ in 0..*size {
                        a.push(*id);
                    }
                }
                FSBlock::Free(size) => {
                    for _ in 0..*size {
                        a.push(0);
                    }
                }
            }
        }
        a.iter()
            .enumerate()
            .map(|(i, id)| i * id)
            .collect::<Vec<usize>>()
            .iter()
            .sum()
    }
}

#[derive(Debug, Clone)]
enum FSBlock {
    File(usize, usize),
    Free(usize),
}

pub fn part_two(input: &Path) -> anyhow::Result<usize> {
    let mut reader = BufReader::new(File::open(input)?);

    let mut input_str = String::new();
    let _ = reader.read_line(&mut input_str)?;
    let input = input_str
        .trim()
        .chars()
        .map(|c| -> usize { c.to_string().parse().unwrap() })
        .collect();
    let mut fs = FS::from_disk_map(input);
    //fs.print_blocks();
    fs.compact();

    Ok(fs.checksum())
}