Checking a word grid

Question

I wrote this program where you can input x amount of words that of length x that checks if the grid formed is the same words vertically as they are horizontally:

F I L E
I C E D
L E A D
E D D Y

The words can be entered in any order and the letters must stay in the same order. i.e. F I L E can't be F E L I

The permutations part of my code is so I can get all permutations of the words to check if they work in a grid

This feels very clunky and I'd like to slim it down. Does anyone have any suggestions?

import sys
import itertools
numWords = int(raw_input('Enter Number of Words: '))
words = []
stuff = []
for i in range(numWords):
    word = raw_input('Enter Word: ')
    if len(word) != numWords:
        print('Not Valid Grid')
        sys.exit()
    words.append(word)

stuff = list(itertools.permutations(words))
for i in range(len(stuff)):
    count = 0
    for j in range(0,4):
        s = ''
        for k in range(0,4):
            if stuff[i][j][k] == stuff[i][k][j]:
                s += stuff[i][k][j]
                if s in stuff[i]:
                    count += 1
    if count == numWords:
        for l in stuff[i]:
            print l
        sys.exit()
print('Not a Valid Grid')

Answer 1

You can use zip() to interleave iterables. This function produces tuples, so we'll just make everything a tuple for easy comparison. The * operator unpacks the arguments, sending each separate "word" to zip() so it works as expected.

>>> words = ['file', 'iced', 'lead', 'eddy'] # simulated input
>>> words = tuple(map(tuple, words))
>>> words == tuple(zip(*words))
True
>>> print(*words)
('f', 'i', 'l', 'e') ('i', 'c', 'e', 'd') ('l', 'e', 'a', 'd') ('e', 'd', 'd', 'y')
>>> print(*(tuple(zip(*words)))) # True because these results are the same
('f', 'i', 'l', 'e') ('i', 'c', 'e', 'd') ('l', 'e', 'a', 'd') ('e', 'd', 'd', 'y')
>>> words = ['file', 'iced', 'eddy', 'lead'] # different order
>>> words = tuple(map(tuple, words))
>>> words == tuple(zip(*words))
False
>>> print(*words)
('f', 'i', 'l', 'e') ('i', 'c', 'e', 'd') ('e', 'd', 'd', 'y') ('l', 'e', 'a', 'd')
>>> print(*(tuple(zip(*words)))) # False because these results are different
('f', 'i', 'e', 'l') ('i', 'c', 'd', 'e') ('l', 'e', 'd', 'a') ('e', 'd', 'y', 'd')

To check whether any permutation is a successful grid, you can use a construct like for..else:

>>> words = ['file', 'iced', 'eddy', 'lead'] # there exists a successful permutation
>>> for words_per in itertools.permutations(words):
...     if tuple(map(tuple, words_per)) == tuple(zip(*words_per)):
...         print('Success!')
...         break
... else:
...     print('Failure.')
...
Success!

To print the successful grids:

>>> words = ['file', 'iced', 'eddy', 'lead'] # there exists a successful permutation
>>> success = False # set a flag to watch for success
>>> for words_per in itertools.permutations(words):
...     if tuple(map(tuple, words_per)) == tuple(zip(*words_per)):
...         success = True # set the flag to True
...         print(*(''.join(word) for word in words_per), sep='\n') # print the grid
...
file
iced
lead
eddy
>>> if not success:
...     print('No matches.')
...
>>>

If you want the words printed in uppercase with each letter separated by a space, you can replace ''.join(word) with ' '.join(word.upper()).

F I L E
I C E D
L E A D
E D D Y

Answer 2

This problem statement is simply asking if the array is a symmetrical matrix, so lets explore making a function which checks that!

We want a function which checks an object for all the qualities of a symmetrical matrix. Because we like to reuse functions in future programs, we're gonna make this function robust.

It checks that the parameter is a 2d array of either tuples or lists, that the matrix is a square, and checks that element i,j is the same as element j,i.

def check_symmetrical(array2d):
    # Check that the array is a valid square matrix
    if not type(array2d) is list and not type(array2d) is tuple:
        return False
    for row in array2d:
        if (not type(row) is list) and (not type(row) is tuple):
            return False
        if not len(row) == len(array2d):
            return False
    # Check that the array is a valid symmetrical matrix
    for i in range(len(array2d)):
        for j in range(len(array2d)):
            if not array2d[i][j] == array2d[j][i]:
                return False
    # if no failures then it must be good!
    return True

Lets revisit your input code

numWords = int(raw_input('Enter Number of Words: '))

This line has the opportunity to crash our code. Never trust the user! Lets use the isdigit function to fix that up

num_words = raw_input('Enter Number of Words: ') 
if not num_words.isdigit():
    print('Not a Valid Number')
    sys.exit()
num_words = int(num_words)

When a user input garbage, the program will close gracefully.

Now we need to turn that list of words into a 2d array. Lets use list comprehension

words = []
for i in range(num_words):
    word = raw_input('Enter Word: ')
    if len(word) != num_words:
        print('Not Valid Grid')
        sys.exit()
    words.append(word)
# comprehension used to create a list of lists
word_array2d = [list(word) for word in words]

Finally, run that array through our check_symmetrical function!

if check_symmetrical(word_array2d):
    print('Valid Grid')
else:
    print('Not a Valid Grid')

Answer 3

Inspired by Calpratt's observation that this is really a question about testing matrix symmetry, I wanted to post a numpy version.

from sys import exit
from itertools import permutations

import numpy as np

# Size of the problem n
n = int(raw_input('Enter Number of Words: '))

# Get n words, each of length n, and recast them into a matrix of integers
words = []
for i in range(n):
    word = raw_input('Enter Word: ')
    if len(word) != n:
        print('Not Valid Grid')
        exit()
    words.append(map(ord, word))
matrix = np.array(words)

# Check each row permutation of the matrix for symmetry:
row_permutation_iter = permutations(range(n))
success = False
for row_permutation in row_permutation_iter:
    if (matrix[row_permutation, :].transpose() == matrix).all():
        success = True
        break

# Print results
if success:
    print 'Success!  Your word list can be permuted into a symmetric matrix.'
else:
    print 'Your word list cannot be permuted into a symmetric matrix.'

Key changes from the posted version:

1. Each word is converted to a list of integers by map(ord, word).
2. The words list is converted to a numpy matrix.
3. Instead of nested for loops, there is just one for loop, over the permutations of the row order of the matrix.
4. The key expression is (matrix[row_permutation, :].transpose() == matrix).all(). This tests if every element (all()) in the transpose of the row-permuted matrix is equal to the corresponding element original matrix.
5. Since only one function from sys and one from itertools were used, I just imported them by themselves.
6. I added more comments.
7. Rather than just sys.exit() from the middle of the loop, I added a success variable and set it to True only on success. This allows putting the print messages for success/failure in the same place of the code, which should facilitate future changes or porting this script into a function. If you want/need it, you could add exit() at the end of my code block.

Whether you regard my code as an improvement probably will depend on how familiar you are with numpy. I doubt it matters in this particular application, but if for some reason you wanted to do it with huge words, this version would likely be faster.

Sample output:

Enter Number of Words: 4
Enter Word: fire
Enter Word: iced
Enter Word: eddy
Enter Word: lead
Your word list cannot be permuted into a symmetric matrix.

---

Enter Number of Words: 4
Enter Word: file
Enter Word: iced
Enter Word: lead
Enter Word: eddy
Success!  Your word list can be permuted into a symmetric matrix.

Answer 4

Once stuff[i][j][k] != stuff[i][k][j], you can directly break out of the inner loops (e.g. by throwing an exception) and continue with the next i. This will improve performance immensely.