Python fails to compare strings

Question

I'm facing a strange problem in python. I have a maze, x's stand for walls, g is a goal, s is the starting point and the numbers are portals which bring you from one number to the other (e.g. if you go on one of the 2's it will transport you to the other 2).

xxxxxxxxxxxxxxxxxxxx
x2                 x
x       xxx        x
x   1   x xxxxx    x
x   s     x        x
x       x x  xxxxxxx
x  xx xxxxx        x
x      x      g    x
x   1  x  2        x
xxxxxxxxxxxxxxxxxxxx

I'm trying to find all portals and put them into an array. So far this works, the program finds all four portals.

import tkinter as tk
from tkinter import filedialog

root = tk.Tk()
root.withdraw()
file = filedialog.askopenfilename()

def readMazeToArray(path):
    with open(path) as f:
        return [list(line.strip()) for line in f]

maze = readMazeToArray(file)

def findPortals(maze):
    portals = []
    for i in range(0, len(maze)):
        for j in range(0, len(maze[i])):
            if (maze[i][j] != 'g' and maze[i][j] != 's' 
            and maze[i][j] != 'x' and maze[i][j] != ' '):
                portals.append([i, j])
    return portals

And from then on things are getting a bit strange. Here's the code that doesn't seem to work right:

def portalHeuristic(maze, x1, x2, y1, y2):
    portals = findPortals(maze)
    for portal in portals:
        for i in range(0, len(maze)):
            for j in range(0, len(maze[i])):

                if maze[i][j] == maze[portal[0]][portal[1]] 
                and (portal[0] != i or portal[1] != j):

                     return abs(x1 - portal[0]) + abs(y1 - portal[1]) 
                            + abs(x2 - i) + abs(y2 - j))

        print(maze[i][j] == maze[portal[0]][portal[1]])

        print("x1 = ", x1, ", y1 = ", y1, ", portal0 = ", 
        portal[0], ", portal1 = ", portal[1], ", x2 = ",
        x2, ", y2 = ", y2, ", i = ",  i, ", j = ", j)


portalHeuristic(maze, 4, 4, 7, 14)

What portalHeuristic basically does is it now iterates through one portal after another looking for the same symbol (maze[i][j] == maze[portal[0]][portal[1]]) of the current portal but ensures that it didn't find the current portal itself by comparing the coordinates of the current portal and the portal it has found with the same symbol/ number (portal[0] != i or portal[1] != j). Eventually it computes the distance between starting point and current portal and its twin portal and the goal.

But it seems like maze[i][j] == maze[portal[0]][portal[1]] doesn't seem to work since my program always tells me the other portal was found at i=9, j=19, no matter which portal. Strangely enough if I test for the equality of the strings on its own python realizes that it is always false. What am I doing wrong? I've now spent more than 3 hours looking for the error, but I can't seem to find it. Maybe it's a really stupid one? Also, please bear with my terrible code. I just started with python.

Answer 1

In your findPortal method, you create a list that will contain the coordinates of your portals. At the end it should be something like this (it's random numbers) : portals = [[2,5], [5,1], ...]

In your portalHeuristic, in your condition maze[i][j] == maze[portal[0]][portal[1]], portal[0] = [2,5] and portal[1] = [5,1]. So basically, you're doing maze[i][j] == maze[[2,5]][[5,1]] which it is strange that python didn't raise an exception. So that's why your condition is always false.

---

That being stated, your code is very inefficient. You iterate over the maze to find portals and then reiterate again (and 4 times since you have 4 portals) on your maze. What about pairing the portals directly when you search them? You can use a dictionary with the key being the number of your portal (here 1 or 2), it can even be the character "1" or "2" and not the number, and the value would be a list with 2 elements, each element is the coordinate of the portal.

def findPortals(maze):
    portals = {} #That's a dict
    for i in range(0, len(maze)):
        for j in range(0, len(maze[i])):
            if (maze[i][j] != 'g' and maze[i][j] != 's' 
            and maze[i][j] != 'x' and maze[i][j] != ' '):
                if maze[i][j] in portals:
                    # We already have one, put the other
                    portals[maze[i][j]].append([i,j])
                else:
                    # It is the first one
                    portals[maze[i][j]] = [[i,j]]
    return portals

Good luck from there!

---

You can see dictionaries as a list where the key do not need to be a number and do not have to be sequential (if you have 5 items in your list, they will be accessible with list[0], list[1], etc..). So if you want to access an item in your dict, just pass the key. In your heuristic, you seem to want to find the distance between [x1, y1] and the first portal discovered in your list and sum it with the other distance between the portal associated and [x2, y2]. That is a bit too specific, you can specify the portal you wanna check (like '1' or '2').

Therefore your function become:

def portalHeuristic(portals, x1, y1, x2, y2, portal_number):
    # Check if the portal exist in you list
    if portal_number not in portals:
        print("This portal number is not in the list")
        return
    # This line is a shortcut. Since we know that portals[x] is a list of 
    # two elements (coordinates of both portals with the same number), 
    # you can assign the first element with first_portal and the second element 
    # with second_portal.
    first_portal, second_portal = portals[portal_number]
    return abs(x1 - first_portal[0]) + abs(y1 - first_portal[1]) 
                        + abs(x2 - second_portal[0]) + abs(y2 - second_portal[1]))

Don't forget that your keys are character there ('1' or '2') and not 1 or 2 (integers). portal_number should be a character then.

Answer 2

its hard to write out for loops once you're familliar with list comprehensions

but perhaps you can work backwards from my example list comps with http://treyhunner.com/2015/12/python-list-comprehensions-now-in-color/

I added line breaks and leading whitespace inside the listcomps in an atempt to help readability

you should also see that enumerate is very helpful in these types of indexing loops with test on elements

maze = ['xxxxxxxxxxxxxxxxxxxx',
 'x2                 x',
 'x       xxx        x',
 'x   1   x xxxxx    x',
 'x   s     x        x',
 'x       x x  xxxxxxx',
 'x  xx xxxxx        x',
 'x      x      g    x',
 'x   1  x  2        x',
 'xxxxxxxxxxxxxxxxxxxx']

prtls = [[c, (j, k)]
         for k, ln in enumerate(maze)
            for j, c in enumerate(ln) if c.isdigit()]
prtls
Out[206]: [['2', (1, 1)], ['1', (4, 3)], ['1', (4, 8)], ['2', (10, 8)]]

grpd_prtls = [[n, [p[1]
               for p in prtls if p[0] == n]]
              for n in sorted(set(p[0] for p in prtls))]
grpd_prtls
Out[207]: [['1', [(4, 3), (4, 8)]], ['2', [(1, 1), (10, 8)]]]

the grpd_prtls is sorted by portal number sorted(set(p[0] for p in prtls))

to calc 'Manhatten Distance' from my grpd_prtls, assmuming just 2 portals per number

[[p[0], sum(abs(a-b)
            for a, b in zip(*p[1]))]
 for p in grpd_prtls] 
Out[214]: [['1', 5], ['2', 16]]