Stations Pathfinder

The objective is not distance

The acceptance criterion is the turn count. In main.go, one variable holds the objective:

var leastTurns int = math.MaxInt32
...
if turnsCount1 < leastTurns {
    bestMoves = moves1
    leastTurns = turnsCount1
}

The final objective is turn count, although path length is one term in the ranking heuristic. Routes of equal length can still take different numbers of turns because of contention at intermediate stations.

What a turn actually is

One tick of a global clock. In each turn, every train may traverse at most one track, and:

• a track may carry only one train per turn
• a station may hold only one train
• the start station can always be left, and the destination can always be entered

// Start station can always be left
if occupyingTrain, occupied := stationOccupancy[from]; occupied && occupyingTrain != trainID {
    return false
}
// End station can always be entered
if to == endStation {
    return true
}

That last pair of exceptions is why the problem is interesting: a train is never stuck at its origin, and never locked out of its destination.

Not Dijkstra

The obvious assumption is wrong. There is no shortest-path search here at all. The algorithm enumerates every simple path by depth-first search with backtracking:

for neighbor := range net.Connections[current] {
    if !visited[neighbor] {
        dfs(net, neighbor, end, visited, append(path, neighbor), allPaths, maxDepth)
    }
}
visited[current] = false   // unmark on the way out

Then it ranks them. There is a textbook container/heap min-heap in the same file, fully implemented with Len, Less, Swap, Push and Pop. It is dead code. It appears nowhere except its own definition.

The search enumerates candidates up to its depth limit and ranks them with heuristics rather than proving a globally optimal schedule. Depth is capped at 100 and maps above 10,000 stations are rejected, but a dense graph can still produce an impractically large number of simple paths within those bounds.

The heuristic predicts contention, not length

score := 2*pathLength +
    (sharedStationScore / float64(numTrains)) +
    float64(bottleneckPenalty) / float64(numTrains)

Three terms, sorted ascending to minimise:

• 2 * len(path): longer is worse, and it dominates
• shared / numTrains: overlap with other candidate paths is a penalty, normalised by fleet size. Two trains cannot occupy the same station in the same turn, so candidates that share stations will contend
• bottleneck / numTrains: a station appearing on more paths than there are trains is a structural chokepoint

A worked example

The README's own example: jungle → desert, 10 trains, over a 14-station network. DFS finds exactly three simple paths:

farms appears on all three paths; jungle and desert are endpoints shared by definition. No station exceeds 10 occurrences, so the bottleneck term is zero throughout.

The six-station route loses despite being a viable shape, and the two five-station routes tie at 10.70. That is because wetlands and treetop each appear on only one path and so cannot differentiate them. Resolving a genuine tie is the simulator's job. The next section is about that.

Ten iterations, because randomness broke determinism

Go randomises map iteration order. The DFS visits neighbours in a different order on every run, greedy tie-breaks land differently, and identical input produced different turn counts. For fleets up to twenty trains, the program runs the search ten times and keeps the best simulated result; larger fleets use one run:

// Running pathfinding in loop to mitigate randomness, choosing the best solution
loops := 10
if numTrains > 20 {
    loops = 1
}

That loop is not a performance hack. It is an admission that the scoring proxy does not reliably predict turn count. So both ranking functions are simulated on every iteration, and the winner is whichever produced fewer turns.

Validation you can read at a glance

A -ae flag collects every error instead of exiting at the first, which is why the repository contains an errormap fixture annotated with the failure each line provokes:

Duplicate: "jungle" appears again
Duplicate coordinates: "4,4"
invalid!station,7,7
negative,-1,-1
jungle-jungle
nonexistent1-nonexistent2

Thirteen distinct checks in total, including unreachable endpoints, self-connections, dangling edges, stations at identical coordinates, and illegal characters in names.

Dependencies and search limits

The no-third-party-dependency claim is grounded in go.mod, which declares no external requirements, and the source imports, which are all standard-library or project-local packages. The standard-library imports are bufio, flag, fmt, math, os, path/filepath, sort, strconv and strings. Absence of go.sum alone would not prove the claim.

Repeated search is a heuristic workaround. It improves the chance of finding a better simulated schedule without establishing determinism, a runtime guarantee or global optimality.