4 The Way Back
By the end of this chapter, the computer sorts the whole picture. At the end of a forward pass it turns around and walks back, carrying the smallest piece to the start. Then forward again, then back, each pass a little shorter, while green edges close in from both ends. Keep pressing Step, and the last comparison brings the last piece home.
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 5 from it.
To open it, start Myth Engine, choose File › Open Project... and pick the downloaded file.
4.1 The Idea
The corner of the Village is home. At the end of Chapter 3, the leaves and pink flowers sat in the last slot, and the computer stopped there and said so.
Now look for the opposite corner. In the Preview, the top-left of the picture is purple wisteria hanging over a yellow wall. On the board, that piece is a long way from home, at the start of the fourth row. The whole forward pass moved it one slot to the left. That’s all.
Why so little? A forward pass carries the biggest number it meets all the way along. A small number gets no such ride. When the pass reaches it, it can step back one slot at most. Then the pass moves on without it. At that pace, the wisteria needs a pass for every slot it has to travel.
So the computer turns around. It asks the very same question, about the very same kind of pair: does the left piece belong later? But now it moves from the end toward the start. Going this way is a backward pass. The smallest number in the range wins every comparison it meets now, and it rides all the way to the front.
Think back to the line of children. The tallest walked to the end of the line, and stayed there. Now the teacher walks back along the line, and the same rule, taller one on the right, sends the shortest child all the way to the front.
A piece that a pass has carried to its end is final. Nothing will ever need to move it again. That piece is settled, and its slot leaves the unsorted range, so after a forward pass the range ends one slot sooner. After a backward pass, it starts one slot later. So every pass is one comparison shorter than the one before: 63, then 62, then 61.
The board will show it. Settled slots get green edges, one more at an end after every pass.
And when does it stop? Count the pairs on the board where the piece with the later home comes first. That’s an out-of-order pair. The Village’s first deal has 819 of them. A swap trades two neighbors in the wrong order, so it puts exactly one out-of-order pair right. It spoils none, because every other piece stays on the same side of both. The sort is done when none are left, after exactly 819 swaps.
Out-of-order pairs have a short name, inversions, and they measure how mixed up a board is. A board in order has none. A board laid out back to front has the most: every pair of its pieces is one.
4.2 The Plan
Here’s how the pieces work together now. The chain from Chapter 3 is still there, and these lines are what changes.
- A Step on a board the computer hasn’t checked -> Computer Sort’s Fresh checks it, remembers the swaps so far, and begins a forward pass.
- A forward pass’s pair reaches the end of the range -> the range ends one slot sooner, and Finish Sort Pass answers whether the sort goes on.
- Computer Sort sends
passFinished-> every Outline paints itself, and the new settled slot turns green. - The sort goes on -> Computer Sort turns to Backward Pass, which compares the pair one slot to the left of the last one. If it’s over, Computer Sort switches to Finished instead.
- A backward pass’s pair reaches the start of the range -> the range starts one slot later, and Finish Sort Pass answers again, so the computer turns forward or stops.
- The last piece comes home -> the count of pieces home changes, and Computer Sort switches to Finished, where Step does nothing.
4.3 Set Up
Nothing new to set up this time. There are no new pictures, keys, Globals or placements. Everything this chapter adds lives in four pieces of Logic and two tables.
Save your project, and again at the end of each part.
4.4 Room for the Way Back
First, Computer Sort gets its new shape.
Chapter 3’s stepRequested has three Modes: Fresh, Forward Pass and Pass Done, the pause at the end. Fresh and Forward Pass stay. Pass Done goes. Its job was to say “Step 03 adds the way back”, and now the way back is here.
Right-click the Pass Done Mode and choose Rename Mode…, naming it Backward Pass. Delete the one Action it held. Then right-click stepRequested and choose New Mode… for Finished, with no Actions. Modes shows how those blocks fit together.
Computer Sort gains a small form, Computer Sort Data, holding swapsBeforePass. Make it with the Data Structures card’s +, and give it the field below. Its job comes in the next part.
What Computer Sort remembers on Puzzle Rules: swapsBeforePass, the number of swaps when the pass under way began, so Finish Sort Pass can tell whether the pass swapped anything.
Now the Messages table can let the passDone row go, since nothing reads it anymore. Click any cell in that row, and press Delete Selected Row, under the grid beside Add Row.
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.Outline Colors gains its last row, settled, a soft green.
#46615a#2579bc#f3d49c#e3b76d#78b99aLook at Forward Pass’s Switch Mode, the one that used to switch to Pass Done. Its Mode box reads Backward Pass now, because a renamed Mode is still the same one. That’s fine for now.
Run the game, and press Step a few times. It works as it did at the end of Chapter 3, until the forward pass ends. Then Step goes quiet, because Backward Pass is still empty. The next two parts fill the gap.
4.5 The End of a Pass
Every pass ends with the same question, whichever way it went, so the question gets a Function of its own.
4.5.1 Finish Sort Pass
Finish Sort Pass is called at the moment a pass reaches its end, right after the unsorted range has moved in by one slot. It has one decision to make: is the sort over?
Three things would end it. The pass may have found every pair in order, so it made no swaps at all. The range may have no pair left, its start meeting its end. Or the pass’s last comparison may have brought the last piece home.
The first question needs a memory. Finish Sort Pass never saw the pass. All it has is $swaps, the count of swaps since the sort began, which says nothing about this one pass on its own. So the caller hands it swapsBeforePass, the count when the pass began. If the two are equal, the pass swapped nothing.
Any one of the three is enough to end the sort, so the If joins them by ||, meaning or. When the sort is over, its answer, sortGoesOn, is false. Otherwise it’s true.
It only answers. Switching Computer Sort to Finished, and telling the Outlines that a pass has ended, are Computer Sort’s own work, in the next part. A Function can’t switch Modes, and the Modes are Computer Sort’s.
Ends one pass of the computer's sort, after the unsorted range has moved in by one slot. When the pass made no swaps, the range has no pair left to compare, or every piece is home, the sort is finished: sortGoesOn answers false. Otherwise it answers true so Computer Sort can begin the next pass.
- Type
Boolean- Name
sortGoesOn- Value
true
$swaps == swapsBeforePass || $rangeStart >= $rangeEnd || $piecesHome == ($gridSize * $gridSize)- Variable
sortGoesOn- Value
false
- Variable
sortGoesOn- Value
true
- Value
sortGoesOn
Nothing calls Finish Sort Pass yet, but Computer Sort will, in the next part.
4.6 The Turn
Now the computer turns around. It’s the chapter’s one hard idea, so take it beat by beat.
4.6.1 Computer Sort
Picture the last Step of a forward pass. The pair at the end of the range has been compared, and the bigger piece is in the last slot. That slot is settled now.
Forward Pass’s If sees it, because its pair ended on $rangeEnd, as in Chapter 3. But instead of switching to Pass Done, it moves the range’s end in by one slot and asks Finish Sort Pass whether the sort goes on. Its answer is forwardPassEnd, and two small Ifs, inside the big one, act on it.
The first small If asks whether forwardPassEnd.value is false. If it is, the sort is over, and the Event switches to Finished. Then, whatever the answer, Computer Sort sends passFinished, so every Outline can paint the slot that has settled. The second small If asks whether the answer is true. If it is, the Event switches to Backward Pass.
Last, still inside the big If but after the small ones, it writes the swaps so far into self.computerSortData.swapsBeforePass. The next pass starts its own count from there.
On the next Step, Backward Pass answers. It calls Compare Next Pair at $comparedSlot - 1, one slot to the left of the last pair. That’s all it takes to turn around.
There’s no marker for where the computer is, and no flag for which way it’s going. The last pair compared is the place, as in Chapter 3. The Mode is the direction. Forward Pass reads one slot to the right of the last pair, and Backward Pass reads one slot to the left.
The comparison doesn’t change at all. Compare Next Pair still asks whether the left piece belongs later, and swaps if it does. Going backward, that drags the small number along to the left, the way going forward dragged the big one right.
Backward Pass ends where the range starts, so its If asks whether the newest pair began on $rangeStart. From there it mirrors Forward Pass. The range starts one slot later, and Finish Sort Pass answers, as backwardPassEnd. False switches the Event to Finished, passFinished goes out, and true switches it back to Forward Pass.
Fresh gains one line before its first comparison. It keeps $swaps in self.computerSortData.swapsBeforePass, because the first pass needs a starting count too. The round handles join that line between the two old ones.
The fourth Mode, Finished, is empty. It’s where Computer Sort rests when the picture is done, and a Step on a finished picture lands there and changes nothing.
One more Event watches for the end. On a board like the Village’s, the last piece comes home in the middle of a pass. Waiting for a whole pass with no swaps would mean comparing pairs the computer already knows are in order. So a Variable Changed Event watches $piecesHome, as Picture Complete does. When every piece is home, it switches stepRequested to Finished at once.
On the card, Pass Done is struck out and Backward Pass is green, under the same heading. That’s the rename you made at the start of the chapter, not a new Mode.
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. Passes then go back and forth over the unsorted range, which shrinks by one slot at the end of each pass, until every piece is home or a pass makes no swaps.
Any Objectself.computerSortData- Action Name
boardCheck
boardCheck.value == true- Variable
$rangeStart- Value
0
- Variable
$rangeEnd- Value
$gridSize * $gridSize - 1
- Component Value
self.computerSortData.swapsBeforePass- Value
$swaps
- 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
$rangeEnd- Operator
-=- Value
1
- Action Name
forwardPassEnd- swapsBeforePass
self.computerSortData.swapsBeforePass
forwardPassEnd.value == false- Event
On Step Requested- Mode
Finished
- Custom Event
passFinished
forwardPassEnd.value == true- Event
On Step Requested- Mode
Backward Pass
- Component Value
self.computerSortData.swapsBeforePass- Value
$swaps
- Variable
$message- Value
data('Messages', 'passDone', 'words')
- leftSlot
$comparedSlot - 1
$comparedSlot == $rangeStart- Variable
$rangeStart- Operator
+=- Value
1
- Action Name
backwardPassEnd- swapsBeforePass
self.computerSortData.swapsBeforePass
backwardPassEnd.value == false- Event
On Step Requested- Mode
Finished
- Custom Event
passFinished
backwardPassEnd.value == true- Event
On Step Requested- Mode
Forward Pass
- Component Value
self.computerSortData.swapsBeforePass- Value
$swaps
- Event
On Step Requested- Mode
Fresh
- Event
On Step Requested- Mode
Fresh
$piecesHome == ($gridSize * $gridSize)- Event
On Step Requested- Mode
Finished
Run the game. Press Step 63 times, as in Chapter 3, and then once more. The amber pair doesn’t stop. It’s one slot to the left now, and the computer is walking back.
4.7 Green at Both Ends
Last, the board shows which slots are settled.
4.7.1 Color Outline
Color Outline’s coats of paint gain one more, green, for a settled slot. It goes on right after the normal color, before blue, gold and amber, so the new steps go between old ones, with the round handles. So a settled slot still turns blue under the focus or gold when you choose it, and the amber pair shows over everything.
A slot is settled when it’s outside the unsorted range. The range runs from $rangeStart to $rangeEnd. So there are two questions, two new Ifs: is this slot before the start, or past the end? Either one paints it green.
Each If starts with the same test as the amber If: has the computer compared any pair? Before the sort begins, and after Clear Sort, $comparedSlot is -1. The range then holds whatever it held before, and no slot should look settled.
Colors one Outline from what is shown on the board now: a settled slot is green, 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')
$comparedSlot >= 0 && outlineSlot < $rangeStart- Applies to
outline- Value
data('Outline Colors', 'settled', 'color')
$comparedSlot >= 0 && outlineSlot > $rangeEnd- Applies to
outline- Value
data('Outline Colors', 'settled', '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')
4.7.2 Show Outline
Show Outline gains one Event, passFinished, calling Color Outline with outline set to Self, like its other three. That’s how a slot turns green the moment its pass ends.
Colors this Outline whenever what it shows may have changed: the player's selection, focus or press, or the computer's compared pair and unsorted range.
Any Objectself.slotNumber- outline
self
- outline
self
- outline
self
- outline
self
Run the game, and press Step through the first pass and one Step more. The last slot’s edge is green.
Watch for each of these.
- Every edge starts dark green-gray, before you touch a piece or press a key. A press paints blue. A selection paints gold.
- The whole sort takes many Steps, so the list below follows only its start. The Challenge at the end of the chapter gives you a whole sort in a few dozen Steps.
- Press Step 63 times. The leafy corner is home, and the counter says Comparisons 63 and Swaps 51, with 5 / 64 above the board. The amber pair is the last two slots.
- Press Step once more. The amber pair moves one slot to the left, the bottom line says Kept, and the last slot’s edge is green.
- Keep pressing. The amber walks back along the bottom row, then up the board, right to left. The first twelve pairs of the way back are all Kept.
- Watch the purple wisteria piece, at the start of the fourth row. The first pass moved it one slot, and the way back leaves it alone at first. From the 102nd Step, every Step says Swapped, and it rides left, row after row.
- After the 125th Step, the wisteria is in the top-left corner. The counter says Comparisons 125 and Swaps 99.
- The caption says 3 / 64, fewer than after the first pass. That’s because home isn’t settled. When the wisteria rides past a piece that’s home, the two swap, and that piece steps one slot out of its home.
- Press Step once more. The amber pair is the second and third slots, and the first slot’s edge is green. The third pass has begun, one slot in from the start.
- Every pass is one comparison shorter. The third ends after 61 more Steps, the fourth after 60, and green closes in from both ends.
- The whole sort is 1478 Steps. That’s a lot of pressing, and Chapter 5’s Sort button will press for you. If you go all the way, the counter ends on Comparisons 1478 and Swaps 819, the caption reads 64 / 64, and the bottom line says Picture complete.
- Press Step on the finished picture. Nothing changes.
- Press R. The counters go back to 0, and the green and amber are gone.
Fresh checks the board and starts forward. Forward Pass carries the big number to the end, and Backward Pass carries the small one to the start. At the end of each pass, Finish Sort Pass decides whether another follows, and Computer Sort turns or stops on its answer. Color Outline paints what’s settled green.
That’s Cocktail Shaker Sort, the whole of it. One question about two neighbors, asked forward and then backward, over a range that shrinks by a slot at every turn. The computer never knows where a piece belongs. It only knows which number is bigger. And every swap puts exactly one out-of-order pair right, so 819 of them put the Village back.
4.8 If It Didn’t Work
The way back has a lot of moving parts, and most of them only show at the end of a pass. That’s normal. Press Step through a turn, watch the amber, and think it through.
Step goes quiet after the 63rd Step? Perhaps Forward Pass never switches. Look at the two Ifs inside Forward Pass’s If, which read forwardPassEnd.value: false switches to Finished, and true to Backward Pass. Does Finish Sort Pass return sortGoesOn? And look at its If, whose tests are joined by ||, meaning or.
Does the amber jump after the turn? Look at Backward Pass’s leftSlot, $comparedSlot - 1, with a minus.
The way back runs past the start of the board, or stops early? Look at Backward Pass’s If, $comparedSlot == $rangeStart, with no + 1 this time.
Every pass is the full length of the board? Then the range never moves in, so look at the Operators in both passes. Forward Pass takes 1 away from $rangeEnd with -=, and Backward Pass adds 1 to $rangeStart with +=.
The sort stops too soon? Perhaps Finish Sort Pass thinks the pass made no swaps. Look at where each pass writes $swaps into self.computerSortData.swapsBeforePass. It’s the last step in the If, after Finish Sort Pass, never before it.
No green anywhere? Look for Show Outline’s passFinished Event, and for the settled row in Outline Colors. If everything outside the amber turns green at once, look at Color Outline’s new Ifs: the first asks < against $rangeStart, and the second > against $rangeEnd.
The picture is complete, but Step still adds comparisons? Look at Computer Sort’s Variable Changed Event, the one that watches piecesHome.
Each of these is one small fix. Make it, run the game, 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.
Watch a whole sort from start to finish. In Show Piece’s Globals card, using New Global…, set $gridSize’s Default to 3, and run the game. Now the board has nine slots, and the game deals them with a Shuffle. The pieces stand apart, because each one is still cut for a board of 64, but the numbers sort all the same. That’s a short sort. Press Step until the bottom line says Picture complete. How many passes did it take, and which way was the last one going? Shuffle, and guess before you press. Put the 8 back when you’re done, because Chapter 5 cuts the picture for every size.
The wisteria is home in its corner, and the leaves and flowers in theirs, and the computer walked between them until the Village was whole. In Chapter 5, it learns to walk by itself.