A word-and-number arrangement machine, when given an input line of words and numbers, rearranges it in steps. In each step the smallest perfect square among the numbers not already shifted is taken out and placed at the extreme left end of the line. Every other element keeps its relative position. Numbers that are not perfect squares are never shifted, and the machine stops as soon as no perfect square is left to shift. Input: raven 45 sable 25 thorn 72 willow 49 vixen 16. Which of the following is the last step of the above arrangement?

Question

Accepted Answer

49 25 16 raven 45 sable thorn 72 willow vixen. The perfect squares are 16, 25 and 49; 45 and 72 are not squares and never move. Step 1: 16 raven 45 sable 25 thorn 72 willow 49 vixen. Step 2: 25 16 raven 45 sable thorn 72 willow 49 vixen. Step 3: 49 25 16 raven 45 sable thorn 72 willow vixen, and the machine halts. Because each square is dropped at the extreme left, the block reads 49 25 16 rather than 16 25 49 — writing it the other way round records the order of the moves. Note also that 45 and 72 stay exactly where they are; they are not swept to the right end.

Step-by-Step Solution

Master this topic in 30 minutes a day.

More Input-Output practice