Old version
This is the CS 111 site as it appeared on May 10, 2018.
Final Project FAQ
If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.
General questions
-
What parts of the project should we submit for Problem Set 10?
You should submit parts I and II from the final project. Be sure to submit your work for these parts of the project in the Problem Set 10 section of Apollo.
-
Are comments needed for each method/function?
As always, please include docstrings. You should also include comments for portions of your code if they might be hard to understand without the comments.
Part I
-
In the
Board
class, does thetiles
attribute have to be a 2-D list of integers, or can it contain strings?It must be a 2-D list of integers, with 0 representing the blank cell. For example, let’s say that you construct a
Board
object as follows:>>> b = Board('012345678')
If you then evaluate its
tiles
attribute, here is what you should see:>>> b.tiles [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
You should not see the following:
>>> b.tiles [['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']]
If you do, you should fix your code.
-
What should our
move_blank
method do if a direction other than'left'
,'right'
,'up'
, or'down'
is passed in for the input?It should print an error message (see the example cases for the format of the message) and return
False
, without making any changes to the object. Make sure that you don’t try to return the error message. It should be printed, and then you should returnFalse
.
Part II
-
In the
__init__
method for theState
class, how can we determine the number of moves of the predecessor?Keep in mind that the predecessor is also a
State
object. Therefore, you can access itsnum_moves
attribute using dot notation.For example, if
p
is the predecessor, you would dop.num_moves
. You should replacep
with the appropriate expression for the predecessor. -
In the
is_goal
method, how can I access the tiles in theBoard
object associated with theState
object?Inside any
State
method,self.board
will give us access to theBoard
object associated with theState
object. And becausetiles
is an attribute of theBoard
object, you can use the following expression to access the tiles:self.board.tiles
-
In the
generate_successors
method, what should we use as the input for the predecessor when we construct the newState
object?As the hints provided for this method suggest, you should use the variable
self
for the predecessor, since the current state (the one represented by the called objectself
) is itself the predecessor of the new state. -
In the
generate_successors
method, when I try to add a successor to the list of successors, I get an error that saysState object is not iterable
. What am I doing wrong?When you use the
+
or+=
operator to add aState
object to the list of successors, you need to perform list concatenation – adding one list to another list. As a result, you need to make sure that you put square brackets[]
around theState
object. -
My
generate_successors
method doesn’t produce the expected results. What am I doing wrong?One thing worth checking: Make sure that you aren’t mistakenly calling
move_blank()
twice for a given move.Each call to
move_blank()
does up to two things: if the move is possible, it modifies the contents of theBoard
object, and it also returns eitherTrue
orFalse
to indicate whether the move was possible. As a result, you should only call it once per move. However, many people have been mistakenly calling it twice per move: once to check if the move is possible, and once to make the move.For example, this is not correct:
# don't do this! if b.move_blank(direction) == True: b.move_blank(direction) # no! this moves the blank again! s = State(b, ...) ...
Rather, you should do this instead:
# do this instead! if b.move_blank(direction) == True: s = State(b, ...) ...
Part III
-
My
should_add
method doesn’t seem to work correctly for the case in which the inputstate
would create a cycle. I don’t see any errors in myshould_add
. Is it possible that the providedcreates_cycle
method has a bug?No! However, it is possible that the problem actually goes back to one of your
Board
methods. Thecreates_cycle
method compares twoBoard
objects to check for a cycle, so if one of yourBoard
methods is making an improper change to aBoard
object, then it’s possible that twoBoard
objects that should be considered equal are actually considered unequal.Here’s one piece of test code that could help you to diagnose the problem:
>>> b = Board('012345678') >>> b.tiles [[0, 1, 2], [3, 4, 5], [6, 7, 8]] >>> b.move_blank('right') True >>> b.tiles [[1, 0, 2], [3, 4, 5], [6, 7, 8]]
Make sure that the 2-D lists that you get for
b.tiles
match the ones that you see above. In particular, make sure that all of the elements of the lists are integers, not strings. If your results forb.tiles
are not correct, check your__init__
andmove_blank
methods.Other possible sources of the problem are: (1) the
__eq__
,copy
, anddigit_string
methods in theBoard
class, and (2) the__init__
andgenerate_successors
methods in theState
class, which might be failing to set up an appropriate connection between aState
object and its predecessor. Here is some additional test code that may help you to diagnose the problem:>>> b = Board('012345678') >>> b.tiles [[0, 1, 2], [3, 4, 5], [6, 7, 8]] >>> b.digit_string() '012345678' >>> b.tiles [[0, 1, 2], [3, 4, 5], [6, 7, 8]] >>> b2 = b.copy() >>> b2.tiles [[0, 1, 2], [3, 4, 5], [6, 7, 8]] >>> b.tiles [[0, 1, 2], [3, 4, 5], [6, 7, 8]] >>> s = State(b, None, 'init') >>> s.predecessor == None True >>> succ = s.generate_successors() >>> succ [312045678-down-1, 102345678-right-1] >>> succ[0].predecessor 012345678-init-0 >>> succ[1].predecessor 012345678-init-0
Part IV
-
How can we determine which state has been in the list the longest?
Try tracing through some examples on paper of adding states–one at a time–to the list, and think about which of them should be removed if you want the one that has been in the list the longest.
-
Our
DFSearcher
works for all the tests cases except the one that imposes a depth limit (the third test case). How can I figure out what is going wrong?Here are a few things to check:
-
Is your
DFSearcher
‘s depth limit being set properly? Try this from the Shell:>>> d = DFSearcher(25) >>> d.depth_limit 25
If you don’t see 25, then you should take a look at how you are constructing a
DFSearcher
. If your class is simply using the constructor inherited fromSearcher
, then check to ensure that theSearcher
constructor is properly initializing thedepth_limit
attribute. -
Is the
should_add()
method that you defined in theSearcher
class—and that yourDFSearcher
should simply inherit – dealing appropriately with states that are beyond the depth limit? Here’s some test code:>>> d = DFSearcher(25) >>> s = State(Board('012345678'), None, 'init') >>> s.num_moves = 26 # artificially change the number of moves >>> d.should_add(s) False
If you don’t see
False
, then fix yourshould_add()
method inSearcher
and/or make sure thatDFSearcher
is simply using the inherited version ofshould_add()
and not defining its own version. -
Is
should_add()
being properly called in the context of aDFSearcher
‘s execution offind_solution()
? In Part III, we indicated thatadd_states()
inSearcher
should useshould_add()
to decide whether to add a state. Is youradd_states()
doing that? Is yourDFSearcher
simply using the inheritedadd_states()
as it should?
-
-
When I try to use the
eight_puzzle
driver function to test my Greedy and A* searchers, I receive an error that saysTypeError: 'int' object is not callable
. How can I fix this?When you use
eight_puzzle()
to test Greedy or A*, you need to make sure to pass in the heuristic function as the third input, rather than a depth limit. For example:>>> eight_puzzle('142358607', 'A*', h1)
We recently updated the assignment to emphasize this fact.
-
My
GreedySearcher
class passes the tests that are given in task 4 of Part IV, but when I try to use Greedy Search in the context of theeight_puzzle
driver function in task 6, I’m getting an error that says that a ‘State’ object does not support indexing. What I am doing wrong?The problem may actually be in your
Searcher
class, sinceGreedySearcher
inherits fromSearcher
. In particular, make sure that theadd_states
method inSearcher
calls theadd_state
method to add each new state toself.states
. It should not add the individual states on its own (e.g., by performing list concatenation).The reason that this matters is that
GreedySearcher
overrides the version ofadd_state()
that it inherits fromSearcher
, but it doesn’t override the inherited version ofadd_states
. As a result, ifadd_states()
doesn’t calladd_state()
as it should, theGreedySearcher
version ofadd_state()
won’t get called, and thus the list of states won’t include the priorities as required.
Part V
-
How do I read from a file?
In lecture, we presented two different ways to read the contents of a file. You can consult the lecture notes from a couple weeks ago or check out the example code online. For the project, we recommend reading in the file one line at a time using a
for
loop. -
I’ve completed my
process_file
function, and I’m performing the initial tests that you recommend using the10_moves.txt
file. Although my earlier tests of BFS all went fine, I’m getting non-optimal solutions when I perform BFS usingprocess_file
. Do you have any suggestions for how to find the problem?Yes! Make sure that you create a new searcher object for each puzzle (i.e., for each line of the file). Otherwise, the searcher will still have information inside it from previous searches when it starts to solve a new puzzle.
-
When I test the
process_file
function using the10_moves.txt
file. I’m able to reproduce the results for BFS, but I don’t get the same results for Greedy. Is that a problem?Probably. When you first implemented the
GreedySearcher
class in Part IV, task 4, if you got the same results as we did for the examples that we provided, then you should get more or less the same results here as well. The only possible exception is the number of searches that you choose to terminate.If your results don’t match ours, one thing to double check is your
num_misplaced
method in theBoard
class. Here are some additional test cases for that method that should help you to ensure that it’s working correctly in all cases:>>> b = Board('012345678') >>> b.num_misplaced() 0 >>> b.move_blank('right') True >>> b.num_misplaced() 1 >>> b.move_blank('down') True >>> b.num_misplaced() 2 >>> b.move_blank('left') True >>> b.num_misplaced() 3 >>> b.move_blank('up') True >>> b.num_misplaced() 3
-
My
h2
heuristic function still doesn’t allow A* to solve the 24-move or 27-move puzzles in a reasonable amount of time. Is that okay?Probably. To ensure that your
h2
heuristic is good enough, try comparing it toh1
in the context of puzzles that require fewer moves. For example:>>> process_file('15_moves.txt', 'A*', h1) >>> process_file('15_moves.txt', 'A*', h2)
When you look at the results of these two calls, you should see that:
-
using
h2
allows A* to test fewer states than it does when it usesh1
-
the
h2
solutions are still optimal (i.e., they require the specified number of moves).
If both of these things are true, then your
h2
is good enough! -