Note: all functions presented in this answer return 23248 as the answer for 'bike', because I like counting from 0. If you prefer counting from 1, and want to get the answer 23249, then just add a +1 somewhere in the functions.
First idea: Write your own increment_word function:
You can iterate through words by writing a function that calculates the next word. For instance, the next word after bikd should be bike, and the next word after cdzz should be ceaa.
Strings are immutable in python, so for ease we're going to use a list of chars instead of a string.
def increment_word(w):
i = len(w) - 1
while (w[i] == 'z'):
w[i] = 'a'
i = i - 1
w[i] = chr(ord(w[i]) + 1)
Note that this function is only guaranteed to work if called on a word that contains at least one non-'z' letter. It's up to the user not to ask for the next word after 'zzz'.
Now we can solve your problem:
def find_word(w):
candidate = ['a' for _ in w]
w = list(w)
count_attempts = 0
while candidate != w:
increment_word(candidate)
count_attempts += 1
return count_attempts
Second idea: Use itertools.product
In general, when you want to iterate over complex things in python, someone already wrote exactly the looping construct you need and it's in the itertools package. If it's not, then maybe it's in itertools recipes or in more_itertools.
In this case, you can use itertools.product:
from string import ascii_lowercase
from itertools import product
def find_word(w):
for count_attempts, candidate in enumerate(product(*[ascii_lowercase]*len(w))):
if all(x == y for x,y in zip(w, candidate)):
return count_attempts
Note how we use string.ascii_lowercase rather than typing out the whole alphabet ourselves. Someone was kind enough to teach python the alphabet. No need to be overzealous and rewrite the alphabet ourselves (with the risk of forgetting a letter and breaking everything).
Third idea: Use recursion instead of iteration
Any kind of complex looping can be simulated using recursion. Note that python is a pretty bad language for recursion - in particular, recursive functions tend to be pretty slow in python; not to mention the program might crash if the recursion is too deep, because python doesn't optimize tail-calls. But you should think about this option if you ever need to use a language other than python.
def find_word(word):
return find_word_aux(word, 'a'*len(word), 0)
def find_word_aux(word, candidate, count_attempts):
if candidate == word:
return count_attempts
else:
i,c = max((i,c) for i,c in enumerate(candidate) if c != 'z')
return find_word_aux(word, candidate[:i] + chr(ord(c)+1) + 'a'*(len(word)-i-1), count_attempts + 1)
Note how this ends up being extremely similar to the increment_word version. Unfortunately, with default python parameters on my machine, it only works for words between aaa and bmg. For any word after bmh, it crashes with exception RecursionError: maximum recursion depth exceeded in comparison. If you translate this code to a language which optimize tail-calls, such as OCaml, Haskell or C, then it will work for any word.
Fourth idea: use combinatorics to solve your problem instantly
Instead of iterating through words one by one, you could try to count batches of words using multiplication. For instance, it is easy to see that there are:
26 * 26 * 26 = 26^3 = 17576 words between aaaa and azzz;8 * 26 * 26 = 5408 words between baaa and bhzz;10 * 26 = 260 words between biaa and bijz;5 words between bika and bike.
Total: 23249 words between aaaa and bike.
This gives us a python program:
def find_word(w):
count_attempts = 0
for i,c in enumerate(w):
n = ord(c) - ord('a')
count_attempts += n * 26**(len(w) - i - 1)
return count_attempts
Note that the for-loop here is over the characters of w rather than over all possible words; so we are iterating 4 times and not 23249 times. This function is much faster than the other versions.
