--- Day 16: No-turn maze ---

December 16

Listening to: Vinesauce (corruptions)


Finally, a Maze time!

This one seems like a pretty simple use of a Priority queue (managed queue where the item with the lowest score is dequeued), with some sort memoization to prevent revisiting of spaces.

private long GetLowestScore(List<List<char>> maze)
{
    var seen = new HashSet<(int, int, char)>();
    var queue = new PriorityQueue<(int, int, char), long>();

    var (startX, startY) = Utils.Find2D(maze, 'S');

    var startVal = (startX, startY, '>');
    queue.Enqueue(startVal, 0);

    while (queue.TryDequeue(out var currentSpot, out var score))
    {
        if (seen.Contains(currentSpot)) continue;

        var (x, y, dir) = currentSpot;
        if (maze[x][y] == 'E') return score;
        if (maze[x][y] == '#') continue;
        seen.Add(currentSpot);

        long upTurnScore = 0, downTurnScore = 0, leftTurnScore = 0, rightTurnScore = 0;
        switch (dir)
        {
            case '^': upTurnScore = 0000; leftTurnScore = 1000; downTurnScore = 2000; rightTurnScore = 1000; break;
            case 'V': upTurnScore = 2000; leftTurnScore = 1000; downTurnScore = 0000; rightTurnScore = 1000; break;
            case '<': upTurnScore = 1000; leftTurnScore = 0000; downTurnScore = 1000; rightTurnScore = 2000; break;
            case '>': upTurnScore = 1000; leftTurnScore = 2000; downTurnScore = 1000; rightTurnScore = 0000; break;
        }

        // Enqueue each turn
        queue.Enqueue((x - 1, y, '^'), score + 1 + upTurnScore);
        queue.Enqueue((x + 1, y, 'V'), score + 1 + downTurnScore);
        queue.Enqueue((x, y - 1, '<'), score + 1 + leftTurnScore);
        queue.Enqueue((x, y + 1, '>'), score + 1 + rightTurnScore);
    }

    return -1;
}

Admittedly I got stuck on this for about 15 minutes because it turns out I was starting facing < when I should have been facing >. Whoops!


Okay, this one doesn't seem too bad for a part 2! I already did a priority queue for this for part 1 to find the score, so after a few false starts here's one needs to be done for part 2:

  • Do Part 1 to get the best score
  • Do depth-first search, pruning branches with a greater score than the best (basically, stack instead of queue)
  • Change 'Already Seen' to include direction
  • Keep track of the paths in the queue
  • Modify the end condition to mark spots in the path along a best route
  • If the current queue priority is higher than an already found best path, break
  • Count marked spots

There were a lot of false starts to figure all of that out, including a few near-infinite loops, but it runs for now!

private void GetMazePaths(List<List<char>> maze)
{
    var stack = new Stack<(int, int, char, ImmutableList<(int, int)>, long)>();
    var (startX, startY) = Utils.Find2D(maze, 'S');
    var seen = new Dictionary<(int, int, char), long>();
    stack.Push((startX, startY, '>', ImmutableList.Create<(int, int)>(), 0));

    while (stack.Count > 0)
    {
        var (x, y, dir, path, score) = stack.Pop();
        if (maze[x][y] == '#') continue;
        if (score > bestScore) continue;
        if (maze[x][y] == 'E')
        {
            foreach (var tile in path) bestPaths.Add(tile);
            bestPaths.Add((x, y));
            continue;
        }

        if (seen.TryGetValue((x, y, dir), out var seenScore))
        {
            if (score > seenScore) continue;
        }
        seen[(x, y, dir)] = score;

        long upTurnScore = 0, downTurnScore = 0, leftTurnScore = 0, rightTurnScore = 0;
        switch (dir)
        {
            case '^': upTurnScore = 0000; leftTurnScore = 1000; downTurnScore = 2000; rightTurnScore = 1000; break;
            case 'V': upTurnScore = 2000; leftTurnScore = 1000; downTurnScore = 0000; rightTurnScore = 1000; break;
            case '<': upTurnScore = 1000; leftTurnScore = 0000; downTurnScore = 1000; rightTurnScore = 2000; break;
            case '>': upTurnScore = 1000; leftTurnScore = 2000; downTurnScore = 1000; rightTurnScore = 0000; break;
        }

        // Enqueue each turn
        var newPath = path.Add((x, y));
        stack.Push((x - 1, y, '^', newPath, score + 1 + upTurnScore));
        stack.Push((x + 1, y, 'V', newPath, score + 1 + downTurnScore));
        stack.Push((x, y - 1, '<', newPath, score + 1 + leftTurnScore));
        stack.Push((x, y + 1, '>', newPath, score + 1 + rightTurnScore));
    }
}

Right now this runs just under 9 seconds on the input. With some more effort I could probably bring down the time even more, but this is more than adequate for now.


Time taken: 2 hours

My solutions for today's puzzles