Having stumbled on Day 16 yesterday, I decided I was tired of being behind, and would skip Day 17 to do Day 18 today, on the 18th instead. The puzzle was a joy. No painful input parsing. No obscure algorithms. Just, for me, straightforward C++.
In todays puzzle we are working with a point cloud, or voxel type structure representing a spec of lava. We are asked to calculate the surface area, based on point adjacency. The point cloud is around 3k dots in a 20x20x20 cube (8k). I will store the points in a bit array, similar to Day 14, and access it through helper functions.
// in D18Actor.h, definintion of AD18Actor, an AActor based class
UPROPERTY(EditAnywhere, BlueprintReadOnly)
TArray< FVector > Points;
TBitArray<> LavaBuf;
TBitArray<> AirBuf;
FBounds3d Bounds;
inline bool InBounds(FVector P) const
{
return (P.X>=Bounds.Min.X &&
P.Y>=Bounds.Min.Y &&
P.Z>=Bounds.Min.Z &&
P.X<=Bounds.Max.X &&
P.Y<=Bounds.Max.Y &&
P.Z<=Bounds.Max.Z);
}
bool Get( const TBitArray<>& Buff, FVector P )const;
void Set( TBitArray<>& Buff, FVector P, bool V=true );
void AirFill();AirBuff and AirFill are needed for Part 2, more on that later.
Then I do all the work in the actor Begin Play. Reading the input and setting up is 2 pass again:
// Read the points and set up the Bounding volume
Bounds = FBounds3d();
Points.Reset();
for(auto Line : PuzzleInput->Lines)
{
TArray<FString> C;
Line.ParseIntoArray(C, TEXT(","));
FVector P;
P.X = FCString::Atoi(*C[0]);
P.Y = FCString::Atoi(*C[1]);
P.Z = FCString::Atoi(*C[2]);
Bounds += P;
Points.Add(P);
}
// Set up the buffers and write the points into the Lava buffer
auto Size = Bounds.Max - Bounds.Min + FVector(1,1,1);
int Count = Size.X * Size.Y * Size.Z;
LavaBuf.Reset();
LavaBuf.Add(false, Count);
AirBuf.Reset();
AirBuf.Add(false, Count);
for (auto P : Points)
{
Set(LavaBuf, P,true);
}That Set function looks like this:
void AD18Actor::Set(TBitArray<>& Buff, FVector P, bool V)
{
P -= Bounds.Min;
auto Size = Bounds.Max - Bounds.Min + FVector(1,1,1);
int I = P.X + P.Y*Size.X + P.Z*Size.X*Size.Y;
Buff[I]=V;
}And the mirror Get function looks like this:
bool AD18Actor::Get(const TBitArray<>& Buff, FVector P) const
{
if (InBounds(P))
{
P -= Bounds.Min;
auto Size = Bounds.Max - Bounds.Min + FVector(1,1,1);
int I = P.X + P.Y*Size.X + P.Z*Size.X*Size.Y;
return Buff[I];
}
return false;
}Answering Part 1 is then a matter of looking at each of the points and checking the adjacent cells:
int Part1=0;
for (auto P : Points)
{
int C=0;
for (auto F : Faces)
{
if (Get(LavaBuf, P+F)==false) C++;
}
Part1+=C;
}
UE_LOG(LogTemp, Log, TEXT("D18 Part 1 Result: %i"), Part1);Faces is just a static array, its used in that AirFill function as well so its defined outside the function scope:
static const TArray<FVector> Faces {
FVector(1,0,0),
FVector(-1,0,0),
FVector(0,1,0),
FVector(0,-1,0),
FVector(0,0,1),
FVector(0,0,-1),
};Important to note Get returns false for out-of-bounds. Part 2 asks us to exclude internal air pockets from the calculation. Once the AirBuf is set up, the Part 2 calculation is the same as Part 1, but instead of checking the cell isn’t set in the LavaBuf, we check if it is set in the AirBuf. Since my bounds box is tight, I also need count a face as touching air if its adjacency is out of bounds:
// Part 2
int Part2=0;
for (auto P : Points)
{
int C=0;
for (auto F : Faces)
{
FVector V = P+F;
if (!InBounds(V) || Get(AirBuf, V)==true) C++;
}
Part2+=C;
}
UE_LOG(LogTemp, Log, TEXT("D18 Part 2 Result: %i"), Part2);The AirBuf is the “hard work” of part 2. I need to be able to determine if any given point has connectivity to the “outside”, can I path from any given point out of the bounds of the point cloud. If I can do that it is outside the lava blob. If I can’t, it is inside. AirBuf contains the result of that for every point. I approach this as a flood-fill that starts from all the non-lava face edges of the cube:
void AD18Actor::AirFill()
{
TArray<FVector> AirEdge;
AirEdge.Reserve(1024*1024);
// init air edges nodes along XY face at Min+Max Z
for (auto X = Bounds.Min.X; X<=Bounds.Max.X; ++X)
{
for (auto Y = Bounds.Min.Y; Y<=Bounds.Max.Y; ++Y)
{
FVector V[2]={{X,Y,Bounds.Min.Z},{X,Y,Bounds.Max.Z}};
for (int i=0;i!=2;++i)
{
if (Get(LavaBuf, V[i])==false)
{
Set(AirBuf, V[i], true);
AirEdge.Add(V[i]);
}
}
}
}
// init air edges nodes along ZY face at Min+Max X
for (auto Z = Bounds.Min.Z; Z<=Bounds.Max.Z; ++Z)
{
for (auto Y = Bounds.Min.Y; Y<=Bounds.Max.Y; ++Y)
{
FVector V[2]={{Bounds.Min.X,Y,Z},{Bounds.Max.X,Y,Z}};
for (int i=0;i!=2;++i)
{
if (Get(LavaBuf, V[i])==false)
{
Set(AirBuf, V[i], true);
AirEdge.Add(V[i]);
}
}
}
}
// init air edges nodes along XZ face at Min+Max Y
for (auto X = Bounds.Min.X; X<=Bounds.Max.X; ++X)
{
for (auto Z = Bounds.Min.Z; Z<=Bounds.Max.Z; ++Z)
{
FVector V[2]={{X,Bounds.Min.Y,Z},{X,Bounds.Max.Y,Z}};
for (int i=0;i!=2;++i)
{
if (Get(LavaBuf, V[i])==false)
{
Set(AirBuf, V[i], true);
AirEdge.Add(V[i]);
}
}
}
}
UE_LOG(LogTemp, Warning, TEXT("D18 %i Air Edges"), AirEdge.Num());
// Flood fill
while(AirEdge.IsEmpty()==false)
{
auto P = AirEdge[0];
AirEdge.RemoveAtSwap( 0 );
ensure(Get(LavaBuf, P)==false);
ensure(Get(AirBuf, P)==true);
for (auto F : Faces)
{
auto V = P+F;
if (Get(LavaBuf, V)==false)
{
if (Get(AirBuf, V)==false)
{
if (InBounds(V))
{
Set(AirBuf, V, true);
AirEdge.Add(V);
}
}
}
}
}
}Finished in time to add dumb render of the blob in BP afterwards:
