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.
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()
