Pythonic way of figuring out straight paths on a square lattice grid?

Question

I'm not really sure how to describe my question here, so I guess I'll try and explain the situation first. I've got a data set being pulled in from a square lattice grid of 4 sided polygons. The lattice dimensions aren't guaranteed to be anything in particular. I have access to the data that describes the neighbours of any given point on the grid (ie, "point 236 has edges to points 417, 872, 123, and 331") and that's about it.

What I have is this:

graph = [set([5, 9]), set([4, 11]), set([5, 6, 12]), set([6, 10, 2]), \
         set([1, 3, 8]), set([3, 7, 4]), set([6, 12, 10, 16]), \
         set([5, 9, 18, 12]), set([1, 8, 13]), set([4, 11, 7, 15]), \
         set([2, 10, 17]), set([3, 7, 8, 14]), set([9, 18]), \
         set([18, 12, 16]), set([16, 10, 17]), set([14, 7, 15]), \
         set([15, 11]), set([13, 8, 14])]

Where graph[n] lets me access the neighbours of any given point by index n... The entire data set of which can be visualized by the 2D graph shown below (which I don't have access to other then via the data listed above):

*--------*--------*-------*-------*-------*
| 1      | 5      | 3     | 6     | 4     | 2
|        |        |       |       |       |
|        |        |       |       |       |
*--------*--------*-------*-------*-------*
| 9      | 8      | 12    | 7     | 10    | 11
|        |        |       |       |       |
|        |        |       |       |       |
*--------*--------*-------*-------*-------*
  13       18       14      16      15      17

And I'm trying to turn it into a set of data that looks like this:

u = [[1, 5, 3, 6, 4, 2], [9, 8, 12, 7, 10, 11], [13, 18, 14, 16, 15, 17]]
v = [[1, 9, 13], [5, 8, 18], [3, 12, 14], [6, 7, 16], [4, 10, 15], [2, 11, 17]]

The output data describes the parallel lines of the grid (starting at the corner with the lowest index number). Each point is guaranteed to have a unique index, and the grid is guaranteed to have a contiguous set of indices (in this case, 1 through to 18) but the order is not guaranteed in any way. The dimensions of the grid are not known beforehand. Each point will only ever have a valance of 2 (corner point), 3 (edge point), or 4 (point somewhere in the centre).

Now, I've written a brute force approach to this, but it's fairly inefficient. It consists of figuring out the first two horizontal and vertical edges (in this case, [1, 5, 3, 6, 4, 2] and [1, 9, 13]), then "shifting" each edge over by getting the connected neighbours of each point and subtracting an already visited set from that (so 1 -> 5, 9 -> 8, 13 -> 18) and repeating this process until you hit the other side of the grid.

What I was wondering was if there was a more "pythonic" way of handling this. My own code is split up into several different phases, but I figured there's got to be some way of doing this in one fell swoop rather then iterating over everything so many times (it's currently taking me about 60ms per run to figure all this out, and I'm trying to get that down to 20ms if possible).

Answer 1

I think you can build your grid gradually, one node at a time without too much trouble. Here's how I'd do it:

1. Start with any corner node, which you can detect by it only having two neighbors.
2. Find one edge (it doesn't matter which) by picking either of your start node's neighbors and then repeatedly moving on to a neighbor with exactly three neighbors of its own (rather than four), avoiding going back to the previous node. The end case is when you get to another corner.
3. Loop over the row you just found, taking the remaining neighbor of each node. There's only one neighbor node left (that's not already in the grid) so there's no complexity here.
4. Repeat step 3 until you get to the far edge.
5. Make your second list (of the columns) by transposing the lists (e.g. with zip(*rows))

If your neighbor data is in the form of a dictionary mapping from each node to a list of its neighbors, this code should work:

def make_grid(neighbor_dict):
    # step 1, find the first corner
    for node, neighbors in neighbor_dict:
        if len(neighbors) == 2:
            break  # node and neighbors will hold our start corner and its neighbors

    # step 2, build the first edge
    row = [node, neighbor[0]]  # start with the corner, and an arbitrary neighbor
    while len(neighbors_dict[row[-1]]) == 3:
        for neighbor in neighbor_dict[row[-1]]:
            if neighbor != row[-2] and len(neighbor_dict[neighbor]) <= 3:
                row.append(neighbor)
                break

    # setup for steps 3 and 4
    seen = set(row)  # a set of all nodes we've added to the grid so far
    rows = []
    done = False

    while not done:  # this loop is step 4, building all rows
        rows.append(row)
        new_row = []
        for node in row:  # this is step 3, building a new row from the previous row
            for neighbor in neighbor_dict[node]:
                if neighbor not in seen:
                    new_row.append(neighbor)
                    seen.add(neighbor)
                    break
            else:  # no break hit in for loop, only happens if `row` is the far edge
                done = True
                break
        row = new_row

    # step 5, transpose to get columns from rows
    columns = list(zip(*rows))

    return rows, columns

Answer 2

You might want to take a look at this code:

def lattice_paths_of_n(n):
    list2 = []
    my_list = []
    for i in range(1, n+2):
        list2.append(i)
    for i in range(1, n+2):
        my_list.append(list2)
    for i in range(0,n+1):
        for f in range(0,n+1):
            if f == 0 or i == 0:
                my_list[i][f] = 1
            else:
                my_list[i][f] = my_list[i-1][f]+my_list[i][f-1]
    return my_list[n][n]
import math
start_time = time.time()
print(lattice_paths_of_n(20))
print(time.time()-start_time)

Although it is quite inefficient, I hope you find it useful.