Find diagonal positions for bishop movement

Question

In a chess board, I need to find the diagonals a bishop can move on, and more specifically, the coordinates of those squares. So, given a grid of any size and a position in that grid (expressed in coordinates within the grid), I have to compute the coordinates of the diagonals of that initial position.

I'm using zero-based indexing, and the (row, column) notation for coordinates.

For example, on a 8x8 grid, with starting position of (0, 0), the returned list should be [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7)].

On a 8x8 grid, with starting position of (3, 4), the returned list should be [(3, 4), (2, 3), (1, 2), (0, 1), (4, 5), (5, 6), (6, 7), (4, 3), (5, 2), (6, 1), (7, 0), (2, 5), (1, 6), (0, 7)]

This is my working program in Python 3:

def diagonals(coord, size):
    limit = size - 1
    coords = [coord]
    row = coord[0]
    col = coord[1]

    while row > 0 and col > 0:
        row -= 1
        col -= 1
        coords.append((row, col))

    row = coord[0]
    col = coord[1]

    while row < limit and col < limit:
        row += 1
        col += 1
        coords.append((row, col))

    row = coord[0]
    col = coord[1]

    while row < limit and col > 0:
        row += 1
        col -= 1
        coords.append((row, col))

    row = coord[0]
    col = coord[1]

    while row > 0 and col < limit:
        row -= 1
        col += 1
        coords.append((row, col))

    return coords

coord = (3, 4)
size = 8
print(diagonals(coord, size))

Depending on the diagonal (4 cases), row and column are added or subtracted by one until the last square is reached, and everything is kept in a list, which in the end is returned.

It works, but it left me wondering if there's a simpler, different, better way of doing this, probably using linear algebra or something? And what about idiomatically, how can this be more pythonic?

Answer 1

The biggest problem you have is you have five lines that are nearly identical, four times.

row = coord[0]
col = coord[1]

while row > 0 and col > 0:
    row -= 1
    col -= 1

There is two ways to come at this. (1) make a function that yield the rows and columns. (2) use zip and range.

The first way you need to enter a start, limit and step for both the x and y axis. You then need to limit all inputs by 0 < x < x_limit, and the same for the y axis too. This is as we don't really know what direction we're going. We then add the step to x each iteration. This can make:

def _diagonal(x, y, x_limit, y_limit, x_diff, y_diff):
    while 0 < x < x_limit and 0 < y < y_limit:
        x += x_diff
        y += y_diff
        yield (x, y)

Where you'd use it like:

for x, y in _diagonal(row, col, limit, limit, 1, 1):
    coords.append((x, y))

However this is quite alike to range, we enter a start, limit and step in both. Take range(row + 1, limit, 1). To then get both x and y you need to use zip which works perfectly as it stops iterating when any of the inputs stop. And so you can get:

for x, y in zip(range(row + 1, limit, 1), range(col + 1, limit, 1)):
    coords.append((x, y))

This I would say is better than creating your own function as you don't really have to implement anything yourself.

Either way you'll want to remove the duplicate code to append to coords. To do this you can use itertools.chain. This lets you chain iterators to become one iterator. So since you want a list as output you'll have to 'wrap' the call in a list call.

This can get you:

from itertools import chain

def diagonals(coord, size):
    x, y = coord
    return list(chain(
        [(x, y)],
        zip(range(x - 1, -1, -1), range(y - 1, -1, -1)),
        zip(range(x + 1, size, 1), range(y + 1, size, 1)),
        zip(range(x + 1, size, 1), range(y - 1, -1, -1)),
        zip(range(x - 1, -1, -1), range(y + 1, size, 1)),
    ))

print(diagonals((3, 4), 8))

Answer 2

Remarks

1. The code is readable, and appears to be correct. That's a pretty good starting point. It's shorter than what's presented here.

2. I'm always skeptical of the word "Pythonic". The original code may be more Pythonic than that presented here because it is more explicitly procedural. Then again, someone could come along and claim that because Python has objects, true Pythonic code is object oriented. Down at the level of a single statement or expression, there are some dominant idioms. But up at the level of programs "Pythonic" is mostly part of a pejorative "Not Pythonic".

3. The problem is such that there's no good way of avoiding the fact that there are four cases. Where the code in the question is weak is the level of abstraction at which the four cases are articulated. There's lots of fiddly-bits around columns and rows and limits up near the top-level of the function. Even though our top level abstraction is a diagonal. The mathematics works, but it's not obvious exactly why.

4. One way of thinking about Remark 2 is that the code 'one level down' is reductionist rather than compositional. It expresses itself in terms a bit more like 'machine code' than 'business logic'...or perhaps the mathematical logic suggested when linear algebra was mentioned.

A More Mathematical Approach

Because, limitations of computer hardware aside, the chessboard can be arbitrarily large, looking at the solution for a bishop on an infinitely large chessboard might be a place to begin looking for a general solution.

The first thing that popped out is that the choice of coordinate system origin point is important because an infinitely sized chessboard does not have any corners. Since the choice of origin point is arbitrary, maybe placing the Bishop at (0,0) might things easier to understand. It gives us a Cartesian grid:

         |           
   IV    |   I
         |           
         |           
---------+---------- 
         |           
         |           
  III    |   II
         |           
         |           

Cartesian Space

The bishop's diagonals are defined by simple functions.

 \       |       / 
   \     |     / 
     \   |   /   y = x 
       \ | / 
---------+----------
        /|\ 
      /  |  \ 
     /   |    \   y = -x
   /     |      \ 
 /       |        \

Bishop Diagonals as the Union of Two Functions

And a board of finite size can be visualized as:

         |
    +----+----+
    |    |    |
    |    |    |
----+----+----+-----
    |    |    |
    +----+----+
         |           
         |           
         |       

Clipped Cartesian Space

A bit of Linear Algebra

Since it was mentioned in the question, perhaps there are some useful abstractions there. It is possible to think of y = x and y = -x as two matrices. Each has two columns and an infinite number of rows. Going further y = x can be transformed into the other matrix by the 2x1 matrix [1,-1] where the values are arranged in a column.

Going back to the original Cartesian grid, we translate the solution for the portion of the diagonal lying in one quadrant, into the relevant diagonal for the other column:

def diagonals(coord, size):
    """generate the worst case solution 
       for quadrant I (northeast) where
       each value is (+,+)"""
    base = zip(range(1, size),range(1, size))
    max_index = size - 1

The other diagonals in the other quadrants can be generated from the worst case diagonal for Quadrant I (northeast). Technically, the transformation can be seen as either a four-fold rotation or two mirror planes. I thought that rotation seemed easier.

    """rotation matrices"""
    northeast = (1,1)
    southeast = (-1,1)
    southwest = (-1,-1)
    northwest = (1,-1)

    def rotate_diagonal(diagonal,direction):
        def rotate(coord_i):
            return (coord_i[0] * direction[0], coord_i[1] * direction[1])
        return map(rotate, diagonal)

Each diagonal gets clipped at the board boundaries based on the distance of the bishop from the edges. The distance of the bishop from the edges is defined by it's coordinate value.

    def clip_diagonal(direction):
        a = coord[0] if direction[0] < 0 else max_index - coord[0]
        b = coord[1] if direction[1] < 0 else max_index - coord[1]
        return base[:min(a,b)]

The last piece is to undo my arbitrary choice of origin. It boils down to a simple 2d translation. If the bishop is on square (i,j) then the equations become y + j = x + i and y + j = -x + i.

    def translate_diagonal(diagonal):
        def translate(coord_i):
            return (coord[0] + coord_i[0], coord[1] + coord_i[1])
        return map(translate, diagonal)

Then all that's left to do is to make the diagonals for each quadrant. Clipping is applied first to reduce the number of calculations where possible. Translation is applied last because rotation produces negative values.

    def make_diagonal(direction):
        clipped = clip_diagonal(direction)
        rotated = rotate_diagonal(clipped, direction)
        return translate_diagonal(rotated)

    return [coord]+make_diagonal(northeast)+make_diagonal(southeast)+make_diagonal(southwest)+make_diagonal(northwest) 

The last line is dreadful, I think, but clear enough I suppose. That's the price of staying onside.