From a7a6b86002b595bc167af72606b14c67ed1bdf8f Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Wed, 24 Nov 2021 22:25:42 +0000 Subject: init commit --- 17/input | 20 ++++++++++++++++++++ 17/solution.py | 30 ++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+) create mode 100644 17/input create mode 100644 17/solution.py (limited to '17') 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)) -- cgit v1.2.3-54-g00ecf