reset password
Author Message
dan2430
Posts: 5
Posted 17:29 Sep 12, 2019 |

I'm trying to run the auto grader but its giving me an error on depth first search and breadth first search.

It seems like the test cases uses letters instead of numbers for coordinates? If that is the case would I have to rewrite my search functions to work with the auto grader?

 

 

It works fine on the pacman search examples

Last edited by dan2430 at 17:30 Sep 12, 2019.
kmarlis
Posts: 35
Posted 17:47 Sep 12, 2019 |

One thing is to make sure you are returning a list of actions. You build up that list of actions by calling problem.getSuccessors() which is an iterable of tuples: (successor, action, stepCost). Make sure you are adding just the action to the list. If it helps, here's what a successful implementation results in:

 

Last edited by kmarlis at 17:48 Sep 12, 2019.
sdo8
Posts: 54
Posted 18:15 Sep 12, 2019 |

The autograder uses both the pacman game and graph searches to test your code.

For example, on small maze, Pacman's starting state: in this case, consists of just a (x, y) coordinate, which is (5,5).

The children of this state are ((4,5), 'West', 1) and ((5,4),'South', 1).. which are the only two available children that aren't walls.

This is the same as a triple with 3 elements.. (next coordinate as a tuple, direction as a string, and cost as an int)

When you add these children to your stack and pop them off, you are changing states from (5,5) to (4,5) or (5,4) - depending on your search or tie-breaking.

With the Graph search, the state is represented with just a character 'A' or 'B'.. etc. instead of a coordinate (5,4). 

Using the graph_backtrack.test, If you start off with 'A', you look at its children..  (('B', '0:A->B', 1.0), ('C', '1:A->C',2.0), ('D', '2:A->D', 4.0)).. 

It's in the same format as a triple with 3 elements.. (simply a char as state, direction as string, and cost as double), so your DFS should be able to handle the graph search as well.

 

Hope this helps.

rabbott
Posts: 1649
Posted 18:22 Sep 12, 2019 |

The error message (unsupported operand types for -: str - str) says that you are trying to subtract one string from another.

It refers to the line where you are creating a tuple by subtraction: tupe = (prev[0]-cur[0], prev[1]-cur[1]).

Check out that line and see what you are really subtracting. What are the components of prev and cur?

The first test case for Q1 is in test_cases/q1: the graph-backtract.test.

In this example, the nodes are not points on a grid; they are simply nodes with labels: A, B, C, D, G. Code written to assume that it is always dealing with nodes that are characterized by x-y coordinates stored in a tuple will run into problems.

Last edited by rabbott at 20:05 Sep 12, 2019.
dan2430
Posts: 5
Posted 18:35 Sep 12, 2019 |

Okay my problem was I was assuming we would only be working with coordinates in tuple format. My algorithm finds the correct path in coordinates and then does some tuple math to return the correct actions, hence the string subtraction . I understand the full problem now