I hope you like edge cases, because Day 22 is all about the edge cases. Lets wrap around…
Starting with Part 1 I follow a now familiar pattern: Create a new Actor class, and a new Unreal Test Class, both in C++, and write some tests using IMPLEMENT_SIMPLE_AUTOMATION_TEST that closely follow the puzzle example:
bool AoC2022D22_Test::RunTest(const FString& Parameters)
{
TArray<FString> Example={
TEXT(" ...#"),
TEXT(" .#.."),
TEXT(" #..."),
TEXT(" ...."),
TEXT("...#.......#"),
TEXT("........#..."),
TEXT("..#....#...."),
TEXT("..........#."),
TEXT(" ...#...."),
TEXT(" .....#.."),
TEXT(" .#......"),
TEXT(" ......#."),
TEXT(""),
TEXT("10R5L5R10L4R5L5")
};
auto grid = AD22Actor::CreateGrid(Example);
FD22Cursor current = AD22Actor::GetInitial(grid);
TestEqual(TEXT("Initial position is on 1st Row"), current.Pos.Y, 0.0);
TestEqual(TEXT("Initial position is on 9th Column"), current.Pos.X, 8.0);
TestEqual(TEXT("Initial direction is Right"), current.GetDirChar(), TCHAR('>'));
grid.Log();
FD22Cursor result = AD22Actor::Follow(grid,current,Example.Last());
grid.Log();
int Row = result.Pos.Y+1;
int Column = result.Pos.X+1;
TestEqual(TEXT("In the above example, the final row is 6"), Row, 6);
TestEqual(TEXT("... the final column is 8"), Column, 8);
TestEqual(TEXT("... the final facing is 0"), result.GetFacing(), 0);
// The final password is the sum of 1000 times the row, 4 times the column, and the facing.
TestEqual(TEXT("So, the final password is 1000 * 6 + 4 * 8 + 0: 6032."), result.Password(), 6032);
return true;
}
In writing my Tests I discover I want Cursor and Grid types, to hold the current state of the head of the path. I define them as structs with the Actor:
// in the header file
USTRUCT(BlueprintType)
struct FD22Cursor
{
GENERATED_BODY()
FVector2d Pos;
FVector2d Dir;
TCHAR GetDirChar()const;
int GetFacing() const;
int Password() const;
};
// in the .cpp
TCHAR FD22Cursor::GetDirChar() const
{
if (Dir.X>0) return TCHAR('>');
if (Dir.X<0) return TCHAR('<');
if (Dir.Y>0) return TCHAR('v');
if (Dir.Y<0) return TCHAR('^');
return TCHAR('o');
}
int FD22Cursor::GetFacing() const
{
// Facing is 0 for right (>), 1 for down (v), 2 for left (<), and 3 for up (^).
if (Dir.X>0) return 0;
if (Dir.X<0) return 2;
if (Dir.Y>0) return 1;
if (Dir.Y<0) return 3;
return -1;
}
int FD22Cursor::Password() const
{
int Row = Pos.Y+1;
int Column = Pos.X+1;
return 1000 * Row + 4 * Column + GetFacing();
}
My Grid uses a single buffer and provides some very basic off-edge behaviors to help keep my path tracing loop light on bounds checking:
USTRUCT(BlueprintType)
struct FD22Grid
{
GENERATED_BODY()
int Width=0;
int Height=0;
TArray<TCHAR> Data;
void Set(int x, int y, TCHAR c) { Data[x+y*Width]=c; }
bool Set(FVector2d Pos, TCHAR c)
{
if (Pos.X>=Width ||
Pos.Y>=Height ||
Pos.X<0 ||
Pos.Y<0) return false;
Set(Pos.X,Pos.Y,c);
return true;
}
TCHAR Get(int x, int y) const { return Data[x+y*Width]; }
TCHAR Get(FVector2d Pos) const
{
// infinite blank in all directions
if (Pos.X>=Width ||
Pos.Y>=Height ||
Pos.X<0 ||
Pos.Y<0) return ' ';
return Get(Pos.X,Pos.Y);
}
void Log();
};Creating the Grid and Getting the Initial Cursor position are straightforward input handling:
FD22Grid AD22Actor::CreateGrid(const TArray<FString>& Lines)
{
int i,j=0;
for (i=0;i!=Lines.Num();++i)
{
if (Lines[i].IsEmpty()) break;
if (Lines[i].Len()>j) j=Lines[i].Len();
}
FD22Grid Result;
Result.Width=j;
Result.Height=i;
Result.Data.Init(TCHAR(' '), i*j);
for (i=0;i!=Result.Height;++i)
{
for (j=0;j!=Lines[i].Len();++j)
{
Result.Set(j,i,Lines[i][j]);
}
}
return Result;
}
FD22Cursor AD22Actor::GetInitial(const FD22Grid& Grid)
{
// You begin the path in the leftmost open tile of the top row of tiles.
int Row=0;
int Column=0;
while (TCHAR(' ')==Grid.Get(Column, Row )) Column++;
FD22Cursor Initial;
Initial.Pos.X=Column;
Initial.Pos.Y=Row;
// Initially, you are facing to the right
Initial.Dir=FVector2D(1,0);
return Initial;
}Turning a 90 rotation for a 2D Vector can be implemented with a X Y swap and negate one, depending on direction:
FVector2d AD22Actor::Turn(const FVector2d& V, TCHAR D)
{
if (D==TCHAR('R'))
{
return FVector2d(-V.Y, V.X);
}
else
{
ensure(D==TCHAR('L'));
return FVector2d(V.Y, -V.X);
}
}Taking a single move the key detail is to work the Next after wrapping before updating the position, so wall-blocking works around edges:
FD22Cursor AD22Actor::Move(FD22Grid& Grid, const FD22Cursor& Start, int Steps)
{
FD22Cursor Result = Start;
while(Steps--)
{
FVector2d Next = Result.Pos+Start.Dir;
// continue to step through the blank spaces with wrap around:
while(Grid.Get(Next)==TCHAR(' '))
{
if (Next.X<0) Next.X+=Grid.Width;
else if (Next.X>=Grid.Width) Next.X-=Grid.Width;
else if (Next.Y<0) Next.Y+=Grid.Height;
else if (Next.Y>=Grid.Height) Next.Y-=Grid.Height;
else Next+=Start.Dir;
}
if (Grid.Get(Next)==TCHAR('#')) break;
Grid.Set(Result.Pos, Result.GetDirChar());
Result.Pos=Next;
};
return Result;
}Also note, writing the path back into the grid is for debugging / validation.
The Move method is then used to write the path follow. The ReadNum you may recognize from Day 21. It is modified here to take the i parameter by reference, so we can use it as an iterator for parsing number/turn-letter pairs and advance through the path:
FD22Cursor AD22Actor::Follow(FD22Grid& Grid, const FD22Cursor& Start, const FString& Path)
{
int i=0;
FD22Cursor Current = Start;
while(i<Path.Len())
{
int Steps = ReadNum(Path,i);
Current = Move(Grid,Current,Steps);
if (i<Path.Len()) Current.Dir = Turn(Current.Dir, Path[i++]);
}
return Current;
}And that is Part 1 complete. Part 2 explains the map is a Cube that has been unwrapped, and the wrap around should be implemented to move the cursor from face to face.
In a move that might be described as sadistic, the example problem is unfolded with a different face positioning to my problem data. I decide to hard-code my solution to the layout I am given:
7 face-links. Each one bi-directional, each one with 2 axis, each one providing different opportunities for off-by-one errors. Working through each one carefully took some time. I made several mistakes, and a mixture of unit tests, assertions, and visually inspecting the paths from the logging helped me identify.
A modified “Move” handles the different ways you can move between faces. This is not elegant code:
FD22Cursor AD22Actor::CubeMove(FD22Grid& Grid, const FD22Cursor& Start, int Steps)
{
FD22Cursor Result = Start;
while(Steps--)
{
FVector2d NextDir = Result.Dir;
FVector2d Next = Result.Pos+Result.Dir;
if (Grid.Get(Next)==TCHAR(' '))
{
if (Next.X==-1)
{
ensure (Next.Y>=100);
if (Next.Y<150)
{
// 0,2 -> 1.0
Next.X = 50;
Next.Y = 49 - (Next.Y-100);
NextDir = FVector2d(1,0);
}
else
{
//0,3 -> 1,0
Next.X = 50 + (Next.Y-150);
Next.Y = 0;
NextDir = FVector2d(0,1);
}
}
else if (Next.X==49)
{
ensure (Next.Y<100);
if (Next.Y<50)
{
// 1,0 -> 0,2
Next.X = 0;
Next.Y = 149 - Next.Y;
NextDir = FVector2d(1,0);
}
else
{
//1,1 -> 0,2
Next.X = Next.Y-50;
Next.Y = 100;
NextDir = FVector2d(0,1);
}
}
else if (Next.X==50 && Next.Y>149)
{
// 0,3 -> 1,2
Next.X = 50 + (Next.Y - 150);
Next.Y = 149;
NextDir = FVector2d(0,-1);
}
else if (Next.X==100 && Result.Dir.X==1)
{
if (Next.Y<100)
{
// 1,1 -> 2,0
Next.X = 100 + (Next.Y-50);
Next.Y = 49;
NextDir = FVector2d(0,-1);
}
else
{
// 1,2 -> 2,0
Next.X = 149;
Next.Y = 49 - (Next.Y-100);
NextDir = FVector2d(-1,0);
}
}
else if (Next.X==150)
{
// 2,0 -> 1,2
Next.X = 99;
Next.Y = 149 - Next.Y;
NextDir = FVector2d(-1,0);
}
else if (Next.Y==-1)
{
if (Next.X<100)
{
// 1,0 -> 0,2
Next.Y = 150 + Next.X-50;
Next.X = 0;
NextDir = FVector2d(1,0);
}
else
{
// 2,0 -> 0,3
Next.Y = 199;
Next.X = Next.X - 100;
NextDir = FVector2d(0,-1);
}
}
else if (Next.Y==50)
{
// 2,0 -> 1,1
Next.Y = 50 + Next.X-100;
Next.X = 99;
NextDir = FVector2d(-1,0);
}
else if (Next.Y==99)
{
// 0,2 -> 1,1
Next.Y = 50 + Next.X;
Next.X = 50;
NextDir = FVector2d(1,0);
}
else if (Next.Y==150)
{
// 1,2 -> 0,3
Next.Y = 150 + Next.X-50;
Next.X = 49;
NextDir = FVector2d(-1,0);
}
else if (Next.Y==200)
{
// 0,3 -> 2,0
Next.Y = 0;
Next.X = Next.X + 100;
}
else
{
UE_LOG(LogTemp, Error, TEXT("%i,%i Missing Edge Case Heading %c"),
Next.X, Next.Y, Result.GetDirChar());
}
}
if (Grid.Get(Next)==TCHAR('#')) break;
ensure(Grid.Get(Next)!=' ');
if (Grid.Set(Result.Pos, Result.GetDirChar())==false)
{
Grid.Log();
UE_LOG(LogTemp, Error, TEXT("%i,%i Out of Bounds heading %c"),
Result.Pos.X, Result.Pos.Y, Result.GetDirChar());
break;
}
Result.Pos=Next;
Result.Dir=NextDir;
};
return Result;
}
The line “ensure(Grid.Get(Next)!=’ ‘);” was critical to me finding all the bugs, as was testing the travel in a semi procedural test:
FVector2D a[]={{1,0},{1,0},{2,0},{2,0},{2,0},{1,1},{0,3}};
FVector2D b[]={{0,3},{0,2},{0,3},{1,1},{1,2},{0,2},{1,2}};
FVector2D d[]={{0,-1},{-1,0},{0,-1},{0,1},{1,0},{-1,0},{1,0}};
for (int i=0;i!=sizeof(a)/sizeof(FVector);++i)
{
auto test = MakePart2Grid();
FD22Cursor c;
c.Dir = d[i];
c.Pos = a[i] * 50;
c = AD22Actor::CubeMove(test, c,50);
TestEqual(*FString::FromInt(i), (int)c.Pos.X/50,(int)b[i].X);
TestEqual(*FString::FromInt(i), (int)c.Pos.Y/50,(int)b[i].Y);
test.Log();
}Can you think of a better way? Let me know here or on Mastodon.
1 thought on “Advent of Code in Unreal Engine Day 22”