22806_BuildingBlocks

Artificial Intelligence is a mysterious and glamorous field. Little do most people know that AI can often be like child's play. Consider robotics, where research projects focus on making robots play with toys. Although any four year old child can do this easily, it can be very hard for a robot.

In this problem your program has to interpret and execute a series of commands in a very simple robot planning language. This language is designed to deal with a blocks world, consisting of n blocks numbered 0 to n-1, initially laid side by side. Such a world is shown in Figure 1.

The planning language is designed to instruct a robot to move the blocks around, using the following commands ( a and b are block numbers such that 0 ≤ a, b < n ):

move a onto b

Puts block a on top of block b, after returning any blocks that were stacked on a and b to their original positions.

move a over b

Puts block a on top of the pile on block b, after returning any blocks that were stacked on a to their original positions. Retains the order of the b pile.

pile a onto b

Puts the pile of blocks on top of ( and including ) block a on top of block b, after returning any blocks that were stacked on b to their original positions. Retains the order of the a pile.

pile a over b

Puts the pile of blocks on top of ( and including ) block a on top of the pile of block b. Retains the order of the a and b piles.

quit

Terminates the planning program.

Your job is to ececute these commands in order and display the resulting positions of all of the blocks. Any command in which a=b or in which a and b are in the same stack of blocks is an illegal command and should be ignored. Illegal command should not affect the final block positions.

The input begins with an integer n on a line by itself representing the number of blocks. You may assume that 0 < n < 25. The number of blocks is followed by a sequence of block command, one command per line. Your program should process all commands until the quit command is encountered.

The output should consist of the final state of the blocks world. Each original block position numbered i ( 0 ≤ i < n where n is the number of blocks) should appear followed immediately by a colon, a single space, and a list of blocks that appear stacked in that position with each block number separated from other block numbers by a single space. There should be one line of output for each block position.

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9: