#import "Basic";
#import "String";
#import "File";
#import "Hash_Table";
#import "Hash";
#import "Random";

Vertex :: struct {
    connections: [..]s64;
};

Connection :: struct {
    count: s64 = 0;
};

solve_day25 :: (test: bool) {
    
    rand_state: Random_State;
    rand_state.low = 0x54DF2CC1;
    rand_state.high= 0xAB58C121;

    size, c1, c2 := find_cut(*rand_state);

    while size != 3 {
        size, c1, c2 = find_cut(*rand_state);
    }

    print("Part 1: %\n", c1 * c2);

}

rebind :: (graph: *Table(string, [..]string), old: string, new: string) {

    old_node := table_find_pointer(graph, old);

    if !old_node {
        print("Didn't find %\n", old);
    }

    for n: << old_node {
        other_node := table_find_pointer(graph, n);

        if other_node {
            while array_ordered_remove_by_value(other_node, old) {
                array_add(other_node, new);
            }
        }

    }

}

find_cut :: (rand_state: *Random_State) -> size: s64, c1: s64, c2: s64 {

    file_name :: "inputs/day25.txt";
    input := read_entire_file(file_name);
    lines := split(input, "\n");

    graph : Table(string, [..]string);

    for l : lines {
        if l.count == 0  continue;

        name_split := split(l, ": ");
        connected_to := split(name_split[1], " ");

        for connected_to {
            if it.count == 0  continue;
            register_edge(*graph, name_split[0], it);
            register_edge(*graph, it, name_split[0]);
        }
    }

    component_size : Table(string, s64);
    for _, k : graph {
        table_add(*component_size, k, 1);
    }

    i := 0;

    while graph.count > 2 {
        defer i += 1;

        merged := tprint("merge-%", i);

        merged_array : [..]string;

        r := cast(int)random_get_within_range(rand_state, 0, cast(float)graph.count);

        u := element_key_at_pointer(*graph, r);
        u_node := table_find_pointer(*graph, u);

        r2 := cast(int)random_get_within_range(rand_state, 0, cast(float)u_node.count);
        v  := (<< u_node)[r2];
        v_node := table_find_pointer(*graph, v);

        for << u_node {
            if it != v  array_add(*merged_array, it);
        }

        for << v_node {
            if it != u  array_add(*merged_array, it);
        }

        table_add(*graph, merged, merged_array);
        rebind(*graph, u, merged);
        rebind(*graph, v, merged);

        component_u := table_find_pointer(*component_size, u);
        component_v := table_find_pointer(*component_size, v);


        table_add(*component_size, merged, << component_u + << component_v);

        table_remove(*graph, u);
        table_remove(*graph, v);


    }

    node_a := element_key_at_pointer(*graph, 0);
    node_b := element_key_at_pointer(*graph, graph.count - 1);

    node_a_size,_ := table_find(*component_size, node_a);
    node_b_size,_ := table_find(*component_size, node_b);

    node_a_value,_ := table_find(*graph, node_a);
    node_b_value,_ := table_find(*graph, node_b);

    return node_a_value.count, node_a_size, node_b_size;
}

register_edge :: (graph: *Table(string, [..]string), u: string, v: string) {
    node := table_find_pointer(graph, u);

    if !node {
        n : [..]string;
        array_add(*n, v);
        table_add(graph, u, n);
    } else {
        array_add(node, v);
    }
}

element_key_at_pointer :: (graph: *Table(string, [..]string), index: s64) -> string {
    i := 0;

    for graph.entries {
        if it.hash > FIRST_VALID_HASH {
            if i == index  {
                return it.key;
            }
            i += 1;

        }
    }

    return "";
}