wormholes.py

"""
ID: thomasa3
LANG: PYTHON3
PROG: wormhole
"""
import itertools
from collections import defaultdict

fin = open('wormhole.in', 'r')
fout = open('wormhole.out', 'w')
num_holes = int(fin.readline())
holes = [ ]

for i in range(num_holes):
    hole = list(map(int, fin.readline().split()))
    holes.append(hole)

#
# holes = [
#         [ 987878530, 332490544 ],
#         [ 545074228, 332490544 ],
#         [ 571194544, 278963943 ],
#         [ 32922985, 229703843 ],
#         [ 571194544, 851333603 ],
#         [ 90862786, 28227282 ],
#         [ 219975775, 267376202 ],
#         [ 219975775, 332490544 ],
#         [ 90862786, 62367085 ],
#         [ 872930617, 951881113]
# ]

def find_loops(holes):
    num_pairs = int(len(holes) / 2)
    hole_indices = list(range(len(holes)))
    # all unique sets of 2 in holes
    combo_sets = list(itertools.combinations(hole_indices, 2))
    combos = [ ]
    for i in range(len(combo_sets)):
        combo = list(combo_sets[i])
        combos.append(combo)
    # print("> Combos: ", combos)
    final_combo_sets = list(itertools.combinations(combos, num_pairs))
    final_combos = [ ]
    for i in range(len(final_combo_sets)):
        combo = list(final_combo_sets[i])
        final_combos.append(combo)

    # filter final_combos with sets that contain same element
    combos = [ ]
    for i in range(len(final_combos)):
        combo = final_combos[i]
        # append if all unique
        flattened = list(itertools.chain(*combo))
        # print("> Flattened: ", flattened)
        if len(flattened) == len(set(flattened)):
            # sort combo - put 1st x-axis first
            combo.sort(key=lambda x: x[0])
            combos.append(combo)


    print("> Len combos: ", len(combos))
    rst = 0
    for i in range(len(combos)):
        combo = combos[i]
        board = Board(holes)
        board.connect(combo, holes)
        # board.render()
        if board.is_loop():
            rst += 1
    return rst

def get_key(a):
    return "-".join(list(map(str, a)))

class Board:
    def __init__(self, holes):
        self.connections = [ ] # connections
        self.table = { }
        self.has_loop = False

    def render(self):
        print("> Board: ", self.connections, self.table)

    def find_in(self, a, y_points):
        y = a[1]
        for i in range(len(y_points[y])):
            entry = y_points[y][i]
            if entry[0] > a[0]:
                return entry

    def has_same_in_out(self, in_out_list):
        # print("> In out list: ", in_out_list)
        counter = defaultdict(int)
        for i in range(len(in_out_list)):
            # check if has same in and out
            entry = in_out_list[i]
            if entry[0] == entry[1]:
                return True
            if entry[0] != None and entry[1] != None:
                # add to poss - sort by earliest x value
                entry.sort()
                key = " ".join(str(x) for x in entry)
                counter[key] += 1
                if counter[key] > 1:
                    return True
        # check if any two match
        return False

    def connect(self, combos, holes):
        # sort all connections
        # if any connections on same y-axis, check if any y-axis in between
        y_points = defaultdict(list)
        in_out_list = [ ]

        for i in range(len(combos)):
            combo = combos[i]
            connection = [ holes[combo[0]], holes[combo[1]]]
            start, end = connection
            y1 = start[1]
            y2 = end[1]
            y_points[y1].append(start)
            y_points[y2].append(end)
            y_points[y1].sort(key=lambda x: x[0])
            y_points[y2].sort(key=lambda x: x[0])
            self.connections.append(connection)

        for i in range(len(self.connections)):
            a, b = self.connections[i]
            a_in = b
            b_in = a
            a_out = self.find_in(a, y_points)
            b_out = self.find_in(b, y_points)
            in_out_list.append([a_in, a_out])
            in_out_list.append([b_in, b_out])
        # check if any in_out_list entry has same in & out or same values as anything else
        if self.has_same_in_out(in_out_list):
            self.has_loop = True

    def is_loop(self):
        return self.has_loop

line = find_loops(holes)
fout.write(str(line) + "\n")
fout.close()
# print("> Result: ", line)