Using Breadth-First Search to solve the rabbit crossing river puzzle

rabbit_puzzle_bfs_solver.py

'''
Using Breadth-First Search to solve the rabbit crossing river puzzle
'''

from collections import deque

def goal_test(stones, state):
  if state[0] >= len(stones) -1:
    return True
  return False

def is_legal(stones, state):
  pos = state[0]
  if pos >= 0 and state[1] > 0:
    if pos >= len(stones) or stones[pos] == 1:
      return True
  return False

# initial_state = (initial position of rabbit, initial speed of rabbit)
def bfs_rabbit(stones, initial_state):
  frontier = deque([(initial_state, [])])  #  node is (state, solution path)
  explored = set([])
  
  actions = [(1,0), (1,-1), (1,1), (-1,0), (-1,-1), (-1, 1)] # each action is (direction, speed_change) 
  
  while (frontier):
    node = frontier.popleft()
    if goal_test(stones, node[0]):
      print 'solution found:'
      print node[1]
      return
    explored.add(node[0])
    for a in actions:
      new_pos = node[0][0] + a[0]*node[0][1]
      new_speed = node[0][1] + a[1]
      child_state = (new_pos, new_speed)
      if is_legal(stones, child_state):
        if child_state not in explored: 
          frontier.append((child_state, node[1] + [(a, child_state)])) # solution path is a list of (action taken, (new position, new speed))
  
  print 'solution not found'
  return

# a few test cases
bfs_rabbit([1,1,0,1,1,0,0,1,0,1,0,1,1], (-1, 1))
bfs_rabbit([1,0,1,0,0,1,0,1,0,1,0,1,1], (-1, 1))
bfs_rabbit([1,1,0,0,0,1,0,1,0,1,0,1,1], (-1, 1))