use std::collections::HashSet;
use std::env::args;
use std::fs::File;
use std::io::BufRead;
use std::io::BufReader;

struct Scanner {
    beacons: Vec<[i32; 3]>,
    position: [i32; 3],
}

fn get_data() -> Vec<Vec<[i32; 3]>> {
    let path = args().nth(1).unwrap();
    let file = File::open(path).unwrap();

    let mut scanners = vec![];
    let mut beacons = vec![];

    for line in BufReader::new(file).lines() {
        match line.unwrap().split(",").collect::<Vec<&str>>()[..] {
            [""] => {
                scanners.push(beacons);
                beacons = vec![];
            },
            [a, b, c] => {
                beacons.push([
                    a.parse::<i32>().unwrap(),
                    b.parse::<i32>().unwrap(),
                    c.parse::<i32>().unwrap(),
                ])
            },
            [_] => {},
            _ => unreachable!(),
        }
    }
    scanners.push(beacons);

    return scanners;
}

fn apply_rotation(beacon: [i32; 3], rotation: u8) -> [i32; 3] {
    let [x, y, z] = beacon;
    let [x1, y1, z1] = match rotation / 4 {
        0 => [ x,  y,  z],
        1 => [-z,  y,  x],
        2 => [-x,  y, -z],
        3 => [ z,  y, -x],
        4 => [ x, -z,  y],
        5 => [ x,  z, -y],
        _ => unreachable!(),
    };
    return match rotation % 4 {
        0 => [ x1,  y1, z1],
        1 => [-y1,  x1, z1],
        2 => [-x1, -y1, z1],
        3 => [ y1, -x1, z1],
        _ => unreachable!(),
    };
}

fn apply_position(beacons: &Vec<[i32; 3]>, position: [i32; 3], rotation: u8) -> Vec<[i32; 3]> {
    let [dx, dy, dz] = position;
    beacons
        .iter()
        .map(|beacon| apply_rotation(*beacon, rotation))
        .map(|[x, y, z]| [x + dx, y + dy, z + dz])
        .collect()
}

fn in_scanner_range(beacon: [i32; 3], a: [i32; 3], b: [i32; 3]) -> bool {
    let [x, y, z] = beacon;
    let [ax, ay, az] = a;
    let [bx, by, bz] = b;
    (
        (ax <= bx && bx - 1000 <= x && x <= ax + 1000)
        || (bx <= ax && ax - 1000 <= x && x <= bx + 1000)
    ) && (
        (ay <= by && by - 1000 <= y && y <= ay + 1000)
        || (by <= ay && ay - 1000 <= y && y <= by + 1000)
    ) && (
        (az <= bz && bz - 1000 <= z && z <= az + 1000)
        || (bz <= az && az - 1000 <= z && z <= bz + 1000)
    )
}

fn check_overlap(a: &Scanner, b: &Vec<[i32; 3]>, b_position: [i32; 3], b_rotation: u8) -> bool {
    let a_position = a.position;
    let a_area: HashSet<[i32; 3]> = a.beacons.clone().into_iter().filter(|beacon|
        in_scanner_range(*beacon, a_position, b_position)
    ).collect();
    let n = a_area.len();
    if n < 12 {
        return false;
    }

    // TODO PERF: if match we could reuse this
    let b_mapped = apply_position(b, b_position, b_rotation);
    let b_area: HashSet<[i32; 3]> = b_mapped.into_iter().filter(|beacon|
        in_scanner_range(*beacon, a_position, b_position)
    ).collect();

    return b_area.len() == n && a_area.intersection(&b_area).count() == n;
}

fn find_overlap(a: &Scanner, b: &Vec<[i32; 3]>) -> Option<([i32; 3], u8)> {
    for rotation in 0..24 {
        for beacon in b.iter() {
            let [bx1, by1, bz1] = apply_rotation(*beacon, rotation);
            // PERF: we can skip up to 11 beacons because we need to match at least 12
            for [ax1, ay1, az1] in a.beacons[11..].iter() {
                let pos = [ax1 - bx1, ay1 - by1, az1 - bz1];
                if check_overlap(a, b, pos, rotation) {
                    return Some((pos, rotation));
                }
            }
        }
    }
    return None;
}

fn main() {
    let mut unsettled = get_data();
    let mut queue: Vec<Scanner> = vec![];
    let mut settled: Vec<Scanner> = vec![];

    let first = unsettled.pop().unwrap();
    queue.push(Scanner {
        beacons: first,
        position: [0, 0, 0],
    });

    while queue.len() > 0 {
        println!("unsettled: {}  queued: {}  settled: {}", unsettled.len(), queue.len(), settled.len());
        let cur = queue.pop().unwrap();
        let mut i = 0;
        while i < unsettled.len() {
            match find_overlap(&cur, &unsettled[i]) {
                None => i += 1,
                Some((position, rotation)) => {
                    let beacons = unsettled.remove(i);
                    let mapped = apply_position(&beacons, position, rotation);
                    queue.push(Scanner {
                        beacons: mapped,
                        position,
                    });
                },
            }
        }
        settled.push(cur);
    }

    assert_eq!(unsettled.len(), 0);

    let mut beacons = HashSet::new();
    for scanner in settled.iter() {
        for beacon in scanner.beacons.iter() {
            beacons.insert(beacon);
        }
    }
    println!("{}", beacons.len());

    let mut max_distance = 0;
    for a in settled.iter() {
        let [ax, ay, az] = a.position;
        for b in settled.iter() {
            let [bx, by, bz] = b.position;
            let d = (ax - bx).abs() + (ay - by).abs() + (az - bz).abs();
            if d > max_distance {
                max_distance = d;
            }
        }
    }
    println!("{}", max_distance);
}