This project solves a JetBrains compiler-style task where the goal is to determine which cargo types may be present on a train when it arrives at each station in a railway network.
Each station in the network:
- Unloads one cargo type when a train arrives
- Loads one cargo type before the train departs
Trains start from a given initial station with no cargo and may follow any valid route through the network.
Because multiple routes may reach the same station, different cargo combinations may arrive there.
The task is to compute, for every station, the set of cargo types that might be present upon arrival.
The railway network is modeled as a directed graph:
- Stations → nodes
- Tracks → directed edges
For every station we track:
IN[station]
which represents cargo types that may be on a train when it arrives.
Cargo sets are represented using a bitset (LongArray) for efficient union operations.
When processing a station:
OUT = (IN − unloadCargo) ∪ {loadCargo}
The resulting cargo state is then propagated to neighboring stations:
IN[next] = IN[next] ∪ OUT
The solution uses a worklist (queue-based) dataflow algorithm:
- Start from the initial station with an empty cargo set.
- Process stations from a queue.
- Apply unload/load transformation.
- Propagate the resulting cargo state to neighboring stations.
- If a station's arrival state changes, it is added back to the queue.
The algorithm runs until no states change (a fixpoint is reached).
Bitsets allow efficient cargo set operations even when the number of cargo types grows.
Vanja Sretenović