Machine Input–Output

1Name the rule from two steps

A machine input-output question is a rewriting machine. It is given one line of tokens — words, numbers, or both — and it reprints that line after applying a hidden rule, then reprints it again. The paper shows you the input and two or three of those reprints, called Step I, Step II, Step III, and asks either what the rule is or what a later reprint looks like. We will keep one line for the whole topic: 87 mango 61 grape 24 apple. Every concept below is a different machine, or a different question, about that same mango line.

The first job is not to invent a clever rule from the input alone. The input is just the raw tokens. The rule lives in the difference between two consecutive reprints. Write the input on one row and Step I under it, token under token. Then write Step I and Step II the same way. Three things can have happened, and they name the three families this topic teaches. If some tokens have locked at an end and the rest kept their order, the machine is arranging. If every token slid one or two seats and the one that fell off one end reappeared at the other, the machine is shifting. If the words sat still and the numbers changed value — 87 becoming 88, or 87 becoming 78 — the machine is doing arithmetic on the numbers.

Comparing two consecutive steps names the rule; staring at the input does not. A solver who looks at 87 mango 61 grape 24 apple and invents 'smallest number to the left' has not used any evidence. On this particular line apple already sits at the right end, so Step I of word-left arrangement, mixed-left arrangement and a right circular shift of 1 are the same reprint: apple 87 mango 61 grape 24. One pair of rows is a candidate; the second pair is the confirmation. If the two pairs disagree, you do not have a rule yet.

Write the mango line, Step I and Step II as three rows, token under token. Step I is apple 87 mango 61 grape 24 under three different machines; Step II is what splits them. The family table in this concept lists those three Step IIs.

Order of attack

1. Stack two pairsWrite Input against Step I, then Step I against Step II, token under token. Do not name a rule from the input row alone.
2. Ask what movedDid values change (number-op), did every token slide and wrap (shift), or did one or two tokens lock at an end while the rest kept order (arrangement)?
3. Confirm on the second pairPredict Step II from the candidate rule and check it. On the mango line, Step I is a three-way tie; only Step II names the machine.

2Left / right arrangement

An arrangement machine does not change any token's value. It picks one token by a stated key — the alphabetically first remaining word, or the smallest remaining number — and moves that token to one end of the still-unarranged block. Everything it passes keeps the order it already had. The picked token is now locked: later steps do not touch it. The GIF on this card is that move on the mango line, with words locking at the left.

Run word-left on 87 mango 61 grape 24 apple. The remaining words in alphabetical order are apple, grape, mango. Step I pulls apple from the right end to slot 1; the rest keep order, so the reprint is apple 87 mango 61 grape 24. Step II pulls grape to slot 2: apple grape 87 mango 61 24. Step III pulls mango to slot 3: apple grape mango 87 61 24. That is the last step — the three words are locked and the numbers never moved relative to each other.

The rest of the line keeps its relative order. That is the whole method, and it is also the trap: a solver who sorts the leftover tokens, or who slides a word to the left end of the whole line after something is already locked, writes a line the machine never prints. The same pick-and-lock works at the other end (smallest number to the right) and is recorded in the end-choice table in this concept. One end, one key, one token per step.

How one step locks

1. Name the key and the endWhich token is selected (first remaining word, smallest remaining number) and which end of the unarranged block it locks at.
2. Pull, do not re-sortRemove that token from its current seat and sit it at the named end. Every token it passed stays in the order it already had.
3. Leave locked tokens aloneThe next step searches only among the still-unarranged tokens. Locked seats are not candidates and are not shuffled.

3Positional shift

A shift machine does not pick a winner. Every token moves the same number of seats, in the same direction, and the tokens that fall off one end reappear at the other in the order they fell. Values do not change. Nothing locks. The mango line under a circular left shift of 1 becomes mango 61 grape 24 apple 87, then 61 grape 24 apple 87 mango, then grape 24 apple 87 mango 61. The GIF on this card is those three slides, with 87 riding an arc from slot 1 to slot 6 on the first step.

Because nothing locks, the line is periodic. A left shift of 1 on six tokens reprints the input as Step VI. A block shift of the first two tokens to the end — 87 mango moving together — has period 3 on this line: Step I is 61 grape 24 apple 87 mango, Step II is 24 apple 87 mango 61 grape, Step III is the input again. Read the size of the block from how many tokens vanish from one end and appear, in the same order, at the other.

Nothing locks — the same tokens will cycle back. That is how you tell a shift from an arrangement after two steps: an arrangement grows a locked prefix (or suffix) that never moves again; a shift keeps every token travelling. It is also why a later-step question on a shift is modular arithmetic, not a sort: Step k of a left shift of 1 is the input rotated left by k \bmod n seats.

How to read a shift

1. Watch both endsTokens that leave the left end must appear, in the same order, at the right end (a left shift), or the reverse for a right shift.
2. Count the blockOne token wrapping is a shift of 1. Two tokens wrapping together, order preserved, is a block shift of 2.
3. Use the periodA shift of 1 on n tokens returns at Step n. Step k is the input rotated by k \bmod n, not a sorted line.

4Number and word mixed

Most PO-mains machines run two keys on one line. Words have their own queue (alphabetical). Numbers have their own queue (ascending or descending). The machine interleaves the two queues: the usual exam pattern, and the one we keep on the mango line, locks the next word on an odd step and the next number on an even step, both at the left of the still-unarranged block. Words and numbers are two separate queues, not one alphabet.

On 87 mango 61 grape 24 apple the word queue is apple, grape, mango and the number queue is 24, 61, 87. Mixed-left therefore prints: Step I apple 87 mango 61 grape 24 (word), Step II apple 24 87 mango 61 grape (number), Step III apple 24 grape 87 mango 61 (word), Step IV apple 24 grape 61 87 mango (number), Step V apple 24 grape 61 mango 87 (word). The finished line is the two queues zipped: word, number, word, number, word, number.

The other common mixed pattern locks a number at the left and a word at the right in the same step. That is still two queues; only the ends differ. What it is not is a single sort of all six tokens, and it is not word-left with the numbers treated as extra words. If you alphabetise 24 next to apple you have merged the queues, and the options are built to reward that merge.

Figure. Two queues zip into the finished mango line: words take the first, third and fifth seats; numbers take the second, fourth and sixth.

How the two queues zip

1. Split the queuesList remaining words alphabetically and remaining numbers in the stated numeric order. Never sort the two lists together.
2. Read the interleaveOdd step takes the next word; even step takes the next number (mixed-left). Or one step takes both, one to each end.
3. Pull from the current lineThe selected token leaves its present seat; leftovers keep their order. Locked seats from earlier steps stay put.

5Last step and Step k

Once the rule is named, a later-step question is not an invitation to reprint every line. The last step is the finished order, not one more grind of every line. For mixed-left on the mango line the finished order is the zipped queues apple 24 grape 61 mango 87. That line first appears as Step V; Step VI would only reprint it. Write the finished line from the queues and stop.

A named earlier step is almost as cheap. After k mixed-left placements the first k tokens of the finished line are already locked, and every token that is not among those k is still sitting in its original relative order. Step III of the mango line is therefore apple 24 grape — the first three of the finished line — followed by the leftovers 87, mango, 61 in input order: apple 24 grape 87 mango 61. That is the leftover rule, and it is how you answer Step IV or Step V without writing Step I.

The same shortcut works for a one-end arrangement: word-left's finished line is apple grape mango 87 61 24, so its Step II is apple grape plus leftovers 87, mango, 61, 24. It does not work for a shift — a shift has no finished line, only a rotation — which is why naming the family in the first concept is not optional bookkeeping. If the options offer both the finished mixed line and the word-then-number merge apple grape mango 24 61 87, the merge is the trap, not a shortcut.

Take the finished mixed line apple 24 grape 61 mango 87, keep the first k tokens, and append every leftover token in the order it had on the input. Step III keeps apple 24 grape and appends 87 mango 61.

Jump, do not grind

1. Write the finished lineZip the two queues (or lock every selected token at the named end). That string is the last step.
2. Cut at kStep k is the first k tokens of that finished line, then every leftover token in its original input order.
3. Refuse a shift shortcutIf the machine was a shift, rotate by k \bmod n instead. There is no sorted last step to write.