Inefficient Expansion Algorithm

Question

So I am trying to write a program which takes a grid and a starting point on the grid, and expands the point outward, labeling each cell with how many expansions it took to reach that location.

For my application, the expansion cannot look into other cells and use their values as a reference or overwrite the values of a previously set cell. I have written code to do this, and it works exactly how I want, but when I try to do 8 or more expansions my computer struggles.

Can anyone find anything in my code that would make this so horribly inefficient and give suggestions for how I could make it better?

Thanks in advance!

grid = [[9 for col in range(25)] for row in range(25)]

start = [12, 12]
grid[start[0]][start[1]] = 0
numRips = 7

def handler():
    allExpanded = [start]
    expanded = [start]
    num = 1
    for r in range(numRips):
        toExpand = []
        for n in expanded:
            toExpand = toExpand + (getUnvisitedNeighbors(n, allExpanded))
        expanded = []
        for u in toExpand:
            grid[u[0]][u[1]] = num
            expanded.append(u)
            allExpanded.append(u)
        num += 1




def getUnvisitedNeighbors(loc, visitedCells):
    x, y = loc[0], loc[1]

    neighbors = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1], \
                 [x - 1, y - 1], [x - 1, y + 1], [x + 1, y - 1], [x + 1, y + 1]]

    f = lambda p: p[0] >=0 and p[0] < len(grid) and \
                    p[1] >= 0 and p[1] < len(grid[0]) and \
                    not p in visitedCells

    unvisitedNeighbors = filter(f, neighbors)

    return unvisitedNeighbors

handler()
for i in range(len(grid)):
    print grid[i]

Answer 1

I altered your code so it could be timed:

import os
import sys
import timeit

setup_str = \
'''
from __main__ import setup, handler

setup()
'''
def setup():
    global grid
    grid = [[9 for col in range(25)] for row in range(25)]

    global start
    start = [12, 12]
    grid[start[0]][start[1]] = 0
    global numRips
    numRips = 8

def handler():
    global grid
    global start
    global numRips
    allExpanded = [start]
    expanded = [start]
    num = 1
    for r in range(numRips):
        toExpand = []
        for n in expanded:
            toExpand = toExpand + (getUnvisitedNeighbors(n, allExpanded))
        expanded = []
        for u in toExpand:
            grid[u[0]][u[1]] = num
            expanded.append(u)
            allExpanded.append(u)
        num += 1

def getUnvisitedNeighbors(loc, visitedCells):
    global grid
    x, y = loc[0], loc[1]

    neighbors = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1], \
                 [x - 1, y - 1], [x - 1, y + 1], [x + 1, y - 1], [x + 1, y + 1]]

    f = lambda p: p[0] >=0 and p[0] < len(grid) and \
                    p[1] >= 0 and p[1] < len(grid[0]) and \
                    not p in visitedCells

    unvisitedNeighbors = filter(f, neighbors)

    return unvisitedNeighbors

print timeit.repeat(stmt="handler()", setup=setup_str, repeat=3, number=1)
for i in range(len(grid)):
    print grid[i]

It took: [63.33822661788784, 64.53106826397212, 61.407282939290724] seconds.

Keeping the rough structure of the program, I changed it to:

import os
import sys
import timeit

setup_str = \
'''
from __main__ import setup, handler

setup()
'''

dirs = \
(
    ( - 1,   0),
    ( + 1,   0),
    (   0, - 1),
    (   0, + 1),
    ( - 1, - 1),
    ( - 1, + 1),
    ( + 1, - 1),
    ( + 1, + 1)
)

def setup():
    global grid_max_x
    grid_max_x = 25
    global grid_max_y
    grid_max_y = 25
    global grid
    grid = [[9 for col in range(grid_max_y)] for row in range(grid_max_x)]

    global start
    start = (12, 12)
    grid[start[0]][start[1]] = 0
    global numRips
    numRips = 8

def handler():
    global grid
    global start
    global numRips
    border_expanded = set([start])
    allExpanded = set([start])
    num = 1
    for r in range(numRips):
        toExpand = set([])
        map(lambda x: toExpand.update(x), [(getUnvisitedNeighbors(n, allExpanded)) for n in border_expanded])
        border_expanded = toExpand
        allExpanded.update(toExpand)
        for u in toExpand:
            grid[u[0]][u[1]] = num
        num += 1

def getUnvisitedNeighbors(loc, visitedCells):
    global grid_max_x
    global grid_max_y
    global dirs

    x, y = loc

    neighbors = set([((x + dx) % grid_max_x, (y + dy) % grid_max_y) for (dx, dy) in dirs])

    unvisitedNeighbors = neighbors - visitedCells

    return unvisitedNeighbors

print timeit.repeat(stmt="handler()", setup=setup_str, repeat=3, number=1)
for i in range(len(grid)):
    print grid[i]

This took [0.0016090851488842293, 0.0014349565512783052, 0.0014186988443765235] seconds.

Basically, you want to minimise the amount of allocation, copying and iteration done.