AOC 2023 Day 11

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;

use point2d::point2d::Point2D;

extern crate itertools;
use itertools::Itertools;

// Expand map, where times parameter is the column multiplier
// eg. expanding the map doubles (times=2) the width of empty space
fn expand_map(map: &Vec<Point2D>, times: i64) -> Vec<Point2D> {
    let xmax = map.iter().map(|pt| pt.x).max().unwrap();
    let ymax = map.iter().map(|pt| pt.y).max().unwrap();

    // Determine which rows and columns to expand
    let expanded_rows: Vec<_> =
        (0..=ymax)
        .into_iter()
        .filter(|y| {
            (0..=xmax).into_iter().all(|x| !map.contains(&Point2D { x: x, y: *y}))
        })
        .collect();
    let expanded_cols: Vec<_> =
        (0..=xmax)
        .into_iter()
        .filter(|x| {
            (0..=ymax).into_iter().all(|y| !map.contains(&Point2D { x: *x, y: y}))
        })
        .collect();

    // Generate expanded map
    let mut new_map = map.clone();
    for y in (0..=ymax).rev() {
        if expanded_rows.contains(&y) {
            for g in &mut new_map {
                if g.y > y { g.y += times-1 }
            }
        }
    }
    for x in (0..=xmax).rev() {
        if expanded_cols.contains(&x) {
            for g in &mut new_map {
                if g.x > x { g.x += times-1 }
            }
        }
    }
    new_map
}

fn distance(one: &Point2D, other: &Point2D) -> i64 {
    (one.x - other.x).abs() + (one.y - other.y).abs()
}

fn distance_sum(galaxies: &Vec<Point2D>) -> i64 {
    galaxies
        .iter()
        .combinations(2)
        .map(|g| distance(g[0],g[1]))
        .sum::<i64>()
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {err}"),
        Ok(result) => result,
    };

    // Build map
    let mut galaxies: Vec<Point2D> = Vec::new();
    for (y,line) in input.iter().enumerate() {
        for (x,ch) in line.chars().enumerate() {
            let pt = Point2D { x: x as i64, y: y as i64 };
            if ch == '#' {
                galaxies.push(pt);
            }
        }
    }

    // Part 1 + Part 2
    let part1 = distance_sum(&expand_map(&galaxies,2));
    let part2 = distance_sum(&expand_map(&galaxies,1_000_000));
    println!("Part 1: {part1}"); // 9509330
    println!("Part 2: {part2}"); //635832237682

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}