Let’s Dance

In our last lecture, we introduced the notion that there is a “dance” going on inside the computer. This is actually not a bad way to think about how things happen in the machine. In fact, after pondering about how to get this idea into your heads better, I came up with something (at 3am one night!) we can do in class. We will dance in class!

Don’t worry, you do not need to move (much).

This dance is going to be a bit strange. It will not matter if you cannot dance a lick!

Setting up to Dance

I will ask all of the humans in the room (including your instructor) to stand in a circle with something like a desk between each of you. That desk is going to be a spot where a stack of cards can be placed.

As you stand in this circle, your world is focused on the cards to your left, and the cards to your right. You will not move your feet at all in this dance.

(Sheesh, not much of a dance, if you ask me). I heard you muttering that!

All the action will involve those cards on either side of you.

Note

Obviously, each stack of cards is “shared”, meaning they “belong” to a pair of students, who will fight over them (well, not really!)

Your Role in the Dance

Do you see those two piles of cards to your left and your right? If the number of cards on each side of you is not the same, you are not a happy dancer. You are so unhappy, that you simply must balance the number of cards to be happy.

That means you must pick up the two piles of cards on both sides of you, then split that big pile up into two stacks with as close to the same number of cards in each pile as you can get, then put them back down.

However, there are a couple of rules covering how you do that!

Note

There are two silly rules in this dance:

The first rule should be obvious. You cannot cut any card in half!

The second rule is not so obvious. The cards absolutely want to move to create a balance. If there is only one card on one side, and none on the other, it will move to the spot with no card.

Hey, I am inventing this dance here!

Now, that rule is applied by each “dancer” when it is their turn to dance.

What, we have to take turns dancing? This is really not the dancing I know!

Dance Version 1

There will not be a drum in this dance, pounding away. However, your friendly instructor will start things off. The action will start when I place a stack of cards on my right table.

Initially, all the tables will be clean, there are no cards in sight. Everyone is happy!

However, as soon as I place that pile of cards on the first table, the student on my right is suddenly very unhappy. That student will pick up the two piles (OK, so there is only one)) and try to balance them on both sides. As soon as that student is done, the one on her/his right, will be unhappy, and do the same thing. We will continue this process until everyone is happy!

If it is your turn, and you are happy, just tell the student on your right that you are happy! You are done, and that next student has a turn.

Note

I wonder how long this will take! We will see! I also wonder if we will reach a situation where everyone is happy as can be, and nothing really happens. Hmmm!

You need to think about how this will go. I lay in bed that night, thinking about this, until I came up with this plan on how we will do the dance. It will do what I want it to do!

The Instructors Role

In our first version of this dance, I will not participate in the dance, other than injecting that first pile of cards onto that first table. If cards appear on either side of me, they will just sit there. As you should see, we take turns trying to get happy, and sweep around the circle from left to right. As soon as it is my turn to get happy, I will simply do nothing, and pass the turn to the student on the right, to again try to get happy.

Dance Version 2

In version two of this dance, everything will stay the same, except for one minor twist.

Your role as a student will not change, However, your instructor’s role will change.

Insted of plopping all the cards in my initial pile on that first table, I will place only one card on my right table. The dance will continue until it is my turn again. At that point, I will remove any card found on my left table and keep it in a second (hidden) stack. I will take another card from the first stack and place it on my right table again. The student on my right will then take a turn once more, and the dance continues

I will stop placing new cards on the table when I have as many cards in my left (hidden) pile is the same size as the first pile (the one I use to add new cards into the dance). At that point the dance is done.

Note

Again, I wonder how long this will take!

Dance Version 3

We might do this in class. Otherwise, you get to tink about it.

What would happen is we all just started doing our “dance” at the same time. We might get into small fighting matches, where two players fight over the stack of cards between them. One will want to steal a card, while the other might want to put another on. Maybe both will want to so the same thing. Who knows? The players are going to work a lot harder to get this dance done.

But, after the smoke clears, what will have happened? We will have to see. I suspect, after a suitable amount of time, and a few small fights, we might see similar results.

Interesting!

Final Note

Your first real lab project for this course will be to write a C++ (or Python, if you prefer) program that simulates version 1 of this dance. I will provide some starter code for this after we do the dance in class. That will make sure you understand the rules of the dance well enough to write the code.

I will let you work in teams of three/four students, to discuss the design of this simulation. I still want each of you to write your own version, but you can share ideas. (See the lab assignment for more details)

I hope you read this before class. Otherwise, it will take more time to explain the rules.