Advent of Code (in MiniScript), Day 19
Tags: miniscript, adventofcode, programming
Published: 2022-12-19 22:09:15

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20%23adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  Last night was [Day 19](https://adventofcode.com/2022/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](https://dev.to/joestrout/advent-of-code-in-miniscript-day-16-29a) 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](https://dev.to/joestrout/advent-of-code-in-miniscript-day-16-29a), I would wake up to a bright idea.

But no.  Even having checked the [Reddit thread](https://www.reddit.com/r/adventofcode/comments/zpihwi/2022_day_19_solutions/) 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.