1 files changed, 52 insertions, 0 deletions
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()