# CMPT $317$: Problem Class Template

# Copyright $($c$)2016-2019$ Michael C Horsch and Jeff Long,

# Department of Computer Science, University of Saskatchewan

# This file is provided solely for the use of CMPT $317$ students. Students are permitted

# to use this file for their own studies, and to make copies for their own personal use.

# This file should not be posted on any public server, or made available to any party not

# enrolled in CMPT $317.$

# This implementation is provided on an as$-$is basis, suitable for educational purposes only.

#

import random as rand

import math as math

class State$($object$)$:

def $\_\_$init$\_\_($self$,$ preceding$\_$action$)$:

$"""$

Initialize the State object.

$"""$

# each state MUST store the action that created it

# if you want to be able to actually see your solutions

self.action $=$ preceding$\_$action

pass

def $\_\_$str$\_\_($self$)$:

$"""$ A string representation of the State $"""$

return $""$

def $\_\_$eq$\_\_($self$,$ other$)$:

$"""$ Allows states to be compared"""

return False

class Problem$($object$)$:

$"""$The Problem class defines aspects of the problem.

One of the important definitions is the transition model for states.

To interact with search classes, the transition model is defined by:

is$\_$goal$($s$)$: returns true if the state is a goal state.

actions$($s$)$: returns a list of all legal actions in state s

result$($s$,$a$)$: returns a new state, the result of doing action a in state s

$"""$

def $\_\_$init$\_\_($self$,$ goal$)$:

$"""$ The problem is defined by a target value. We want to measure that many

liters of water.

:param goal: the number of liters of water we want to measure

$"""$

self.goal $=$ goal

# INSERT WHATEVER ELSE YOU NEED HERE

def create$\_$initial$\_$state$($self$)$:

$"""$ returns an initial state

$"""$

return None

def is$\_$goal$($self$,$ a$\_$state:State$)$:

$"""$Determine whether a$\_$state is a goal state"""

return False

def actions$($self$,$ a$\_$state:State$)$:

$"""$ Returns all the actions that are legal in the given state.

$"""$

return $[]$

def result$($self$,$ a$\_$state:State, an$\_$action$)$:

$"""$Implements the transition function.

Given a state and an action, return the resulting state.

$"""$

return None

# end of fileQuestion $2(5$ points$)$:

Purpose: To apply uninformed search algorithms

AIMA Chapter$($s$)$: $3\mathrm{.}1-3\mathrm{.}4$

For this question. your task is to impelement the Water Jugs problem as a search problem.

You have been provided with several Python files. These include a generalized, object$-$oriented imple$-$

mentations of the basic search algorithms below.

Breadth$-$first $($BFS$)$

Depth$-$first $($DFS$)$

Iterative$-$deepening $($IDS$)$

Each of the algorithms above can be run using either the Tree search or Graph search variants.

The only file you need to CHANGE is

WaterJugs.py$.$ This file implements both the State and Problem

classes that are used by the search algorithms. The provided version of

WaterJugs.py contains only

method headers. You need to implement these methods correctly to capture the specific dynamics of

the Water Jugs problem, using your understanding of search problem encoding and of AIMA Chapter $3.$

When you are done, you can test your implementation by running see$\_$solutions $.$py with the following

arguments:

python see$\_$solutions.py $1$ ids graph $10$

If everything is working correctly, this should find a solution to the Water Jug problem for the target value

of $1$ liter.

However, BEFORE you do this, it is crucial that you ensure your state and problem implementation is cor$-$

rect. Testing via search is a BAD idea, as the search may examine thousands or even millions of nodes.

A simple example of a test file is provided to give you some testing ideas. You don't need to hand in this

testing. but there is virtually no chance that your implementation will be correct if you don't do it$.$

Hint: By far the most common problem in implementing a search problem is "not copying things that

need to be copied" when you create a new state. For example, recall that in Python, you can easily create

a $($shallow$)$ copy of a list like so:

new$\_$list $-[$x for $x$ in old$\_$list$]$

Some students are tempted to use built$-$in Python methods like $.$deepcopy, but this can be extraordinarily

inefficient if called blindly. Making manual copies with list comprehensions and copying only what you

need usually works out much better.

What to Hand In

Your problem implementation in a file called WaterJugs $.$ py$.$ You do NOT need to re$-$hand$-$in any of

the other provided files.

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

$5$ marks: Your implementation of the State and Problem classes are correct