// use std::collections::HashSet;

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

fn get_input() -> Vec<(i64, i64, i64, i64)> {
    return lib::iter_input().map(|line| {
        let parts: Vec<&str> = line.split("=").collect();
        return (
            lib::split_once(parts[1], ',').unwrap().0.parse().unwrap(),
            lib::split_once(parts[2], ':').unwrap().0.parse().unwrap(),
            lib::split_once(parts[3], ',').unwrap().0.parse().unwrap(),
            parts[4].parse().unwrap(),
        );
    }).collect();
}

fn range_merge(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
    if b1 > b2 {
        return v;
    }

    let mut result = vec![];
    let mut new1 = b1;
    let mut new2 = b2;
    for (a1, a2) in v.into_iter() {
        if a1 <= new2 && new1 <= a2 {
            new1 = new1.min(a1);
            new2 = new2.max(a2);
        } else {
            result.push((a1, a2));
        }
    }
    result.push((new1, new2));
    return result;
}

fn range_remove(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
    let mut result = vec![];
    for (a1, a2) in v.into_iter() {
        if a1 <= b2 && b1 <= a2 {
            if a1 < b1 {
                result.push((a1, b1 - 1));
            }
            if b2 < a2 {
                result.push((b2 + 1, a2));
            }
        } else {
            result.push((a1, a2));
        }
    }
    return result;
}

fn part1(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
    // different value for test and real input
    let y = if positions.len() == 14 { 10 } else { 2000000 };

    let mut ranges = vec![];

    for (xs, ys, xb, yb) in positions.iter() {
        let d = (xs - xb).abs() + (ys - yb).abs();
        let x1 = xs - d + (y - ys).abs();
        let x2 = xs + d - (y - ys).abs();
        ranges = range_merge(ranges, x1, x2);
    }

    for (xs, ys, xb, yb) in positions.iter() {
        if *ys == y {
            ranges = range_remove(ranges, *xs, *xs);
        }
        if *yb == y {
            ranges = range_remove(ranges, *xb, *xb);
        }
    }

    return ranges.iter().map(|(x1, x2)| x2 - x1 + 1).sum();
}

fn slant(x: i64, y: i64) -> (i64, i64) {
    return (x + y, x - y);
}

fn unslant(x: i64, y: i64) -> (i64, i64) {
    return ((x + y) / 2, (x - y) / 2);
}

fn part2(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
    // different value for test and real input
    let n = if positions.len() == 14 { 20 } else { 4000000 };

    let p1 = slant(n / 2 - n, n / 2);
    let p2 = slant(n / 2 + n, n / 2);
    let mut areas = vec![(p1.0, p1.1, p2.0, p2.1)];

    for (xs, ys, xb, yb) in positions.iter() {
        let d = (xs - xb).abs() + (ys - yb).abs();

        // turn by 45deg so we can work with rectangles areas
        let (x, y) = slant(*xs, *ys);

        let bx1 = x - d;
        let by1 = y - d;
        let bx2 = x + d;
        let by2 = y + d;

        let mut tmp = vec![];
        for (ax1, ay1, ax2, ay2) in areas.into_iter() {
            if ax2 < bx1 || ax1 > bx2 || ay2 < by1 || ay1 > by2 {
                tmp.push((ax1, ay1, ax2, ay2));
            } else {
                // remove one rectangle from another, splitting it into up
                // to 4 smaller ones.
                //
                //    ax1             ax2
                // ay1 +---+-------+---+
                //     |   |   3   |   |
                //     |   +-------+   | by1
                //     | 1 |       | 2 |
                //     |   +-------+   | by2
                //     |   |   4   |   |
                // ay2 +---+-------+---+
                //        bx1     bx2

                if ax1 < bx1 {
                    tmp.push((ax1, ay1, bx1 - 1, ay2));
                }
                if ax2 > bx2 {
                    tmp.push((bx2 + 1, ay1, ax2, ay2));
                }
                let x1 = ax1.max(bx1);
                let x2 = ax2.min(bx2);
                if ay1 < by1 {
                    tmp.push((x1, ay1, x2, by1 - 1));
                }
                if ay2 > by2 {
                    tmp.push((x1, by2 + 1, x2, ay2));
                }
            }
        }
        areas = tmp;
    }

    let filtered = areas.iter().map(|(ax1, ay1, ax2, ay2)| {
        let (x1, y1) = unslant(*ax1, *ay1);
        let (x2, y2) = unslant(*ax2, *ay2);
        return (x1, y1, x2, y2);
    }).filter(|(x1, y1, x2, y2)| !(
        // this filter is not sufficient in the general case, but worked with my data
        (*x1 < 0 && *x2 < 0)
        || (*y1 < 0 && *y2 < 0)
        || (*x1 > n && *x2 > n)
        || (*y1 > n && *y2 > n)
    )).collect::<Vec<(i64, i64, i64, i64)>>();

    assert_eq!(filtered.len(), 1);
    let (x1, y1, x2, y2) = filtered[0];
    assert_eq!(x1, x2);
    assert_eq!(y1, y2);
    return x1 * 4000000 + y1;
}

fn main() {
    let positions = get_input();
    println!("part1: {}", part1(&positions));
    println!("part2: {}", part2(&positions));
}