March 14, 2020 Andrey

Count the number of ways to traverse a Matrix in Swift

Question: Count the number of ways to traverse a from the top left corner to the bottom, right corner.
Limitation: we can only move down or right.

Few solutions: first one brute force and second dynamic programming and measuring their time execution below.
To compute 10 x 10 matrix with recursive brute force took 1.4 seconds while using dynamic programming took 0.04 seconds.

matrix traversal swift 5

matrix traversal swift 5

import Foundation
// recursive solution that has exponential time complexity: O(2^n), since each function call calls itself twice unless it has been recursed n times
func traverse (x: Int,y: Int) -> Int {
  
 if (x == 1) || (y == 1) {
  return 1
 }
  
 return traverse(x: x-1, y: y) + traverse(x:x, y: y-1)
}

// Dynamic programing O(m * n)
func dynamicTraverse (x: Int,y: Int) -> Int {

    var matrix = Array(repeating: Array(repeating: 0, count: x+1), count: y+1)

    for i in 1...x {
        for j in 1...y {
            if i == 1 || j == 1 {
                matrix[i][j] = 1
            } else {
                matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
            }
        }
    }
    
    return matrix[x][y]
}

func main() {
    measureTime {print(traverse(x:10, y:10))}
    measureTime {print(dynamicTraverse(x:10, y:10))}
}

//comupute execution time of any function passed in
func measureTime(closure: () -> Void) {
    let start = CFAbsoluteTimeGetCurrent()
    closure()
    let diff = CFAbsoluteTimeGetCurrent() - start
    print("Took \(diff) seconds")
}

main()
,