solutions

1 files changed, 43 insertions, 0 deletions

diff --git a/24/solution.py b/24/solution.py
new file mode 100644
index 0000000..6aa9ebe
--- /dev/null
+++ b/24/solution.py
@@ -0,0 +1,43 @@
+from functools import reduce
+
+def cansum(packages, target):
+    if target == 0:
+        return True
+    if len(packages) == 0:
+        return False
+    p = next(iter(packages))
+    rest = packages - {p}
+    if p <= target:
+        return cansum(rest, target - p) or cansum(rest, target)
+    else:
+        return cansum(rest, target)
+
+def minimize(packages, pile, target, orig_target=None):
+    if orig_target is None:
+        orig_target = target
+    if target == 0 and cansum(packages, orig_target):
+        return len(pile), reduce(lambda a, b: a * b, pile, 1)
+    if len(packages) == 0:
+        return float('inf'), float('inf')
+    p = next(iter(packages))
+    rest = packages - {p}
+    if p <= target:
+        return min(
+            minimize(rest, pile | {p}, target - p, orig_target),
+            minimize(rest, pile, target, orig_target)
+        )
+    else:
+        return minimize(rest, pile, target)
+
+def part1(packages):
+    return minimize(frozenset(packages), frozenset(), sum(packages) // 3)
+
+def part2(packages):
+    return minimize(frozenset(packages), frozenset(), sum(packages) // 4)
+
+if __name__ == '__main__':
+    with open('input') as f:
+        packages = list(int(l.rstrip()) for l in f)
+        packages.reverse()
+    print(part1(packages))
+    print(part2(packages))