Nada

Laboration 2 - Card trick

"The magician removes the thirteen spades from the pack, holds them as a face-down deck and proceeds as follows: The top card is moved to the bottom, the next card is put down on the table face-up, the next card is moved to the bottom, the next card is put down on the table etc. To the amazement of the spectators, the cards come out in the order ace, deuce, three, four...

Method: Secretly arrange the cards in the following order..."

Here we stop citing Liberg: Trolleri för alla (Magic for everyone). In this lab project, you are required to find out the secret order! Therefore you must write a program that does the following:
Order of cards in deck: 3 1 5 2 4
The cards come out in this order:
1 2 3 4 5

A queue of nodes

The program first builds a queue of the input numbers, then manipulates the queue as specified above. With the abstract data structure queue, you can do three things: put in something, take out something and check if the queue is empty. The corresponding calls are put(x), x=get() och isempty(). Your main program is to fulfil its task with these calls, not caring about how the queue has been implemented. Before starting with the card trick, you may try to make the following test program function. 
   put(1)
   put(2)
   x=get()
   y=get()
   print x,y   # 1 2 should come out

Initially you can write the code for the queue in the same file as the main program, making it obvious that the queue consists of nodes, each containg a number and a pointer. The class node may come first in the file, then the global queue pointers, then the definitions of put(x), get() and isempty() and finally the main program.

It is a little bit tricky to program put(x), since there are two cases depending on whether the queue is empty or not. Picturing these to cases is a great help, so please draw sketches!

When the test program works, you should modify it to solve the secret of the card trick. An input tip is to use raw_input().split(). Experiment with different input orders and reveal the secret!

Yor program also makes intelligent conversation. As an example, input the sentence JAG GILLAR NÄR DU KRAMAR MEJ. Your Swedish neighbour will be pleased to translate the sentence and its answer.

An abstract queue class

But the lab is not finished yet. In order to be able to use several queues simultaneously, you need several queue objects, each with its own first and last. For example, you may want to move values from one queue to another with 
   q1=Queue()
   q2=Queue()
   - - -
   x=q1.get()
   q1.put(x)
Let the file queue.py start with class Queue: and copy all queue code and the node class. Now, every def must have a self-parameter and instead of two global pointers you use self.first and self.last.

The main program lab2.py should start with from queue import Queue, rather than from queue import *, for the node class should remain invisible.

Extra tasks for higher marks (choose one)

Backwards card trick: Finding the correct initial card order by experimentation is time consuming. A brilliant idea is to perform the trick backwards, and you are to program that idea. Thus, the last card put down (the king) is to be handled first, so you need a stack for temporary storage of the other cards (ace--queen). Then the queue work starts, but now the pointer first points to the bottom card and last to the top card. Finally, to print the deck from top to bottom you have to use the stack again. Sigh!

Unsuccessful shuffle: Card sharks always use riffle shuffle, that is they cut the pack in two and riffle the two halves together such that the top card of the lower half becomes the new top card and the bottom card of the upper half becomes the new bottom card. There is a rumour that this shuffle must not be repeated too many times or the cards will return to the original order. Is there any truth in the rumour?

In order to program this, you need three queues. Your program is to ask for the number of cards (an even number) and the number of shufflings to be performed and then print out the resulting order. Test with 6 cards and 3 shuffles or with 62 cards and 6 shuffles. How many are needed for the usual 52 card deck?

Suveränt jobbat av ....................................... fastslår......................... den .............