6
\$\begingroup\$

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')
\$\endgroup\$
  • \$\begingroup\$ Are the words for a successful grid entered in the "correct" order, or would words = ['file', 'iced', 'eddy', 'lead'] be just as successful as words = ['file', 'iced', 'lead', 'eddy']? \$\endgroup\$ – TigerhawkT3 Jul 15 '15 at 20:19
  • \$\begingroup\$ @TigerhawkT3 I misread your comment and probably confused a lot of people, so sorry about that. You are correct in assuming that you can enter those words in any order and should still be able to determine if it's a valid grid. words = ['file', 'iced', 'eddy', 'lead'] and words = ['file', 'iced', 'lead', 'eddy'] should pass when entered in those orders. \$\endgroup\$ – SirParselot Jul 16 '15 at 12:07
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This is the type of answer I was looking for. The formatting is a little different then I wanted but that's not the important part. I was looking for a more python oriented way of doing this and this seems to be spot on \$\endgroup\$ – SirParselot Jul 16 '15 at 16:52
  • \$\begingroup\$ @SirParselot, what kind of formatting were you looking for? \$\endgroup\$ – TigerhawkT3 Jul 16 '15 at 17:03
  • \$\begingroup\$ nothing particular. Just aesthetically pleasing to look at in my opinion. The only thing I changed was that it only printed failure if all of the cases failed. Maybe I just copied it wrong since yours only prints Success! \$\endgroup\$ – SirParselot Jul 16 '15 at 17:41
  • \$\begingroup\$ This prints Success! one time if there's at least one success, and prints Failure. one time if there are no successes. What behavior did you want? \$\endgroup\$ – TigerhawkT3 Jul 16 '15 at 17:44
  • 1
    \$\begingroup\$ @SirParselot, I've added a version that prints out each successful grid. \$\endgroup\$ – TigerhawkT3 Jul 16 '15 at 18:23
8
\$\begingroup\$

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')
\$\endgroup\$
  • \$\begingroup\$ This is only for my personal use so I didn't care about it being robust but I still appreciate it. There are a few problems with the code, wrong variable names and such, but the big problem is that I wanted to be able to enter the words in any order and determine if they could form a valid grid. That's why I have the permutations part in my code. Overall, very nice write-up \$\endgroup\$ – SirParselot Jul 15 '15 at 20:52
  • \$\begingroup\$ @SirParselot ah! I should have waited fo more edits on the question before I wrote :p \$\endgroup\$ – flakes Jul 15 '15 at 20:57
  • 1
    \$\begingroup\$ Sorry, I thought people would pick up on the fact that you could enter the words in any order but now that I look at it you would need to understand the permutations part to pick up on that \$\endgroup\$ – SirParselot Jul 15 '15 at 21:00
4
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.