What is this program doing?

BELOW CODE IS MAIN

from Structure import Structure from PriorityQueue import PriorityQueue

class State: def __init__(self): self.cost = 0 self.parent = None self.parent_action = None def get_actions(self): return [] def get_cost(self,action): return 1 def apply_action(self,action): child = self.copy() child.cost = self.cost + self.get_cost(action) child.parent = self child.parent_action = action return child def is_goal(self): return False def __hash__(self): return 0 def __str__(self): return "the state" def copy(self): return State() def print_history(self): if self.parent is not None: self.parent.print_history() print(self.parent_action) print(self)

class VacuumWorld(State): def __init__(self,pos,floor): super().__init__() self.pos = pos self.floor = floor def get_actions(self): actions = ['suck'] if self.pos != 0: actions.append('left') if self.pos != len(self.floor)-1: actions.append('right') return actions def get_cost(self,action): if action == 'suck': return 2 else: return 1 def apply_action(self,action): next = super().apply_action(action) if action == 'left': next.pos = next.pos - 1 elif action == 'right': next.pos = next.pos + 1 elif action == 'suck': next.floor = next.floor[0:next.pos]+' '+next.floor[next.pos+1:] return next def __str__(self): output = ' '*self.pos output += '^ ' output += self.floor return output def is_goal(self): return '*' not in self.floor def __hash__(self): return hash((self.pos,self.floor)) def __eq__(self,other): return self.pos == other.pos and self.floor == other.floor def copy(self): copy = VacuumWorld(self.pos,self.floor) return copy

''' 1) Put start state into structure and seen list 2) Get state from structure if structure is empty return failure 3) Check if state is the goal state if so return that state as the answer 4) Get children of state 5) For each child: if not yet seen, add to seen list and structure 6) Go back to 2 ''' def search(structure,start_state,weight_f): seen = set() structure.add(start_state,weight_f(start_state)) seen.add(start_state) while not structure.is_empty(): current = structure.remove() if current.is_goal(): return current actions = current.get_actions() for action in actions: child = current.apply_action(action) if child not in seen: seen.add(child) structure.add(child,weight_f(child)) return False

class Stack(Structure): def __init__(self): self.stack = [] def add(self,thing,weight): self.stack.append(thing) def remove(self): return self.stack.pop() def is_empty(self): return len(self.stack)==0

def dummy_weight(state): return 0

def cost_weight(state): return state.cost

def vw_huerisitic1(state): return 3*(state.floor.count("*"))

test1_start = VacuumWorld(1," * * ") test1_dfs_answer = search(Stack(),test1_start,dummy_weight) test1_cfs_answer = search(PriorityQueue(),test1_start,cost_weight) test1_bfs_answer = search(PriorityQueue(),test1_start,vw_huerisitic1)

-----------------------------------------

BELOW CODE IS PRIORITY QUEUE

import heapq from Structure import Structure

class PriorityQueue(Structure): # Requires a hashing function which takes the values # and returns a hashable data object like a tuple. def __init__(self): self.h = [] self.d = dict() self.rd = dict()

# Inserts the value into the PriorityQueue with the given weight. def add(self,value,weight): self.rd[hash(value)] = weight if weight in self.d: self.d[weight].append(value) else: self.d[weight]=[value] heapq.heappush(self.h,weight)

# Removes the smallest element of the PriorityQueue # Returns None if PriorityQueue is empty def remove(self): if self.is_empty(): return None leastweight = self.h[0] values = self.d[leastweight] if len(values) == 1: heapq.heappop(self.h) del self.d[leastweight] retval = values[0] else: retval = values.pop() del self.rd[hash(retval)] return retval

# True if empty, False otherwise def is_empty(self): return len(self.h) == 0

# Changes the weight of the value to newweight # Note that this is O(n) due to the call to index # or remove. def reweight(self,value,newweight): hashval = hash(value) oldweight = self.rd[hashval] del self.rd[hashval] values = self.d[oldweight] if len(values) == 1: i = self.h.index(oldweight) self.h[i] = self.h[-1] self.h.pop() if i < len(self.h): heapq._siftup(self.h, i) heapq._siftdown(self.h,0,i) del self.d[oldweight] else: values.remove(value) self.insert(value,newweight) ------------------------------------

BELOW CODE IS STRUCTURE

class Structure: def add(self,thing,weight): return 0 def remove(self): return 0