#[path = "../lib.rs"]
mod lib;

fn parse() -> Vec<(usize, usize)> {
    let mut galaxies = vec![];
    for (y, line) in lib::iter_input().enumerate() {
        for (x, c) in line.chars().enumerate() {
            if c == '#' {
                galaxies.push((x, y));
            }
        }
    }
    return galaxies;
}

fn expand(galaxies: &Vec<(usize, usize)>, factor: usize) -> Vec<(usize, usize)> {
    let mut current = galaxies.clone();
    current.sort_unstable_by_key(|(x, _)| *x);

    let mut expanded = vec![];
    let mut offset = 0;
    let mut prev = 0;

    for (x, y) in current.iter() {
        if *x > prev {
            offset += (*x - prev - 1) * (factor - 1);
        }
        expanded.push((*x + offset, *y));
        prev = *x;
    }

    current = expanded;
    current.sort_unstable_by_key(|(_, y)| *y);
    expanded = vec![];
    offset = 0;
    prev = 0;

    for (x, y) in current.iter() {
        if *y > prev {
            offset += (*y - prev - 1) * (factor - 1);
        }
        expanded.push((*x, *y + offset));
        prev = *y;
    }

    return expanded;
}

fn count_distances(galaxies: &Vec<(usize, usize)>) -> usize {
    let mut sum = 0;
    for i in 0..galaxies.len() {
        let (x1, y1) = galaxies[i];
        for j in (i + 1)..galaxies.len() {
            let (x2, y2) = galaxies[j];
            sum += x1.abs_diff(x2) + y1.abs_diff(y2);
        }
    }
    return sum;
}

fn main() {
    for _ in 0..1000 {
        let galaxies = parse();

        let expanded1 = expand(&galaxies, 2);
        let sum1 = count_distances(&expanded1);
        println!("part1: {}", sum1);

        let expanded2 = expand(&galaxies, 1_000_000);
        let sum2 = count_distances(&expanded2);
        println!("part2: {}", sum2);
    }
}