3 The Computer Compares
By the end of this chapter, the computer takes its first look at the board. Press Step, and two neighboring pieces light up in amber while the computer compares them. If the left one belongs later, they swap. Press it again and again, and the computer works its way forward across the whole board, counting every comparison and every swap as it goes.
The game as it is at the end of this chapter. Click the game to play.
If your game and this chapter part ways, here is the chapter’s finished project. Open it and compare, or start Chapter 4 from it.
To open it, start Myth Engine, choose File › Open Project... and pick the downloaded file.
3.1 The Idea
The Village lies scattered on the board again. You put it back by hand in the last chapter, and it took a while. Your eyes did most of the work. You looked at the Preview, found a piece, and knew where it went.
The computer can’t do any of that. It never sees the picture. It reads Board Slots, the seating chart from Chapter 1, and nothing else.
So how can something that can’t see put a picture back? It asks one small question, over and over. It reads two neighboring slots and asks: does the left piece belong later than the right one? Each piece’s number is its home, so that’s a question about two numbers. Is the left number bigger?
Asking that question once is a comparison. When the answer is yes, the two pieces trade places, and the computer’s trade is called a swap. When it’s no, they stay where they are. Either way, the computer moves one slot along and asks again.
It’s the same trade your hands made in Chapter 2, with one rule added. Your exchanges could reach across the board. A swap only ever trades two neighbors.
Going along the board this way, from the first slot to the last, is a forward pass. Forward means reading order, left to right and row by row down. The board is one long line of 64 slots, folded into eight rows. So the pair that crosses the end of a row is the last slot of that row and the first slot of the next.
A forward pass does something you can watch. Picture a line of children, and each pair of neighbors swaps if the left one is taller. Once the line reaches the tallest child, that child wins every comparison after, and walks all the way to the end. The piece with the biggest number does the same. Piece 63 is the picture’s bottom-right corner, and one forward pass carries it home to the last slot.
The part of the board still to be sorted is the unsorted range. Today it’s the whole board, start to end. In Chapter 4, after every pass, it starts to shrink from one end or the other.
That’s where this chapter stops: one forward pass, the first half of the shake. The way back comes next.
3.2 The Plan
Here’s how the pieces work together. Read each line from left to right, and come back to them at the end, when every name is something you’ve built.
- The Step button, or Space -> Request Step sends
stepRequestedto Puzzle Rules. - The first
stepRequestedon a board -> Computer Sort calls Check Board Valid, which asks Count Piece Copies about every piece. - A sound board -> Compare Next Pair compares the first pair.
- Each later
stepRequested-> Compare Next Pair compares the pair one slot to the right of the last one. - Each comparison -> Compare Next Pair counts it, swaps the pair through Exchange Slots when the left piece is larger, and sends
pairCompared. - Each
pairCompared-> every Piece shows its piece, Pieces Home counts again, and every Outline paints its edge through Color Outline. - The pair reaches the end of the range -> the next Step only says the forward pass is done.
- An exchange, Reset or Shuffle -> Computer Sort switches back to Fresh and calls Clear Sort -> the counters go back to 0, the amber goes, and the next Step starts fresh.
3.3 Set Up
Chapter 3 adds one key, five Globals and two placements. There are no new pictures.
The Set up card follows these paragraphs, so read them first, and then work down the card from its top.
COMMANDS has one new key, Step, on Space. Press the space bar in the No Input Assigned row, and the row writes its name.
GLOBAL VARIABLES are five new values the computer keeps. Make them in Show Piece’s Globals card, using New Global…, as before. Two are counters, and they start at 0. $rangeStart and $rangeEnd mark the unsorted range, the first slot and the last. And $comparedSlot remembers the pair compared last. It starts at -1, which means no pair yet, the same way -1 meant no slot in Chapter 2.
PLACE THESE holds the Computer Counter and the Step button. Don’t place them yet, even though the card lists them here. Each is placed in its own part below, once the things it needs exist.
SpaceSave your project, and again at the end of each part.
3.4 New Words for the Board
First, the board learns to speak for the computer.
When the computer keeps a pair, the line at the foot of the screen says Kept. When it swaps them, it says Swapped. And under the Moves counter, smaller and gray, a second counter keeps the computer’s score.
Messages gains four rows. Two are the words you’ll see on every Step. The third is for a board the computer refuses, and the last is for the end of the pass.
Reset.Choose another piece.Picture complete.Swapped.Kept.This puzzle needs each home position exactly once.The forward pass is done. Step 03 adds the way back.That last row promises the way back, in “Step 03”. It’s the game’s own name for the next chapter. You’re in Chapter 3 of this book, and the way back is Chapter 4. Type the words as the card shows them.
Outline Colors gains one row too, compared, a warm amber.
#46615a#2579bc#f3d49c#e3b76dThe Computer Counter is a new Object, words like the Player Counter, with two live values. Between Comparisons and Swaps, its Text has three spaces, so the two counts stand a little apart.
Window / UIUIComparisons {$comparisons} Swaps {$swaps}12Medium#526478VectorPlace it at 815 and -756, under the Player Counter. Run the game. It reads Comparisons 0, then Swaps 0, and they’ll stay that way for a while.
3.6 A Board the Computer Can Trust
Before the computer reads a single pair, it checks the board.
You’ll never see this check do anything, because every board your game deals holds each piece exactly once. But the computer’s whole method rests on that. If one piece were missing and another in two slots, no amount of swapping would ever bring the picture home. So the first Step on every board asks the question first, and the computer refuses a board that fails it. The Challenge at the end of the chapter lets you watch it refuse one.
3.6.1 Count Piece Copies
Count Piece Copies answers one question: how many slots hold this piece? It’s given a pieceId. It starts its count at 0 and walks the board. A Repeat visits every slot, and an If asks whether the piece there is the one it’s looking for. When it is, the count goes up by 1.
Return hands this count back as one Number, which the caller reads as its answer’s value. On a sound board, it’s always 1.
This walk should feel familiar. It’s Count Pieces Home from Chapter 1, asking a different question at every slot.
Answers how many slots of the board hold one piece ID. On a sound board the answer is always 1.
- Name
copies- Value
0
$gridSize * $gridSizetimesdata('Board Slots', local.index, 'piece') == pieceId- Variable
copies- Operator
+=- Value
1
- Value
copies
3.6.2 Check Board Valid
Check Board Valid asks Count Piece Copies about every piece in turn. It begins sure of the board, with isValid true, and looks for a reason to change its mind. Then a Repeat runs once for each piece, and local.index is the piece’s number this time. It calls Count Piece Copies, names the answer found, and reads found.value. Any answer other than 1, and isValid turns false.
It never turns back to true, because one bad piece is enough.
Return hands back isValid. Computer Sort reads that Boolean answer’s value before trusting the board.
Answers whether the board holds every piece ID exactly once, so the computer can sort it. isValid is true when it does.
- Type
Boolean- Name
isValid- Value
true
$gridSize * $gridSizetimes- Action Name
found- pieceId
local.index
found.value != 1- Variable
isValid- Value
false
- Value
isValid
Nobody playing Picture Puzzle will see these two Functions at work. They’re how it trusts the board.
3.7 One Comparison
Now the computer’s one move. It’s the chapter’s one hard idea, so take it slowly.
3.7.1 Compare Next Pair
Compare Next Pair is one comparison, from start to finish. It’s given leftSlot, the left slot of the pair, and the right slot is the one after it, leftSlot + 1.
First it counts the comparison, adding 1 to $comparisons. Every comparison counts, whatever the answer.
Then it reads the two pieces from Board Slots and asks its question. Is the left piece’s number bigger than the right one’s? If so, the left piece belongs further along the board, and Compare Next Pair calls Exchange Slots, the cup-holding Function from Chapter 1, to trade the two. It adds 1 to $swaps and puts Swapped on the Message Line. If not, nothing moves, and the Message Line says Kept.
Last, whatever the answer was, it writes leftSlot into $comparedSlot and sends pairCompared to everyone who listens.
That last step does two jobs. The Outlines read $comparedSlot to know which pair to paint amber. And the next comparison reads it to know where to begin, one slot to the right. The game never keeps a separate marker for where the computer is. The pair it compared last is the place.
One comparison of the computer: it reads the pieces of a slot and the slot to its right, and swaps them when the left piece's ID is larger. It counts the comparison and any swap, and tells the board.
- Variable
$comparisons- Operator
+=- Value
1
data('Board Slots', leftSlot, 'piece') > data('Board Slots', leftSlot + 1, 'piece')- firstSlot
leftSlot- secondSlot
leftSlot + 1
- Variable
$swaps- Operator
+=- Value
1
- Variable
$message- Value
data('Messages', 'swapped', 'words')
- Variable
$message- Value
data('Messages', 'kept', 'words')
- Variable
$comparedSlot- Value
leftSlot
- Custom Event
pairCompared
Two pieces of Logic you already have learn the new message. Show Piece hears pairCompared, so the pictures of a swapped pair trade places on the board. Pieces Home hears it too, so the caption keeps count while the computer works.
Shows the picture frame of the piece that Board Slots puts in this Piece's slot. Make Board gives each Piece its slot in its Slot Number (0 is the top-left slot, counting right, then down).
Any Objectself.slotNumber- Frame
data('Board Slots', self.slotNumber.slot, 'piece')
- Frame
data('Board Slots', self.slotNumber.slot, 'piece')
- Frame
data('Board Slots', self.slotNumber.slot, 'piece')
- Frame
data('Board Slots', self.slotNumber.slot, 'piece')
Keeps $piecesHome, the count the Board Caption shows, equal to the number of pieces in their home slots.
Any ObjectEach piece is still on the board exactly once after a swap, because Exchange Slots is the only thing that ever moves one. Your hands, the shuffle and now the computer all trade through it.
3.8 The Amber Pair
Next, the board shows you which pair the computer is looking at.
3.8.1 Color Outline
Remember Show Outline’s coats of paint, from Chapter 2? First the normal color, then blue for the focus or a press, then gold for the selection, and the last coat wins. Those coats move now, into a Function called Color Outline, and they gain a fourth: amber, for the pair compared last.
Why move them? Because three different messages need the same painting now: a selection changes, a pair is compared, or the sort starts fresh. Rather than three copies of the coats, there’s one Function, called from three Events.
A Function has no self, so Color Outline is handed the Outline to paint, outline. It comes out as a Target. Its Compatibility Mode, two buttons, starts on Structural. Leave it there. Structural is what lets a Target carry a Required Component, the same as self. So give it Show Piece’s: press Add Required Component, and fill in Slot Number named slotNumber. That’s unlike Request Step’s puzzleRules, which is Nominal. Each Change Sprite Tint Property names outline in its Applies To, so the paint lands on that Outline.
Its first step copies the Outline’s slot into outlineSlot, which keeps the questions short.
The amber tests join with &&, meaning and. Has the computer compared a pair? Is this slot between that left slot and its neighbor? Every test must be true, or the amber coat stays off this slot’s edge. Type the card’s whole condition into the If.
Colors one Outline from what is shown on the board now: the keyboard focus and a pressed piece are blue, the selected piece is gold, the pair the computer compared last is amber, and every other Outline keeps the normal color.
slotNumberData StructureSlot Number- Name
outlineSlot- Value
0
- Variable
outlineSlot- Value
outline.slotNumber.slot
- Applies to
outline- Value
data('Outline Colors', 'normal', 'color')
outlineSlot == $focusSlot || outlineSlot == $pressedSlot- Applies to
outline- Value
data('Outline Colors', 'focus', 'color')
outlineSlot == $selectedSlot- Applies to
outline- Value
data('Outline Colors', 'selected', 'color')
$comparedSlot >= 0 && outlineSlot >= $comparedSlot && outlineSlot <= ($comparedSlot + 1)- Applies to
outline- Value
data('Outline Colors', 'compared', 'color')
3.8.2 Show Outline
Show Outline gets much shorter. Its old painting steps come out, and Color Outline goes in. Its outline box is a list, and Self is in it: pick Self, so each Outline hands over itself. It also gains two Events, pairCompared and sortCleared, each calling Color Outline the same way.
Colors this Outline whenever what it shows may have changed: the player's selection, focus or press, or the computer's compared pair.
Any Objectself.slotNumber- Value
data('Outline Colors', 'normal', 'color')
self.slotNumber.slot == $focusSlot || self.slotNumber.slot == $pressedSlot- Value
data('Outline Colors', 'focus', 'color')
self.slotNumber.slot == $selectedSlot- Value
data('Outline Colors', 'selected', 'color')
- outline
self
- outline
self
- outline
self
Nothing sends pairCompared yet, so nothing turns amber. One piece of Logic is left, and it’s the one that sends it.
3.9 The First Forward Pass
Last, the computer takes its turns.
3.9.1 Computer Sort
Computer Sort lives on Puzzle Rules, and it answers every Step. Its main Event is stepRequested, and like Player Exchange’s pieceChosen, it behaves in different ways at different times. So it has three Modes.
Fresh is where it starts. Before anything else, it has Check Board Valid look over the whole board. If the board is sound, the unsorted range becomes the whole board, the first pair is compared, and the Event switches to Forward Pass. If it isn’t, the Message Line says so, and nothing is compared.
Forward Pass answers every Step after that. It calls Compare Next Pair one slot to the right of the last pair, $comparedSlot + 1. Then its If looks at the pair it has compared. That pair’s left slot is in $comparedSlot now, so its right slot is $comparedSlot + 1. Is that the range’s last slot? If so, the pass has reached the end of the board, and the Event switches to Pass Done.
Pass Done only shows the passDone words, because the way back is Chapter 4’s.
Two more Events start the sort over. After Reset or Shuffle, boardArranged arrives, and after your own exchange, piecesExchanged does. Either way, the old comparisons no longer fit the board, so both switch stepRequested back to Fresh, then call Clear Sort.
Those Switch Modes pick the Event and the Mode from lists, as Player Exchange’s did. So build in the order you used for Player Exchange, and make Computer Sort’s Events and Modes first, with no Actions yet. They’re stepRequested, with Fresh, Forward Pass and Pass Done, then boardArranged and piecesExchanged. Attach it to Puzzle Rules. Then make Clear Sort, below. Then come back and fill in Computer Sort from its card, which comes after Clear Sort’s.
3.9.2 Clear Sort
Clear Sort wipes the slate. The pieces stay where they are, but the computer forgets the old board: its score and its place in the pass. Afterward it acts as if it had never seen this board. The next Step checks it and begins at the first slot.
One Function keeps all of that work together, ready for either message to call it. The one to notice is the last, sortCleared, because the Outlines are waiting for it to take the amber off.
Like Clear Selection, it has no Switch Mode. Computer Sort switches its own stepRequested back to Fresh, just before each call.
Starts the computer's sort fresh: the counters go back to 0, no pair is shown as compared, and the next Step checks the board and begins a new forward pass.
- Variable
$comparisons- Value
0
- Variable
$swaps- Value
0
- Variable
$comparedSlot- Value
-1
- Custom Event
sortCleared
Now fill in Computer Sort. Fresh tests boardCheck.value == true, the answer Check Board Valid returned.
The computer's cocktail shaker sort, one comparison per Step. The first Step on a board checks it and begins a forward pass from the first slot; each later Step compares the next pair to the right. This checkpoint stops when the first forward pass reaches the end of the board.
Any Object- Action Name
boardCheck
boardCheck.value == true- Variable
$rangeStart- Value
0
- Variable
$rangeEnd- Value
$gridSize * $gridSize - 1
- leftSlot
$rangeStart
- Event
On Step Requested- Mode
Forward Pass
- Variable
$message- Value
data('Messages', 'invalid', 'words')
- leftSlot
$comparedSlot + 1
($comparedSlot + 1) == $rangeEnd- Event
On Step Requested- Mode
Pass Done
- Variable
$message- Value
data('Messages', 'passDone', 'words')
- Event
On Step Requested- Mode
Fresh
- Event
On Step Requested- Mode
Fresh
Its Changes card shows Computer Sort in its place on Puzzle Rules, using its puzzleRules Shared Variable.
Make BoardMake Board DataPuzzle RulesPiece OutlinePieceRun the game, and press Step. Two pieces at the top-left of the board turn amber at their edges, and the bottom line says Kept. Press Space a few more times, and watch the amber pair walk to the right.
Watch for each of these.
- Under Moves 0: Comparisons 0, then Swaps 0, a little apart.
- Every edge starts dark green-gray, before you touch a piece or press a key. A press paints its edge blue, and a selection paints that same edge gold.
- Press Step. The first two slots, at the top-left, have amber edges. The bottom line says Kept, and the counter says Comparisons 1.
- Press Space. The amber pair moves one slot to the right, and it’s Kept again. The first twelve pairs are all in order.
- The 8th Step compares the last slot of the top row and the first slot of the second row. The two amber edges are at opposite sides of the board. That’s one pair, along the folded line.
- The 13th Step says Swapped, in the second row. A piece of leaves and pink flowers trades places with a piece of mountains and a sailboat. Swaps 1.
- Keep pressing. The leaves and flowers are the picture’s bottom-right corner, piece 63, and from here on every Step says Swapped. The piece rides to the right with each one, row after row.
- On the 15th Step, the caption above the board reads 1 / 64, because a piece the leafy corner passed has landed home.
- After the 63rd Step, the corner piece sits in the last slot, home. The counter says Comparisons 63, then Swaps 51, and the caption reads 5 / 64.
- Press Step once more. The bottom line says The forward pass is done. Step 03 adds the way back. The counters stay where they are.
- Press R. Both counters go back to 0, the amber is gone, and the next Step starts again at the top-left.
- Exchange two pieces with your hands. Moves goes up, and the computer’s counters go back to 0.
Request Step asks. Computer Sort decides which pair is next. Check Board Valid makes sure the board can be sorted, once, at the start. Compare Next Pair asks its one question, and swaps through Exchange Slots when the answer is yes. Every Piece, every Outline and the caption hear about it.
Underneath, there’s still only the seating chart. The computer never moves a picture and never looks at one. It compares two numbers, sometimes trades them, and moves along. Because it only trades neighbors, the biggest number it meets keeps winning, and it’s carried all the way to the end. That’s one forward pass.
3.10 If It Didn’t Work
This chapter has a lot of quiet machinery, so a slip can hide. That’s normal. Press Step, watch what the board does, and think it through.
Step does nothing at all, and the counters stay at 0? Perhaps the request never arrives. Check Request Step’s stepRequested, and the name in Computer Sort’s When bar, capital R and all. Look for Computer Sort on Puzzle Rules. If Space works but the button doesn’t, look at the Step button’s Command Variable, which should say Step.
The bottom line says This puzzle needs each home position exactly once, on an ordinary board? Then Check Board Valid is answering false. Check isValid’s Declare Variable, starting true. Look at Count Piece Copies’ Return, whose Value is copies. And look at the If in Check Board Valid, which turns isValid false on !=, not on ==.
Comparisons counts, but nothing ever swaps? Look at the If in Compare Next Pair, where the comparison is > and the left side reads leftSlot.
Swaps counts, but the pictures don’t change? Show Piece needs its fourth Event, pairCompared. If the pictures change but the caption doesn’t, Pieces Home needs the same Event.
No amber anywhere? Look for Show Outline’s pairCompared Event. Then look at Color Outline’s last If, and its joined tests. If amber shows on the wrong slots, check $comparedSlot + 1 in that condition.
Does the amber ever move? Fresh may never switch to Forward Pass. Look at the Switch Mode at the end of Fresh’s If. Or Forward Pass may read leftSlot as $comparedSlot instead of $comparedSlot + 1.
The pass runs on past the end of the board, or stops before it gets there? Look at Forward Pass’s If, $comparedSlot + 1 == $rangeEnd, and at $rangeEnd in Fresh, with its - 1.
The counters don’t go back to 0 after Reset? Look at Computer Sort’s boardArranged Event, and at Clear Sort’s first two steps.
Each of these is one small fix. Make it, press Step again, and you’re back with the chapter. The catch-up download in the Goal is this chapter’s game, finished, if you’d like to compare.
Make the guard speak. In Make Board, step 4’s formula is (5 * local.index + 3) % self.makeBoardData.slotCount, and the 5 is the step it deals by, as in Chapter 1’s Challenge. Change it to 4, and run the game. Some pieces turn up more than once now, and some never appear. Press Step. Instead of a comparison, the bottom line reads This puzzle needs each home position exactly once, and Comparisons stays at 0. Now press N. The shuffle puts every piece home before it deals, so the new board holds each piece once, and Step works again. Put the 5 back when you’re done, because Chapter 4 counts from that deal.
The corner of the picture is home, carried there one pair at a time by something that never saw it. In Chapter 4, the computer learns the way back.