10
\$\begingroup\$

As a puzzle we were asked to bring out the possibilities in breaking a 4 letter wordlock combination. It was to be a four letter word from the English dictionary. There were 10 possible characters in each place. So \$10^4\$ possibilities of random words. I brute forced my code to return a list of possible words by first reading a file of 300k English words and storing it in a list. Then I applied a filter at each place to narrow down the list of possible words that could work on the combo.

I know I am brute forcing the code down to 1089 possibilities, did I overlook other possibilities? I am a beginner and if I wanted to learn how to improve the efficiency of my code and make it simpler/functioning, what steps can I take?

filterlist2 = ['a','r','t','h','i','v','o','y','l','e',]
filterlist3 = ['a','l','t','o','i','n','s','r','m','f',]
filterlist4 = ['a','m','d','k','e','s','x','p','l','y',]

#filterlist1 basically before I realized I can store parameters in a list
lines = tuple(open("words.txt", 'r'))
char1filter=[]
for element in lines:
    if len(element)==5:
        if element.startswith('b') is True:
            char1filter.append(element)
        elif element.startswith('p') is True:
            char1filter.append(element)
        elif element.startswith('t') is True:
            char1filter.append(element)
        elif element.startswith('s') is True:
            char1filter.append(element)
        elif element.startswith('m') is True:
            char1filter.append(element)
        elif element.startswith('d') is True:
            char1filter.append(element)
        elif element.startswith('c') is True:
            char1filter.append(element)
        elif element.startswith('g') is True:
            char1filter.append(element)
        elif element.startswith('f') is True:
            char1filter.append(element)
        elif element.startswith('l') is True:
            char1filter.append(element)


#print(char1filter)

print(len(char1filter))
#returned 3935 results
#filter 2 for second character
char2filter =[]
for element1 in char1filter:
    if element1[1] in filterlist2:
        char2filter.append(element1)
print('char2 filter applied')
print(char2filter)
print(len(char2filter))
#filter 2 returned 3260 words
#filter 3

char3filter =[]
for element2 in char2filter:
    if element2[2] in filterlist3:
        char3filter.append(element2)
print(char3filter)
print(len(char3filter))
#filter 3 returned 1991 words
#filter 4
char4filter =[]
for element3 in char3filter:
    if element3[3] in filterlist4:
        char4filter.append(element3)
print(char4filter)
print(len(char4filter))

#filter 4 returned 1089 words
\$\endgroup\$
  • \$\begingroup\$ For starters, I'd get rid of that horrible repetitive if/else chain. I wrote this function to handle all of those cases at once. \$\endgroup\$ – Braden Best Aug 7 '16 at 4:08
  • \$\begingroup\$ Oh wait, I'm thinking in C. The less tedious way to do it would be to just use element[0] in "bptsmdcgfl" \$\endgroup\$ – Braden Best Aug 7 '16 at 4:21
  • 1
    \$\begingroup\$ Adding is True to a boolean condition is useless. In fact sometimes the condition doesn't return a bool value, and in such case adding is True breaks the condition. \$\endgroup\$ – Bakuriu Aug 7 '16 at 10:01
  • \$\begingroup\$ @Bakuriu is correct. is does a strict equality check looking at both the value and type. It's kind of (but not exactly) like JavaScript's === operator \$\endgroup\$ – Braden Best Aug 7 '16 at 19:50
7
\$\begingroup\$

In addition to the suggestions made by Joe Wallis, here’s one that will help performance:

Don’t store the entire file in a tuple.

This requires Python to store the entire file in memory, which is neither efficient nor necessary. Since you immediately take this tuple and iterate over it, it would be more efficient to iterate over the open file directly. In terms of Joe’s version, it looks more like this:

with open('words.txt', 'r') as f:
    data = [
        element
        for element in f
        if len(element) == 5
    ]
\$\endgroup\$
11
\$\begingroup\$

First off I'd change how you are making char1filter. Here's what I'd do differently:

  • Remove the is True as it's implied.
  • Change the element.startswith('') to element[0] == 'a'.
  • Merge all the element checks into one, using in. element[0] in 'bptsmdcgfl'.
  • Use a list comprehension.

Merging all this together we should get:

char1filter = [
    element
    for element in lines
    if len(element) == 5 and element[0] in 'bptsmdcgfl'
]

Id however store 'bptsmdcgfl' with filterlist2, filterlist3 and filterlist4. And instead just remove all element that aren't 5 long.

five_long = [
    element
    for element in lines
    if len(element) == 5
]

This leaves you with four roughly identical pieces of code. And so I'd change all the filterlists to be a single list to loop through. And then perform the transformations inside this.

data = five_long
for to_filter in filter_lists:
    data = [
        element
        for element in data
        if element[0] in to_filter
    ]
    print(data)
    print(len(data))

If however you just want the last filter list, then you can merge all the filters into one, and then do a single filter on that.

filter_list = [e for l in filter_list for e in l]
data = [
    element
    for element in five_long
    if element[0] in filter_list
]
print(data)
print(len(data))

You should also read PEP8 to style your code correctly, like I have above, which makes your code much easier to read. You should also use with when opening files, tuple(open('')) is bad and should instead be:

with open('words.txt', 'r') as f:
    lines = tuple(f)

And so the code could be:

FILTER_LISTS = [
    ['b', 'p', 't', 's', 'm', 'd', 'c', 'g', 'f', 'l'],
    ['a', 'r', 't', 'h', 'i', 'v', 'o', 'y', 'l', 'e'],
    ['a', 'l', 't', 'o', 'i', 'n', 's', 'r', 'm', 'f'],
    ['a', 'm', 'd', 'k', 'e', 's', 'x', 'p', 'l', 'y'],
]

with open('words.txt', 'r') as f:
    lines = tuple(f)

data = [
    element
    for element in lines
    if len(element) == 5
]
for to_filter in FILTER_LISTS:
    data = [
        element
        for element in data
        if element[0] in to_filter
    ]
    print(data)
    print(len(data))
\$\endgroup\$
  • \$\begingroup\$ filter_list = [e for l in filter_list for e in l] - No, just use list(itertools.chain.from_iterable(filter_list)). While you're at it, change list() to set() for performance. \$\endgroup\$ – Kevin Aug 7 '16 at 4:28
  • \$\begingroup\$ @Kevin OP is a begginer, and so I chose to not import any external tools. And yes you can use set. \$\endgroup\$ – Peilonrayz Aug 7 '16 at 12:30
  • \$\begingroup\$ Suggested further optimization: I find per-character definitions of the filter lists visually harsh. Your code works equally well if the filter lists are defined as: FILTER_LISTS = ['bptsmdcgfl', 'arthivoyle', 'altoinsrmf', 'amdkesxply']. \$\endgroup\$ – scottbb Aug 7 '16 at 13:18
  • \$\begingroup\$ I object to characterizing a standard library module as "external," but I see your point. \$\endgroup\$ – Kevin Aug 10 '16 at 2:45
1
\$\begingroup\$

One element at a time

While processing, you only care about individual elements. An element is either included or excluded. The filter operation is completely independent: it does not matter what the order of the words is, what number of words there are, or what the outcome is of the word you processed before.

So think of your filter operation as function that works on a single element. As input it takes a single element, and it outputs either True or False, dependent on whether this particular element should pass (True) or be left out (False).

def is_correct(element):
    if len(element) != 5:
        return False
    if element[0] in 'abcdef':
        return True
    # etc. the other answers have good tips

Creating a function that operates on a single element makes it very simple to check whether it actually works, by writing a bunch of tests:

assert is_correct('abcdef')
assert not is_correct('zzzxxxyyy')

Make sure you include enough edge cases. Writing tests can help you prove that your code works like you want it to, and can also be very useful when you want to make changes in the future.

If you figured out how to filter a single element, it becomes very simple to apply this filter over your entire set in either an imperative or functional style, both are easy with Python:

# imperative
filtered = []
for element in lines:
    if is_correct(element):
        filtered.append(element)

# functional
filtered = list(filter(is_correct, lines))

As alexwlchan mentioned in his answer, if you read the file one element at a time, a filter like this helps you to keep only the elements in memory that you are interested in. This will save you a lot of memory, and could allow you to read files many times bigger than the available working memory.

\$\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.