1  from lib import *
 2  
 3  input = read_input(2017, 14).strip()
 4  
 5  
 6  def knot(inp):
 7      lengths = [*map(ord, inp), 17, 31, 73, 47, 23]
 8      nums = [*range(256)]
 9      pos = 0
10      skip = 0
11  
12      def rev(a, b):
13          a %= len(nums)
14          b = (b - a) % len(nums)
15          nums[:] = nums[a:] + nums[:a]
16          nums[:b] = nums[:b][::-1]
17          nums[:] = nums[-a:] + nums[:-a]
18  
19      for _ in range(64):
20          for length in lengths:
21              rev(pos, pos + length)
22              pos += length + skip
23              skip += 1
24  
25      dense = []
26      for i in range(16):
27          x = 0
28          for j in range(16):
29              x ^= nums[i * 16 + j]
30          dense.append(x)
31      return "".join(f"{x:02x}" for x in dense)
32  
33  
34  out = 0
35  for i in range(128):
36      k = bin(int(knot(f"{input}-{i}"), 16))[2:].zfill(128)
37      out += k.count("1")
38  
39  print(out)
40  
41  
42  last = None
43  uf = UnionFind(128 * 128)
44  free = 0
45  for i in range(128):
46      k = bin(int(knot(f"{input}-{i}"), 16))[2:].zfill(128)
47      for j in range(128):
48          if k[j] != "1":
49              free += 1
50              continue
51          if i and last[j] == "1":
52              uf.merge((i - 1) * 128 + j, i * 128 + j)
53          if j and k[j - 1] == "1":
54              uf.merge(i * 128 + j - 1, i * 128 + j)
55      last = k
56  
57  groups = set()
58  for i in range(128 * 128):
59      groups.add(uf.find(i))
60  print(len(groups) - free)