Day 13 has everything you could possibly ask for. It’s got C++! It’s got Blueprints! It’s got Json parsing! Its got recursion and iteration! What more could you want?
Seeing the input looks a lot like Json and is nested arrays of mixed types I figure its better to find out what Unreal can do for me rather than write another parser.
To get access to the Json support from C++ you need to add the Json and JsonUtilities modules to the project:
// In Project.Build.cs, in your project ModuleRules class constructor, add:
PublicDependencyModuleNames.AddRange(new string[] { "Json", "JsonUtilities" });
In my Function Library I am going to deal with conversion of the strings to Json, and then working with the DOM in memory solve the comparison problem. For parsing arbitrary Json, you can use the TJsonReaderFactory to construct a FJsonValue:
// 1 = Left Right order is correct
// 0 = Left Right are equal
// -1 = Left Right are the wrong way around
int UAoC22BPFunctionLibrary::D13_Calculate(FString LeftStr, FString RightStr)
{
TSharedPtr<FJsonValue> Left;
TSharedRef<TJsonReader<TCHAR>> JsonReader1 = TJsonReaderFactory<TCHAR>::Create(LeftStr);
FJsonSerializer::Deserialize(JsonReader1, Left);
TSharedPtr<FJsonValue> Right;
TSharedRef<TJsonReader<TCHAR>> JsonReader2 = TJsonReaderFactory<TCHAR>::Create(RightStr);
FJsonSerializer::Deserialize(JsonReader2, Right);
// in your code, you should check the Deserialize return values!
return JsonD13Compare(Left, Right);
}I then set up some unit tests following the examples provided by the puzzle text, and then set to implementing JsonD13Compare. This works with FJsonValue‘s TryGetNumber, and TryGetArray, iterates over the array and uses recursion to deal with lists within the list:
// 1 = Left Right order is correct
// 0 = Left Right are equal
// -1 = Left Right are the wrong way around
static int JsonD13Compare(TSharedPtr<FJsonValue> Left, TSharedPtr<FJsonValue> Right)
{
// If both values are integers
int32 FirstNumber;
int32 SecondNumber;
bool LeftIsNumber = Left->TryGetNumber(FirstNumber);
bool RightIsNumber = Right->TryGetNumber(SecondNumber);
if (LeftIsNumber && RightIsNumber)
{
// the lower integer should come first.
if (FirstNumber < SecondNumber)
return 1;
else if (FirstNumber == SecondNumber)
return 0;
else
return -1;
}
// If both values are lists...
TArray<TSharedPtr<FJsonValue>>* FirstArray = nullptr;
TArray<TSharedPtr<FJsonValue>>* SecondArray = nullptr;
bool LeftIsArray = Left->TryGetArray(FirstArray);
bool RightIsArray = Right->TryGetArray(SecondArray);
if (LeftIsArray && RightIsArray)
{
int Index = 0;
do
{
bool LeftComplete = !FirstArray->IsValidIndex(Index);
bool RightComplete = !SecondArray->IsValidIndex(Index);
if (LeftComplete)
{
if (RightComplete)
{
// If the lists are the same length and no comparison makes a decision about the order,
// continue checking the next part of the input.
return 0;
}
else
{
// If the left list runs out of items first, the inputs are in the right order.
return 1;
}
}
else if (RightComplete)
{
// If the right list runs out of items first, the inputs are not in the right order.
return -1;
}
else
{
// compare the first value of each list then the second value, and so on ...
int R = JsonD13Compare( (*FirstArray)[Index], (*SecondArray)[Index] );
if (R!=0) return R;
Index++;
}
}while(true);
}
// If exactly one value is an integer,
// convert the integer to a list which contains that integer as its only value,
// then retry the comparison.
if (LeftIsArray && RightIsNumber)
{
TArray< TSharedPtr<FJsonValue> > RightInAnArray{Right};
TSharedPtr<FJsonValueArray> RightAsArray = MakeShareable( new FJsonValueArray(RightInAnArray) );
return JsonD13Compare(Left, RightAsArray);
}
else
{
ensure(LeftIsNumber && RightIsArray);
TArray< TSharedPtr<FJsonValue> > LeftInAnArray{Left};
TSharedPtr<FJsonValueArray> LeftAsArray = MakeShareable( new FJsonValueArray(LeftInAnArray) );
return JsonD13Compare(LeftAsArray, Right);
}
// never gets here
return 0;
}
All done, right? Not quite. I need to pull pairs of strings out of in input to feed to this function. I create an actor for this, processing the input one pair at a time using a sequence node to keep things somewhat orderly. Parts 1 and 2 all together in the Event Graph ends up looking like this:
The link takes you to a zoomable view of the blueprint. Lets look at that sequence one Then at a time:
- (0) Read the Left line. Added in part 2 I pass that straight to the Insert Line function. More on that later.
- (1) Same as 0, but for Right. Also passed to Insert Line. I now have a pair of Left and Right.
- (2) Skip the blank line.
- (3) Call into my C++ “D13 Calculate”, and add the Pair counter to the Sum if the order is correct, and log the Pair index if I’ve set a “verbosity” property on the actor to true.
- (4) Advance the Pair counter.
- (5) Check if the input has been exhausted and finish up by building some result messages to log out.
So, about Insert Line. Part 2 has you ordering the whole list. So a sort function then. In Blueprint. Lets do this:
Okay its not quite a stand alone sort function, but it maintains the sorted order as the lines are added by inserting each of them in the right place as it goes along.
The Array Index being undefined outside the loop tripped me up, and the separate Insert Index local variable dampens the elegancy, but still a fun challenge and a pleasing result.