From deb9cd82db7f5b6a44f613feb0959110ce70c2e6 Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Fri, 26 Nov 2021 23:51:59 +0000 Subject: solutions --- 24/solution.py | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 24/solution.py (limited to '24') 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)) -- cgit v1.2.3-54-g00ecf