init commit

2 files changed, 50 insertions, 0 deletions

diff --git a/17/input b/17/input
new file mode 100644
index 0000000..f796965
--- /dev/null
+++ b/17/input
@@ -0,0 +1,20 @@
+11
+30
+47
+31
+32
+36
+3
+1
+5
+3
+32
+36
+15
+11
+46
+26
+28
+1
+19
+3
diff --git a/17/solution.py b/17/solution.py
new file mode 100644
index 0000000..fa3e985
--- /dev/null
+++ b/17/solution.py
@@ -0,0 +1,30 @@
+from collections import Counter
+from functools import cache
+
+def part1(containers: list[int]) -> int:
+    @cache
+    def combinations(index: int, remaining: int) -> int:
+        if index == len(containers):
+            return 1 if remaining == 0 else 0
+        return combinations(index + 1, remaining) + combinations(index + 1, remaining - containers[index])
+    return combinations(0, 150)
+
+def part2(containers: list[int]) -> int:
+    @cache
+    def min_used(index: int, remaining: int, used: int) -> int | float:
+        if index == len(containers):
+            return used if remaining == 0 else float('inf')
+        return min(min_used(index + 1, remaining, used), min_used(index + 1, remaining - containers[index], used + 1))
+    min_used = min_used(0, 150, 0)
+    @cache
+    def count_min(index: int, remaining: int, used: int) -> int | float:
+        if index == len(containers):
+            return 1 if (remaining == 0 and used == min_used) else 0
+        return count_min(index + 1, remaining, used) + count_min(index + 1, remaining - containers[index], used + 1)
+    return count_min(0, 150, 0)
+
+if __name__ == '__main__':
+    with open('input') as f:
+        containers = list(sorted((int(line.strip()) for line in f), reverse=True))
+    print(part1(containers))
+    print(part2(containers))