#![allow(dead_code)]
#![allow(unused_variables)]
#![allow(unused_mut)]
use std::env;
use std::fs::File;
use std::io::Read;

#[derive(Debug, PartialEq, Clone)]
struct Block {
    isfile: bool,
    id: u64,
}

fn print_fs(fs: &Vec<Block>) {
    for b in fs {
        if b.isfile {
            print!("{}", b.id);
        } else {
            print!(".");
        }
    }
    println!();
}

fn compact(mut fs: Vec<Block>) -> Vec<Block> {
    for i in (0..fs.len()).rev() {
        if !fs[i].isfile {
            continue;
        }
        for j in 0..fs.len() {
            if i < j {
                break;
            }
            if !fs[j].isfile {
                fs.swap(i, j);
                break;
            }
        }
    }
    fs
}

fn same(index: usize, fs: &Vec<Block>) -> (usize, usize) {
    let mut start: usize = 0;
    let mut end: usize = 0;
    let b = &fs[index];

    for e in index..fs.len() {
        if fs[e].isfile == b.isfile && (!fs[e].isfile || fs[e].id == b.id) {
            end = e;
        } else {
            break;
        }
    }

    for s in (0..=index).rev() {
        if fs[s].isfile == b.isfile && (!fs[s].isfile || fs[s].id == b.id) {
            start = s;
        } else {
            break;
        }
    }

    return (start, end - start + 1);
}

fn compact2(mut fs: Vec<Block>) -> Vec<Block> {
    let mut i = fs.len() - 1;
    loop {
        let mut il;
        (i, il) = same(i, &fs);

        if !fs[i].isfile {
            if i == 0 {
                break;
            }
            i -= 1;
            continue;
        }

        let mut j = 0;
        let mut jl;
        loop {
            (j, jl) = same(j, &fs);
            if j > i {
                break;
            }
            if fs[j].isfile || il > jl {
                if j + jl >= fs.len() {
                    break;
                }
                j = j + jl;
                continue;
            }

            for r in 0..il {
                fs.swap(i + r, j + r);
            }

            if j + jl >= fs.len() {
                break;
            }
            j = j + jl;
        }

        if i == 0 {
            break;
        }
        i -= 1;
    }

    fs
}

fn checksum(fs: &Vec<Block>) -> u64 {
    let mut sum = 0;
    for i in (0..fs.len()).rev() {
        if fs[i].isfile {
            sum += (i as u64) * fs[i].id;
        }
    }
    return sum;
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = if args.len() == 1 {
        "in/".to_owned() + args[0].split('/').last().unwrap() + ".pzl"
    } else {
        args[1].clone()
    };
    let mut f = File::open(filename).expect("cannot open file");
    let mut content = String::new();
    f.read_to_string(&mut content).expect("cannot read file");
    let mut lines = content.trim_end().split("\n");

    let line = lines.next().unwrap();

    let mut fs: Vec<Block> = Vec::new();
    let mut isfile = true;
    let mut id = 0;
    for (i, c) in line.chars().enumerate() {
        let n = c.to_digit(10).unwrap() as usize;

        for j in 0..n {
            let b = Block {
                isfile: isfile,
                id: id,
            };
            fs.push(b);
        }
        if isfile {
            id += 1;
        }
        isfile ^= true;
    }

    //print_fs(&fs);
    let fs1 = compact(fs.clone());
    //print_fs(&fs1);
    let res1 = checksum(&fs1);

    //print_fs(&fs);
    let fs2 = compact2(fs.clone());
    //print_fs(&fs2);
    let res2 = checksum(&fs2);

    println!("res1: {}", res1);
    println!("res2: {}", res2);
    assert_eq!(res1, 6370402949053);
    assert_eq!(res2, 6398096697992);
}