-
-
Save jamiees2/5531924 to your computer and use it in GitHub Desktop.
| # Enter your code here. Read input from STDIN. Print output to STDOUT | |
| class Node: | |
| def __init__(self,value,point): | |
| self.value = value | |
| self.point = point | |
| self.parent = None | |
| self.H = 0 | |
| self.G = 0 | |
| def move_cost(self,other): | |
| return 0 if self.value == '.' else 1 | |
| def children(point,grid): | |
| x,y = point.point | |
| links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]] | |
| return [link for link in links if link.value != '%'] | |
| def manhattan(point,point2): | |
| return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0]) | |
| def aStar(start, goal, grid): | |
| #The open and closed sets | |
| openset = set() | |
| closedset = set() | |
| #Current point is the starting point | |
| current = start | |
| #Add the starting point to the open set | |
| openset.add(current) | |
| #While the open set is not empty | |
| while openset: | |
| #Find the item in the open set with the lowest G + H score | |
| current = min(openset, key=lambda o:o.G + o.H) | |
| #If it is the item we want, retrace the path and return it | |
| if current == goal: | |
| path = [] | |
| while current.parent: | |
| path.append(current) | |
| current = current.parent | |
| path.append(current) | |
| return path[::-1] | |
| #Remove the item from the open set | |
| openset.remove(current) | |
| #Add it to the closed set | |
| closedset.add(current) | |
| #Loop through the node's children/siblings | |
| for node in children(current,grid): | |
| #If it is already in the closed set, skip it | |
| if node in closedset: | |
| continue | |
| #Otherwise if it is already in the open set | |
| if node in openset: | |
| #Check if we beat the G score | |
| new_g = current.G + current.move_cost(node) | |
| if node.G > new_g: | |
| #If so, update the node to have a new parent | |
| node.G = new_g | |
| node.parent = current | |
| else: | |
| #If it isn't in the open set, calculate the G and H score for the node | |
| node.G = current.G + current.move_cost(node) | |
| node.H = manhattan(node, goal) | |
| #Set the parent to our current item | |
| node.parent = current | |
| #Add it to the set | |
| openset.add(node) | |
| #Throw an exception if there is no path | |
| raise ValueError('No Path Found') | |
| def next_move(pacman,food,grid): | |
| #Convert all the points to instances of Node | |
| for x in xrange(len(grid)): | |
| for y in xrange(len(grid[x])): | |
| grid[x][y] = Node(grid[x][y],(x,y)) | |
| #Get the path | |
| path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid) | |
| #Output the path | |
| print len(path) - 1 | |
| for node in path: | |
| x, y = node.point | |
| print x, y | |
| pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ] | |
| food_x, food_y = [ int(i) for i in raw_input().strip().split() ] | |
| x,y = [ int(i) for i in raw_input().strip().split() ] | |
| grid = [] | |
| for i in xrange(0, x): | |
| grid.append(list(raw_input().strip())) | |
| next_move((pacman_x, pacman_y),(food_x, food_y), grid) |
Ok, can I see the error log and source code (literally the file you are using)?
Also, on which OS are you on? I'm on Linux. The reason I ask this is bc I'm trying to replicate the error so I can understand what is happening ok.
I'm on Windows . And below is the source code
class Node:
def init(self,value,point):
self.value = value
self.point = point
self.parent = None
self.H = 0
self.G = 0
def move_cost(self,other):
return 0 if self.value == '.' else 1
def children(point,grid):
x,y = point.point
links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
links = []
for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:
links.append(grid[d[0]][d[1]])
def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])
def aStar(start, goal, grid):
#The open and closed sets
openset = set()
closedset = set()
#Current point is the starting point
current = start
#Add the starting point to the open set
openset.add(current)
#While the open set is not empty
while openset:
#Find the item in the open set with the lowest G + H score
current = min(openset, key=lambda o:o.G + o.H)
#If it is the item we want, retrace the path and return it
if current == goal:
path = []
while current.parent:
path.append(current)
current = current.parent
path.append(current)
return path[::-1]
#Remove the item from the open set
openset.remove(current)
#Add it to the closed set
closedset.add(current)
#Loop through the node's children/siblings
for node in children(current,grid):
#If it is already in the closed set, skip it
if node in closedset:
continue
#Otherwise if it is already in the open set
if node in openset:
#Check if we beat the G score
new_g = current.G + current.move_cost(node)
if node.G > new_g:
#If so, update the node to have a new parent
node.G = new_g
node.parent = current
else:
#If it isn't in the open set, calculate the G and H score for the node
node.G = current.G + current.move_cost(node)
node.H = manhattan(node, goal)
#Set the parent to our current item
node.parent = current
#Add it to the set
openset.add(node)
#Throw an exception if there is no path
raise ValueError('No Path Found')
def next_move(pacman,food,grid):
#Convert all the points to instances of Node
for x in xrange(len(grid)):
for y in xrange(len(grid[x])):
grid[x][y] = Node(grid[x][y],(x,y))
#Get the path
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
#Output the path
print len(path) - 1
for node in path:
x, y = node.point
print x, y
pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]
grid = []
for i in xrange(0, x):
grid.append(list(raw_input().strip()))
next_move((pacman_x, pacman_y),(food_x, food_y), grid)
Stdin: 0 0
3 3
4 4
..%.
..%.
%...
....
Error after executing the above code:
Traceback (most recent call last):
File "main.py", line 15, in
for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:
NameError: name 'x' is not defined
Ok.. so.. just to clarify bc this gave such a headache when I looked at it (no kidding). You do indent your code right?
About this error log, (which is not a syntax error anymore), x is not defined. Ok.
Which kind of program are you using to compile the code? Is it really native python from command line, or some kind of framework?
You see, (from the code you gave me), you define x and y at the line 12 like this:
x,y = point.point
The variable point is a tuple, holding data like (0,1). So this operation should just define x as 0, and y as 1.
Try to change this line to:
x = point.point[0]
y = point.point[1]
Maybe it's your compiler's fault this time, because it should be working.
Now, other than this, be careful about indentation. One single tab placed in the wrong line can basically break the code.
In case of trouble, here's the author's code (with a few modifications of my part). I tested it right now, and it is working (at least on my pc :D)
# Enter your code here. Read input from STDIN. Print output to STDOUT
class Node (object):
def __init__(self,value,point):
self.value = value
self.point = point
self.refresh()
def refresh(self):
self.parent = None
self.H = 0
self.G = 0
def move_cost(self,other):
return 0 if self.value == '.' else 1
def children(point,grid):
x,y = point.point
links = []
# for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:
for i in [x-1, x, x+1]:
for j in [y-1, y, y+1]:
if i != x or j != y:
if (i >= 0 and j >= 0 and i < len(grid) and j < len(grid[0])):
links.append(grid[i][j])
ret = [link for link in links if (link.value != '%')]
return ret
def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[1])
def aStar(start, goal, grid):
#The open and closed sets
openset = set()
closedset = set()
#Current point is the starting point
current = start
#Add the starting point to the open set
openset.add(current)
#While the open set is not empty
while openset:
#Find the item in the open set with the lowest G + H score
current = min(openset, key=lambda o:o.G + o.H)
#If it is the item we want, retrace the path and return it
if current == goal:
path = []
while current.parent:
path.append(current)
current = current.parent
path.append(current)
return path[::-1]
#Remove the item from the open set
openset.remove(current)
#Add it to the closed set
closedset.add(current)
#Loop through the node's children/siblings
for node in children(current,grid):
#If it is already in the closed set, skip it
if node in closedset:
continue
#Otherwise if it is already in the open set
if node in openset:
#Check if we beat the G score
new_g = current.G + current.move_cost(node)
if node.G > new_g:
#If so, update the node to have a new parent
node.G = new_g
node.parent = current
else:
#If it isn't in the open set, calculate the G and H score for the node
node.G = current.G + current.move_cost(node)
node.H = manhattan(node, goal)
#Set the parent to our current item
node.parent = current
#Add it to the set
openset.add(node)
#return empty list, as there is not path leading to destination
return []
def next_move(pacman,food,grid):
#Convert all the points to instances of Node
for x in xrange(len(grid)):
for y in xrange(len(grid[x])):
grid[x][y] = Node(grid[x][y],(x,y))
#Get the path
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
#Output the path
print len(path) - 1
for node in path:
x, y = node.point
print x, y
pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]
grid = []
for i in xrange(0, x):
grid.append(list(raw_input().strip()))
next_move((pacman_x, pacman_y),(food_x, food_y), grid)
Damn! Now this was srsly a headache and after so much efforts (yours obviously) it did worked !! Thank you so much 🤝
@anshika99 @carlHR Isn't Line 51 a bug? if node.G > new_g:
Here, node is an element from children.
Now, in line 53: node.G = new_g when you update the G value, it is updating the G value of an element of children, not of the desired element in openset
The aim was to update the G value of node in openset, in case the node was already present in the openset. For this update process, we should get to point the element in openset. But this is not happening. For all getting the output, this is because your example didn't hit such case where an update was needed.
Moreover, you cannot update any element of a set. (referring to openset)
Getting error: TypeError: unhashable type: 'Node'
when trying to add start node to openset Set.
Any idea how to overcome this ?
In line 51, you are checking to see if there's a better path to reach the child node from tge current node. Just check the algorithm's Wikipedia page to understand.
In line 53 we are updating it. Node is just reference to data in memory, like C pointers. It is not a copy from the openset element, it is a reference to the element itself. Confusing, but yeah, it's python, it's implicit.
About your error.. don't know much without seeing the full code.
The reason of why I want to see your code is because you might have modified something, even if just a line or a variable, and it might have some impact over the full code. After all, as the old ones said: "In my PC at home the code works, not sure why on yours it doesn't".
Why the aStar function is calling four times in next_move function?
If you are referring to my version, not the author's one, the answer I should give you is: my bad. I can't remember what I was trying to do at the time, maybe I just clicked the ctrl+v shortcut a few times by mistake. I just can't see a reason for executing 4 times the same thing.
I've tried and tested everything on python 2.7, but it is still not executing..