Today's puzzle doesn't seem too bad. A two pass approach - trace the guard's path & count distinct spaces visited - seems somewhat trivial.
One possibly ugly thing was putting the directions as arrays of x/y changes for each turn direction in order, but it works out pretty elegantly in practice, and runs pretty quick
int x, y, turn = 0;
int[] xdir = { -1, 0, 1, 0 };
int[] ydir = { 0, 1, 0, -1 };
while (true)
{
// Mark spot
grid[x][y] = 'X';
var nextX = x + xdir[turn];
var nextY = y + ydir[turn];
if (!Utils.IsInBounds(grid, nextX, nextY)) break;
// Check if turning
if (grid[nextX][nextY] == '#')
{
turn = (turn + 1) % 4;
}
else
{
// Move
x += xdir[turn];
y += ydir[turn];
}
}
Part 2... This seems like a bit of a pain to do, finding a change that can intentionally cause a loop.
Offhand I don't have an issue with possibly bruteforcing this, but I'm more concerned with finding a loop in the first place. Perhaps if I'm a bit more clever about it - leaving a different character depending on the direction they are facing. So if the guard is moving right (>
) on the same square more than once, they will end up tracing the same path! All I have to do is keep track of direction characters specifically instead of just marking spots.
... except that doesn't work in one edge case.
.#.....#.
#...<...#
.#.....#.
Here, the guard will go back and forth forever, but keep changing directions perfectly.
If I instead keep count of how many times a space has been visited? The way I figure, a space can be visited at most four times without being in a loop (once from each direction), so if it's visited a 5th time, then it's a loop.
private bool willLoop(int obstacleX, int obstacleY)
{
var testGrid = new List<List<char>>();
foreach (var s in grid)
{
testGrid.Add(new List<char>(s));
}
testGrid[obstacleX][obstacleY] = '#';
testGrid[startX][startY] = '.';
int x = startX, y = startY, turn = 0;
while (true)
{
// Check spot & mark
if (testGrid[x][y] == '4') return true;
else if (testGrid[x][y] >= '1' && testGrid[x][y] <= '3') testGrid[x][y]++;
else testGrid[x][y] = '1';
var nextX = x + xdir[turn];
var nextY = y + ydir[turn];
if (!Utils.IsInBounds(testGrid, nextX, nextY)) return false;
// Check if turning
if (testGrid[nextX][nextY] == '#')
{
turn = (turn + 1) % 4;
}
else
{
// Move
x += xdir[turn];
y += ydir[turn];
}
}
}
It takes a little bit to run, but works!