1. Predict, then shunt
Goal: put the wagons in ascending order, left to right. Each ↔ button swaps only the two wagons beside it. This is a number puzzle, not a simulation of real railway operations.
Inspect all out-of-order pairs
A long train may wrap onto a second line on a small screen. Read left to right, then continue on the next line. Every swap button names its positions for screen readers.
2. Why the minimum is not a guess
An out-of-order pair (also called an inversion) is a larger number anywhere before a smaller number. In 3, 1, 2 there are two: 3 before 1 and 3 before 2. The numbers do not have to be neighbours.
Swapping neighbours changes the order of exactly that pair. If the left number was bigger, the inversion count falls by one; otherwise it rises by one. Every inversion must disappear to finish sorting.
So the starting inversion count is a lower bound on the swaps. Always swapping a bigger left neighbour with a smaller right neighbour removes one each time, reaching that bound exactly.
Turn the idea into an algorithm
- Look for neighbouring numbers with the bigger one on the left.
- Swap them.
- Repeat until there are no such neighbours. The whole train is now sorted.
Scanning left to right repeatedly and swapping out-of-order neighbours is a bubble-sort strategy. Comparisons and swaps are different: you may compare an already ordered pair without swapping it. This lab counts swaps, not comparisons.
3. Explain it to someone else
- Why can one adjacent swap remove only one inversion?
- Can the backwards train be sorted with fewer swaps than its inversion count?
- What changes if you may swap any two wagons, not just neighbours? Our minimum proof would no longer apply.
No accounts, saved scores or input uploads. Reloading starts over. Undo removes a move from your current attempt; it is a practice tool, not a competition.