hackerrank password cracker timeout due to recursion

Question

This problem simply restated is this: given a bunch of strings and a target string, what all combinations from the given string can combine together to form target string with and without repetition.

e.g.

strings: we do what we must because we can

target: wedowhatwemustbecausewecan

output: we do what we must because we can

Approach I took is to remove every longer word from the target until target becomes empty. If targets becomes empty then just return the output. If longer words doesn't lead to a solution then try with shorter words and so on. I am also using memoization to make sure that if the target is already tried then just return, same as backtracking with memoization.

This apporach passed all the testcases except 2, where I am getting timeout.

def recursions(word_map, paswd, output, remember):
    flag = 0
    if len(paswd) == 0:
        return 1
    if paswd in remember:
        return flag
    for char in paswd:
        for word in (word_map[char] if char in word_map else []):
            if paswd.startswith(word):
                output.append(word + " ")
                if recursions(word_map, paswd[len(word):], output, remember):
                    return 1
                output.pop()
        remember[paswd] = 1
    return flag

Please help in providing a hint. Complete solution is here.

The code looks correct, except perhaps you'd have problems if the recursion goes too deep. But debugging problems on stackoverflow require a specific problem and reproduction of the problem in the question. — Paul Hankin
– Paul Hankin, Commented Aug 27, 2017 at 6:55
Try to switch to pypy. Though the timeout for pypy is much lower than for python, in some cases you won't exceed it. — Aleksandr Borisov
– Aleksandr Borisov, Commented Aug 27, 2017 at 8:08

niemmi · Accepted Answer · 2017-11-04 09:10:57Z

1

You could try dynamic programming approach where you mark the ending locations of each password. Start by trying every password at the beginning of the longer string. If it fits there mark down the ending position in the longer string. You could then repeat the same process for every location in longer string where previous location is marked as ending position.

Hope this helps you getting started, I've intentionally left out some of the information required for full solution so let me know in comments if you're still stuck.

EDIT Here's a short example on what I'm talking about. It doesn't allow you to reconstruct the solution but it shows how to do the matching without recursion:

passwords = ['foo', 'bar']
login = 'foobar'

ends_here = [False] * len(login)

for i in range(len(ends_here)):

    # Match password at the beginning or if password match
    # ended to previous index
    if i == 0 or ends_here[i - 1]:
        for pw in passwords:
            if login.find(pw, i, i + len(pw)) != -1:
                ends_here[i + len(pw) - 1] = True

print(ends_here)
print('We can match whole login attempt:', ends_here[-1])

Output:

[False, False, True, False, False, True]
We can match whole login attempt: True

EDIT Took a closer look at the code provided in the question. The issue is on the line where matched strings are filtered by the characters contained in the target: for char in paswd:. Instead of doing filtering for every character in the target string the filtering should be done for every unique character: for char in set(paswd):. Fix that and solution runs much faster but would probably be even faster if there wouldn't be that kind of filtering at all since the maximum number of shorter strings is 10.

edited Nov 4, 2017 at 9:10

answered Aug 27, 2017 at 6:54

niemmi

17.3k7 gold badges38 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

user3053970 Over a year ago

can you elaborate more as I am doing very similar to that in my recursive approach?

niemmi Over a year ago

@user3053970 Added short example on how to do the matching without recursion. You need to modify it though so that you can print the passwords in case there's a match,

niemmi Over a year ago

@monster You're correct but that was intentionally left out since the question was asking hint, not a full solution.

monster Over a year ago

oh sorry. deleted my comment so no worries:)

niemmi Over a year ago

@user3053970: Added explanation why the code provided in the question is so slow compared to example in the answer.

|

Collectives™ on Stack Overflow

hackerrank password cracker timeout due to recursion

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related