foob​​ar 失败测试用例 - a* 带有易碎墙

Question

正在处理 google foo-bar 挑战，我被困在一个失败的测试用例上（这是一个隐藏的测试用例 - 所以我无法直接看到问题所在）

基本上，该测试是一个具有单个易碎墙的迷宫解算器的实现。

我正在进行修改后的 a* 搜索 - 为包含断墙的路径使用布尔标志，这样当它到达第二堵墙时（沿着有断墙的路径）它会跳过该路径.

我已经检查了这段代码，但我似乎看不到错误（即使有错误 - 在这一点上我几乎确信测试用例有某种错误）

参数：

给定一个高度为 x,y 的网格，其中填充了 0 或 1，分别代表空间和墙壁：如果您可以恰好打破 1 堵墙（如果需要），请找到最短路径

一个例子：

[
[0,1,0,0,0,1,0,0,0,0,0]
[0,0,0,1,0,0,1,0,1,1,0]
[1,1,1,1,1,0,1,0,1,0,1]
[0,0,0,0,0,0,0,0,1,1,0]
]

22 is the shortest path breaking 1 wall.

我想要一个正确方向的指针：我觉得我所缺少的一切都是微不足道的。

下面是代码。

from math import sqrt, ceil
cardinal_moves=[(0,1), (0,-1), (1,0), (-1,0)]

class Node:
    def __init__(self, pos ,parent =None):
        self.parent = parent
        self.pos = pos
        self.g = 0
        self.h = 0
        self.f = 0
        self.wall_broken = False
    def __eq__(self, other):
        return ((self.pos == other.pos) and (self.wall_broken == other.wall_broken))
    def update_heuristic(self,parent,end):
        self.g = parent.g + 1
        self.h = ceil(sqrt((end.pos[0] - self.pos[0])**2 + (end.pos[1] - self.pos[1])**2))
        self.f = self.g + self.h
def not_inside_maze(pos,maze):
    return pos[0] < 0 or pos[0] >= len(maze) or pos[1] < 0 or pos[1] >= len(maze[0])
def astar_with_1_breakable_wall(maze):
    start_pos = (0,0)
    end_pos = (len(maze)-1, len(maze[0])-1)
    start = Node(start_pos)
    end = Node(end_pos)
    not_visted = []
    visited = []
    not_visted.append(start)
    while not_visted:
        current_node = not_visted[0]
        for node in not_visted:
            if current_node.f > node.f:
                current_node = node
        not_visted.remove(current_node)
        visited.append(current_node)
        if current_node.pos == end.pos:
            temp = current_node
            path = []
            while temp:
                path.append(temp.pos)
                temp = temp.parent
            return path[::-1]
        children = []
        for position in cardinal_moves:
            new_pos = (current_node.pos[0] + position[0], current_node.pos[1] + position[1])
            if not_inside_maze(new_pos,maze):
                continue
            if maze[new_pos[0]][new_pos[1]] == 1:
                if current_node.wall_broken:
                    continue
                else:
                    check = Node(new_pos,current_node)
                    check.wall_broken = True
                    already_visited = False
                    for node in visited:
                        if check == node:
                            already_visited = True
                            break
                    if not already_visited:
                        children.append(check)
                    continue
            already_visited = False
            check = Node(new_pos,current_node)
            check.wall_broken = current_node.wall_broken
            for node in visited:
                if check == node:
                    already_visited = True
                    break
            if already_visited:
                continue
            children.append(check)
        for child in children:
            child.update_heuristic(current_node,end)
            
            for open_node in not_visted:
                if open_node == child:
                    if open_node.g > child.g:
                        idx = not_visted.index(open_node)
                        not_visted[idx] = child
                        continue
                    else:
                        continue
            not_visted.append(child)

def shortest_path(maze):
    if (astar_with_1_breakable_wall(maze)):
        return len(astar_with_1_breakable_wall(maze))
    else:
        return -1

但是我在我的机器上所做的每一次检查都表明这是正确的：

#imports added
import sys
#then added this below the maze solver
test = [
[0,1,0,0,0,1,0,0,0,0,0],
[0,0,0,1,0,0,1,0,1,1,0],
[1,1,1,1,1,0,1,0,1,0,1],
[0,0,0,0,0,0,0,0,1,1,0],
]
test2=[
[0,1,0,0,0,0,1,0,0,0,0],
[0,1,0,1,1,0,1,0,1,0,0],
[0,0,0,1,0,0,1,0,1,0,0],
[1,1,1,1,0,1,1,0,1,0,1],
[0,0,0,0,0,0,0,0,1,0,1],
]
print("first test")
print(shortest_path(test))
print("second test")
print(shortest_path(test))
#both of these tests give the correct result
def generate_matrix(h,w,n):
    sequence = "{0:b}".format(n).zfill(h*w)
    maze =[]
    if(sequence[0]=="1" or sequence[len(sequence)-1]=="1"):
        return -1
    i=0
    for y in range(h):
        maze.append([])
        for x in range(w):
            maze[y].append(int(sequence[i])) 
            i=i+1
   
    return(maze)

for i in range(20):
    for j in range(20):
        if(i < 6 or j <6):
            continue
        shortest=j+i
        for k in range(2**(i*j)):
            if not k%2==0:
                continue
            if k> 2**(i*j-1):
                continue

            maze = generate_matrix(i,j,k)
            if(not maze == -1):
                path = astar_with_1_breakable_wall(maze)
                res = shortest_path(maze)
                if(res > shortest):
                    print("\n",res, "shortest was ", shortest)
                    for index,line in enumerate(maze):
                        for indx,cell in enumerate(line):
                            if ((index,indx) in path):
                                print("3[94m"+str(cell),end="")
                            else:
                                print("3[92m"+str(cell),end="")
                        print("\n")
                    for point in path:
                        print(point ," ", end="")
                    print("\n\n")
                else:
                    sys.stdout.write("\r")

上面的代码使每个矩阵成为可能，如果路径比基本情况长，则打印（突出显示路径）矩阵。

每个结果都如我所料 - 返回正确的最短路径...我还没有发现为什么只有第三个测试用例失败的问题...

Answer 1

答案显然是 python 2.7.13 特有的——需要一些调试才能弄清楚，但 not_visited.remove(current_node) 是在某些情况下失败了。