1 files changed, 30 insertions, 36 deletions

diff --git a/search.py b/search.py
index c9c438e..e9a4b34 100644
--- a/search.py
+++ b/search.py
@@ -86,45 +86,39 @@ def depthFirstSearch(problem):
     print "Is the start a goal?", problem.isGoalState(problem.getStartState())
     print "Start's successors:", problem.getSuccessors(problem.getStartState())
     """
-    "*** YOUR CODE HERE ***"
-
-    def traverse(problem, node, visited):
-
-        # Add nextNode to visited list
-        visited.append(node[0])
 
-        # Recursive base case
+    # The only differences between the search functions:
+    # 1. Cost: Lambda function to get the total cost of a node
+    # 2. Nodes: Data structure to store the nodes
+    cost = lambda node: 1
+    nodes = util.Stack()
+    
+    # Initialize start node and push onto nodes, 
+    nodes.push((problem.getStartState(), None, 0, []))
+    
+    # Dictionary of visited nodes; key: node's (x,y); value: current cost of 
+    # actions to get to the node
+    visited = {}
+
+    while not nodes.isEmpty():
+        node = nodes.pop()
+
+        # If the node has been traversed by a cheaper path, skip it
+        if visited.has_key(node[0]) and visited[node[0]] <= cost(node):
+            continue
+
+        # Add set the value at the nodes index to the cost
+        visited[node[0]] = cost(node)
+
+        # Chech if the current node is the goal state and if it is, return the path
         if problem.isGoalState(node[0]):
-            return [node[1]]
-
-        pq = util.PriorityQueueWithFunction(lambda child: child[2])
-
-        # Get all successors and push them into a priority queue based on cost
-        children = problem.getSuccessors(node[0])
-        for nextNode in children:
-            # Check that nextNode has not been visited
-            if nextNode[0] in visited:
-                continue
-
-            # Push the child if it was not visited
-            pq.push(nextNode)
-
-        while not pq.isEmpty():
-            # Pop lowest cost child from the queue
-            nextNode = pq.pop()
-
-            # Recursive call to nextNode
-            path = traverse(problem, nextNode, visited)
-
-            # Check if recursive call returned values
-            if path != None:
-                # Check to not add the initial node
-                if node[1] != None:
-                    # Add the node the start of the list (reverse it)
-                    path.insert(0, node[1])
-                return path
+            return node[3]
 
-    return traverse(problem, (problem.getStartState(), None, 0), [])
+        # Get all successors, and set each nodes's path to previous node's 
+        # path + nextNode's direction and push it onto stack
+        for nextNode in problem.getSuccessors(node[0]):
+            nextNode = nextNode + (node[3] + [nextNode[1]],)
+            nodes.push(nextNode)
 
 
 def breadthFirstSearch(problem):