Visit the Advent of Code website for the problem statement here.

Today's problem looked frightening first, because it's asking for the longest path between two points of a map. Shortest path is a no brainer with Dijkstra or whatever graph search, but I don't know about an efficient way to calculate the longest one. I have a feeling that it is somehow related to the Hamiltonian path which is NP-complete, so there might not even exists a super efficient algorithm to solve today's problem in the generic case.

But this is a puzzle, so let's get to it. I decided to convert the problem from map traversal to graph traversal first. Created nodes from the crossroads of the map (those tiles that connect 3 or more "." cells). Also assigned a node to the entry and one to the exit.

Two nodes become connected if there is a road between them. That is, they are reachable following the path in the map without visiting other crossroads in between.

This reduced the problem quite a bit. In my case it went down to about 30 nodes and 120 edges for Part 2. Part 1 is even smaller with 60 edges or so.

This graph is small enough to solve it using dynamic programming with a cache. Since we have just 30+ nodes, I represented them as powers of 2 and a set of these became a bitset stored in a long.

namespace AdventOfCode.Y2023.Day23;

using System;
using System.Collections.Generic;
using System.Numerics;
using System.Linq;
using Map = System.Collections.Generic.Dictionary<System.Numerics.Complex, char>;
using Node = long;
record Edge(Node start, Node end, int distance);

[ProblemName("A Long Walk")]
class Solution : Solver {

    // Instead of dealing with the 'map' tiles directly, we convert it to a graph.
    // Nodes: the entry tile, the exit and the crossroad tiles.
    // Edges: two nodes are connected if there is a direct path between them that 
    //        doesn't contain crossroads.
    // This reduces a problem to ~30 nodes and 120 edges for the Part 2 case
    // which can be solved using a dynamic programming approach.

    static readonly Complex Up = -Complex.ImaginaryOne;
    static readonly Complex Down = Complex.ImaginaryOne;
    static readonly Complex Left = -1;
    static readonly Complex Right = 1;
    static readonly Complex[] Dirs = [Up, Down, Left, Right];

    Dictionary<char, Complex[]> exits = new() {
        ['<'] = [Left],
        ['>'] = [Right],
        ['^'] = [Up],
        ['v'] = [Down],
        ['.'] = Dirs,
        ['#'] = []
    };

    public object PartOne(string input) => Solve(input);
    public object PartTwo(string input) => Solve(RemoveSlopes(input));

    string RemoveSlopes(string st) =>
        string.Join("", st.Select(ch => ">v<^".Contains(ch) ? '.' : ch));

    int Solve(string input) {
        var (nodes, edges) = MakeGraph(input);
        var (start, goal) = (nodes.First(), nodes.Last()); 

        // Dynamic programming using a cache, 'visited' is a bitset of 'nodes'.
        var cache = new Dictionary<(Node, long), int>();
        int LongestPath(Node node, long visited) {
            if (node == goal) {
                return 0;
            } else if ((visited & node) != 0) {
                return int.MinValue; // small enough to represent '-infinity'
            }
            var key = (node, visited);
            if (!cache.ContainsKey(key)) {
                cache[key] = edges
                    .Where(e => e.start == node)
                    .Select(e => e.distance + LongestPath(e.end, visited | node))
                    .Max();
            }
            return cache[key];
        }
        return LongestPath(start, 0); 
    }

    (Node[], Edge[]) MakeGraph(string input) {
        var map = ParseMap(input);

        // row-major order: 'entry' node comes first and 'exit' is last
        var nodePos = (
            from pos in map.Keys
            orderby pos.Imaginary, pos.Real
            where IsFree(map, pos) && !IsRoad(map, pos)
            select pos
        ).ToArray();

        var nodes = (
            from i in Enumerable.Range(0, nodePos.Length) select 1L << i
        ).ToArray();

        var edges = (
            from i in Enumerable.Range(0, nodePos.Length)
            from j in Enumerable.Range(0, nodePos.Length)
            where i != j
            let distance = Distance(map, nodePos[i], nodePos[j])
            where distance > 0
            select new Edge(nodes[i], nodes[j], distance)
        ).ToArray();

        return (nodes, edges);
    }

    // Length of the road between two crossroads; -1 if not neighbours
    int Distance(Map map, Complex crossroadA, Complex crossroadB) {
        var q = new Queue<(Complex, int)>();
        q.Enqueue((crossroadA, 0));

        var visited = new HashSet<Complex> { crossroadA };
        while (q.Any()) {
            var (pos, dist) = q.Dequeue();
            foreach (var dir in exits[map[pos]]) {
                var posT = pos + dir;
                if (posT == crossroadB) {
                    return dist + 1;
                }  else if (IsRoad(map, posT) && !visited.Contains(posT)) {
                    visited.Add(posT);
                    q.Enqueue((posT, dist + 1));
                }
            }
        }
        return -1;
    }

    bool IsFree(Map map, Complex p) =>
        map.ContainsKey(p) && map[p] != '#';

    bool IsRoad(Map map, Complex p) => 
        IsFree(map, p) && Dirs.Count(d => IsFree(map, p + d)) == 2;

    Map ParseMap(string input) {
        var lines = input.Split('\n');
        return (
            from irow in Enumerable.Range(0, lines.Length)
            from icol in Enumerable.Range(0, lines[0].Length)
            let pos = new Complex(icol, irow)
            select new KeyValuePair<Complex, char>(pos, lines[irow][icol])
        ).ToDictionary();
    }
}

Please ☆ my repo if you like it!