60 lines
1.3 KiB
Python
60 lines
1.3 KiB
Python
from lib import *
|
|
|
|
input = read_input(2017, 14).strip()
|
|
|
|
|
|
def knot(inp):
|
|
lengths = [*map(ord, inp), 17, 31, 73, 47, 23]
|
|
nums = [*range(256)]
|
|
pos = 0
|
|
skip = 0
|
|
|
|
def rev(a, b):
|
|
a %= len(nums)
|
|
b = (b - a) % len(nums)
|
|
nums[:] = nums[a:] + nums[:a]
|
|
nums[:b] = nums[:b][::-1]
|
|
nums[:] = nums[-a:] + nums[:-a]
|
|
|
|
for _ in range(64):
|
|
for length in lengths:
|
|
rev(pos, pos + length)
|
|
pos += length + skip
|
|
skip += 1
|
|
|
|
dense = []
|
|
for i in range(16):
|
|
x = 0
|
|
for j in range(16):
|
|
x ^= nums[i * 16 + j]
|
|
dense.append(x)
|
|
return "".join(f"{x:02x}" for x in dense)
|
|
|
|
|
|
out = 0
|
|
for i in range(128):
|
|
k = bin(int(knot(f"{input}-{i}"), 16))[2:].zfill(128)
|
|
out += k.count("1")
|
|
|
|
print(out)
|
|
|
|
|
|
last = None
|
|
uf = UnionFind(128 * 128)
|
|
free = 0
|
|
for i in range(128):
|
|
k = bin(int(knot(f"{input}-{i}"), 16))[2:].zfill(128)
|
|
for j in range(128):
|
|
if k[j] != "1":
|
|
free += 1
|
|
continue
|
|
if i and last[j] == "1":
|
|
uf.merge((i - 1) * 128 + j, i * 128 + j)
|
|
if j and k[j - 1] == "1":
|
|
uf.merge(i * 128 + j - 1, i * 128 + j)
|
|
last = k
|
|
|
|
groups = set()
|
|
for i in range(128 * 128):
|
|
groups.add(uf.find(i))
|
|
print(len(groups) - free)
|