aoc/2018/3/area.py

#!/usr/bin/env python3

import collections
import numpy
import re
import sys

matrix_size = [1000, 1000]

class Claim:
    id = None
    # Vector2 ish
    origin = None
    # Vector2 ish
    size = None
    matrix = None
    def __init__(self, id, origin, size):
        self.id = id
        self.origin = origin
        self.size = size
        # Not great to stop the matrix for the entire field in memory,
        # but it's small enough in this case.
        self.matrix = numpy.zeros(matrix_size, dtype = numpy.bool_)
        # Set '1' for all positions of
        x_offset = 0
        while x_offset < int(size[0]):
            y_offset = 0
            while y_offset < int(size[1]):
                position = (int(origin[0]) + x_offset, int(origin[1]) + y_offset)
                #print(position)
                self.matrix.itemset(position, True)
                y_offset += 1
            x_offset += 1

    def all_points(self):
        d = {}
        x = int(self.origin[0])
        x_max = x + int(self.size[0])
        y_max = int(self.origin[1]) + int(self.size[1])
        while x < x_max:
            y = int(self.origin[1])
            while y < y_max:
                d[(x,y)] = 1
                y += 1
            x += 1
        return d

    def does_overlap(self, other):
        other_start = other.vertices()[0]
        other_end = other.vertices()[3]
        # If any vertice is in the area defined by the other start and end,
        # the claims overlap in some way.
        for v in self.vertices():
            #print("Checking if {} is inside {}, {}".format(v, other_start, other_end))
            if (v[0] >= other_start[0] and v[0] <= other_end[0]) and (v[1] >= other_start[1] and v[1] <= other_end[1]):
                return True
        return False

    def vertices(self):
        return [
            [self.origin[0], self.origin[1]],
            [self.origin[0], self.origin[1] + self.size[1]],
            [self.origin[0] + self.size[0], self.origin[1]],
            [self.origin[0] + self.size[0], self.origin[1] + self.size[1]]
        ]

    def overlap(self, other):
        return numpy.transpose(numpy.nonzero(numpy.logical_and(self.matrix, other.matrix)))

    def __str__(self):
        return "#{} {},{}: {}x{}".format(self.id, int(self.origin[0]),
                                         int(self.origin[1]), int(self.size[0]),
                                         int(self.size[1]))

def read_input(lines, pattern):
    r = []
    for l in lines:
        m = pattern.match(l)
        if m is None:
            print('Warning: did not match line "{}"'.format(l))
            continue
        r.append(
            Claim(m.group('id'),
                  numpy.array([m.group('origin_x'), m.group('origin_y')], dtype = int),
                  numpy.array([m.group('size_x'), m.group('size_y')], dtype = int)
                  )
        )
    return r

if __name__ == '__main__':
    p = re.compile('^#(?P<id>\d+) @ (?P<origin_x>\d+),(?P<origin_y>\d+): (?P<size_x>\d+)x(?P<size_y>\d+)')
    lines = sys.stdin.readlines()
    claims = read_input(lines, p)
    print("{} claims".format(len(claims)))
    other_claims = claims.copy()
    checked = 0
    check_count = len(claims) * ((len(claims)-1)/2)
    overlapping_points = set()
    single_points = set()
    counter = collections.Counter()
    claimPoints = {}
    for claim in claims:
        #print(claim.all_points())
        p = set(claim.all_points())
        claimPoints[claim] = p
        counter.update(p)
    for k, v in counter.items():
        if v >= 2:
            overlapping_points.add(k)
        else:
            single_points.add(k)
    print("{} overlapping points, {} single points".format(len(overlapping_points), len(single_points)))
    potential_claims = set()
    for claim in claims:
        pts = claimPoints[claim].intersection(overlapping_points)
        print("{}: {} intersecting points".format(claim, len(pts)))
        if len(pts) == 0:
            potential_claims.add(claim)
    for c in potential_claims:
        print(c)
    #overlaps = {}
    #for claim in claims:
    #    other_claims.remove(claim)
    #    if claim in overlaps.keys():
    #        continue
    #    for other in other_claims:
    #        if claim in overlaps.keys():
    #            break
    #        if other in overlaps.keys():
    #            continue
    #        print("Checking {} vs {} ({} current overlaps)".format(claim, other, len(overlaps.keys())))
    #        if numpy.any(claim.overlap(other)):
    #            if claim in overlaps:
    #                overlaps[claim].append(other)
    #            else:
    #                overlaps[claim] = [other]
    #            if other in overlaps:
    #                overlaps[other].append(claim)
    #            else:
    #                overlaps[other] = [claim]
    #for claim in claims:
    #    if claim not in overlaps.keys():
    #        print(claim)
    #    #unOverlapped = [x for x in claims and x not in overlaps.keys()]
    #    #print(unOverlapped)