Just a casual NP-hard problem

Problem
Code

You're given a map. Find the length of the longest path you can take without repeating any tiles. This is known as the longest path problem, and it's NP-hard, which, roughly, means there's no general fast solution to it.^[1]

Thankfully, we don't need a general solution, because the map is pretty specific. The start point, end point and 34 junctions are all connected by 1-tile-wide corridors. This means we can reduce the entire map to a graph! In part 1 it is directed (thanks to the one-ways on every junction), and in part 2 it is undirected.

In addition, thanks to the graph-ic nature of our map, all we need to do to avoid stepping on the same tile twice is not visiting the same node twice on our path.

Given all that, 36 total nodes is few enough that you can kinda just... solve the problem by brute force. The bulk of my code is reducing the map to a graph representation, but assuming we already have that, the solution is relatively simple:

// graph[i] = nodes reachable from node #i, as a pair of (target node index, steps)
// graph[0] = starting node
// ending node not in list
type Graph = Vec<Vec<(usize, usize)>>;

fn longest_to_end(input: &str, backwards: bool) -> Option<usize> {
    fn work(g: &Graph, from: usize, used: u64) -> Option<usize> {
        if from == g.len() {
            return Some(0);
        }

        let mut best = None;
        for &(next, steps) in &g[from] {
            if next == usize::MAX {
                return Some(steps);
            }
            if used & (1 << next) > 0 {
                continue;
            }

            best = best.max(work(g, next, used | (1 << next)).map(|n| n + steps));
        }

        best
    }

    let g = build_graph(input, backwards);
    work(&g, 0, 1)
}

I (recursively) try every path, always remembering which nodes I've already visited. Because of the small number of nodes, we can do this with a 64-bit bit mask: used. The ith least significant bit of used is treated as a bool saying whether the ith node has been visited already.

With these two optimizations (graph, bitmask), the running time of the solution is pretty reasonable.