Day 15 is all about the negative space. A fun puzzle, which tripped me with with an unexpected gotcha. Solution spoilers, C++ and some light commentary contained within.
In the problem we are dealing with Sensors. Each Sensor can detect the closest Beacon. I define a struct to store them:
USTRUCT(BlueprintType)
struct FSensorZone
{
GENERATED_BODY()
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "D15")
FVector2D Location;
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "D15")
FVector2D Beacon;
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "D15")
int32 Size;
};In a new actor I create a static member function to load Sensor & Beacon pairs from the input strings:
FSensorZone AD15Actor::SensorZoneFromString(const FString& Line)
{
TArray<FString> SplitString;
Line.ParseIntoArray(SplitString, TEXT("="), true);
ensure(SplitString.Num()==5);
FSensorZone Result;
Result.Location.X = FCString::Atoi(*SplitString[1]);
Result.Location.Y = FCString::Atoi(*SplitString[2]);
Result.Beacon.X = FCString::Atoi(*SplitString[3]);
Result.Beacon.Y = FCString::Atoi(*SplitString[4]);
Result.Size = ManhattenDistance(Result.Location,Result.Beacon );
return Result;
}
int AD15Actor::ManhattenDistance(FVector2d From, FVector2d To)
{
return FMath::Abs(From.X-To.X) + FMath::Abs(From.Y-To.Y);
}I wrote some unit tests to make sure the loading works. The look like this, but more of them:
Zone = AD15Actor::SensorZoneFromString(TEXT("Sensor at x=9, y=16: closest beacon is at x=10, y=16"));
TestEqual(TEXT("the sensor at X=9"), (int)Zone.Location.X, 9);
TestEqual(TEXT("the sensor at Y=16"), (int)Zone.Location.Y, 16);
TestEqual(TEXT("the closest beacon at X=10"), (int)Zone.Beacon.X, 10);
TestEqual(TEXT("the closest beacon at Y=16"), (int)Zone.Beacon.Y, 16);Part one asks us to consider just one row only, and count the spaces that are “safe” (closer to a sensor than its closest beacon). Since the problem asked for just one row I implemented a helper function to check if a Sensor Zone intersects it. I also returned the start and end of the column for that row so I could use it later to determine bounds and jump spans. I used half-open ranges.
//static
bool AD15Actor::IntersectsRow(const FSensorZone& Zone, int Row, int& ColumnStart, int &ColumnEnd)
{
int MinY = Zone.Location.Y-Zone.Size;
int MaxY = Zone.Location.Y+Zone.Size + 1;
bool Result = (Row >= MinY && Row < MaxY );
if (Result)
{
int DY = FMath::Abs(Row - Zone.Location.Y );
int DX = Zone.Size - DY;
ColumnStart = Zone.Location.X - DX;
ColumnEnd = Zone.Location.X + DX + 1;
}
return Result;
}I add some tests for this as well:
Zone = AD15Actor::SensorZoneFromString(TEXT("Sensor at x=8, y=7: closest beacon is at x=2, y=10"));
TestEqual(TEXT("the sensor at X=8"), (int)Zone.Location.X, 8);
TestEqual(TEXT("the sensor at Y=7"), (int)Zone.Location.Y, 7);
int Start, End;
TestFalse( TEXT("Above"), AD15Actor::IntersectsRow(Zone,-3, Start, End));
TestTrue( TEXT("Top"),AD15Actor::IntersectsRow(Zone,-2, Start, End));
TestEqual( TEXT("Start=8"), Start, 8);
TestEqual( TEXT("Width=1"), End-Start, 1);
TestTrue( TEXT("Bottom"), AD15Actor::IntersectsRow(Zone,16, Start, End));
TestEqual( TEXT("Start=8"), Start, 8);
TestEqual( TEXT("Width=1"), End-Start, 1);
TestFalse( TEXT("Below"), AD15Actor::IntersectsRow(Zone,-3, Start, End));The IntersectsRow function will be used to determine the first and last column in the row that need checking. I will need a function to check if a space is “Safe”. A space is safe it is within ANY sensors safe zone:
bool AD15Actor::SafeSpace(int Row, int Column) const
{
for (auto Zone : Sensors)
{
int Start, End;
if (IntersectsRow(Zone, Row, Start, End))
{
if (Column>=Start && Column<End) return true;
}
}
return false;
}I will also need a function that tells me if a space already has a beacon on it:
bool AD15Actor::BeaconLocation(int Row, int Column) const
{
FVector2D P(Column,Row);
for (auto Zone : Sensors)
{
if (Zone.Beacon==P) return true;
}
return false;
}With these three helper-functions: IntersectsRow, SafeSpace and BeaconLocation I can write my Part 1 Solution Finder, CountSafeInRow:
int AD15Actor::CountSafeInRow(int Row) const
{
// find the start and end columns occupied on this Row
int MinC=INT_MAX, MaxC=-INT_MAX;
for (auto Zone : Sensors)
{
int Start, End;
if (IntersectsRow(Zone, Row, Start, End))
{
if (Start<MinC) MinC = Start;
if (End>MaxC) MaxC = End;
}
}
// check every square 1 at a time from start to end on this row
int Total = 0;
for (int Column = MinC; Column!=MaxC; ++Column)
{
if (BeaconLocation(Row, Column)) continue;
if (SafeSpace(Row, Column)) Total++;
}
return Total;
}This did not work first time. I didn’t have the BeaconLocation check, that came after figuring out why it was off-by-one against the puzzle example.
Part 2 turns this on its head. I read the problem and then went to eat. Then I read it again. I need to find the one unsafe (not in any of the sensors ranges) in a massive 4 million x 4 million square grid. Every square needs checking against 32 beacons.
I’ve been working in rows so far so I decide to go with span-skipping. Once I have a Sensor and I know it overlaps a Row, then I know the start and end and I don’t need to check inside them. I will be checking every Row, but I cant think of a quick way to know I can skip a row so I just hope skipping columns will be fast enough, and so I write it out and after “some debugging” I end up with this:
int64 AD15Actor::LocateBeacon(int Lowest, int Largest) const
{
int Row = Lowest;
int Column = Lowest;
do
{
bool foundSafe = true;
for (auto Zone : Sensors)
{
int Start, End;
if (IntersectsRow(Zone, Row, Start, End))
{
if (Column>=Start && Column<End)
{
foundSafe = false;
Column = End;
break;
}
}
}
if (foundSafe && !BeaconLocation(Row, Column))
{
ensure(!SafeSpace(Row,Column));
int64 Result = Column;
Result *= 4000000;
Result += Row;
UE_LOG(LogTemp, Log, TEXT("D15 64bit Check: %lld"), Result);
return Result;
}
if (Column>Largest)
{
Column = Lowest;
Row ++;
}
}
while (Row <= Largest);
return 0;
}This algorithm is good and fast enough to not worry about. You will note however that the function returns an int64, and that I have an extra logging using %lld formatting. This is because I spent at least an hour scratching my head about why my solver matched the example input but didn’t get the right part 2 answer. I should really have anticipated that multiply by 4 million overflows my poor lowly integers, but I went looking for fence post errors and problems with rounding to int from float – the Vector class in unreal was switched to double in 5.0, which holds bigger ints (exactly) than a 32 bit int.
Right well that’s that for now. I hope you enjoyed reading this. Until tomorrow!