Day 11 is all about the big numbers, and doing it in Unreal didn’t help me at all. Some horrible input handing, and some nasty gotchas. It’s all in C++.
It starts with the Monkey struct. A plain old C++ struct, and really just so I can mangle the text input into memory:
static const FString starting_str = TEXT(" Starting items: ");
static const FString operation_str = TEXT(" Operation: new = old ");
static const FString test_str = TEXT(" Test: divisible by ");
static const FString test_true = TEXT(" If true: throw to monkey ");
static const FString test_false= TEXT(" If false: throw to monkey ");
struct Monkey
{
TArray< int64 > Items;
FString Op;
int64 Test;
int TrueDest;
int FalseDest;
uint64 Inspections=0;
Monkey(const TArray<FString>& Input, int& Line)
{
TArray<FString> Strings;
ensure(Input[Line].StartsWith(starting_str));
Input[Line].RightChop(starting_str.Len()).ParseIntoArray(Strings, TEXT(","));
for (auto S : Strings)
Items.Add( FCString::Atoi(*S) );
Line++;
ensure(Input[Line].StartsWith(operation_str));
Op = Input[Line].RightChop(operation_str.Len());
Line++;
ensure(Input[Line].StartsWith(test_str));
Test = FCString::Atoi(*Input[Line].RightChop(test_str.Len() ));
Line++;
ensure(Input[Line].StartsWith(test_true));
TrueDest = FCString::Atoi(*Input[Line].RightChop(test_true.Len() ));
Line++;
ensure(Input[Line].StartsWith(test_false));
FalseDest = FCString::Atoi(*Input[Line].RightChop(test_false.Len() ));
Line++;
}
};Then that is used by a single function that can handle either parts 1 and part 2 via the Relief and MaxRounds arguments:
//static
int UAoC22BPFunctionLibrary::D11_MonkeyAround(const TArray<FString>& Input, int Relief, int MaxRounds)
{
int Line = 0;
TArray< Monkey* > Monkeys;
while (Line<Input.Num())
{
// skip monkey id, just goes up
Line++;
Monkeys.Emplace(new Monkey(Input, Line));
// skip blank line
Line++;
}
// find the combined multiplier of all the monkeys tests
// see: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
int64 combined = 1;
for (auto M : Monkeys)
{
combined *= M->Test;
}
for (int Rounds=0; Rounds!=MaxRounds; ++Rounds)
{
// ROUND
for (auto M : Monkeys)
{
// TURN
const int i = 0;
while (M->Items.Num())
{
int64 OpVal = (M->Op.EndsWith(TEXT("old")))
? M->Items[i]
: FCString::Atoi(*M->Op.RightChop(2));
switch (**M->Op)
{
case '*': M->Items[i] *= OpVal; break;
case '+': M->Items[i] += OpVal; break;
default: UE_LOG(LogTemp, Warning, TEXT("Expected Op: %s"), *M->Op); break;
}
M->Items[i] /= Relief;
M->Items[i] %= combined;// keep it from overflowing
if ((M->Items[i] % M->Test)==0)
{
Monkeys[M->TrueDest]->Items.Add( M->Items[i] );
M->Items.RemoveAt(i);
}
else
{
Monkeys[M->FalseDest]->Items.Add( M->Items[i] );
M->Items.RemoveAt(i);
}
M->Inspections++;
}
}
}
int C=0;
for (auto M : Monkeys)
{
UE_LOG(LogTemp, Warning, TEXT("Monkey %i inspected items %i times."), C, M->Inspections);
C++;
}
Monkeys.Sort([](auto a, auto b){return a.Inspections > b.Inspections;});
UE_LOG(LogTemp, Warning, TEXT("Monkey business: %i * %i = %llu"),
Monkeys[0]->Inspections, Monkeys[1]->Inspections, Monkeys[0]->Inspections*Monkeys[1]->Inspections);
return 0;
}This jumped out as “probably needs 64 bit ints” right away, but 2 further stumbling blocks held me up a long time:
- It overflows even 64 bits in the Items value repeatedly. You need to use Chinese remainder theorem to prevent that from affecting the results.
- The final combined monkey business result is also a large number. Forgetting to use %llu in my logging had me scratching my head for ages.