AoC 2023 day 11

use std::collections::HashSet;

fn main() {
    let input = std::fs::read_to_string("../inputs/input.txt").unwrap();
    let grid: Vec<Vec<char>> = input.lines().map(|line| line.chars().collect()).collect();

    let empty_rows: Vec<usize> = grid
        .iter()
        .enumerate()
        .filter(|(_, row)| row.iter().all(|&c| c == '.'))
        .map(|(i, _)| i)
        .collect();

    let grid_height = grid.len();
    let grid_width = grid[0].len();

    let empty_columns: Vec<usize> = (0..grid_width)
        .filter(|&x| (0..grid_height).all(|y| grid[y][x] == '.'))
        .collect();

    let mut galaxy_locations: Vec<(usize, usize)> = Vec::new();
    for (y, row) in grid.iter().enumerate() {
        for (x, &c) in row.iter().enumerate() {
            if c == '#' {
                galaxy_locations.push((y, x));
            }
        }
    }

    let mut already_checked: HashSet<((usize, usize), (usize, usize))> = HashSet::new();

    let mut part_1_lengths: Vec<usize> = Vec::new();
    let mut part_2_lengths: Vec<usize> = Vec::new();

    for &pos1 in galaxy_locations.iter() {
        for &pos2 in galaxy_locations.iter() {
            if pos1 == pos2 {
                continue;
            }
            if already_checked.contains(&(pos1, pos2)) || already_checked.contains(&(pos2, pos1)) {
                continue;
            }
            already_checked.insert((pos1, pos2));
            part_1_lengths.push(get_distance(pos1, pos2, &empty_rows, &empty_columns, 2));
            part_2_lengths.push(get_distance(
                pos1,
                pos2,
                &empty_rows,
                &empty_columns,
                1000000,
            ));
        }
    }

    println!("part 1: {}", part_1_lengths.iter().sum::<usize>());
    println!("part 2: {}", part_2_lengths.iter().sum::<usize>());
}

fn get_distance(
    pos1: (usize, usize),
    pos2: (usize, usize),
    empty_rows: &[usize],
    empty_columns: &[usize],
    empty_cost: usize,
) -> usize {
    let (y1, x1) = pos1;
    let (y2, x2) = pos2;

    let (low_x, high_x) = if x1 < x2 { (x1, x2) } else { (x2, x1) };

    let (low_y, high_y) = if y1 < y2 { (y1, y2) } else { (y2, y1) };

    let mut path_len = 0;
    for x in (low_x..=high_x).skip(1) {
        if empty_columns.contains(&x) {
            path_len += empty_cost;
        } else {
            path_len += 1;
        }
    }
    for y in (low_y..=high_y).skip(1) {
        if empty_rows.contains(&y) {
            path_len += empty_cost;
        } else {
            path_len += 1;
        }
    }
    path_len
}