CSC207 - Lab 13
Die Hard III

Assigned Nov 4th 2 p.m.
Due Nov 9th 12 p.m.

Overview

This lab will combine mathematics, instantiable classes, and bone-chilling terror. ;) Always a famous puzzle in the Artifical Intelligence circles, the WaterJug problem recently came to popular culture through the classic action movie Die Hard III. In Die Hard III, a mad bomber is chasing Bruce Willis and Samuel L. Jackson. They must solve different puzzles or else things will explode and people will die.

Design

The WaterJug puzzle can be explained as follows:
You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug to capacity, (2) you can completely empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.

For this demonstration, we'll state that A has capacity 4 and B has capacity 3. Our goal, which we must complete in less than one minute, is to somehow get exactly 2 gallons of water in jug A. We need to find a set of operations, filling, emptying, and pouring, where we can reach this goal. One possible solution is as follows:

FILL A
POUR from A to B
EMPTY B
POUR from A to B
FILL A
POUR from A to B

We now have exactly 2 gallons of water jug A. (Try it!). Phew, we're still alive! Wouldn't it be nice to have a computer program to help us solve this? We can do that using Python, by simulating the physical world using mathematical calculations inside Objects called WaterJugs. Now let's design the general WaterJug class.

Each WaterJug will need to have two components that we can think of as the state of that WaterJug.

components:

Also, a WaterJug needs some functionality to change the state of the internal components. In object-oriented programming, these are called methods.

methods:

Components and Constructors

To create a class in Python, we begin with a new keyword class. 

  class WaterJug():

Our constructor sets up the components of the object, so it can be used later. In general, we bring in a parameter for each component and assign them to a piece of a special variable called self using dot notation.

But we must be careful with our methods, and also with our constructors, to make sure we don't violate the integrity of our class. In our constructor method, there could be serious problems when we're not careful. If we write the following constructor: 

     def __init__(self, cap, cont):
        self.capacity = cap
        self.contents = cont

We've opened ourselves up to a problem. A malicious user could call george = WaterJug(7, 23) , and we have a physically impossible WaterJug. We can avoid creating invalid WaterJug objects by raising an exception. 

     def __init__(self, cap, cont):
        if cap < 0 or cont < 0 or cap < cont:
           raise NameError("Invalid parameters for WaterJug")
        self.capacity = cap
        self.contents = cont

This exception can then be caught by whomever is using this class. These are things you need to watch for as a programmer. Be defensive.

The __str__ method

The next common method you will see in an instantiable object is the __str__ method. If we try to print a WaterJug without this method, we will only see <__main__.WaterJug instance at 0x90e7b0>

To get a better notion of the contents of this WaterJug, we can write the following method 

     def __str__(self):
        return "(" + str(self.capacity) + "," + str(self.contents) + ")"

Now, when we print a WaterJug, the output is (4,3) for a WaterJug with capacity 4 and contents 3.

The fill method

Let's work on the "fill" method next. We want to take a variable amount of water, changing the contents inside of the WaterJug, and return any overflow of water that will not fit. First, we somehow must update the contents, and this can be achieved by the line 

     def fill(self, amount):
        self.contents += amount
        return 0

This works fine when amount + self.contents <= self.capacity. However, it fails if amount + self.contents > self.capacity. So we must do more. 

     def fill(self, amount):
        self.contents += amount
        if self.contents >= self.capacity:
           overflow = self.contents - self.capacity
           self.contents -= overflow
           return overflow
        else:
           return 0

Wonderful, now we take care of the overflow when more is added than possible for this WaterJug to hold.

The empty method

For our empty method, we want to erase the contents from a WaterJug and return the contents. Now this can be a little tricky too, and and illustrates a basic idea in computer science, the swap. We can't simply return self.contents as our method body, since this misses the point of emptying a WaterJug, namely that the contents go to zero. Also, we cannot use the following code: 

     def empty(self):
        self.contents = 0
        return self.contents

We want to place a zero in contents and get back the value, but this code squashes the value of contents first. All we will ever return is zero. So we must do more. We need a temporary place to put the value of contents so that it is not squashed by our method, so we can swap zero and the value of contents. This temporary value can then be returned, and our method succeeds. 

     def empty(self):
        temp = self.contents
        self.contents = 0
        return temp

Puzzle Implementation

For this lab, you will implement a main function that allows the user to set up and then solve a WaterJugs puzzle. Your function should:

You never know when a Python class could save your life. And remember, "Think fast, Look alive, Die hard."

What to Hand In

Log in to cs.centenary.edu through either Secure FTP or WinSCP using your cs login and password. Create a subdirectory from csc207 called lab13. Copy your waterjug.py file into this directory. Make sure you have followed the Python Style Guide, and have run your project through the Automated Style Checker.

You must hand in:

© Mark Goadrich 2009, Centenary College of Louisiana