Initial commit

3 files changed, 91 insertions, 0 deletions

diff --git a/17/input.txt b/17/input.txt
new file mode 100644
index 0000000..6b25a72
--- /dev/null
+++ b/17/input.txt
@@ -0,0 +1,20 @@
+33
+14
+18
+20
+45
+35
+16
+35
+1
+13
+18
+13
+50
+44
+48
+6
+24
+41
+30
+42
diff --git a/17/main.py b/17/main.py
new file mode 100755
index 0000000..d301334
--- /dev/null
+++ b/17/main.py
@@ -0,0 +1,52 @@
+#!/usr/bin/python
+
+
+
+def find_combos(sizes, taken, avail, remaining):
+    result = set()
+
+    # For each container we haven't used yet
+    for i in avail:
+        # If its capacity is less than what we need, recurse to find
+        # containers for the remaining liquid, which might not succeed.
+        if sizes[i] < remaining:
+            _taken = taken | {i}
+            _avail = avail - {i}
+            _remaining = remaining - sizes[i]
+            for c in find_combos(sizes, _taken, _avail, _remaining):
+                result |= {frozenset([i]) | c}
+        # If its capacity is exactly what we need, we've found an option
+        elif sizes[i] == remaining:
+            result |= {frozenset([i])}
+        # If its capacity is too large, this isn't an option; continue
+
+    return result
+
+
+
+def solve_partn(partn, combos):
+    if partn == 1:
+        options = combos
+    else: # partn == 2
+        lengths = map(len, combos)
+        min_len = min(lengths)
+        options = {c for c in combos if len(c) == min_len}
+    return len(options)
+
+
+
+def main():
+    # Read container volumes from the input text file
+    with open("input.txt", "r") as f:
+        sizes = list(map(int, f.read().splitlines()))
+
+    # Extremely expensive (takes several minutes), so do it once up front
+    combos = find_combos(sizes, set(), set(range(len(sizes))), 150)
+
+    print("Part 1 solution:", solve_partn(1, combos)) # 1304 for me
+    print("Part 2 solution:", solve_partn(2, combos)) #   18 for me
+
+
+
+if __name__ == "__main__":
+    main()
diff --git a/17/test.py b/17/test.py
new file mode 100755
index 0000000..74943db
--- /dev/null
+++ b/17/test.py
@@ -0,0 +1,19 @@
+#!/usr/bin/python
+
+import unittest
+
+import main
+
+
+
+class Examples(unittest.TestCase):
+    def test_example1(self):
+        sizes = [20, 15, 10, 5, 5]
+        combos = main.find_combos(sizes, set(), set(range(len(sizes))), 25)
+        self.assertEqual(main.solve_partn(1, combos), 4)
+        self.assertEqual(main.solve_partn(2, combos), 3)
+
+
+
+if __name__ == "__main__":
+    unittest.main()