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

fn len(x: f32, y: f32) -> f32 {
    return (x * x + y * y).sqrt();
}

fn d(a: (f32, f32), b: (f32, f32)) -> f32 {
    return len(a.0 - b.0, a.1 - b.1);
}

fn parse_input() -> Vec<Vec<bool>> {
    let mut names = vec![];
    for line in lib::iter_input() {
        let (left, right) = line.split_once(": ").unwrap();
        names.push(left.to_string());
        for r in right.split(" ") {
            names.push(r.to_string());
        }
    }
    names.sort();
    names.dedup();

    let mut graph = vec![vec![false; names.len()]; names.len()];

    for line in lib::iter_input() {
        let (left, right) = line.split_once(": ").unwrap();
        let i = names.iter().position(|x| x == left).unwrap();
        for r in right.split(" ") {
            let j = names.iter().position(|x| x == r).unwrap();
            graph[i][j] = true;
            graph[j][i] = true;
        }
    }

    return graph;
}

fn force(graph: &Vec<Vec<bool>>, rounds: usize) -> Vec<(f32, f32)> {
    let n = graph.len();
    let mut pos = vec![(0.0, 0.0); n];

    for i in 0..n {
        // random start positions would be nice, but I just use mod13 here
        pos[i] = (i as f32, (i % 13) as f32);
    }

    for r in 0..rounds {
        let step = (n as f32) * ((rounds - r) as f32) / 2.0;
        for i in 0..n {
            let mut x = 0.0;
            let mut y = 0.0;
            for j in 0..n {
                if i == j {
                    continue;
                }
                let dx = pos[i].0 - pos[j].0;
                let dy = pos[i].1 - pos[j].1;
                let d = len(dx, dy);
                if graph[i][j] {
                    x -= dx * d;
                    y -= dy * d;
                } else {
                    x += dx / d / d;
                    y += dy / d / d;
                }
            }

            let s = step / len(x, y);
            pos[i] = (
                pos[i].0 + x * s,
                pos[i].1 + y * s,
            );
        }
    }
    return pos;
}

fn cluster(pos: &Vec<(f32, f32)>, rounds: usize) -> usize {
    let x_center = pos.iter().map(|(x, _)| *x).sum::<f32>() / (pos.len() as f32);
    let y_center = pos.iter().map(|(_, y)| *y).sum::<f32>() / (pos.len() as f32);

    let mut c1 = (x_center - 1.0, y_center);
    let mut c2 = (x_center + 1.0, y_center);
    let mut n = 0;

    for _ in 0..rounds {
        let mut x1 = 0.0;
        let mut y1 = 0.0;
        let mut n1 = 0;

        let mut x2 = 0.0;
        let mut y2 = 0.0;
        let mut n2 = 0;

        for i in 0..pos.len() {
            if d(pos[i], c1) < d(pos[i], c2) {
                x1 += pos[i].0;
                y1 += pos[i].1;
                n1 += 1;
            } else {
                x2 += pos[i].0;
                y2 += pos[i].1;
                n2 += 1;
            }
        }

        c1 = (x1 / n1 as f32, y1 / n1 as f32);
        c2 = (x2 / n2 as f32, y2 / n2 as f32);
        n = n1;
    }

    return n;
}

fn main() {
    let graph = parse_input();

    let pos = force(&graph, 20);
    let a = cluster(&pos, 4);

    println!("part1: {}", a * (graph.len() - a));
}