The Historians are quite pixelated again. This time, a massive, black building looms over you - you're right outside the CPU!

While The Historians get to work, a nearby program sees that you're idle and challenges you to a race. Apparently, you've arrived just in time for the frequently-held race condition festival!

Visit the website for the full story and full puzzle description.

The problem included a small but crucial hint: there is only a single path from the start to the end. Moreover, there are no dead ends in the input; it's just a single, continuous trace.

The definition of cheating was super hard to understand. I have to admit that instead, I used my intuition and used a more simple definition: in cheat mode you can step to any cell within the distance of 2 (or 20 for the second part). This really worked.

I created a function that returns the points of the track in finish to start order. This way, the index of an item in the array corresponds to its distance to the finish line.

Then, I go over the path. For each position, the number of possible cheats is calculated by checking what happens if we are trying to make a shortcut to any other positions around.

There are a number of cases to consider:

• the target position is too far away. This happens when its Manhattan distance is greater than the allowed cheat limit
• the target is within range, but actually further away from the finish than we are (the saving is negative).
• the target is within range, closer to the finish, but the saving is still less than 100
• the target is within range, and the saving is at least 100

We need to determine the number of good cheats for each position add them up. I used Parallel LINQ here, as the regular sequential one took significantly more time.

namespace AdventOfCode.Y2024.Day20;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

[ProblemName("Race Condition")]
class Solution : Solver {

    public object PartOne(string input) => Solve(input, 2);
    public object PartTwo(string input) => Solve(input, 20);

    int Solve(string input, int cheat) {
        var path = GetPath(input);
        var indices = Enumerable.Range(0, path.Length).ToArray();

        // sum up the worthy cheats for each index along the path
        var cheatsFromI = (int i) => (
            from j in indices[0..i]
                let dist = Manhattan(path[i], path[j])
                let saving = i - (j + dist)
            where dist <= cheat && saving >= 100
            select 1
        ).Sum();

        // parallel is gold today, it gives us an 3-4x boost
        return indices.AsParallel().Select(cheatsFromI).Sum();
    }

    int Manhattan(Complex a, Complex b) =>
        (int)(Math.Abs(a.Imaginary - b.Imaginary) + Math.Abs(a.Real - b.Real));

    // Follow the path from finish to start, supposed that there is a single track in the input.
    // The index of a position in the returned array equals to its distance from the finish
    Complex[] GetPath(string input) {
        var lines = input.Split("\n");
        var map = (
            from y in Enumerable.Range(0, lines.Length)
            from x in Enumerable.Range(0, lines[0].Length)
            select new KeyValuePair<Complex, char>(x + y * Complex.ImaginaryOne, lines[y][x])
        ).ToDictionary();

        Complex[] dirs = [-1, 1, Complex.ImaginaryOne, -Complex.ImaginaryOne];

        var start = map.Keys.Single(k => map[k] == 'S');
        var goal = map.Keys.Single(k => map[k] == 'E');

        var (prev, cur) = ((Complex?)null, goal);
        var res = new List<Complex> { cur };

        while (cur != start) {
            var dir = dirs.Single(dir => map[cur + dir] != '#' && cur + dir != prev);
            (prev, cur) = (cur, cur + dir);
            res.Add(cur);
        }
        return res.ToArray();
    }
}

Please ☆ my repo if you like it!