def search_in(transitions, visited, path, pos, goal):
  """ Recursive helper for depth-first search. Takes transition map, set of visited
    positions, list of path thus far, the next step to consider, and a goal. Returns
    a complete path to goal or None if no path found from this start state. """
  # If we're about to go someplace we've been, it's a loop: no path to goal
  if pos in visited:
    return None
  # Add pos to visited locations and path thus far
  visited.add(pos)
  path.append(pos)
  # If pos is the goal, we're done
  if pos == goal:
    return path
  # For each adjacent position, try moving there
  for next in transitions[pos]:
    r = search_in(transitions, visited, path, next, goal)
    if r:
      return r
  # If we get here, none of these led to the goal, so pos is a bad path, retrace by
  # removing pos from path & visited, then returning failure
  path.pop()
  visited.remove(pos)
  return None