kartikkukreja

def depthLimitedDFS(problem, state, depth):
  if problem.isGoalState(state):
    return state[1]
  if depth <= 0:
    return None
  for move in problem.getSuccessors(state):
    solution = depthLimitedDFS(problem, move, depth-1)
    if solution is not None:
      return solution
  return None

kartikkukreja

from collections import deque
class Queue:
  def __init__(self):
    self.queue = deque()
	  
  def push(self, item):
    self.queue.append(item)
	  
  def pop(self):
    return self.queue.popleft()

kartikkukreja

class Stack:
  def __init__(self):
    self.stack = []

  def push(self, item):
    self.stack.append(item)

  def pop(self):        
    return self.stack.pop()

kartikkukreja

def graphSearch(problem, strategy):
  start = problem.getStartState()
  explored = set([start[0]])
  strategy.push(start)
  
  while not strategy.empty():
    node = strategy.pop()
    if problem.isGoalState(node):
      return node[1]
    for move in problem.getSuccessors(node):            

kartikkukreja

def treeSearch(problem, strategy):
  strategy.push(problem.getStartState())    
  while not strategy.empty():
    node = strategy.pop()
    if problem.isGoalState(node):
      return node[1]
    for move in problem.getSuccessors(node):            
      strategy.push(move)
  return None

kartikkukreja

class PacmanProblem:
  # grid is a 2D array
  # pacman & food are tuples (r,c)
  def __init__(self, grid, pacman, food):
    self.grid = grid
    self.rows = len(grid)
    self.columns = len(grid[0])
    self.pacman = pacman
    self.food = food
      

kartikkukreja

class SearchProblem:
  def __init__(self):
    # initialize
    
  def getStartState(self):
    # return start state
    
  def isGoalState(self, state):
    # return True if state is a goal state else False
    

kartikkukreja

def TreeSearch(problem, strategy):
  Initialize search tree using the state state of problem
  while True:
    if there are no candidates for expansion:
      return failure
    choose a leaf node for expansion according to strategy
    if the node contains a goal state:
      return the corresponding solution
    else:
      expand the node and add its successors to the search tree

kartikkukreja

struct SegmentTreeNode {
  int start, end; // this node is responsible for the segment [start...end]
  int count;
  bool pendingUpdate;
  
  SegmentTreeNode() : count(0), pendingUpdate(false) {}
  
  void assignLeaf(bool value) {}
  
  void merge(SegmentTreeNode& left, SegmentTreeNode& right) {

kartikkukreja

struct SegmentTreeNode {
  int start, end; // this node is responsible for the segment [start...end]
  ll total, pendingUpdate;
  
  SegmentTreeNode() : total(0), pendingUpdate(0) {}
  
  void assignLeaf(ll value) {
    total = value;
  }