Assignment 4

Due Mon, Aug 5

Please create a single file named
hw4-1.py (the solution to question 1)

Email your solution to zschneider <at> berkeley.edu. Include comments in each script stating your name, the name of any collaborators, and approximate time it took you to complete the exercise.

To assist with grading, please name all your functions exactly as they are specified below, and use the same list of arguments.

1. A Marbles Game

In a particular board game, there are N spaces in a row, numbered 0 through N - 1 from left to right. There are also N marbles, numbered 0 through N - 1, initially placed in their corresponding spaces. The single player begins by shuffling the marbles into a random order. After that, there are two moves available:

Switch: Switch the marbles in positions 0 and 1, and

Rotate: Move the marble in position 0 to position N - 1, and move all other marbles one space to the left (one index lower).

The objective is to arrange the marbles in order, with each marble i in position i.

a. Write a class, MarblesBoard, to represent the game above. The class should be initialized with its size, N. Include a shuffle() method to rearrange the marbles in random order. To do this, you may want import the random package at the start of your script:

import random

Once you do that, then if x_list is a list, you can use the following statement to shuffle it:

random.shuffle(x_list)

Also include switch() and rotate() methods to simulate the player's moves. Write a method, is_solved(), that returns True if the marbles are in the correct order.

Additionally, write __str__ and __repr__ methods that display the current state of the board. Your class should behave like the following example (though your shuffle method will, of course, return different results).

>>> board = MarblesBoard(9)
>>> board
0 1 2 3 4 5 6 7 8
>>> board.shuffle()
>>> board
3 6 7 4 1 0 8 2 5
>>> board.switch()
>>> board
6 3 7 4 1 0 8 2 5
>>> board.rotate()
>>> board
3 7 4 1 0 8 2 5 6
>>> board.switch()
>>> board
7 3 4 1 0 8 2 5 6

b. Write a class, Solver, that actually plays the MarblesGame. You class should take a MarblesBoard in its constructor. Write a solve() method that repeatedly calls the switch() and rotate() methods of the given MarlesBoard until the game is solved. You should print out the state of the game board after ever move.

>>> board = MarblesBoard(4)
>>> board.shuffle()
>>> board
3 2 1 0
>>> board = MarblesBoard(4)
>>> board.shuffle()
>>> board
1 3 0 2
>>> player = Solver(board)
>>> player.solve()
3 0 2 1
0 2 1 3
2 1 3 0
1 2 3 0
2 3 0 1
3 0 1 2
0 1 2 3