How to create a for loop that goes through all diagonal possibilities of a list?

user_10568263 0
Viewed 795

Context

How would you find words in this list diagonally? Note: To show that a word has been found, it can be replaced by any character such as '-' 

grid =   ["HXXWXXXXXD",
          "XOXXOXXXOX",
          "XXRXXCXGXX",
          "XXXSXXXXXT",
          "XXXXEXXXEX"]

I figured that all possibilities of diagonals in the grid are:

  • Going downwards and left
  • Going downwards and right
  • Going upwards and left
  • Going upwards and right

The words to find, in this instance would be:

words = ["HORSE","COW","DOG","ET"] # don't ask

How I found words vertically and horizontally

Finding words diagonally seems much more difficult than horizontally or vertically. When finding words horizontally, I could just loop through each row in grid and each word in words. I could then replace word in row with a symbol * len(word)to illustrate that it had been found. Vertically, I rotated the grid 90° clockwise and then did the same process of looping through the lists horizontally. I then rotated the list back to its original state.

What different solutions are there to finding words diagonally?

list python
4 Answers

You can transform the list by shifting each of the string as list by 1 more than the last - and fill the created space with filler (Using '0' in this case):

mearray = np.array([[e for e in g] for g in grid])
words = ["HORSE","COW","DOG","ET"] # don't ask

I used numpy because I'm more used to it and it's easier to show here, but it could certainly be done in regular list comprehension. After this, your array is now a numpy array:

[['H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D']
 ['X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X']
 ['X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X']
 ['X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T']
 ['X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X']]

Transform this by adding in shifting fillers:

leng = len(mearray)
def pad_with(vector, pad_width, iaxis, kwargs):
    pad_value = kwargs.get('padder', '0')
    vector[:pad_width[0]] = pad_value
    vector[-pad_width[1]:] = pad_value
    return vector
np.array([np.pad(mearray[i], (leng-i, i+1), pad_with) for i in range(leng)])

Your array is now:

[['0' '0' '0' '0' '0' 'H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D' '0']
 ['0' '0' '0' '0' 'X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X' '0' '0']
 ['0' '0' '0' 'X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X' '0' '0' '0']
 ['0' '0' 'X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T' '0' '0' '0' '0']
 ['0' 'X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X' '0' '0' '0' '0' '0']]

You can clearly see that HORSE and COW are normalized. You'll need to do this again by switching the filler direction so you'll have GOD and ET:

Reverse direction: np.array([np.pad(mearray[i], (i+1, leng-i), pad_with) for i in range(leng)])

[['0' 'H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D' '0' '0' '0' '0' '0']
 ['0' '0' 'X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X' '0' '0' '0' '0']
 ['0' '0' '0' 'X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X' '0' '0' '0']
 ['0' '0' '0' '0' 'X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T' '0' '0']
 ['0' '0' '0' '0' '0' 'X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X' '0']]

Now you can see GOD and ET (upside down) in your matrix. You should be able to use your original function to retrieve them.

user_80462320

If you do not care too much about the order in which all diagonals are traversed, this generator function in pure Python will do, making use of the fact that up-right is down-left backwards:

def rotate(row, n):
    return row[n:] + row[:n]

def diags(grid, rev=False):
    n = len(grid)
    _grid = [list(row) + [None]*(n-1) for row in grid]  # pad for rotation
    for diag in zip(*(rotate(_grid[i], (i, -i)[rev]) for i in range(n))):
        d = ''.join(filter(None, diag))
        yield from (d, d[::-1])
    if not rev:
        yield from diags(grid, rev=True) 

>>> list(diags(grid))
['H',
 'H',
 'XX',
 'XX',
 'XOX',
 'XOX',
 'WXXX',
 'XXXW',
 'XXRXX',
 'XXRXX',
 'XOXXX',
 'XXXOX',
 'XXXSX',
 'XSXXX',
 'XXCXX',
 'XXCXX',
 'XXXXE',
 'EXXXX',
 'DOGXX',
 'XXGOD',
 'XXXX',
 'XXXX',
 'XXX',
 'XXX',
 'TE',
 'ET',
 'X',
 'X',
 'HORSE',
 'ESROH',
 'XXXXX',
 'XXXXX',
 'XXXXX',
 'XXXXX',
 'WOCXX',
 'XXCOW',
 'XXXXE',
 'EXXXX',
 'XXGXX',
 'XXGXX',
 'XXXT',
 'TXXX',
 'XOX',
 'XOX',
 'XX',
 'XX',
 'D',
 'D',
 'X',
 'X',
 'XX',
 'XX',
 'XXX',
 'XXX',
 'XXXX',
 'XXXX']
user_23901820

To iterate over all possible diagonals, you can use numpy diagonal. Also use numpy fliplr, flipud, flip to get diagonals in all directions:

import numpy as np

grid = [
    "HXXWXXXXXD",
    "XOXXOXXXOX",
    "XXRXXCXGXX",
    "XXXSXXXXXT",
    "XXXXEXXXEX"]
data_orig = np.array(list(map(list, grid)))

transformations = {
    'Downwards and Right': np.array,
    'Downwards and left': np.fliplr,
    'Upwards and Right': np.flipud,
    'Upwards and left': np.flip,
}

for descr, trans in transformations.items():
    data = trans(data_orig)
    print(descr)
    print(data)
    offset_row = 1 - data.shape[0]
    offset_column = data.shape[1]
    for offset in range(offset_row, offset_column):
        print(data.diagonal(offset=offset))

Ouput:

Downwards and Right
[['H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D']
 ['X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X']
 ['X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X']
 ['X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T']
 ['X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X']]
['X']
['X' 'X']
['X' 'X' 'X']
['X' 'X' 'X' 'X']
['H' 'O' 'R' 'S' 'E']
['X' 'X' 'X' 'X' 'X']
['X' 'X' 'X' 'X' 'X']
['W' 'O' 'C' 'X' 'X']
['X' 'X' 'X' 'X' 'E']
['X' 'X' 'G' 'X' 'X']
['X' 'X' 'X' 'T']
['X' 'O' 'X']
['X' 'X']
['D']
Downwards and left
[['D' 'X' 'X' 'X' 'X' 'X' 'W' 'X' 'X' 'H']
 ['X' 'O' 'X' 'X' 'X' 'O' 'X' 'X' 'O' 'X']
 ['X' 'X' 'G' 'X' 'C' 'X' 'X' 'R' 'X' 'X']
 ['T' 'X' 'X' 'X' 'X' 'X' 'S' 'X' 'X' 'X']
 ['X' 'E' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'X']]
['X']
['T' 'E']
['X' 'X' 'X']
['X' 'X' 'X' 'X']
['D' 'O' 'G' 'X' 'X']
['X' 'X' 'X' 'X' 'E']
['X' 'X' 'C' 'X' 'X']
['X' 'X' 'X' 'S' 'X']
['X' 'O' 'X' 'X' 'X']
['X' 'X' 'R' 'X' 'X']
['W' 'X' 'X' 'X']
['X' 'O' 'X']
['X' 'X']
['H']
Upwards and Right
[['X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X']
 ['X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T']
 ['X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X']
 ['X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X']
 ['H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D']]
['H']
['X' 'X']
['X' 'O' 'X']
['X' 'X' 'X' 'W']
['X' 'X' 'R' 'X' 'X']
['X' 'X' 'X' 'O' 'X']
['X' 'S' 'X' 'X' 'X']
['X' 'X' 'C' 'X' 'X']
['E' 'X' 'X' 'X' 'X']
['X' 'X' 'G' 'O' 'D']
['X' 'X' 'X' 'X']
['X' 'X' 'X']
['E' 'T']
['X']
Upwards and left
[['X' 'E' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'X']
 ['T' 'X' 'X' 'X' 'X' 'X' 'S' 'X' 'X' 'X']
 ['X' 'X' 'G' 'X' 'C' 'X' 'X' 'R' 'X' 'X']
 ['X' 'O' 'X' 'X' 'X' 'O' 'X' 'X' 'O' 'X']
 ['D' 'X' 'X' 'X' 'X' 'X' 'W' 'X' 'X' 'H']]
['D']
['X' 'X']
['X' 'O' 'X']
['T' 'X' 'X' 'X']
['X' 'X' 'G' 'X' 'X']
['E' 'X' 'X' 'X' 'X']
['X' 'X' 'C' 'O' 'W']
['X' 'X' 'X' 'X' 'X']
['X' 'X' 'X' 'X' 'X']
['E' 'S' 'R' 'O' 'H']
['X' 'X' 'X' 'X']
['X' 'X' 'X']
['X' 'X']
['X']
user_38588830

You can iterate over each character, and if the character is part of a word, then each possibility (vertical, horizontal, right-diag, left-diag) can be checked:

from collections import namedtuple
d = ['HXXWXXXXXD', 'XOXXOXXXOX', 'XXRXXCXGXX', 'XXXSXXXXXT', 'XXXXEXXXEX']
node = namedtuple('node', ['val', 'ischar'])
_d = [[node(i, i != 'X') for i in b] for b in d]
def traverse(_func, _start, _board):
  while True:
    try:
       _a, _b = _func(*_start)
       if not _board[_a][_b].ischar:
         break
       _start = [_a, _b]
       yield _board[_a][_b].val
    except:
       break

def get_words(board, *args):
  funcs = [[lambda x, y:(x-1, y), lambda x, y:(x+1, y)], [lambda x, y:(x, y+1), lambda x, y:(x, y-1)], [lambda x:(x-1, y-1), lambda x, y:(x+1, y+1)], [lambda x, y:(x-1, y+1), lambda x, y:(x+1, y-1)]]
  for _s1, _s2 in funcs:
     yield ''.join(traverse(_s1, args, board))+board[args[0]][args[1]].val+''.join(traverse(_s2, args, board))


def words(board, to_find):
  for i in range(len(board)):
    for b in range(len(board[0])):
      if board[i][b].ischar:
        for word in get_words(board, i, b):
          if word in to_find:
            yield word
          if word[::-1] in to_find:
            yield word[::-1] 

print(list(set(words(_d, ["HORSE","COW","DOG","ET"]))))

Output:

['DOG', 'ET', 'HORSE', 'COW']
user_73267380
Related