On Indian Railways, a train can show "waiting list" for days and still leave with empty berths. People cancel late, don't turn up, or book only part of the route. Once the railway prepares the reservation chart , the berth-level picture is public, but it's spread across dozens of coaches and station pairs. Almost nobody can use it by hand.

I built GapSeat to answer one question: is there a berth I can use between my two stations? And if no single berth covers the trip, what's the fewest number of berth changes that does? This post is about the model and the search behind that second answer, which I call seat hopping.

The data: a berth is a list of segments

After the chart is prepared, each berth comes with segments along the train's route: booked from station A to station D, vacant from D to F, booked again from F onwards, and so on.…