A rail yard’s freight trains
A rail yard keeps each freight train as a doubly linked list of cars, and its yard tool holds handles to the cars it works on: the lesson’s worklist, with cars for jobs. The cars come from the checker’s plumbing, which counts every link read (each step along the train) and every link write, so the checker can tell a correct operation that walks from one that relinks, however the code is written. Each level starts from the previous level’s finished code, so you can begin at any of them.
A teammate’s pull request adds two yard-tool functions. Before a train departs, one removes every car carrying a flagged load. During the day, the other runs the yardmaster’s shunting plan. QA reports that a train with two flagged tankers left with one still on it, and that a 600-step plan on a 1,000-car train takes far too long. You are reviewing the pull request.
A flagged car leaving with the train is a safety incident. A shunting plan whose every step walks the train costs time in proportion to the train’s length times the plan’s length.
Reproduce dropFlagged(loco → tanker → tanker2, ["tanker", "tanker2"]) should leave loco; today tanker2 stays. A three-step plan on a six-car train reads 23 links, most of them walking from the locomotive to find its cars; walking the train once for a handle to every car, it needs at most 18: six for the walk and four per step.
Acceptance criteria Dropping flagged cars removes every flagged car, wherever it is, including flagged cars next to each other and the locomotive itself. The shunting plan gives the order it describes, step by step, skipping a step whose cars are not in the train. When two cars share a number, a step means the first of them from the locomotive, as find does. The plan walks the train at most once, however many steps it has: for n cars and m steps, at most n + 4m link reads, one walk plus the few reads each move makes. Everything from the earlier levels still works. Notes Cases print the train walked from the locomotive (or its length and first cars), whether walking back agrees, and, for plans, whether the link reads stayed within the budget. The plumbing counts the links as before: every read of a car’s previous or next link is a link read (one step along the train), and every assignment to one is a link write, whether or not it changes the value. The train’s head and tail are not counted. A walk over n cars reads n links, whoever writes the loop. Keep the train’s fields and its methods’ names and signatures, and both functions’; the checker calls them.