A word-and-number arrangement machine, when given an input line of words and numbers, rearranges it in steps. In each step the smallest number that has not already been shifted is taken out and placed at the extreme right end of the line, every other element keeping its relative position. The machine does not always shift every number: it stops as soon as a step produces a line whose leftmost element is a word, and if that never happens it stops when the last number has been shifted. Input: 91 anchor 48 birch 27 cedar 63 dogwood 35. At which step of the above arrangement does the line "91 anchor birch cedar 63 dogwood 27 35 48" appear?

Question

Accepted Answer

Step 3. Ascending order: 27, 35, 48, 63, 91. Step 1: 91 anchor 48 birch cedar 63 dogwood 35 27. Step 2: 91 anchor 48 birch cedar 63 dogwood 27 35. Step 3: 91 anchor birch cedar 63 dogwood 27 35 48 — the line asked about. Because 91 is the largest number it stays at the head until the very end, so the stopping rule never bites early here: Step 4 is 91 anchor birch cedar dogwood 27 35 48 63 and Step 5, the last, is anchor birch cedar dogwood 27 35 48 63 91. Three numbers sit in the finished tail of the quoted line, which pins it to Step 3.

Step-by-Step Solution

Master this topic in 30 minutes a day.

More Input-Output practice