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.