You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
120 lines
3.4 KiB
120 lines
3.4 KiB
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
|
|
|
|
def adjacent(x,y,pos):
|
|
dirs = [(0,1), (1,0), (0,-1), (-1,0)]
|
|
for p in pos:
|
|
for d in dirs:
|
|
if p[0] == d[0] + x and p[1] == d[1] + y:
|
|
return True
|
|
return False
|
|
|
|
|
|
def join(rs):
|
|
if len(rs) == 1: return rs
|
|
removable = []
|
|
for i in range(len(rs)):
|
|
if i in removable:
|
|
continue
|
|
r1 = rs[i]
|
|
for j, r2 in enumerate(rs[i+1:]):
|
|
if j+i+1 in removable: continue
|
|
for r in r1:
|
|
if adjacent(*r,r2):
|
|
r1 += r2
|
|
r2 = []
|
|
removable.append(i+1+j)
|
|
break
|
|
for i in sorted(removable, reverse=True):
|
|
rs.remove(rs[i])
|
|
|
|
|
|
if __name__ == '__main__':
|
|
plots = [list(line.strip('\n')) for line in open(sys.argv[1])]
|
|
|
|
def fence(p):
|
|
x,y = p
|
|
dirs = [(0,1), (1,0), (0,-1), (-1,0)]
|
|
fences = 0
|
|
for d in dirs:
|
|
nx = d[0] + x
|
|
ny = d[1] + y
|
|
if 0 <= nx < len(plots[0]) and 0 <= ny < len(plots):
|
|
if plots[y][x] != plots[ny][nx]: fences += 1
|
|
else: fences += 1
|
|
return fences
|
|
|
|
def disc_fence(region):
|
|
fences = 0
|
|
horizontal = {}
|
|
vertical = {}
|
|
for (x,y) in region:
|
|
v = [(1,0), (-1,0)]
|
|
h = [(0,1), (0,-1)]
|
|
for d in v:
|
|
nx = d[0] + x
|
|
if 0 <= nx < len(plots[0]):
|
|
if plots[y][x] != plots[y][nx]:
|
|
if (x, nx) in vertical: vertical[(x,nx)].append(y)
|
|
else: vertical[(x, nx)] = [y]
|
|
else:
|
|
if (x, nx) in vertical: vertical[(x,nx)].append(y)
|
|
else: vertical[(x, nx)] = [y]
|
|
|
|
for d in h:
|
|
ny = d[1] + y
|
|
if 0 <= ny < len(plots):
|
|
if plots[y][x] != plots[ny][x]:
|
|
if (y,ny) in horizontal: horizontal[(y, ny)].append(x)
|
|
else: horizontal[(y, ny)] = [x]
|
|
else:
|
|
if (y,ny) in horizontal: horizontal[(y, ny)].append(x)
|
|
else: horizontal[(y, ny)] = [x]
|
|
|
|
for ys in vertical.values():
|
|
prev = -2
|
|
for y in sorted(ys):
|
|
if y - prev > 1: fences += 1
|
|
prev = y
|
|
for xs in horizontal.values():
|
|
prev = -2
|
|
for x in sorted(xs):
|
|
if x - prev > 1: fences += 1
|
|
prev = x
|
|
return fences
|
|
|
|
|
|
# 'A': [[(x,y), (x,y),..],...]
|
|
regions = {}
|
|
for y, pls in enumerate(plots):
|
|
for x, p in enumerate(pls):
|
|
if p not in regions:
|
|
regions[p] = [[]]
|
|
regions[p][0].append((x,y))
|
|
else:
|
|
t = False
|
|
for l in regions[p]:
|
|
if adjacent(x,y,l):
|
|
l.append((x,y))
|
|
t = True
|
|
break
|
|
if not t: regions[p].append([(x,y)])
|
|
|
|
res1, res2 = 0, 0
|
|
|
|
for p, rs in regions.items():
|
|
join(rs)
|
|
join(rs)
|
|
for r in rs:
|
|
res1 += sum(map(fence,r)) * len(r)
|
|
res2 += disc_fence(r) * len(r)
|
|
|
|
# challenge 1
|
|
# 1400060 is too low! -> double join.. not very nice xD
|
|
print(f"challenge 1:\n{res1}\n")
|
|
|
|
# challenge 2
|
|
print(f"challenge 2:\n{res2}")
|
|
|
|
|