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: 46 tulip 23 marsh 58 clover 31 birch. How many steps are needed to complete the rearrangement of the above input?

Question

Accepted Answer

3. The numbers in ascending order are 23, 31, 46, 58. Step 1: 46 tulip marsh 58 clover 31 birch 23 — the line still opens with 46, a number, so the machine goes on. Step 2: 46 tulip marsh 58 clover birch 23 31 — still opening with 46. Step 3: tulip marsh 58 clover birch 23 31 46 — the line now opens with tulip, a word, so the machine halts here and 58 is never shifted at all. Three steps. Ignoring the stopping rule and shifting all four numbers gives four; counting the words gives five; and two comes from checking the leftmost element before the step rather than after it.

Step-by-Step Solution

Master this topic in 30 minutes a day.

More Input-Output practice