day 16

2 files changed, 107 insertions, 0 deletions

diff --git a/20/README b/20/README
index 9260dce..03d5894 100644
--- a/20/README
+++ b/20/README
@@ -17,6 +17,7 @@ Day     Time            Ans     Time            Ans
  13    0.006           2095    0.018 598411311431841
  14    4.357 15018100062885   55.561  5724245857696
  15    0.363            232 10516.154       18929178
+ 16    3.340          18227   32.481  2355350878831
       -------                 -------
 tot    TBD   ms                TBD   ms
 
@@ -25,6 +26,7 @@ Stats:
 
       -------Part 1--------   -------Part 2--------
 Day       Time  Rank  Score       Time  Rank  Score
+ 16   00:13:11   830      0   00:50:54  1318      0
  15   00:59:43  5655      0   01:17:06  4904      0
  14   00:43:31  4037      0   01:00:44  2402      0
  13   01:16:45  7549      0   02:27:40  3806      0
diff --git a/20/py/d16.py b/20/py/d16.py
new file mode 100644
index 0000000..e2c1170
--- /dev/null
+++ b/20/py/d16.py
@@ -0,0 +1,105 @@
+#!/usr/bin/env python3
+import aoc20
+import sys
+
+
+def pt1(_in):
+    things = []
+    for line in _in[:20]:
+        thing = []
+        line = line.strip().split(": ")
+        name = line[0]
+        for a in line[1].split(" or "):
+            b = a.split("-")
+            thing.append(range(int(b[0]), int(b[1])+1))
+        # things.append((name, thing))
+        things.append(thing)
+    res = 0
+    for line in _in[25:]:
+        for n in line.strip().split(","):
+            n = int(n)
+            valid = False
+            for thing in things:
+                if any(n in r for r in thing):
+                    valid = True
+                    break
+            if not valid:
+                res += n
+    return res
+
+
+def pt2(_in):
+    constraints = []
+    for line in _in[:20]:
+        thing = []
+        line = line.strip().split(": ")
+        name = line[0]
+        for a in line[1].split(" or "):
+            b = a.split("-")
+            thing.append(range(int(b[0]), int(b[1])+1))
+        # constraints.append((name, thing))
+        constraints.append(thing)
+    print("\n".join(str(c) for c in constraints))
+
+    tickets = []
+    for line in _in[25:]:
+        valid_ticket = True
+        for n in line.strip().split(","):
+            n = int(n)
+            valid_field = False
+            for thing in constraints:
+                if any(n in r for r in thing):
+                    valid_field = True
+                    break
+            if not valid_field:
+                valid_ticket = False
+                break
+        if valid_ticket:
+            tickets.append(list(int(n) for n in line.strip().split(",")))
+
+    # for each field
+    #   assume it can be anything
+    candidates = [set(range(20)) for _ in range(20)]  # one set per field
+    print("\n".join(str(c) for c in candidates))
+
+    # for each ticket
+    for t, ticket in enumerate(tickets):
+        print(t, ticket)
+        for f, field in enumerate(ticket):
+            print(f, field)
+            print(candidates[f])
+            for c, constraint in enumerate(constraints):
+                print(c, constraint)
+                if c in candidates[f] and not any(field in cons for cons in constraint):
+                    print(f"{f} cannot be {c}")
+                    candidates[f].remove(c)
+
+    print("\n".join(str(c) for c in candidates))
+
+    know = [-1 for _ in range(20)]
+    while any(len(c) > 0 for c in candidates):
+        print(know, "\n", "\n".join(str(c) for c in candidates))
+        for c, cand in enumerate(candidates):
+            if len(cand) == 1:
+                know[c] = cand.pop()
+                to_remove = know[c]
+                break
+        for cand in candidates:
+            if to_remove in cand:
+                cand.remove(to_remove)
+        print()
+    print("\n".join(str(c) for c in candidates))
+
+    my = list(int(n) for n in _in[22].strip().split(","))
+    res = 1
+    for f, field in enumerate(know):
+        print(f, field)
+        if field < 6:
+            res *= my[f]
+    return res
+
+
+if __name__ == "__main__":
+    input = aoc20.read_input(sys.argv[1:], 16)
+    print(pt1(input))
+    print(pt2(input))