Guessing strings non-recursively

user_5217346 0
Viewed 60

I am making a Swift program to stress test certain pieces of computer hardware for a research project I am working on. One of the programs I am making is guessing a password. I currently have an implementation that works by doing it recursively.

func passwordCracker(_ password: String, _ guess: String) {
        for letter in letters {
            let newGuess = guess + letter
            tryCount = tryCount + 1
            if (password == newGuess) {
                let stop = DispatchTime.now().rawValue
                print("the password is \(newGuess) and it took \((stop - start)/1_000_000_000) seconds and \(tryCount) guesses.")
                //return
                
                //This causes the program to "crash" ending all the other recursive calls.
                //We use this instead of return as return will still continue to do other recursive calls after the fact
                exit(0)
            }
        }
        
        if(guess.count + 1 >= depth) { return }
        
        for letter in letters {
            passwordCracker(password, guess + letter)
        }
    }

I want to create a way of doing it non-recursively but have been unable to do so. My current implementation works only when the password to be guessed is in alphabetical order (abc, abcd, etc.). Would welcome any suggestions on how to fix it.

func iterative(_ pwd: String) {
        var guess = ""
        for _ in 0..<depth {
            for letter in letters {
                guess = guess + letter
                for l in letters {
                    if guess + l == pwd {
                        print("Password found. It is: \(pwd)")
                        return
                    }
                }
            }
        }
        print("Password NOT found")
    }
swift recursion
1 Answers

Issues with your versions

The problem with your recursive version is that the limits on stack size are quickly reached due to its elementary approach and the combinatorial explosion.

The algorithm works with a depth first exploration, and relies on the backtracking the recursive call allows: once you have reached a dead-end (no more letter to add and string not guessed), you return, and the previous level of recursion starts with the next combination restarting from previous guess.

By the way, instead of using exit you could make your function returns a boolean that would be true if the right combination is found. This would allow to gracefully return recursively instead of loosing time to explore all the other possibilities.

In your iterative guessing version, you only have one guess and only add letters to it, but if you have reached a dead-end, you do not backtrack (or just by one letter). This is why you explore only a small part of the possibilities.

How to make an iterative version

If you want to transform a recursive exploration of string combinatorics into an iterative one, you need to use a queue. Here is how a string guessing function could look like:

func iterativeGuess(_ solution: String) {
    var queue  = [ "" ]         // start with an empty string
    for _ in 0..<depth {        // depth first approach
        var newqueue =  [ String ] ()
        for guess in queue {    // add a letter to each strings generated
            for letter in letters {
                let newguess = guess + letter
                if newguess == solution {
                    print("String guessed. It is: \(newguess)")
                    return
                }
                else {
                    newqueue.append(newguess)
                    print ("tried \(newguess)")
                }
            }
        }
        queue = newqueue
    }
    print("String not guessed")
}

This function uses a breath-first exploration to guess a known string: first it tries all possible combination of length 1, then all the combinations of length 2 and so on. I leave as an exercise to transform it in depth first.

Disclaimer: It is important to underline that the question and its code appears to be about simulating the time to guess an already known string using brute-force for legitimate purposes and without malicious intent. The answer provided bears no risk of harm; the elementary knowledge provided is available in any CS textbook.

user_37234230
Related