Prepare the Bunnies Escape - Foobar-CodePudding

I've been at this for a while and for the life of me I cannot figure out why I cannot pass test cases 4 and 5. My code is below, including my own custom test cases that all execute and pass in under 5ms.

Basically I added a third dimension to each node's position that represents whether a wall has already been traversed or not. When analyzing each current node's neighbor, if it's a wall and the current node has a zero for its third coordinate, then moving to the wall and to a 1 on the third coordinate becomes an option. On paper, it works great. In my own IDE, it works great.

I'm starting to wonder if there's something in here that's Python 3 and not working correctly in foobar or something. I'd appreciate any help.

class Node():
    def __init__(self, position):
        self.position = position
        
        self.gCost = 1
        self.hCost = 0
        self.fCost = 0
    
    def __eq__(self, other):
        return self.position == other.position


def solution(map):
    
    startNode = Node((0, 0, 0))
    endNode = Node((len(map[0]) - 1, len(map) - 1, 0))
    
    openList = [startNode]
    closedList = []

    while openList:
        currentNode = openList[0]
        currentIndex = 0

        for i in range(len(openList)):
            if openList[i].fCost < currentNode.fCost:
                currentNode = openList[i]
                currentIndex = i
        
        openList.pop(currentIndex)
        closedList.append(currentNode)

        if currentNode.position[0] == endNode.position[0] and currentNode.position[1] == endNode.position[1]:
            return currentNode.gCost

        for offset in [(1, 0), (-1, 0), (0, 1), (0, -1)]:

            neighborPosition = (currentNode.position[0]   offset[0], currentNode.position[1]   offset[1], currentNode.position[2])

            if neighborPosition[0] < 0 or neighborPosition[0] >= len(map[0]) or neighborPosition[1] < 0 or neighborPosition[1] >= len(map):
                continue

            if map[neighborPosition[0]][neighborPosition[1]] == 1:
                if currentNode.position[2] == 1:
                    continue
                neighborPosition = (neighborPosition[0], neighborPosition[1], 1)

            neighbor = Node(neighborPosition)

            if neighbor in closedList: 
                continue
            
            if neighbor in openList:

                openNodeIndex = openList.index(neighbor)
                if openList[openNodeIndex].gCost < currentNode.gCost   1:
                    continue
                openList.pop(openNodeIndex)
                openList.append(neighbor)

            else:
                openList.append(neighbor)

            neighbor.gCost = currentNode.gCost   1
            neighbor.hCost = endNode.position[0] - neighbor.position[0]   endNode.position[1] - neighbor.position[1]
            neighbor.fCost = neighbor.gCost   neighbor.hCost

    
    return -1

import time

start = time.time()
map1 = [[0, 0, 0, 1], [1, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 0]]
sol1 = solution(map1)
print("Result: ", sol1, "Expected: ", 7)
map2 = [[0,1,0,0,0], [0,1,0,1,0], [0,1,0,1,0], [0,1,0,1,0], [0,0,0,1,0]]
sol2 = solution(map2)
print("Result: ", sol2, "Expected: ", 9) 
map3 = [[0,0,0,0,0,0,1,0,0,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,0,0,1,0]]
sol3 = solution(map3)
print("Result: ", sol3, "Expected: ", 19)
map4 = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]]
sol4 = solution(map4)
print("Result: ", sol4, "Expected: ", 11)
map5 = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]
sol5 = solution(map5)
print("Result: ", sol5, "Expected: ", 7)
map6 = [[0,1,0], [0,1,0], [0,1,0]]
sol6 = solution(map6)
print("Result: ", sol6, "Expected: ", 5)
map7 = [[0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0]]
sol7 = solution(map7)
print("Result: ", sol7, "Expected: ", 123)
map8 = [[0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0],[0,1,0,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1],[0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,0,1,0,1,0,1,0,0,0,1,1,1,0,1,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0],[1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0],[0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,1,1,0,0]]
sol8 = solution(map8)
print("Result: ", sol8, "Expected: ", 89)

end = time.time()
print("Time: ", end - start)

Edit: Quick update - converted the closedList to a set and now it solves my test cases in under 1ms, still fails Google's test cases 4 and 5 though.

CodePudding user response：

So I figured it out. The line

if map[neighborPosition[0]][neighborPosition[1]] == 1:

had the x and y coordinates backwards. It should have been

if map[neighborPosition[1]][neighborPosition[0]] == 1:

In cases where the map was not square it was going out of bounds. Just needed to add a test case that wasn't square and figured it out pretty quick from there.