--- Day 6: Looping Guards ---

December 6

Listening to: 90s Style Ambient Jungle Mix


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!


Time taken: 50 minutes

My solutions for today's puzzles