How do you create any number of nested loops?

Question

I'm trying to write a program that tests every possible string before matching a specific string and also gives the number attempt. Take this example:

a = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g', 7: 'h', 8: 'i', 9: 'j', 10: 'k', 11: 'l', 12: 'm',
     13: 'n', 14: 'o', 15: 'p', 16: 'q', 17: 'r', 18: 's', 19: 't', 20: 'u', 21: 'v', 22: 'w', 23: 'x', 24: 'y',
     25: 'z'}

word = 'bike'

found = False
counter = 0
for i in range(len(a)):
    for j in range(len(a)):
        for k in range(len(a)):
            for m in range(len(a)):
                string = f'{a[i]}{a[j]}{a[k]}{a[m]}'
                counter += 1
                print(string, counter)
                if string == word:
                    found = True
                    break
            if found:
                break
        if found:
            break
    if found:
        break

And the output would look something like this:

aaaa 1
aaab 2
aaac 3
aaad 4
aaae 5
aaaf 6
...
bijz 23244
bika 23245
bikb 23246
bikc 23247
bikd 23248
bike 23249

You can use this code if you know that the word will always be four characters, but what if you don't know the length? How would you create this when the length is not known? I'm trying to think if there is some recursive function that could achieve this, but nothing is working out. The program that I am trying to achieve would have an output like this:

a 1
b 2
c 3
...
aa 27
ab 28
ac 29
...
ba #
bb #
bc #
...
aaa #
aab #
aac #

Answer 1

this should work; you enter the length in the repeat argument of product while enumerate enumerates the words (starting at 0 by default; you could add start=1 depending on your needs):

from itertools import product


search = "bike"

for i, item in enumerate(product(a.values(), repeat=len(search))):
     word = "".join(item)
     print(word, i)
     if word == search:
          break

it outputs:

...
bikb 23245
bikc 23246
bikd 23247
bike 23248

---

if you are only interested in this number you could translate the word into a number in base 26 and convert that using int:

alpha_to_digits = str.maketrans(
    "abcdefghijklmnopqrstuvwxyz", "0123456789abcdefghijklmnop")

word = 'bike'

d = word.translate(alpha_to_digits)
print(d, int(d, base=26))
# 18a4 23248

which translates the word bike to its digit representation in base 26 (18a4) which can then be converted to an integer (23248).

packed into a function:

def number(word):
    return int(word.translate(alpha_to_digits), base=26)

Answer 2

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.

Answer 3

You can use itertools.product (for nested for loops) + dict.values (to loop over the letters directly) + enumerate (starting at 1, to get the counter):

from itertools import product

word = 'bike'

for counter, letters in enumerate(product(a.values(), repeat = len(word)), 1):
  string = ''.join(letters)
  print(string, counter)
  if string == word:
      break

Output:

...
...
...
bika 23245
bikb 23246
bikc 23247
bikd 23248
bike 23249