Grokking Algorithms

algorithms.swift

// Chapter 1 Binary Search

func binarySearch(arr: [Int], num: Int) -> Int? {
    var low = 0
    var high = arr.count - 1

    while low <= high {
        let mid = (low + high) / 2
        let guess = arr[mid]
        if guess == num {
            return mid
        }
        if guess < num {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return nil
}

// Chapter 2 Selection Sort

func findMinIndex(_ arr: [Int]) -> Int {
    var minElement = arr[0]
    var minIndex = 0
    
    for index in 1..<arr.count {
        if arr[index] < minElement {
            minElement = arr[index]
            minIndex = index
        }
    }
    return minIndex
}


func selectionSort(_ arr: [Int]) -> [Int] {
    var mutableArr = arr
    var sortedArr = [Int]()
    
    for _ in mutableArr {
        let index = findMinIndex(mutableArr)
        sortedArr.append(mutableArr.remove(at: index))
    }
    
    return sortedArr
}

// Chapter 3 Recursion

func factorial(_ x: Int) -> Int {
    return x == 1 ? 1 : x * factorial(x - 1)
    
    // OR:
    /*
        if x == 1 {
            return 1
        } else {
            return x * factorial(x - 1)
        }
    */
}

factorial(3)

/*
 factiorial(1) -> 1
 
 factiorial(2) -> 2 * factiorial(1) = 2 * 1 = 2
 
 factorial(3) -> 3 * factiorial(2) = 3 * 2 = 6
 */


// Chapter 4 Quick Sort

func sum(_ arr: [Int]) -> Int {
    guard !arr.isEmpty else { return 0 }
    
    var tempArr = arr
    return tempArr.removeLast() + sum(tempArr)
}

sum([1,2,3])

/*
 sum([]) -> 0
 
 sum([1]) -> sum([]) + 1 = 0 + 1
 
 sum([1,2]) -> sum([1]) + 2 = 1 + 2 = 3
 
 sum([1, 2, 3]) -> sum([1,2]) + 3 = 3 + 3 = 6
*/

func count(_ arr: [Int]) -> Int {
    guard !arr.isEmpty else { return 0 }

    var tempArr = arr
    tempArr.removeLast()
    return 1 + count(tempArr)
}

count([1,2,3])

/*
 count([]) -> 0
 
 count([1]) -> 1 + count([]) = 1 + 0 = 1
 
 count([1,2]) -> 1 + count([1]) = 1 + 1 = 2
 
 count([1,2,3]) -> 1 + count([1,2]) = 1 + 2 = 3
*/

func max(_ arr: [Int]) -> Int {
    guard arr.count > 1 else { return arr.first ?? 0 }
    
    if arr.count == 2 {
        return arr[0] > arr[1] ? arr[0] : arr[1]
    }
    
    let subMax = max(arr.dropLast())
    return (arr.last! > subMax) ? arr.last! : subMax
}

max([1, 5, 10, 25, 16, 1])

/*
 max([1, 5]) -> 5
 
 max([1, 5, 10]: subMax = max([1, 5]) = 5 -> 10
 
 max([1, 5, 10, 25]: subMax = max([1, 5, 10]) = 10 -> 25
 
 max([1, 5, 10, 25, 16]: subMax = max([1, 5, 10, 25] = 25 -> 25
 
 max([1, 5, 10, 25, 16, 1]): subMax = max([1, 5, 10, 25, 16]) = 25
*/

// Maybe O(n^2) or O(n log n)
func quickSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }

    let pivot = arr[0]
    var less = [Int]()
    var greater = [Int]()

    arr.dropFirst().forEach {
        $0 <= pivot ? less.append($0) : greater.append($0)
    }
    return quickSort(less) + [pivot] + quickSort(greater)
}

var arr = Array(1...100).shuffled()
quickSort(arr)

// Will be O(n log n)
func quickSort(_ arr: inout [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }

    let pivot = arr.remove(at: arr.count / 2)
    var less = [Int]()
    var greater = [Int]()

    arr.forEach {
        $0 <= pivot ? less.append($0) : greater.append($0)
    }
    return quickSort(&less) + [pivot] + quickSort(&greater)
}
var arr = Array(1...100)
print(quickSort(&arr))


// Chapter 6: Breadth Search

// Dequeue Realization

public struct Deque<T> {
    private var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    public mutating func enqueueFront(_ element: T) {
        array.insert(element, at: 0)
    }
    
    public mutating func dequeue() -> T? {
        if isEmpty {
            return nil
        } else {
            return array.removeFirst()
        }
    }
    
    public mutating func dequeueBack() -> T? {
        if isEmpty {
            return nil
        } else {
            return array.removeLast()
        }
    }
    
    public func peekFront() -> T? {
        return array.first
    }
    
    public func peekBack() -> T? {
        return array.last
    }
}

func personIsSeller(name: String) -> Bool {
    return name.last == "m"
}

var graph = [String : [String]]()
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

func search(name: String) -> Bool {
    var searchQueue = Deque<String>()
    var searched = [String]()
    
    for name in graph[name]! {
        searchQueue.enqueue(name)
    }
    
    while !searchQueue.isEmpty {
        let person = searchQueue.dequeue()!
        if !searched.contains(person) {
            if personIsSeller(name: person) {
                print("\(person) is Mango Seller")
                return true
            } else {
                for name in graph[person]! {
                    searchQueue.enqueue(name)
                }
                searched.append(person)
            }
        }
    }
    
    return false
}

search(name: "you")
// thom is Mango Seller


// Chapter 7. Dijkstra's algorithm (SPF)

// Chapter 8. Greedy algorithm

// You pass an array in, and it gets converted to a set.
var statesNeeded : Set = ["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]

var stations = [String: Set<String>]()
stations["kone"] = ["id", "nv", "ut"]
stations["ktwo"] = ["wa", "id", "mt"]
stations["kthree"] = ["or", "nv", "ca"]
stations["kfour"] = ["nv", "ut"]
stations["kfive"] = ["ca", "az"]

var finalStations = Set<String>();

while !statesNeeded.isEmpty {
    var bestStation = String()
    var statesCovered = Set<String>()
    
    for station in stations {
        var covered = statesNeeded.intersection(station.value)
        if covered.count > statesCovered.count {
            bestStation = station.key
            statesCovered = covered
        }
        statesNeeded = statesNeeded.subtracting(statesCovered)
        //Swift note: We should avoid adding empty station to Set
        if !bestStation.isEmpty {
            finalStations.insert(bestStation)
        }
    }
}

print(finalStations) // -> ["kone", "kfive", "ktwo", "kthree"]

// Chapter 9: Dynamic Programming