Assignment #1

From an early draft of his Canterbury tales, Chaucer removed an account of the pilgrims staying at Anne

Hoy’s1

inn, an establishment that served bad ale, but good cheese. The missing account explained how Anne

kept her high-quality cheese stacked on stools, the largest rounds underneath the smaller rounds, to stop

rats and mice from getting at them.

Occasionally the stool holding the cheese would need some maintenance (for example, the legs would

start to buckle under the weight), and Anne would shift the entire stack from one stool to another. Since

she could only move a single (hundred-pound plus) round of cheese at one time, and she refused to stack

a larger-diameter cheese round on a smaller one (the outer part of the larger cheese would droop) she used

three stools: one was her destination for her entire stack of cheese, one was the source (which likely needed

its legs reinforced), and the third was for intermediate stacking. Chaucer immortalized the complicated

routine Anne endured, lugging rounds of cheese from stool to stool as \The tour of Anne Hoy ” (TOAH).2

One of Chaucer’s pilgrims had a mathematical bent. She had seen a miraculous early draft of the

Wikipedia article on the Tower of Hanoi in a vision, and noticed that Anne’s routine for moving cheeses

was identical to the problem of moving rings between three posts. Using this similarity she calculated that

to move n cheeses in this way required 2n 1 moves. This disheartened Anne, who had plans to increase

her stack of cheese beyond the 8 she currently had. She decided to invest some of her pro?ts in a fourth

stool.

Anne ?gured that she could do substantially better than 2n 1 moves using the following strategy:

? For a stack of 1 cheese round, her four-stool con?guration allowed her to move the stack in 1 move,

using her previous three-stool TOAH method.

? To move a stack of n 1 cheese rounds from some origin stool to some destination stool, she reasoned

that she could think of some number i between 1 and n 1, and then:

1. Move n i cheese rounds to an intermediate stool using all four stools.

2. Move i cheese rounds from the origin stool to the destination stool, using the (now) only three

available stools and her TOAH method.

3. Move the n i smallest cheese rounds from the intermediate stool to the destination stool, using

all four stools

Notice that steps 1 and 3 require Anne to know how to move n i cheese rounds using four stools. Anne

gured this wasn’t a problem, since she could apply her recursive strategy to this smaller problem. She

presented her plan to the above-mentioned mathematically-inclined pilgrim who said that if she called the

minimum number of moves that her strategy needed to move n rounds of cheese M(n), and if some i between

1 and n 1 were chosen, then (reasoning recursively):

M(n) = (

1 n == 1

2 M(n i) + 2i 1 otherwise:

(1)

1

In Middle English her name would have been spelled Auyne H’Oeuil

2Chaucer conjectured Anne’s muttered \cheeses crust!” and \gentle jumping cheeses!” were veiled religious oaths, not

mundane references to cheese mainte

After experimenting a bit Anne found she could move 3 cheese rounds in 5 moves (a little better than the

7 required by the TOAH method), and 6 cheese rounds in 17 moves | much better than the 63 required

by the TOAH method. But the choice of i made all the di?erence. She (and the aforementioned math-geek

pilgrim, who had decided to stay at her inn permanently) spent many hours with early prototypes of pencil

and paper, ?guring out the best strategies for moving ever-larger stacks of cheese.

This is where matters stood, for centuries, until the invention of the computer.

your job

The Tour of Anne Hoy Game is to move a stack of cheeses from the ?rst stool to the last stool, using only

valid moves as described in the previous paragraphs.

You will implement parts of a step-by-step design of an object-oriented program for a Tour of Anne

Hoy game. In order to guide you, we present the steps below, in the order we recommend. Notice that you

get credit for each step you complete.

We know that this is a challenging assignment. We aim to help guide you to a successful submission,

provided you follow the guidance we o?er. You may work on this assignment in groups of 1, 2, or at most

3. You should be familiar with and understand all the code that your group submits . . . or you’ll pay for it

come test time.

We encourage you to submit your work to MarkUs frequently, especially each time you complete one of

the steps below.

Step 1: Read and understand the Cheese class in toah model.py, and implement the methods where we have

given headers (don’t change the headers). This step is worth 5%.

Step 2: Read all client code in gui controller.py, gui viewables.py, console controller.py, and tour.py, to

see how it uses class TOAHModel. Unlike ConsoleController, GUIController is already completely

implemented for you. You do not need to understand (and you certainly should not change) the

code in the ?les gui controller.py and gui viewables.py, but your implementation of TOAHModel will be

expected to work with both ConsoleController (once you complete step 4) and GuiController.

Write the method headers for TOAHModel in toah model.py according to their uses in client code. You

may need to add some methods to be used for implementations you write for ConsoleController and

in module tour.

Step 2 is worth 45% of the credit for this assignment (of course, you’ll need to have done Step 1).

Step 3: Write the implementations of the TOAHModel methods from Step 2. Notice in particular how

ConsoleController and GUIController rely on a TOAHModel object to throw exceptions in certain

circumstances (and without altering the state of the TOAHModel object).

When you’re done, you should be able to run gui controller.py to manually play the Tour of Anne

Hoy game. Do not change anything in gui controller.py or gui viewables.py.

You also need to implement TOAHModel.__eq__. The header in toah model.py has instructions.

You can assume that no two Cheese objects of the same size will ever be added to a TOAHModel object.

Steps 1{3 are worth 65% of the credit for this assignment.

Step 4: Now we want you to get a console-based version of the game working. Implement the methods

play_loop, __init__, and the function move in console controller.py. The headers are already written

2

for you, and the docstrings provide additional instructions. You will also need to put appropriate code

under if __name__ == “__main__”:.

When you’re done, you should be able to run console controller.py to manually play the Tour of Anne

Hoy game through the console.

Steps 1{4 are worth 70% of the credit for this assignment.

Step 5: Implement the module-level function tour_of_four_stools in tour.py to solve four stool instances

of Anne Hoy’s cheese-moving problem, trying to minimize the number of moves. You should be able

to move n cheeses in considerably less than 2n 1 moves achievable with just three stools.

We will check your solution using TOAHModel.get_move_seq, so make sure to use the class MoveSequence

in toah model.py to record the moves that your solver makes. If we cannot verify your sequence of

moves using TOAHModel.get_move_seq, then we cannot give you marks for this step.

Step 5 is worth 22% of the credit for this assignment. Any solution of the game (that doesn’t take,

say, more than twice as long as the 3-stool towers-of-Hanoi strategy) will get 3%. If you solve it in

fewer moves than required by the 3-stool strategy (fewer than 2n 1), we’ll give you an additional 7%.

If your solution is close to as good as the best-known solution, which we described above, then you’ll

get an additional 8%. If you implement the best-known solution, you’ll get an additional 4%.

Step 6: Add an option to your tour module that enables animating your solver in the console. The header

for tour.tour_of_four_stools already has two optional arguments for this; when console_animate

is True, animation should be displayed in the console, and delay_btw_moves gives the number of

seconds to wait between showing two moves. We recommend using TOAHModel.__str__, but this isn’t

required (you can make your own string-based representation).

Step 6 is worth 8% of the credit for this assignment.

Steps 1-6 are worth 100% of the credit for this assignment.

Those licenses: Notice that the starter code that we provide is distributed with a GNU GPL license. One

consequence of this is that any copies of that code, or any work you derive from it (for example the

les you submit to MarkUs), must be similarly licensed if you pass it on to someone else | you may

just add your name to the license declaration, and include the COPYING notice when passing it along.

what to submit

You’ll need to submit your version of the following ?les to MarkUs:

? toah model.py

? tour.py

? console controller.py

? We will deduct up to 10% for ?les that do not pass the python_ta.check_all(…) code that we

include at the end of your starter code, or that do not follow the class and function design recipes.

The python_ta.check_all(…) directives include config=… to specify a con?guration ?le saying

which python_ta warnings to disable. You may not change the con?g ?les.