Day 19 has us figuring out the right order to build resource collection devices to get the optimal number of end-of-chain resources. I have approached this as a Depth First Search. My solution works, but completed in a length of time measured in minutes, and would benefit from better pruning.
I am using some structs for the core concepts. The naming is a little tricky, with some overlap between Blueprints the unreal concept (solution space), and Blueprints the puzzle input concept (problem space).
constexpr int D19_None = -1;
constexpr int D19_Ore = 0;
constexpr int D19_Clay = 1;
constexpr int D19_Obs = 2;
constexpr int D19_Geode = 3;
// material costs for a thing
USTRUCT(BlueprintType)
struct FD19Costs
{
GENERATED_BODY()
int Mats[4];
};
// material costs for each thing
USTRUCT(BlueprintType)
struct FD19Blueprint
{
GENERATED_BODY()
UPROPERTY(BlueprintReadWrite)
int Id;
FD19Costs Bots[4];
int Caps[4];
};
USTRUCT(BlueprintType)
struct FD19State
{
GENERATED_BODY()
int Mats[4]={0};
int Bots[4]={0};
};I will also use Test Automation, and structure the Actor around making that easy:
bool AoC2022D19_Test::RunTest(const FString& Parameters)
{
FString BP1Line = TEXT("Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.");
FD19Blueprint BP1 = AD19Actor::ReadBlueprint(BP1Line);
TestEqual(TEXT("BP1 Id = 1"), BP1.Id,1);
FString BP2Line = TEXT("Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.");
FD19Blueprint BP2 = AD19Actor::ReadBlueprint(BP2Line);
TestEqual(TEXT("BP2 Id = 2"), BP2.Id,2);
TestEqual(
TEXT("Using blueprint 1 ... the largest number of geodes you could open in 24 minutes is 9."),
AD19Actor::Simulate(BP1, 24),
9);
TestEqual(
TEXT("by using blueprint 2 ... the largest number of geodes you could open in 24 minutes is 12."),
AD19Actor::Simulate(BP2, 24),
12);
return true;
}ReadBlueprint is a static function on the actor. It reads the integers out of the string and puts them in an array. I use the array to fill out my robot “blueprint” spec. My first attempt at reducing the search space was, noting you can only build 1 robot at a time, to put a cap (maximum) on the harvesting robots, so I never build bots that would result in more resources gathered than can be used:
//static
FD19Blueprint AD19Actor::ReadBlueprint(FString& Line)
{
TArray<int> Ints;
Ints.Reserve(7);
int Accu=0;
for(int i=0;i<Line.Len();++i)
{
// scan to first number
while (i<Line.Len() && !FChar::IsDigit(Line[i])) ++i;
// parse the number
if (i<Line.Len())
{
do
{
Accu = Accu*10 + Line[i]-'0';
i++;
}while (i<Line.Len() && FChar::IsDigit(Line[i]));
Ints.Add(Accu);
Accu = 0;
}
}
ensure (Ints.Num()==7);
FD19Blueprint Result;
// zero the costs
for (int i=0;i!=4;++i)
for (int j=0;j!=4;++j)
Result.Bots[i].Mats[j] = 0;
Result.Id = Ints[0];
// Ore bots are made of Ore
Result.Bots[0].Mats[0] = Ints[1];
// Clay bots are made of Ore
Result.Bots[1].Mats[0] = Ints[2];
// Obsidian bots are made of Ore and Clay
Result.Bots[2].Mats[0] = Ints[3];
Result.Bots[2].Mats[1] = Ints[4];
// Geode bots are made of Ore and Obsidian
Result.Bots[3].Mats[0] = Ints[5];
Result.Bots[3].Mats[2] = Ints[6];
// given we can only buy one bot per turn,
// work out the maximum usable number of each bot type
// if the most ore a bot costs is 1 Ore the, having more than 1 Ore bot is useless
for (int i=0;i!=4;++i)
{
Result.Caps[i]=0;
for (int b=0;b!=4;++b)
if (Result.Caps[i] < Result.Bots[b].Mats[i])
Result.Caps[i] = Result.Bots[b].Mats[i];
}
// geode bots are uncapped
Result.Caps[D19_Geode] = INT_MAX;
return Result;
}With the branch in the search being what bot to build, the order of operations: select what to build, collect resources, build that bot, made structuring the recursion feel awkward. This is what ended up with:
int BuyAndContinue(const FD19Blueprint& Blueprint, FD19State State, int Bot, int Minutes)
{
int Result = State.Mats[D19_Geode];
// pay
if (Bot>-1)
{
for (int i=0;i!=4;++i)
State.Mats[i] -= Blueprint.Bots[Bot].Mats[i];
}
while (Minutes)
{
// collect resources
for (int i=0;i!=4;++i)
State.Mats[i] += State.Bots[i];
// acquire the bot
if (Bot>-1) State.Bots[Bot]++;
Bot=-1;
// work out what we can afford, high end first
for (int b=3;b>=0;--b)
{
if (State.Bots[b]<Blueprint.Caps[b])
{
bool CanAfford = true;
for (int i=0;i!=4 && CanAfford;++i)
CanAfford = State.Mats[i] >= Blueprint.Bots[b].Mats[i];
if (CanAfford)
{
int R = BuyAndContinue(Blueprint, State, b, Minutes-1);
if (R>Result) Result=R;
// if i can buy a higher end robot, do not consider any alternatives
// break; [fast but fails tests]
if (b==D19_Obs || b==D19_Geode) break;
}
}
}
// loop instead of recurse for the no-purchase path
int R = State.Mats[D19_Geode];
if (R>Result) Result=R;
Minutes = Minutes-1;
}
return Result;
}
int AD19Actor::Simulate(FD19Blueprint Blueprint, int Minutes)
{
FD19State State;
State.Bots[D19_Ore]=1;
return BuyAndContinue(Blueprint, State, -1, Minutes);
}Note the “if (b==D19_Obs || b==D19_Geode) break;” this prune was the game-changer that made the solution viable. As you can see, I tried break unconditionally first, but the Blueprint 2 example test fails with that change.
With that C++ in place, the Unreal Blueprint to solve Part 1 looks like this (wired from Event Tick):
Each tick takes about a second. Fast enough to watch but slow enough to be harmful to interactivity. I unwired Part 1 to run the BP for Part 2:
Part 2 takes minute(s) per line but with just 3 lines to process and the correct answer for my second star, I’m not motivated to optimize it further.
The pattern that is forming as these get harder is: Problem state in USTRUCT(s), C++ static functions on an Actor that can be unit tested in isolation, and an Actor to hook puzzle input up and tick the problem solver in BP.