Interesting... cheating in a race, intentionally. I could probably just use another simple pathfinding algorithm, and do it on every pair walls that would make sense to. Actually, I think that might be the only realistic way of doing it.

After working on this for a bit though, I realized that the hard part is finding which "cheat" pathes are even valid. They specifically have to be something that the racers could do in order.

private IEnumerable<Cheat> MazeCheatPossibleLocations(List<List<char>> maze, IEnumerable<(int, int)> path)
{
    for (int x = 1; x < maze.Count - 1; x++)
    {
        for (int y = 1; y < maze[x].Count - 1; y++)
        {
            if (maze[x][y] == '#' && maze[x + 1][y] != '#') yield return new Cheat(x, y, x + 1, y);
            if (maze[x][y] == '#' && maze[x - 1][y] != '#') yield return new Cheat(x, y, x - 1, y);
            if (maze[x][y] == '#' && maze[x][y + 1] != '#') yield return new Cheat(x, y, x, y + 1);
            if (maze[x][y] == '#' && maze[x][y - 1] != '#') yield return new Cheat(x, y, x, y - 1);
        }
    }

    yield break;
}

This ends up giving far too many apparently 'invalid' cheats though... I need to figure something else out.

What if I start by finding the base path - from there I look at all "cheats" that have a path shorter than the base does from that point

private IEnumerable<Cheat> GetCheats(List<List<char>> maze, int x, int y)
{

    if (maze[x + 1][y] == '#')
    {
        if (Utils.IsInBounds(maze, x + 2, y) && maze[x + 2][y] == '.') yield return new Cheat(x + 1, y, x + 2, y);
        else if (Utils.IsInBounds(maze, x + 1, y + 1) && maze[x + 1][y + 1] == '.') yield return new Cheat(x + 1, y, x + 1, y + 1);
        else if (Utils.IsInBounds(maze, x + 1, y - 1) && maze[x + 1][y - 1] == '.') yield return new Cheat(x + 1, y, x + 1, y - 1);
    }
    // Repeat for all four directions...
}

private IEnumerable<(Cheat, int)> GetValidCheats(List<List<char>> baseMaze, IEnumerable<(int, int)> path, (int, int) end)
{
    var maze = Utils.Duplicate2DList(baseMaze);
    int progress = 0;
    int baseLength = path.Count();

    foreach (var (x, y) in path)
    {
        foreach (var cheat in GetCheats(maze, x, y))
        {
            var cheatedMaze = GetCheatedMaze(maze, cheat);
            var cheatPath = Utils.GetShortestPath(cheatedMaze, (x, y), end, x => x != '#' && x != 'X');

            if (cheatPath.Count() + progress < baseLength) yield return (cheat, cheatPath.Count() - 1 + progress);
        }

        maze[x][y] = 'X';
        progress++;
    }

    yield break;
}

It takes a while to run (about a minute and a half) but it gets the right answer when sorted properly.

Ooookay, now I think I realized my error for part one when I look at part 2 now. Honestly, a path should consist of 3 parts:

• A valid normal path up to N spots long
• A path ignoring walls up to C spots away
• The remaining path to E

I'm actually wondering if I might have a better shot by doing this backwards.

• Label each spot by it's (non-cheating) distance from the end
• Going backwards, find every spot that could be cheated to and check the distances

A lot less pathfinding this way; more like path validating.

private IEnumerable<int> GetCheatDistances(int cheatTime)
{
    int baseDistance = 0;
    int targetDistance = basePath.Count();
    foreach (var (x, y) in basePath.Reverse())
    {
        foreach (var warp in GetWarps(x, y, cheatTime).Where(w => IsWarpValid(w)))
        {
            var newDistance = baseDistance + warp.dist + distances[(warp.x, warp.y)];
            if (newDistance < targetDistance) yield return newDistance;
        }
        baseDistance++;
    }

    yield break;
}

private IEnumerable<Warp> GetWarps(int x, int y, int maxTime)
{
    for (int i = 0; i <= maxTime; i++)
    {
        for (int j = 0; j < i; j++)
        {
            int k = i - j;
            yield return new Warp { x = x + j, y = y + k, dist = i };
            yield return new Warp { x = x - k, y = y + j, dist = i };
            yield return new Warp { x = x - j, y = y - k, dist = i };
            yield return new Warp { x = x + k, y = y - j, dist = i };
        }
    }

    yield break;
}

private bool IsWarpValid(Warp warp)
{
    return Utils.IsInBounds(baseMaze, warp.x, warp.y) && baseMaze[warp.x][warp.y] == '.';
}

And done! Rather quickly too! Retrofitting it to my Part 1 answer, and it crunches through it in 20ms!

Sometimes you just need something to twist the problem in your brain into something simpler to solve.