Perhaps my favorite so far. Day 21 part 1 is a relatively straight forward recursive solve of a binary expression tree, then Part 2 turns it on its head an has you working out the missing term to needed to have the expression evaluate to a specific result. My solution is all in C++.
I start with a data structure the represents a node in the expression tree:
USTRUCT(BlueprintType)
struct FD20Monkey
{
GENERATED_BODY()
int64 Cached;
int L;
int R;
TCHAR Op;
};
// Op types
constexpr TCHAR D20Op_Literal = 0;
constexpr TCHAR D20Op_Add = '+';
constexpr TCHAR D20Op_Sub = '-';
constexpr TCHAR D20Op_Mul = '*';
constexpr TCHAR D20Op_Div = '/';And a test-automation that closely matches the example from the problem description:
#include "D21Actor.h"
#include "Misc/AutomationTest.h"
IMPLEMENT_SIMPLE_AUTOMATION_TEST(AoC2022D21_Test, "AoC_2022.AoC_2022.AoC2022D21_Test",
EAutomationTestFlags::EditorContext | EAutomationTestFlags::EngineFilter)
bool AoC2022D21_Test::RunTest(const FString& Parameters)
{
FD20Monkey Monkey;
AD21Actor::Read(TEXT("root: pppw + sjmn"),&Monkey);
TestEqual(TEXT("Op == +"),Monkey.Op,D20Op_Add);
TArray<FString> Example = {
TEXT("root: pppw + sjmn"),
TEXT("dbpl: 5"),
TEXT("cczh: sllz + lgvd"),
TEXT("zczc: 2"),
TEXT("ptdq: humn - dvpt"),
TEXT("dvpt: 3"),
TEXT("lfqf: 4"),
TEXT("humn: 5"),
TEXT("ljgn: 2"),
TEXT("sjmn: drzm * dbpl"),
TEXT("sllz: 4"),
TEXT("pppw: cczh / lfqf"),
TEXT("lgvd: ljgn * ptdq"),
TEXT("drzm: hmdt - zczc"),
TEXT("hmdt: 32")
};
// PART 1
TMap< int, FD20Monkey > Troup = AD21Actor::Read(Example);
int64 R = AD21Actor::GetResult_Part1(Troup, AD21Actor::ReadId(TEXT("root")));
TestEqual(TEXT("root monkey yells 152 in example"),152LL,R);
return true;
}Note that the node ids are all fixed length 4 character strings, which can be represented as ints, and that the Op is a TCHAR that can also be copied from the input string without any further processing.
I write some input handling code, with functions for extracting node Ids and Numbers from strings, and load all the expressions into a map of int (node id) to node struct.
int AD21Actor::ReadId(const FString& Line, int i)
{
int Result = 0;
for(int j=0;j!=4;++j)
Result = Result*32 + (Line[i+j]-'a');
return Result;
}
int AD21Actor::ReadNum(const FString& Line, int i)
{
int Result = 0;
const int e = Line.Len();
for(;i!=e && FChar::IsDigit(Line[i]);++i)
Result = Result*10 + (Line[i]-'0');
return Result;
}
int AD21Actor::Read(const FString& Line, FD20Monkey* Result)
{
ensure(Result);
const int Monkey = ReadId(Line,0);
if (FChar::IsDigit(Line[6]))
{
Result->Op = D20Op_Literal;
Result->Cached=ReadNum(Line,6);
}
else
{
Result->L=ReadId(Line,6);
Result->Op = Line[11];
Result->R=ReadId(Line,13);
}
return Monkey;
}
TMap<int, FD20Monkey> AD21Actor::Read(const TArray<FString>& Lines)
{
TMap<int, FD20Monkey> Result;
for(const FString& Line : Lines)
{
FD20Monkey D;
int Id = Read(Line,&D);
Result.Add(Id, D);
}
return Result;
}This sets my up to solve Part 1 with a recursive solver:
int64 AD21Actor::GetResult_Part1(TMap<int, FD20Monkey>& Troup, int Id)
{
FD20Monkey* Monkey = Troup.Find(Id);
if (Monkey->Op==D20Op_Literal)
return Monkey->Cached;
int64 Left = GetResult_Part1(Troup, Monkey->L);
int64 Right = GetResult_Part1(Troup, Monkey->R);
int64 Result = 0;
switch (Monkey->Op)
{
case D20Op_Add:
Result = Left + Right;
break;
case D20Op_Sub:
Result = Left - Right;
break;
case D20Op_Mul:
Result = Left * Right;
break;
case D20Op_Div:
Result = Left / Right;
break;
}
Monkey->Op=D20Op_Literal;
Monkey->Cached=Result;
return Result;
}I don’t think the caching is helpful for the problem dataset, and is perhaps an example of my incorrectly anticipating performance problems ahead of actually encountering them.
This solution works and Part 2 warrants a new solver function, I leave Part 1 as is and create a new function for Part 2 that handle 2 new node types:
// introduced for part 2 constexpr TCHAR D20Op_Eq = '='; constexpr TCHAR D20Op_Unknown = '?';
Extra tests:
// PART 2 (a)
R=0;
bool okay = AD21Actor::GetResult(Troup, AD21Actor::ReadId(TEXT("root")), &R, nullptr);
TestEqual(TEXT("root monkey yells 152 in example"),152LL,R);
// re-parse part 2 to clear cached values
Troup = AD21Actor::Read(Example);
R=AD21Actor::SolvePart2(Troup);
TestEqual(TEXT("the number you need to yell to pass root's equality test is 301"),301LL,R);
The Part 2 Solver starts with a modified version of the GetResult used in Part 1, modified to handle the new “Unknown” node type. For that I need to return more data. I return the success as a bool. True means no unknowns where found, and so a value was calculated. That value is written into an 64 bit integer Result argument. When the Unknown node is encountered it pushes it into an array, the UnknownPath argument and returns false. That ends up looking like this:
bool AD21Actor::GetResult(TMap<int, FD20Monkey>& Troup, int Id, int64* Result, TArray< FD20Monkey* >* UnknownPath)
{
ensure(Result);
FD20Monkey* Monkey = Troup.Find(Id);
if (Monkey->Op==D20Op_Literal)
{
*Result = Monkey->Cached;
return true;
}
if (Monkey->Op==D20Op_Unknown)
{
if (UnknownPath) UnknownPath->Add(Monkey);
return false;
}
int64 LeftValue;
bool LeftOkay = GetResult(Troup, Monkey->L, &LeftValue, UnknownPath);
int64 RightValue;
bool RightOkay = GetResult(Troup, Monkey->R, &RightValue, UnknownPath);
if (LeftOkay && RightOkay)
{
switch (Monkey->Op)
{
case D20Op_Add:
*Result = LeftValue + RightValue;
break;
case D20Op_Sub:
*Result = LeftValue - RightValue;
break;
case D20Op_Mul:
*Result = LeftValue * RightValue;
break;
case D20Op_Div:
*Result = LeftValue / RightValue;
break;
}
Monkey->Op=D20Op_Literal;
Monkey->Cached=*Result;
}
else
{
if (UnknownPath) UnknownPath->Add(Monkey);
// return false;
}
return LeftOkay && RightOkay;
}That this still works as a Part 1 solver is tested in my unit test and against the real data before I move on to writing the other half of Part 2 – working back from the Equals node along the UnknownPath to solve each step and calculate the missing value at the end that the Unknown node represents:
// part 2, Id is the node we want to solve
int64 AD21Actor::SolvePart2(TMap<int, FD20Monkey>& Troup)
{
int RootId = AD21Actor::ReadId(TEXT("root"));
int LeafId = AD21Actor::ReadId(TEXT("humn"));
// change the root and humn nodes per the problem description
FD20Monkey* RootPtr = Troup.Find(RootId);
FD20Monkey* LeafPtr = Troup.Find(LeafId);
RootPtr->Op = D20Op_Eq;
LeafPtr->Op = D20Op_Unknown;
// look at both left and right sides of the root node
int64 LeftValue;
TArray< FD20Monkey* > LeftPath;
bool LeftOkay = GetResult(Troup, RootPtr->L, &LeftValue, &LeftPath);
int64 RightValue;
TArray< FD20Monkey* > RightPath;
bool RightOkay = GetResult(Troup, RootPtr->R, &RightValue, &RightPath);
UE_LOG(LogTemp, Warning, TEXT("D21 Part 2, Solve for %s = %s"),
LeftOkay ? *FString::Printf(TEXT("%lld"),LeftValue) : TEXT("???"),
RightOkay ? *FString::Printf(TEXT("%lld"),RightValue) : TEXT("???"));
int64 KnownValue = LeftOkay ? LeftValue : RightValue;
TArray< FD20Monkey* >* Path = LeftOkay ? &RightPath : &LeftPath;
while(Path->Num())
{
FD20Monkey* Node = Path->Pop();
if (Node->Op == D20Op_Unknown) return KnownValue;
LeftOkay = GetResult(Troup, Node->L, &LeftValue, nullptr);
RightOkay = GetResult(Troup, Node->R, &RightValue, nullptr);
UE_LOG(LogTemp, Warning, TEXT("...Solve for %s %c %s = %lld"),
LeftOkay ? *FString::Printf(TEXT("%lld"),(LeftValue)) : TEXT("???"),
Node->Op,
RightOkay ? *FString::Printf(TEXT("%lld"),(RightValue)) : TEXT("???"),
KnownValue);
// rearranging to solve this step in the expression
switch (Node->Op)
{
case D20Op_Add:
if (RightOkay)
KnownValue = KnownValue-RightValue;
else if (LeftOkay)
KnownValue = KnownValue-LeftValue;
break;
case D20Op_Sub:
if (RightOkay)
KnownValue = KnownValue+RightValue;
else if (LeftOkay)
KnownValue = LeftValue-KnownValue;
break;
case D20Op_Mul:
if (RightOkay)
KnownValue = KnownValue/RightValue;
else if (LeftOkay)
KnownValue = KnownValue/LeftValue;
break;
case D20Op_Div:
if (RightOkay)
KnownValue = KnownValue*RightValue;
else
KnownValue = LeftValue/KnownValue;
break;
}
}
return KnownValue;
}
The logging helped me spot where I’d made basic math mistakes. A fun challenge at just the right level for me to feel a little pushed, but not frustrated or stuck.
1 thought on “Advent of Code in Unreal Engine Day 21”