That was wrong. Here is some of my code: $\text{'}\text{'}\text{'}$

CMSI $2130-$ Homework $1$

Author:

Modify only this file as part of your submission, as it will contain all of the logic

necessary for implementing the A$*$ pathfinder that solves the target practice problem.

$\text{'}\text{'}\text{'}$

import queue

from dataclasses import $*$

from typing import $*$

import heapq

from maze$\_$problem import MazeProblem

from dataclasses import dataclass

from typing import Optional, List, Tuple, Dict

from typing import List, Tuple

@dataclass

class SearchTreeNode:

player$\_$loc: Tuple$[$int$,$ int$]$

action: str

parent: Optional$["$SearchTreeNode$"]$

# TODO: Add any other attributes and method overrides as necessary!

cost: int $=0$

total$\_$cost: int $=0$ # g$($n$)$ path cost $+$ h$($n$)$ future cost

def $\_\_$lt$\_\_($self$,$ other$)->$ bool:

return self.total$\_$cost $$ other.total$\_$cost

def $\_\_$eq$\_\_($self$,$ other$)->$ bool:

return self.total$\_$cost $==$ other.total$\_$cost # and self.player$\_$loc $==$ other.player$\_$loc

def $\_\_$str$\_\_($self$)->$ str:

return f$"$@: $\{$self$.$player$\_$loc$\},$ cost: $\{$self$.$cost$\}"$

def heuristic$($current: Tuple$[$int$,$ int$],$ goal: Tuple$[$int$,$ int$])->$ int:

return abs$($current$[0]-$ goal$[0])+$ abs$($current$[1]-$ goal$[1])$

def pathfind$($problem: "MazeProblem"$)->$ Optional$[$list$[$str$]]$:

targets$\_$left $=$ problem.get$\_$initial$\_$targets$()$

frontier: List$[$SearchTreeNode$]=[]$

initial$\_$state $=$ SearchTreeNode$($problem$.$get$\_$initial$\_$loc$(),"",$ None, $0,0)$

frontier.append$($initial$\_$state$)$

graveyard: Set$[$Tuple$[$Tuple$[$int$,$ int$],$ int$]]=$ set$()$

while frontier:

current$\_$node $=$ frontier.pop$(0)$

# Process neighbors

neighbors $=$ problem.get$\_$transitions$($current$\_$node.player$\_$loc, targets$\_$left$)$

for action, transition in neighbors.items$()$:

next$\_$loc $=$ transition$["$next$\_$loc"$]$

cost $=$ current$\_$node.cost $+$ transition$["$cost$"]$

targets$\_$hit $=$ transition$["$targets$\_$hit"$]$

# Update remaining targets

new$\_$targets$\_$left $=$ targets$\_$left $-$ targets$\_$hit

# Check if all targets are destroyed

if not new$\_$targets$\_$left:

solution$\_$path: List$[$str$]=[]$

while current$\_$node.parent is not None:

solution$\_$path.insert$(0,$ current$\_$node.action$)$

current$\_$node $=$ current$\_$node.parent

return solution$\_$path

# Calculate total cost with heuristic

total$\_$cost $=$ cost $+$ heuristic$($next$\_$loc, current$\_$node.player$\_$loc$)$

# Create a new search tree node

new$\_$node $=$ SearchTreeNode$($next$\_$loc, action, current$\_$node, cost, total$\_$cost$)$

# Check if this state has been visited before

state$\_$signature $=($new$\_$node.player$\_$loc, len$($new$\_$targets$\_$left$))$

if state$\_$signature not in graveyard:

frontier.append$($new$\_$node$)$

graveyard.add$($state$\_$signature$)$

return None # If no solution found

Now please edit my code to have the tests come out right. I only go the nosoultions $(2/8$ tests passed$)$ but need $8/8$ to be passed.

DO NOT MODFIY ANYTHING FROM BELOW. Just above code

maze$\_$problem.py

def get$\_$initial$\_$loc $($self$)->>$ tuple$[$int$,$ int$]$:

Returns the player"s starting position in the maze $("$g$").$

Returns:

tuple$[$int$,$ int$]$:

The player's starting location in the maze: $($col$,$ row$)=($x$,$y$).$

$"$n$=$

def get$\_$goal$\_$loc $($self$)->$ tuple$[$int$,$ int$]$:

$""=$

Returns the location of the goal that must be reached.

Returns:

tuple$[$int$,$ int$]$:

The goal's location tuple: $($col$,$ row$)=($x$,$y$).$

n$"$

def get$\_$transitions$($self$,$ player$\_$loc: tuple$[$int$,$ int$])->$ dict:

Returns a dictionary describing all possible transitions that a player may take from their

given position.

Parameters:

player$\_$loc$($tuple$[$int$,$ int$])$:

The current location of the player in the maze.

Returns:

dict:

A dictionary whose keys are the possible actions fron the given player$\_$loc, with mapped

values next$\_$loc $($tuple$[$int$,$ int$])$ values that show the player's location after taking that action.

Exanple:

For example, if only the actions $"$ D$","$U$",$ and $"$L$"$ were possible from the current player$\_$loc of $(3,3),$

we might see an output of:

$\{$

$"$D$"$:$(3,4),$

$"$U$"$: $(3,2),$

$"$L$"$:$(2,3)$

$\}$