Dynamic programming - number of possible passwords

user_6719765 0
Viewed 203

I have a question a dynamic programming problem. I find it very difficult, so I hope I can get some help.

Given a list of words and the length n of a password, I would like to know the amount of possible combinations of passwords. Passwords can be either a single word of length n or a combination of words separated by underscores.

For example, passwords(5, ["house, "no"]) = 2 because the possible passwords are "house" and "no_no".

What I have tried so far:

def voc_to_list(vocabulary):
    """
    produces a list lengths such that lengths[i] is the number of
    words of length i in vocabulary
    """
    max_len = max([len(w) for w in vocabulary])
    lengths = [0] * (max_len + 1)
    for w in vocabulary:
        wordLength = len(w)
        lengths[wordLength] += 1
    return lengths


def passwords(L, vocabulary):
    lengths = voc_to_list(vocabulary)
    k = len(lengths)
    tbl = [0] * (L + 1)
    for i in range(L + 1):
        if i < k:
            tbl[i] = lengths[i]
        for j in range(min(i, k)):
            # This is where I am stuck
            tbl[i] += ??
    return tbl[L]

Inside tbl[i] I already have the words of length i. I am stuck in how to fill out the table to take into account the combinations of words.

dynamic-programming python
1 Answers

You should store in tbl[i] the maximal number of possible passwords with length i, that much you already figured out. The update step involves combinatorics. A simple example would be passwords(9, ["a", "e", "i", "o", "u"]) == 5**5. If this is not intuitive for you, I suggest revisiting the needed maths.

So, the update step is actually the sum of products of the maximal number of combinations tbl[i-j-1] and the new word candidates which "complete" the password length to that point lengths[j]. For this, you iteratively update:

def passwords(L, vocabulary):
    lengths = voc_to_list(vocabulary)
    k = len(lengths)
    tbl = [0] * (L + 1)
    for i in range(L + 1):
        if i < k:
            tbl[i] = lengths[i]
        for j in range(1, min(i-1, k)):
            tbl[i] += tbl[i-j-1] * lengths[j]  # -1 due to underscores
    return tbl[L]
user_138063260
Related