1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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))
|
