advent-of-code

commit 5f7e3475a8a262a265e449ec92a0e50885ce06c2
parent 42a79ad9b3b87b2903508c31c34520d0bf5b8ab9
Author: mpizzzle <michael.770211@gmail.com>
Date:   Fri, 15 Dec 2017 15:15:04 +0000

puzzle 15 complete

Diffstat:
A
files/puzzle15.txt
 | 
2
++
M
puzzle14.py
 | 
23
++++++++++-------------
A
puzzle15.py
 | 
26
++++++++++++++++++++++++++

3 files changed, 38 insertions(+), 13 deletions(-)
diff --git a/files/puzzle15.txt b/files/puzzle15.txt
@@ -0,0 +1,2 @@
+Generator A starts with 703
+Generator B starts with 516
diff --git a/puzzle14.py b/puzzle14.py
@@ -27,17 +27,7 @@ disk = [knot_hash([ord(c) for c in "amgozmfv-" + str(i)]) for i in range(128)]
 
 print sum([binary_hash[c] for c in "".join(disk)])
 
-binary_disk = ["".join(["".join([str(int(int(c, 16) & 2**i > 0)) for i in reversed(range(4))]) for c in row]) for row in disk]
-disk_hash = {}
-network = []
-
-print binary_disk
-
-for x in range(128):
-    for y in range(128):
-        disk_hash[str(x) + ',' + str(y)] = int(binary_disk[x][y])
-
-def traverse(node):
+def traverse(node, network):
     network.append(node)
     x_y = [int(n) for n in node.split(',')]
     neighbours = [str(x_y[0]) + ',' + str(x_y[1] - 1), str(x_y[0]) + ',' + str(x_y[1] + 1), str(x_y[0] - 1) + ',' + str(x_y[1]), str(x_y[0] + 1) + ',' + str(x_y[1])]
@@ -45,14 +35,21 @@ def traverse(node):
         if neighbour not in network:
             if neighbour in disk_hash:
                 if disk_hash[neighbour]:
-                    traverse(neighbour)
+                    traverse(neighbour, network)
 
+network = []
 size_of_network = 0
 network_count = 0
+binary_disk = ["".join(["".join([str(int(int(c, 16) & 2**i > 0)) for i in reversed(range(4))]) for c in row]) for row in disk]
+disk_hash = {}
+
+for x in range(128):
+    for y in range(128):
+        disk_hash[str(x) + ',' + str(y)] = int(binary_disk[x][y])
 
 for node in disk_hash.keys():
     if disk_hash[node] and node not in network:
-        traverse(node)
+        traverse(node, network)
         if len(network) > size_of_network:
             size_of_network = len(network)
             network_count += 1
diff --git a/puzzle15.py b/puzzle15.py
@@ -0,0 +1,26 @@
+with open('files/puzzle15.txt') as f:
+    seeds = [int(line.split(" ")[4]) for line in f.readlines()]
+
+matches = 0
+a, b = seeds[0], seeds[1]
+
+for i in range(40000000):
+    a = (a * 16807) % 2147483647
+    b = (b * 48271) % 2147483647
+    if a & 0xffff == b & 0xffff:
+        matches += 1
+
+print matches
+
+a, b = seeds[0], seeds[1]
+a_candidates, b_candidates = [], []
+
+while len(a_candidates) < 5000000 or len(b_candidates) < 5000000:
+    a = (a * 16807) % 2147483647
+    b = (b * 48271) % 2147483647
+    if a % 4 == 0:
+        a_candidates.append(a)
+    if b % 8 == 0:
+        b_candidates.append(b)
+
+print sum([int(a & 0xffff == b & 0xffff) for a, b in zip(a_candidates, b_candidates)])