Iterating based on a variable number of inner loops

Question

In the below code I am trying to go through all possible combination of alphabets for number of characters which are runtime variable.

The purpose of this code is to build a kind of password cracker, which basically brute-force guess the string. I want to use loop, because I will be able to break the loop as soon as the correct combination is hit thus saving on time and resources which otherwise will be required if I try to build an array of all possible combinations in first step.

I have a static code which works for a string 5 characters long but in reality my string could be any length. How can I make my code work with any length of string?

let len = textField.text?.characters.count //Length of string
let charRange = "abcdefghijklmnopqrstuvwxyz" //Allowed characterset

for char1 in charRange.characters {
    for char2 in charRange.characters {
        for char3 in charRange.characters {
            for char4 in charRange.characters {
                for char5 in charRange.characters {
                     // Do whatever with all possible combinations
                }
            }
        }
    }
}

I think I have to utilize for totalChars in 1...len { somehow but can't figure out how the for loops are going to be created dynamically?

Answer 1

As suggested by Martin R, you can use recursion

This is the function

func visit(alphabet:[Character], combination:[Character], inout combinations:[String], length: Int) {
    guard length > 0 else {
        combinations.append(String(combination))
        return
    }

    alphabet.forEach {
        visit(alphabet, combination: combination + [$0], combinations: &combinations, length: length - 1)
    }
}

The helper function

func combinations(alphabet: String, length: Int) -> [String] {
    var combinations = [String]()
    visit([Character](alphabet.characters), combination: [Character](), combinations: &combinations, length: length)
    return combinations
}

Test

Now if you want every combination of 3 chars, and you want "ab" as alphabet then

combinations("ab", length: 3) // ["aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"]

Duplicates

Please note that if you insert duplicates into your alphabet, you'll get duplicate elements into the result.

Time complexity

The visit function is invoked as many times as the nodes into a perfect k-ary tree with height h where:

• k: the number of elements into the alphabet param
• h: the length param

Such a tree has

nodes. And this is the exact number of times the function will be invoked.

Space complexity

Theoretically The max number of stack frames allocated at the same time to execute visit is length.

However since the Swift compiler does implement the Tail Call Optimization the number of allocated stack frames is only 1.

Finally we must consider that combinations will be as big as the number of results: alphabet^length

So the time complexity is the max of length and elements into the result.

And it is O(length + alphabet^length)

---

Update

It turns out you want a brute force password breaker so.

func find(alphabet:[Character], combination:[Character] = [Character](), length: Int, check: (keyword:String) -> Bool) -> String? {
    guard length > 0 else {
        let keyword = String(combination)
        return check(keyword: keyword) ? keyword : nil
    }

    for char in alphabet {
        if let keyword = find(alphabet, combination: combination + [char], length: length - 1, check: check) {
            return keyword
        }
    }

    return nil
}

The last param check is a closure to verify if the current word is the correct password. You will put your logic here and the find will stop as soon as the password is found.

Example

find([Character]("tabcdefghil".characters), length: 3) { (keyword) -> Bool in
    return keyword == "cat" // write your code to verify the password here
}

Answer 2

Idea: form the string using an array of indices into your alphabet; each time increment the indices.

[0, 0, 0] -> [1, 0, 0] -> [2, 0, 0] ->
[0, 1, 0] -> [1, 1, 0] -> [2, 1, 0] ->
[0, 2, 0] -> [1, 2, 0] -> [2, 2, 0] ->
[0, 0, 1] ... [2, 2, 2]

Here's an example using a length of 3 and an alphabet of abcd

let len = 3
let alphabet = "abcd".characters.map({ String($0) })
var allStrings = [String]()
let maxIndex = alphabet.endIndex
var indicies = Array(count: len, repeatedValue: 0)

outerLoop: while (true) {
    // Generate string from indicies
    var string = ""
    for i in indicies {
        let letter = alphabet[i]
        string += letter
    }
    allStrings.append(string)
    print("Adding \(string)")

    // Increment the index
    indicies[0] += 1

    var idx = 0
    // If idx overflows then (idx) = 0 and (idx + 1) += 1 and try next
    while (indicies[idx] == maxIndex) {
        // Reset current
        indicies[idx] = 0
        // Increment next (as long as we haven't hit the end done)
        idx += 1
        if (idx >= alphabet.endIndex - 1) {
            print("Breaking outer loop")
            break outerLoop
        }
        indicies[idx] += 1
    }
}

print("All Strings: \(allStrings)")

Answer 3

Alternative to recursion; loop radix representation of incremental (repeated) traversing of your alphabet

An alternative to recursion is to loop over an numeral representation of your alphabet, using a radix representative for the different number of letters. A limitation with this method is that the String(_:,radix:) initializer allows at most base36 numbers (radix 36), i.e., you can at most perform your "password cracking" with a set of characters with a unique count <=36.

---

Help function

// help function to use to pad incremental alphabeth cycling to e.g. "aa..."
let padToTemplate: (str: String, withTemplate: String) -> String = {
    return $0.characters.count < $1.characters.count
        ? String($1.characters.suffixFrom($0.characters.endIndex)) + $0
        : $0
}

Main radix brute-force password checking method

// attempt brute-force attempts to crack isCorrectPassword closure
// for a given alphabet, suspected word length and for a maximum number of 
// attempts, optionally with a set starting point
func bruteForce(isCorrectPassword: (String) -> Bool, forAlphabet alphabet: [Character], forWordLength wordLength: Int, forNumberOfAttempts numAttempts: Int, startingFrom start: Int = 0) -> (Int, String?) {
    
    // remove duplicate characters (but preserve order)
    var exists: [Character:Bool] = [:]
    let uniqueAlphabet = Array(alphabet.filter { return exists.updateValue(true, forKey: $0) == nil })
    
    // limitation: allows at most base36 radix
    guard case let radix = uniqueAlphabet.count
        where radix < 37 else {
        return (-1, nil)
    }
    
    // begin brute-force attempts
    for i in start..<start+numAttempts {
        let baseStr = String(i, radix: radix).characters
            .flatMap { Int(String($0), radix: radix) }
            .map { String(uniqueAlphabet[$0]) }
            .joinWithSeparator("")
        
        // construct attempt of correct length
        let attempt = padToTemplate(str: baseStr,
            withTemplate: String(count: wordLength, repeatedValue: alphabet.first!))
        
        // log
        //print(i, attempt)
        
        // test attempt
        if isCorrectPassword(attempt) { return (i, attempt) }
    }
    return (start+numAttempts, nil) // next to test
}

---

Example usage

Example usage #1

// unknown content closure
let someHashBashing : (String) -> Bool = {
    return $0 == "ask"
}

// setup alphabet
let alphabet = [Character]("abcdefghijklmnopqrstuvwxyz".characters)

// any success for 500 attempts?
if case (let i, .Some(let password)) =
    bruteForce(someHashBashing, forAlphabet: alphabet,
               forWordLength: 3, forNumberOfAttempts: 500) {
    print("Password cracked: \(password) (attempt \(i))")
} /* Password cracked: ask (attempt 478) */

Example usage #2 (picking up one failed "batch" with another)

// unknown content closure
let someHashBashing : (String) -> Bool = {
    return $0 == "axk"
}

// setup alphabet
let alphabet = [Character]("abcdefghijklmnopqrstuvwxyz".characters)

// any success for 500 attempts?
let firstAttempt = bruteForce(someHashBashing, forAlphabet: alphabet,
                              forWordLength: 3, forNumberOfAttempts: 500)
if let password = firstAttempt.1 {
    print("Password cracked: \(password) (attempt \(firstAttempt.0))")
}
// if not, try another 500?
else {
    if case (let i, .Some(let password)) =
        bruteForce(someHashBashing, forAlphabet: alphabet,
                   forWordLength: 3, forNumberOfAttempts: 500,
                   startingFrom: firstAttempt.0) {
        print("Password cracked: \(password) (attempt \(i))")
    } /* Password cracked: axk (attempt 608) */
}