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
31
32
33
34
35
36
37
38
39
40
41
42
|
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 = [int(l.rstrip()) for l in f]
print(part1(packages))
print(part2(packages))
|
