Advent of Code (in MiniScript), Day 19

Welcome back to my series of Advent of Code solutions in MiniScript! Last night was Day 19.

This challenge had us prioritizing builds and allocating resources in a factory. There were basically four types of resources, and four types of resource-gatherers. It takes some of resource A to build a bot that gathers resource A or B; some of A and B to build a bot that gathers resource C; and some of A and C to build a bot that gathers resource D. Resource D isn't used for anything, but it is the goal: maximize the amount of that one that can be made in 24 minutes.

Oh, and do this according to a variety of different "blueprints" which define how much of each resource is required to build each robot.

At first I thought, "Aha, another dynamic programming problem!" I quickly coded it up that way, and let it run. And run. And run some more.

The problem is, the search space is just too big. Moreover, the state necessarily includes how much of each of three different resources (ignoring the last one) you have, as well as how many of each robot you've built. So there doesn't seem to be very much repetition in various branches of the search tree. I let my program add over 3.5 million entries to my memo map before admitting that this just wasn't working.

I then thrashed around for a while trying other approaches, and ultimately went to bed, as it was getting quite late and today's a work day. I'd hoped that, as on Day 16, I would wake up to a bright idea.

But no. Even having checked the Reddit thread now, it appears there is no clever trick for this one. It's just a big honking search problem, and to make it tractable, you have to come up with some heuristics by trial and error. The heuristics mean you're no longer guaranteed to get the optimal solution (since there is no way to know when what you've found so far is optimal). But eventually you get lucky.

So, here is a thoroughly unsatisfying solution to the problem:

import "mapUtil"
import "aoc"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.pop

plans = []

for line in lines
    m = line.match("Blueprint {num}: Each ore robot costs {oreCost} ore. Each clay robot costs {clayCost} ore. Each obsidian robot costs {obsOreCost} ore and {obsClayCost} clay. Each geode robot costs {geoOreCost} ore and {geoObsCost} obsidian.")
    if not m then
        print "Pattern did not match on line: " + line
        continue
    end if
    m.applyToValues @val
    print m
    plans.push m
end for

memo = {}
bestScore = function(plan, ore, clay, obs, geo, oreBots, clayBots, obsBots, geoBots, timeLeft)
    //print [ore, clay, obs, geo, oreBots, clayBots, obsBots, geoBots, timeLeft].join(",")
    nextGeo = geo + geoBots
    if timeLeft == 1 then return nextGeo
    nextOre = ore + oreBots
    nextClay = clay + clayBots
    nextObs = obs + obsBots
    if ore >= plan.geoOreCost and obs >= plan.geoObsCost then
        return bestScore(plan, nextOre - plan.geoOreCost, nextClay, 
            nextObs - plan.geoObsCost,
            nextGeo, oreBots, clayBots, obsBots, geoBots + 1, timeLeft - 1)
    end if
    if ore >= plan.obsOreCost and clay >= plan.obsClayCost then
        return bestScore(plan, nextOre - plan.obsOreCost, nextClay - plan.obsClayCost,
            nextObs, nextGeo, oreBots, clayBots, obsBots + 1, geoBots, timeLeft - 1)
    end if
    options = []
    if ore < 6 then
        options.push bestScore(plan, nextOre, nextClay, nextObs,
            nextGeo, oreBots, clayBots, obsBots, geoBots, timeLeft - 1)
    end if
    if ore >= plan.oreCost then
        options.push bestScore(plan, nextOre - plan.oreCost, nextClay, nextObs,
            nextGeo, oreBots + 1, clayBots, obsBots, geoBots, timeLeft - 1)
    end if
    if ore >= plan.clayCost then
        options.push bestScore(plan, nextOre - plan.clayCost, nextClay, nextObs,
            nextGeo, oreBots, clayBots + 1, obsBots, geoBots, timeLeft - 1)
    end if
    return options.max  
end function

if true then
    // Part One:
    quality = 0
    for plan in plans
        score = bestScore(plan, 0, 0, 0, 0, 1, 0, 0, 0, 24)
        print "Plan " + plan.num + " score: " + score
        quality = quality + plan.num * score
    end for
    print "Total quality: " + quality
else
    // Part Two:
    product = 1
    for plan in plans[:3]
        score = bestScore(plan, 0, 0, 0, 0, 1, 0, 0, 0, 32)
        print "Plan " + plan.num + " score: " + score
        product = product * score
    end for
end if

I basically took out the dynamic programming part of the search, because it wasn't helping and only wasted oodles of memory. So it's a dumb exhaustive search, with a couple of rules added to make it finish in reasonable time:

1. If you can afford to build a "geode" bot (the goal resource), build it.
2. Otherwise, if you can afford to build a bot that harvests obsidian (resource C), build that.

If either of those apply, then there is no branching at that node at all; we just do what the rules say. Otherwise, there are multiple options to consider: build each of the lower-resource bots, or build nothing at all. We consider that option (do nothing) only if we have less than 6 of resource A.

Why 6? Because I tried 4, and though it worked on the sample problem, it didn't work on the real input file. So I increased it to 6, meaning that option is tried in more cases. This resulted in significantly longer run time, but it gave me a right answer.

See what I mean? Unsatisfying.

Final Thoughts

Well, I guess it is the last week of Advent of Code. The problems are intended to be harder. But I still wish there were some better way to do this.

Maybe there is, and I just haven't found it yet. This is a problem I might revisit next year, during the slow summer days when I don't have any elves to guide through volcanoes. Or, maybe one of you kind readers will suggest a different approach? I'd love to think there is something new for me to learn here!

Or maybe the lesson is, not every problem has a clever solution. Sometimes you have to settle for a big dumb search.