Sean McLemon | Advent of Code

2015-12-17 - No Such Thing as Too Much

(original .ipynb)

Puzzle input is a set of integers that describe volumes of containers in litres. Part one involves finding how many combinations of these containers can be used to hold 150 litres of "eggnog". Part two involved finding what combination of these involves the minimum number of containers, and finding how many have that number of containers.

puzzle_input_str = open("./puzzle_input/day17.txt").read()


def combinations_to_target(pieces, target, used_pieces):
    if target == 0:
        yield used_pieces
    elif target > 0 and pieces:
        for i, p in enumerate(pieces):
            if p <= target:
                yield from combinations_to_target(pieces[1+i:], target-p, used_pieces + [p])        

                
def part_one(input_str, target=150):
    pieces = list(sorted([int(line) for line in input_str.split("\n")], reverse=True))
    return sum(1 for s in combinations_to_target(pieces, target, []) if s != None)


test_input_str = """20
15
10
5
5"""


assert 4 == part_one(test_input_str, 25)

print("part one:", part_one(puzzle_input_str))

part one: 1638

def part_two(input_str, target=150):
    pieces = list(sorted([int(line) for line in input_str.split("\n")], reverse=True))
    solution_lengths = [len(soln) for soln in combinations_to_target(pieces, target, []) if soln != None]
    return sum(1 for s in solution_lengths if s == min(solution_lengths))


assert 3 == part_two(test_input_str, 25)

print("part two:", part_two(puzzle_input_str))

part two: 17