How to shuffle an array in Swift

Given a task - write a function for shuffle array. Let's start from simple solution. This method called Pencil and paper method

Example of function which shuffle array

import Foundation

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

func shuffle(array: [Int]) -> [Int] {
    var arrayCopy = array
    var randomArray = [Int]()
    for _ in array {
        let randomIndex = Int(arc4random_uniform(UInt32(arrayCopy.count)))
        let removedValue = arrayCopy.remove(at: randomIndex)
        randomArray.append(removedValue)
    }
    return randomArray
}

let shuffledArray = shuffle(array: array)
print(array) //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(shuffledArray) //[7, 6, 9, 2, 8, 4, 3, 1, 5, 10]

Function shuffle, that provided below, works by following algorithm:

1. Make copy of incoming array to variable arrayCopy (we will remove items from this copy)
2. Make new empty array randomArray(we will add new values to this array)
3. For each item in copied array
1. Generate random index from 0 to arrayCopy length
2. Remove item with random index from arrayCopy (when remove we can store removed item)
3. Add removed item to randomArray
4. Return randomArray

Making Extension for shuffle array

For more handy usage let's move this code to extension

Example of extension for shuffle array

extension Array {
    
    func shuffle() -> [Element] {
        var arrayCopy = self
        var result = [Element]()
        for _ in self {
            let randomIndex = Int(arc4random_uniform(UInt32(arrayCopy.count)))
            let removedItem = arrayCopy.remove(at: randomIndex)
            result.append(removedItem)
        }
        return result
    }
}

let array2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array2) //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array2.shuffle()) //[5, 9, 6, 10, 2, 7, 1, 3, 8, 4]

let strings = ["one", "two", "three", "four", "five"]
print(strings) //["one", "two", "three", "four", "five"]
print(strings.shuffle()) //["five", "four", "one", "three", "two"]

The algorithm remains the same. But for now, because we use extension, any array can be shuffled, as we can see above now we can shuffle array of strings too.

Mutating self extension method
We can add modified version of our extension which modify current array in-place without return new array.

Example of extension which shuffle current array in-place

extension Array {
    
    mutating func shuffleInline() {
        var result = [Element]()
        for _ in self {
            let randomIndex = Int(arc4random_uniform(UInt32(self.count)))
            let removedItem = self.remove(at: randomIndex)
            result.append(removedItem)
        }
        self = result
    }
}

var array3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array3) //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
array3.shuffleInline()
print(array3) //[3, 1, 4, 6, 2, 5, 9, 10, 7, 8]

Complexity of Pencil and paper algorithm

Complexity of this algorithm will be O(nˆ2) because

• O(n) is for one 'for loop'
• O(n) is for removing from array

Model Shuffle Algorithm

How we can improve time complexity of shuffling? There is Modern method which allow us to get linear O(n) complexity. It is because we have only one loop over the array and swap random item on each iteration.

Example of shuffle function implemented modern algorithm 

func shuffleModern(array: [Int]) -> [Int] {
    var length = array.count
    var arrayCopy = array
    for _ in array {
        let randomIndex = Int(arc4random_uniform(UInt32(length)))
        if length - 1 != randomIndex {
            arrayCopy.swapAt(length - 1, randomIndex)
        }
        length -= 1
    }
    return arrayCopy
}

let array4 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array4) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(shuffleModern(array: array4)) //[9, 6, 7, 10, 2, 8, 1, 4, 3, 5]

Generic function
We also can make our function generic and apply it to array of any type, for example for array of strings.

Example of generic implementation

func shuffleModern<T>(array: [T]) -> [T] {
    var length = array.count
    var arrayCopy = array
    for _ in array {
        let randomIndex = Int(arc4random_uniform(UInt32(length)))
        if length - 1 != randomIndex {
            arrayCopy.swapAt(length - 1, randomIndex)
        }
        length -= 1
    }
    return arrayCopy
}

let strings2 = ["one", "two", "three", "four", "five"]
print(strings2) //["one", "two", "three", "four", "five"]
print(shuffleModern(array: strings2)) //["five", "four", "one", "three", "two"]

Also let's create two extensions as before: 1) will return new shuffled array 2) will shuffle array in-place

Example of extension with modern shuffle algorithm (Immutable and In-place)

extension Array {
    
    func shuffleModern() -> [Element] {
        var arrayCopy = self
        var length = arrayCopy.count
        for _ in arrayCopy {
            let randomIndex = Int(arc4random_uniform(UInt32(length)))
            if length - 1 != randomIndex {
                arrayCopy.swapAt(length - 1, randomIndex)
            }
            length -= 1
        }
        return arrayCopy
    }
    
    mutating func shuffleModernInline() {
        var length = self.count
        for _ in self {
            let randomIndex = Int(arc4random_uniform(UInt32(length)))
            if length - 1 != randomIndex {
                swapAt(length - 1, randomIndex)
            }
            length -= 1
        }
    }
}

var array5 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array5) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array5.shuffleModern()) // [2, 6, 10, 5, 4, 7, 3, 8, 9, 1]
array5.shuffleModernInline()
print(array5) // [10, 6, 2, 3, 1, 8, 5, 4, 7, 9]

Source Code

Source code for this post could be found here on GitHub

Swift Defer Statement

defer keyword is used for declaring a block of code that will wait and will be executed just before exit from current scope (function, closure, loop, etc. ).  The block of code inside defer statement is guaranteed to be executed regardless of how we exit from current scope: normally, from a guard, or because of error.

Simple example

func testDefer1() {
    defer {
        print("Defer step 3")
    }
    print("Normal step 1")
    print("Normal step 2")
}

testDefer1()

//Normal step 1
//Normal step 2
//Defer step 3

defer scope

As mentioned before, defer statement will be executed before exit from current scope. So, if scope that contains defer statement is inside other scope, than defer will be executed on exit from inner scope.

defer scope example

func testDefer2() {
    print("Normal step 1")
    customFunc()
    print("Normal step 2")
}

func customFunc() {
    print("Custom step 1")
    print("Custom step 2")
    defer {
        print("Custom defer step 3")
    }
}

testDefer2()

//Normal step 1
//Custom step 1
//Custom step 2
//Custom defer step 3
//Normal step 2

As we can see here:

1. Firstly will be printed strings from begin of outer scope
2. Secondly will be printed strings from inner scope
3. Thirdly will be printed strings from defer that in inner scope (just before exit from inner scope)
4. Fourthly will be printed strings from end of outer scope

defer inside for loop

If we will use defer inside, for example, 'for loop', defer statement will be executed before end of each iteration of the loop.

Example of usage defer inside for loop

func testDefer3() {
    for i in 1...5 {
        print("Normal step iteration begins \(i)")
        defer {
            print("Defer step \(i)")
        }
        print("Normal step iteration ends \(i)")
    }
}

testDefer3()

//Normal step iteration begins 1
//Normal step iteration ends 1
//Defer step 1
//Normal step iteration begins 2
//Normal step iteration ends 2
//Defer step 2
//Normal step iteration begins 3
//Normal step iteration ends 3
//Defer step 3
//Normal step iteration begins 4
//Normal step iteration ends 4
//Defer step 4
//Normal step iteration begins 5
//Normal step iteration ends 5
//Defer step 5

Multiple defer statements

If there are multiple defer statements inside scope they will be executed in reverse order. Their execution will follow LIFO pattern - Last In First Out.

Multiple defer example

func testMultipleDefer() {
    print("Normal step 1")
    defer {
        print("Defer step 1")
    }
    defer {
        print("Defer step 2")
    }
    defer {
        print("Defer step 3")
    }
    print("Normal step 2")
}

testMultipleDefer()

//Normal step 1
//Normal step 2
//Defer step 3
//Defer step 2
//Defer step 1

As you can see, order of execution is reversed to order of adding to scope.

defer limitations

There are some limitations for using defer statement. You cannot exit from body of defer statement with following things:

1. call return
2. call break
3. throw an error

Where we can use defer in Real Life Applications

The defer statement can be very useful when we want to clean up before exit from scope (for example, close connections to database or file, release unneeded resources), even if an error is thrown. For example, when we work with file and open a file to write to, we will want to make sure that we close opened file, even if there is an error happened while we work with file. 

Example of usage defer statement when working with file

func writeToFile(filename: String, text: String) throws {
    if let directory = FileManager.default.urls(for: .documentDirectory, in: .userDomainMask).first {
        
        let path = directory.appendingPathComponent(filename).absoluteString
        
        guard let file = FileHandle(forUpdatingAtPath: path) else {
            print("File open failed")
            throw FileError.fileNotFound(reason: "File not found")
        }
        
        defer {
            print("Close file...")
            file.closeFile()
        }
        
        let fileURL = directory.appendingPathComponent(filename)
        
        do {
            try text.write(to: fileURL, atomically: false, encoding: .utf8)
        }
        catch {
            throw FileError.cannotWriteToFile(reason: "Cannot write to file")
        }
    }
}

In code snippet above, we close file before exit from function. And we close file in defer statement to make sure that we close file at any case, even if error was being thrown.

Source Code

Source code for this article could be found here on GitHub

Coding Interview. String Compression Challenge

Task description

Given a string, write a function that accepts this string as input and returns compressed string. Algorithm of compression is following: every sequence of the same character should be replaced with that character followed by the number of repetitions. If the compressed string is longer than the original string, then function should return the original string.

Algorithm for this challenge also known as Run Length Encoding.

Examples of input and output

• a becomes a (because a1 is not shorter than a)
• aa becomes aa (because a2 is not shorter than aa)
• aaa becomes a3
• abc becomes abc (because a1b1c1 is not shorter than abc)
• aabbbdcccc becomes a2b3d1c4
• aaabbbccc becomes a3b3c3
• aabbbcccdeee becomes a2b3c3d1e3

Swift Implementation Prerequisites

In Swift we cannot get character of string by it's integer index. If we try to do this we will have an error. 

let test = "aaabbbbdcccee"

for i in 0..<(test.count - 1) {
    let ch = test[i] // error
}

'subscript' is unavailable: cannot subscript String with an Int, see the documentation comment for discussion

For getting character we must calculate "String.Index" value first.  

for i in 0..<(test.count - 1) {
    let index = test.index(test.startIndex, offsetBy: i)
    let character = test[index]
    print(character)
}

For simplifying this we can make subscript method for String type and get character by index.

let test = "aaabbbbdcccee"

extension String {
    
    subscript (i: Int) -> Character {
        let index = self.index(self.startIndex, offsetBy: i)
        let character = self[index]
        return character
    }
}

print(test[0]) // a
print(test[3]) // b
print(test[test.count - 1]) // e

Algorithm

1. Create variables 
• result for compressed string
• sum for counting each character
2. For loop from 0 to n-2 (where n = length of string, n - 2 because we will compare current and next characters)
• Compare current and next characters
• If they are equal add 1 to sum
• Else append current character and sum to result and reset sum to 0
3. Append to result last character and sum (because in for loop we update result only in case of characters are changed).
4. Compare lengths of initial and compressed strings and return one with less length.

Swift Implementation

let test1 = "abbbc"
let test2 = "aaa"
let test3 = "abc"
let test4 = "aabbbcccdeee"

func compress(_ str: String) -> String {
    var result = ""
    var sum = 1
    for i in 0..<(str.count - 1) {
        if (str[i] == str[i + 1]) {
            sum += 1
        } else {
            result += "\(str[i])\(sum)"
            sum = 1
        }
    }
    result += "\(str[str.count - 1])\(sum)"
    return result.count < str.count ? result : str
}

print(compress(test1)) // abbbc -> abbbc
print(compress(test2)) // aaa -> a3
print(compress(test3)) // abc -> abc
print(compress(test4)) // aabbbcccdeee -> a2b3c3d1e3

We can improve algorithm

1. Initially assign 0 to sum
2. For loop from from 0 to n-1
3. Increase sum by 1 in each iteration
4. In each iteration check if it is the end of string or current and next characters are different. If Condition is true than append current character and sum to result and reset sum to 0.

func compress_v2(_ str: String) -> String {
    var result = ""
    var sum = 0
    for i in 0..<str.count {
        sum += 1
        if (i + 1 == str.count) || (str[i] != str[i + 1]) {
            result += "\(str[i])\(sum)"
            sum = 0
        }
    }
    return result.count < str.count ? result : str
}

More "Swifty" Implementation

But there could be more "swifty" solution without using string index. We can use for each loop for string characters.

Algorithm

1. Create three variables: 
• currentCharacter - optional variable for current character
• sum - counter for for each character
• result - compressed string
2. For loop for each character in string
• If character is equal to currentCharacter then add 1 to sum
• Else do following
• Check that currentCharacter has value and if it has then add this value and sum to result
• Save character into currentCharacter
• Reset sum to 1
3. After loop finished, append currentCharacter and sum to the result string. (This step can be easily forgotten, because in for loop we only modify result string in case of character changes.)
4. Compare lengths of initial and compressed strings and return one with less length.

func compress_v3(_ str: String) -> String {
    var currentCharacter: Character?
    var sum = 0
    var result = ""
    for ch in str {
        if ch == currentCharacter {
            sum += 1
        } else {
            if let current = currentCharacter {
                result.append("\(current)\(sum)")
            }
            currentCharacter = ch
            sum = 1
        }
    }
    if let current = currentCharacter {
        result.append("\(current)\(sum)")
    }
    return result.count < str.count ? result : str
}

print(compress_v3(test1)) // abbbc -> abbbc
print(compress_v3(test2)) // aaa -> a3
print(compress_v3(test3)) // abc -> abc
print(compress_v3(test4)) // aabbbcccdeee -> a2b3c3d1e3

Complexity

Because we have only one for loop - space complexity of this algorithm will be linear - O(n).

Source Code 

Source code of from this post could be found here on GitHub