Robots Sorting Cards

An offline activity for teaching CS concepts: programs, algorithms, sorting, assumptions, correctness, computational complexity etc. etc. Requires: pen, paper and a deck of cards.

[TL; DR! If you just came here for the printable lesson plan: Here it is]

This activity was developed to give visiting groups of school kids CS content. Otherwise it is just a tour of the architecture and office amenities.¹

Below is a 1–1.5 hour lesson plan that can and has been tailored to suit kindergarteners and high-school seniors. It was developed and field tested over the course of several years and tried on hundreds on visiting students with enthusiastically positive results. Thanks to Mark for the initial idea and discussions around development, and Sergei for helping develop the delivery.

A typical lesson includes:

(Full lesson plan illustrated and linked below)

• A general discussion about what sorting is and why it is central to many solving many problems in CS.Illustrating sorting by handing out a dictionary or a paper phonebook to a volunteer and asking them to look up a name or a word.Then, ask for another volunteer and ask them to find a specific phone number, or a definition that contains a specific word.
• Handing out 5–6 cards to each group of kids (make sure there are no cards with the same number) and ask the kids to take turns laying out the cards in random order and sorting them.
• A discussion about what a is program: a series of instructions.
• Older students can benefit from a short discussion about what an algorithm is (the idea behind the program) — what was your plan to sort the cards?
• Introduction to the “robot” paradigm with a small instruction set (move left , move right, swap)Lay 3 cards out, then write the “program” that causes them to be sorted.One student writes the instructions, another plays the robot.(and either the first or third student reads the instructions to the robots, everyone else makes sure instructions are followed.)
• Introduce the “conditional swap” (swapping only if a specific side is bigger)Now, the target is to write a general program that can deal with any input. (the cards are randomly laid out after the program was written).;Add another role now, a student who tries to reorder the 3 cards to generate an input that the program fails to sort.
• Write a MAX function and compose the SORT program using that.

It can be used to teach various CS concepts :

• Coding (A series of instructions)
• Edge cases, starting conditions, assumptions and clear definitions. (can a robot fall off the edge?)
• Algorithm design (as an abstraction of the method from the instruction)
• Debugging and adversarial input (can you find a counter example.. )
• Sorting methods
• Composing a function of other functions.
• Computational Complexity (High school seniors can calculate the number of actions as a function of the number of cards)

The lesson plan

The printable lesson plan is available on google docs here.please feel free to send me comments or thoughts.

Getting started, Illustrated breakdown

See full lesson plan for details, but just to get you started here is the gist:Break the class into groups of 3–4 students each

1. Known Input, play-by-play. First, shuffle and lay out the cards, then one student takes instructions and follows them one at a time. (no need to write the instructions.)
2. Known Input, all-at-once. Again, lay out the cards first, but now write the entire set of instructions.
3. Unknown input. We introduce a new instruction “Conditional Swap” Now the students must write the entire program (for 3 cards) before the cards are shuffled and laid out.
4. Adversarial input. Rather than shuffling the cards, the students try to find an order for which the program from step 3 won’t work.

Step 1: Known Input, play-by-play.

Start by handing cards out to the students, 4 or five cards will do.One student plays the robot. The robot’s hands are placed on two adjacent cards. The others will take turns giving instructions.The goal is to sort the cards.

The robot only knows three instructions : Move Left, Move Right, and Swap Cards.

The “robot” should react to every instruction, without waiting. later you can ask them to write all the instructions in advance.

So if we start out like this.

Figure 1: At the start, the student who plays the robot, touches two adjacent cards and awaits instructions.

The first instruction might be “MOVE RIGHT” and will result in this.

Figure 2: The student emulates moving right by shifting the hands, the right hands moves to touch the next card, and the left hand moves over and now touches the card previously touched by the right hand.

“MOVE RIGHT” again.

Figure 3: After the second “move right”

Now we have to swap the cards. so “SWAP CARDS”

Figure 4: We have placed the 7 in its final place. we will now have to rearrange the 3 and the 5.

“MOVE LEFT”

Figure 5: The robot has moved left.

“SWAP CARDS”

Figure 6. Now the cards are sorted.Step 2 : Known Input, all-at-once. The first program

Same as step 1, but now the series of instructions is written down, after seeing the cards. Then the instructions are read out one by one, and if at the end, the cards are sorted, the mission is a success. In the above example, with the above starting conditions. an example program might be: (Robot starts on the two leftmost cards)

• Move Right
• Move Right
• Swap Cards
• Move Left
• Swap Cards

Discussion for Steps 1–2

1. The goal of this stage is to convey that the robot follows instructions and does not “think for itself”. It is sometimes entertaining to seed this interaction by suggesting that the kids being the robots try to do what people tell them, not what they mean.
2. Sometimes chaos ensues, this is great, encourage it. Here are a few examples below, I’m sure others will come up, keep it playful, but it is very easy to steer the conversation into various topics that relate to computer problems.
3. If in one group, a robot “accidentally falls” off the table (apparently this is hilarious🤷) because 5 different people were yelling “move right” and it moved right 5 times — you might talk about the problem of communication protocols, the Byzantine Generals Problem. (and then close it off by saying “ok, for now, only one person gives instructions. and each instruction is only carried out once”)
4. If students start arguing about “Whose left, my left or your left? ascending or descending order?” you can lead a short discussion about assumptions in programs, the need for nomenclature and common language, unambiguous instructions etc. (and close it off by saying “from now on, left means the robot’s left, and sorted means the largest card is on the right, the robot’s right”)
5. If a robot goes off the cards, or doesn’t start in the right place, so step 2 is all messed up, you can discuss assumptions, and verification of initial conditions. (and close it off by deciding on some convention of where the robot starts.)
6. Someone may raise the point that a 3 of diamonds can’t be compared with a 2 of spades . This is a great segue into a discussion on comparisons, assumptions, removing ambiguity, and common language. Also how do you decide on the sort order of items that are equal? What if the instructions are first sort by suit then by number, or just by suit? (we can close off this discussion by saying we only care about numbers, and make sure that the cards handed out to the groups have no duplicates,. But whatever the decision, it doesn’t affect the program as long as we can all agree what the correct ordering should be after sorting.)

Step 3 — Unknown input, the first algorithm.

This step is usually too advanced for 6-7 year olds. (there is enough material above for a full lesson for younger students.) YMMV about the age, your call.

For this step, either define the problem as sort the cards, and start with 3 cards , or for a younger group, define the problem as extract the max — put the largest card all the way at the (right) end.

We must also introduce the conditional swap now. This instruction replaces the previous swap instruction — it only swaps the cards if the larger card was on the lefthand side, such that after this instruction the larger card will be on the righthand side whether they were swapped or not. If we issue the instruction “Conditional Swap” when the table looks like it does in figure 5 above, the cards are swapped and the result is as seen in figure 6 but, if we issue it again, nothing happens, the larger card remains on the right.

This exercise is the main part of the lesson, the groups will try and fail several times. Do not skip this, let the groups come up with ideas, walk around the room as they do so. Figure out which group has an idea that works on most but not all inputs. Bring that program up, write it on the board. Show how it works on the input that it was tested on, ask other groups if they can show an example of “input” (card order at the start) for which this fails.

An example program that works on most inputs (for three cards, starting on the two leftmost cards) might be

• Conditional Swap
• Move Right
• Conditional Swap

It will work on [2, 3, 4], [2, 4, 3], [3, 2, 4], and [4, 2, 3]

Step 4 — Adversarial input, try to break it.

It will not work on [4, 3, 2] and [3, 4, 2] .For it to work on those, we need to add a Move Left and a Conditional Swap.

Discussion for 3–4:

But how can we be sure it is right?One way is to test all possible inputs. Testing all possible inputs for sorting is only feasible on very small inputs, but it is a super valid way to prove that our program that sorts 3 cards is correct (no matter which order the 3 cards are presented in).

At this stage we can talk about the Algorithm, or General Ideaᵀᴹ . Up until now we wrote a series of instructions to deal with specific input, now we must come up with an idea that will work on any input. We must be able to reason about the problem in an abstracted way.For example, we can break the problem down into two steps. Step 1. make sure that the largest card is placed in the rightmost positionStep 2. make sure that the last two cards are sorted.

Step 1 may be achieved by starting at the leftmost location, performing a conditional swap, then moving right, one step at a time, each time performing another bubble sort. by the time we’ve reached the end (in the case of 3 cards this takes a single move) we can be sure that the largest card is in its place. (because no matter where it started, at some point the robot got to it, and from that point on, it kept moving it right, by swapping it).

Step 2 is easy, just move left to get the two cards, and conditional swap them.

In general if there were more than three cards, we’d add a step similar to step 1, move the second largest card to the second spot, etc.

We’ve just rediscovered bubble sort.

The printout lesson plans contain other expansions, such as computational complexity. etc. It also suggests when and how to move to more cards. Enjoy. (and lmk if you have comments.)

[1] At the Google office in Waterloo we’d get a lot of requests for school tours. School kids don’t really appreciate the design philosophy expressed with a new-glass-and-steel-decor atop a century old industrial brick building; and while the lounge with a playstation and arcade games is a cool impressive feature, it isn’t really worth the trip. Some of the teachers were impressed with the micro-kitchen budget, but kids have no idea what cashews cost.

Robots Sorting Cards was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.