Day 19 AoC: The factory must grow

16
Jump in the discussion.

No email address required.

So this is a weird situation: this implementation gives the wrong answer to Part 1 but was miraculously correct for Part 2, and I know exactly where in the code that it's underconstrained. My condition for building nothing at all on a turn is dependent on whether you can neither build an ore robot nor a clay robot, but that doesn't always give the optimal result - unless I also add a check to see if I'm at the maximum number of ore robots before building more becomes redundant, which massively slows the program down to the point where it doesn't solve Part 2 within an hour of runtime. I assume there's a more efficient way of narrowing this check without throwing away the optimal path.

This "solves" part 2 in about 10 seconds on my machine.

from multiprocessing import Pool

foo = []
with open('day19_input.txt', 'r') as inp:
    foo = inp.read().split('\n')

costs = []
max_turns = 24
for f in foo:
    f = f.split()
    costs.append([[int(f[6]),0,0],[int(f[12]),0,0],[int(f[18]),int(f[21]),0],[int(f[27]),0,int(f[30])]])

def take_turn(robots, resources, costs, turn_count, max_ore_robots):
    if turn_count == max_turns:
        return resources[3] + robots[3]

    can_build = [False, False, False, False]
    for c in range(4):
        can_build[c] = (costs[c][0] <= resources[0] and costs[c][1] <= resources[1] and costs[c][2] <= resources[2])

    if(robots[0] == max_ore_robots) or max_turns-turn_count < 4:
        can_build[0] = False
    if resources[1]+(max_turns-turn_count)*robots[1] >= costs[2][1]*(max_turns-turn_count) or max_turns-turn_count < 3:
        can_build[1] = False
    if resources[2]+(max_turns-turn_count)*robots[2] >= costs[3][2]*(max_turns-turn_count):
        can_build[2] = False
    if turn_count+1 == max_turns and not can_build[3]:
        if can_build[3]:
            return resources[3] + 2*robots[3] + 1
        return resources[3] + 2*robots[3]
    for c in range(4):
        resources[c] += robots[c]

    states = []
    for c in range(4):
        if can_build[c]:
            new_resources = resources[:]
            new_robots = robots[:]
            new_robots[c] += 1
            for d in range(3):                                                                                
                new_resources[d] -= costs[c][d]
            states.append(take_turn(new_robots, new_resources, costs, turn_count+1, max_ore_robots))

    if not (can_build[0] or can_build[1]):
        new_robots = robots[:]
        new_resources = resources[:]
        states.append(take_turn(new_robots, new_resources, costs, turn_count+1, max_ore_robots))
    return(max(states))

def setup_sim(costs):
    return take_turn([1,0,0,0], [0,0,0,0], costs, 1, max(costs[1][0], costs[2][0], costs[3][0]))

if __name__ == '__main__':
    pool_args = []
    for c in costs:
        pool_args.append(tuple([c]))

    out = []
    with Pool() as pool:
        out = pool.starmap(setup_sim, pool_args)
    print(out)
Jump in the discussion.

No email address required.

Jesse what the frick are you talking about??

Jump in the discussion.

No email address required.

Link copied to clipboard
Action successful!
Error, please refresh the page and try again.