Day 16 is a tough search problem with a few gotchas. I only have a solution to Part 1 so far, and I’m not going to push on for Part 2 today. So lets explore.
Reading the data in works in 2 passes so I can convert the tunnel destination into array indexes.
The presence of singular and plurals in the input data was my first frustration. I just couldn’t see for so long why searching for “valves ” was failing, and then when I realized that there was a singular case, searching for “valve ” as a fallback returned the 0the element, matching “Valve ” at the start of the string, because Unreal’s default FString::Find behavior is to search case-insensitive.
TArray<FValve> AD16Actor::ParseIntoArray(const TArray<FString>& Lines)
{
TArray<FValve> Result;
Result.Reserve(Lines.Num());
// 1st pass read all the names valve names & flow rates
for (auto Line : Lines)
{
FValve Valve;
Valve.Name = FName( Line.Mid(6,2) );
int FlowStart = FString(TEXT("Valve XX has flow rate=")).Len();
int FlowEnd =0;
if (Line.FindChar(TCHAR(';'), FlowEnd))
{
Valve.FlowRate = FCString::Atoi( *Line.Mid(FlowStart, FlowEnd-FlowStart) );
}
Result.Add(Valve);
}
// 2nd pass, fill out the tunnels destination arrays
static const FString MarkerP = TEXT("valves ");
static const FString MarkerS = TEXT("valve ");
for (int i = 0;i!=Lines.Num();++i)
{
// why would they do this
int Ix = Lines[i].Find(MarkerP);
if (Ix!=INDEX_NONE)
{
Ix += MarkerP.Len();
}
else
{
Ix = Lines[i].Find(MarkerS, ESearchCase::CaseSensitive);
ensure(Ix!=INDEX_NONE);
Ix += MarkerS.Len();
}
FString R = Lines[i].RightChop(Ix);
TArray< FString > Connections;
R.ParseIntoArray(Connections, TEXT(", "));
for (FString C : Connections)
{
FName N(C);
int Index = Result.FindByPredicate([N](const auto& X){return X.Name==N;}) - &Result[0];
ensure(Index>=0 && Index<Result.Num());
Result[i].Tunnels.Add(Index);
// order connections by flow rate, if we visit high flow rate tunnels first we should get better pruning
Result[i].Tunnels.Sort([&](int a, int b){return Result[a].FlowRate>Result[b].FlowRate;});
}
}
return Result;
}Parsing and input handling done I moved on to the puzzle. My instinct that it was going to be a straightforward Depth First Search was off the mark. My part 1 solution only finished in acceptable time on the example problem once I introduced a prune. I am certain my prune can be improved, and that improving the prune will be critical to solving Part 2.
My recursive depth-first-search with a prune, and a basic time-skip once valves are all open gets the answer, but takes several minutes to finish – a clear sign I’ve missed a trick with the algorithm used:
int AD16Actor::Explore(
int PressureReleased,
int PressureReleaseRate,
int ValvesOpen,
int Location,
int TimeLeft)
{
if (!TimeLeft || ValvesOpen==OpenableValves)
return PressureReleased + TimeLeft*PressureReleaseRate;
// prune
if (PressureReleased+TimeLeft*MaxFlow < CurrentBest)
{
return 0;
}
PressureReleased += PressureReleaseRate;
int BestR = PressureReleased;
// opening the valve
if (Valves[Location].Open==false && Valves[Location].FlowRate>0)
{
Valves[Location].Open=true;
int R = Explore(
PressureReleased,
PressureReleaseRate + Valves[Location].FlowRate,
ValvesOpen + 1,
Location,
TimeLeft-1);
Valves[Location].Open=false;
if (R>BestR) BestR = R;
}
// moving
if (ValvesOpen<Valves.Num())
{
for (int t=0;t!=Valves[Location].Tunnels.Num();++t)
{
int DestIndex = Valves[Location].Tunnels[t];
int R = Explore(
PressureReleased,
PressureReleaseRate,
ValvesOpen,
DestIndex,
TimeLeft-1);
if (R>BestR) BestR = R;
}
}
// record best results as we go so we can prune against it
if (CurrentBest<BestR) CurrentBest=BestR;
return BestR;
}
Oh and the 2nd gotcha, the reason I expect a lot of folks will hit the “works with example but not with puzzle”, the start location “AA” is the 1st line in the example, but not in the puzzle data.
void AD16Actor::BeginPlay()
{
Super::BeginPlay();
Valves = ParseIntoArray(PuzzleInput->Lines);
MaxFlow = 0;
OpenableValves = 0;
for (auto V : Valves)
{
MaxFlow += V.FlowRate;
if (V.FlowRate>0) OpenableValves++;
}
// gatcha! AA isnt the 1st tunnel in the input
int Initial = Valves.FindByPredicate([](const auto& X){return X.Name==FName("AA");}) - &Valves[0];
ensure(Initial>=0 && Initial<Valves.Num());
CurrentBest = 0;
int R = AD16Actor::Explore(
0,
0,
0,
Initial,
30);
UE_LOG(LogTemp, Log, TEXT("D16 Result: %i"), R);
}My intention now is to return to optimize and solve Part 2 another day. It’s only going to get harder from here.
1 thought on “Advent of Code in Unreal Engine Day 16”