146 lines
4.9 KiB
Python
Executable File
146 lines
4.9 KiB
Python
Executable File
#!/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)
|