Input-Output

Here the line holds words and numbers together. The machine treats them as two separate lists: the words have their own order (A to Z) and the numbers have their own order (largest first or smallest first). A number never enters the word list and a word never enters the number list. Almost every question of this type is one of two forms, and the last step or the question's own sentence tells you which.

Form 1: the alternating line (the commonest). The final line runs number, word, number, word ... (or word, number, word, number ...). In each step one item is lifted to the next free slot from the left, in this pattern. All other items keep their old order.

[[fig:0]]

In the picture the target is built first: the largest number 62, the alphabetically first word elm, the next number 34, then oak, 17 and rat. Step 1 lifts 62 to the front, Step 2 lifts elm to the second slot, and so on. If one list is longer, its extra items stay together at the end in their order. When the target is complete the machine stops, and the next step shows the same line again.

Form 2: two lanes. Words are collected from the left end and numbers from the right end in the same step, and the two lanes grow towards each other.

[[fig:1]]

The final line is all the words in order, then all the numbers in order. Two items can move in one step, so never count steps as items ÷ 2. An item already in its slot is skipped, and the middle part falls into place by itself.

Method. (1) From the question or the last step, find which kind comes first and what order each kind follows. (2) Write the target line. (3) Place the target items one by one; an item already sitting in its slot costs no step.

Write the target first. Each step puts the next target item in its slot; the untouched items keep their old order.

This is the base machine of the whole chapter, so learn it well. In every step one number is lifted and put in its final slot. The numbers it jumps over slide one place; all others keep their old order. The exam prints two or three steps, or one line of rule, and asks for a later step, the number at some position, or the count of steps.

Form 1: smallest first, from the left. After Step k, the first k slots hold the k smallest numbers in ascending order. Input 48 15 62 30 21 becomes 15 48 62 30 21, then 15 21 48 62 30, then 15 21 30 48 62. That is three steps, not four, because 48 and 62 were already in order at the end.

[[fig:0]]

Form 2: other ends and orders. The same machine can take the largest first, or fill from the right.

[[fig:1]]

A one-line version is also asked: "in the first step the largest number moves to the last place". Only that number moves. 2 5 1 becomes 2 1 5, not 1 2 5.

Form 3: alternating. Slot 1 takes the smallest, slot 2 the largest of the rest, slot 3 the next smallest, and so on.

[[fig:2]]

Why the other part looks untidy. Only one number moves in a step, so the numbers not yet touched keep the order they had in the Input. They are sorted only when their turn comes. This one idea gives every option-elimination trick of this type: an option whose untouched part is already sorted is wrong.

Step k = the first k numbers of the target, then the untouched numbers in their old order. A number already in its slot costs no step.

This is the same lift-and-insert machine as Type 2. Only the items change: they are words, letters, or a mixture of kinds. So the whole skill lies in writing the correct target line; after that you place its items one by one.

Words. Three targets are common: alphabetical (A to Z), reverse alphabetical (Z to A), and by length (fewer letters first; for equal length, alphabetical). Compare two words letter by letter from the left; the first different letter decides.

[[fig:0]]

'over' comes before 'owl' because V comes before W. 'pen' comes before 'pencil' because a word that ends first comes first. Never compare only the first letter: sun, sea, sky and star all begin with S.

Letters in two groups. The target has a vowel group and a consonant group, each with its own direction, for example vowels A to Z and then consonants Z to A. Split the Input, sort each group in its own direction, and join the groups in the stated order.

[[fig:1]]

Mixed kinds [New Pattern]. Numbers, words and symbols such as # @ & come together, and the question gives a priority among the kinds, for example 'symbols, then numbers, then words'. Write the target kind by kind. Symbols have no order of their own, so they keep the order in which they appear in the Input.

[[fig:2]]

For all three forms the step concept is the same: one item moves per step, the untouched items keep their old order, and an item already in its slot costs no step.

Target first: sort each kind or group by its own order, join them in the stated priority, then place one item per step.

In a swap machine nothing slides. The chosen item and the item sitting in the target slot simply exchange places, and every other item stays exactly where it is. Compare with Type 2: take 5 9 2 7 4 and bring the smallest number 2 to the front. Lifting gives 2 5 9 7 4, because 5 and 9 slide. Swapping gives 2 9 5 7 4, because only 2 and 5 trade places.

[[fig:0]]

In the picture the red tile is the chosen number, and the blue tile is the item pushed out of its slot; it lands exactly where the red tile came from.

How to recognise a swap. Look at Step 1. If the displaced item has landed exactly where the chosen item came from and nobody else moved, it is a swap. If the items in between slid by one place, it is a lift. Some questions use the word 'swap' or 'exchange'; others show only the steps, so check.

A swap machine usually needs fewer steps than a lift machine on the same line, because a swap can fix one item and improve another. In the picture it finishes 2 3 5 6 8 9 in 3 steps, whereas lifting needs 4. A swap can also push out an item that was already in place, so rewrite the whole line after every swap.

Centre placement. Here the sorted part starts from the middle slot and grows outwards, for example for 7 slots the order of slots may be 4th, 5th, 3rd, 6th, 2nd, 7th, 1st. The statement gives the order of slots, and the result looks like a valley: small in the middle, large at the ends. Mostly it is a swap machine, so each chosen number trades places with whatever sits in its target slot.

[[fig:1]]

Read the slot order, the side that comes next (right or left), and 'smallest' or 'largest' from the question; they change from one question to the next.

Swapping trades two items; never slide the items in between. In centre placement, read the slot order from the question.

In these machines the numbers do not move about; they are changed by arithmetic. The length of the new line tells you which machine it is.

Each-number machine. Every number gets the same operation in a step (add 4, multiply by 3, square, digit sum, product of digits). Each step may have its own operation. Each number makes its own journey: 58 gives digit sum 13, then square 169, then digit sum 16. Work digit by digit, and remember that 13 or 169 is a multi-digit number when the next step arrives.

[[fig:0]]

Sometimes the steps are shown for one Input and asked for another. Find the operation on the first number, test it on the second, and only then apply it to the new line.

Adjacent-pair machine. Each new number is built from two neighbours: their sum, positive difference, product, sum of squares or half of the sum. n numbers make n − 1 pairs, so the line is one shorter after every step.

[[fig:1]]

Letter and digit machine. In every step each letter moves forward by a fixed number of places and each digit changes by a fixed amount. After n steps they have moved n times as much, so you can jump straight to the step asked, provided no letter passes Z, no digit leaves 0 to 9, and the digit change does not depend on odd or even.

[[fig:2]]

Same length: each-number. One shorter: adjacent pairs. After n steps: n times the shift. Every step has its own operation.

Position-pattern machine. This machine does not look at what the items are. It follows one position map, the same in every step: 'the item in place 3 goes to place 1, the item in place 1 goes to place 2' and so on. So the same map works for any new Input. Step I is built by reading the old line in the order 3rd, 1st, 2nd, 5th, 4th.

[[fig:0]]

Because the same map repeats, the line must return to the Input after some steps. That number is the period. Three items in a cycle give ABC, BCA, CAB, ABC again: period 3.

[[fig:1]]

When several cycles run together, the period is the lcm of the cycle lengths: a 3-cycle with a 2-cycle gives lcm(3, 2) = 6. A far step is then easy. Divide the step number by the period and use only the remainder. With period 6, Step XIV is Step II, because 14 = 12 + 2. A remainder of 0 means the Input itself. Always confirm the map on Step II, and apply it to positions, not to the letters you saw in the example.

Matrix (box) input [New Pattern]. The Input is a grid. A step says 'the numbers in each column are arranged in ascending order from top to bottom', or the same for rows. Do it for every column (or row) and rewrite the whole grid; the next step works on the new grid, not on the original. Then read the asked cells: the main diagonal runs from top-left to bottom-right, the other diagonal from top-right to bottom-left, and the centre of a 3 × 3 grid is its middle cell.

[[fig:2]]

Position map, then cycles, then period (lcm), then remainder. For a grid: one pass per step, rewrite the grid, read the asked cells last.

In a reverse question the machine is not run forwards. You are given a later step and asked for the Input (or for where an item came from). Before you start, ask one question: can the machine be undone exactly?

Invertible machines. If each step can be reversed exactly (add 5 can be undone by subtracting 5, double can be undone by halving, letters moved +2 can be moved −2), you simply undo the steps, last step first.

[[fig:0]]

In the picture, Step II is 17 29 9 41. Undo the last operation (subtract 5), then undo the first (halve), and the Input appears. Always check by running the machine forward once.

Non-invertible machines. A lift-and-insert machine cannot be undone by reading backwards. When the number 14 was lifted to the front, it could have come from the 2nd place, the 3rd place, or any other place, and the line after the step looks the same. So two different Inputs may produce one and the same step. In that case the correct answer is "cannot be determined".

How to handle such a question? Take each candidate input from the options and run it forward by the machine. If exactly one option gives the shown step, that is the answer. If two options give it, the answer is "cannot be determined". If the options contain no such choice, trust your forward runs.

[[fig:1]]

The picture shows two candidate Inputs that both lead to the same Step II. So the Input is not fixed.

Invertible: undo the last step first. Lift-and-insert: test every option forward; if two fit, the answer is "cannot be determined".