euler15.swift

// Dumb (and really slow)

import Foundation

func combinations(height: Int, _ level: Int) -> Int {
    if (level == 1) {
        return height + 1
    } else {
        var sum = 0
        for i in 0...height {
            sum += combinations(i, level - 1)
        }
        return sum
    }
}

let solve = { i in combinations(i, i) }

let start = NSDate()

print(solve(15))

let end = NSDate()

print(end.timeIntervalSinceDate(start) * 1000)

// Same, but memoized

import Foundation

struct IntPair: Hashable {
    let a: Int
    let b: Int
    
    var hashValue: Int {
        return (a << 8) | b
    }
}

func == (l: IntPair, r: IntPair) -> Bool {
    return l.a == r.a && l.b == r.b
}

var memoization: [IntPair: Int] = [:]

func combinations(height: Int, _ level: Int) -> Int {
    if level == 1 {
        return height + 1
    } else if let result = memoization[IntPair(a: height, b: level)] {
        return result
    } else {
        var sum = 0
        for i in 0...height {
            sum += combinations(i, level - 1)
        }
        memoization[IntPair(a: height, b: level)] = sum
        return sum
    }
}

let solve = { i in combinations(i, i) }

let start = NSDate()
let result = solve(20)
let end = NSDate()

print(result)
print(end.timeIntervalSinceDate(start) * 1000)

// Dynamic programming

import Foundation

let n = 33

let start = NSDate()

var matrix = Array(count: n, repeatedValue: Array(count: n + 1, repeatedValue: 0))

for level in 0..<n {
    for height in 0...n {
        if level == 0 {
            matrix[level][height] = height + 1
        } else {
            var sum = 0
            if height > 0 {
                sum += matrix[level][height - 1]
            }
            sum += matrix[level - 1][height]
            matrix[level][height] = sum
        }
    }
}

let result = matrix[n - 1][n]

let end = NSDate()

print(result)

print(end.timeIntervalSinceDate(start) * 1000)

// Optimized

import Foundation

let n = 20

let start = NSDate()


var matrix = Array(count: n - 1, repeatedValue: 0)

for i in 1..<n {
    for h in (i-1)...(n-2) {
        let left: Int
        if i == 1 {
            left = h + 3
        } else {
            left = matrix[h]
        }
        
        let above: Int
        if h == i - 1 { // first
            above = left
        } else {
            above = matrix[h - 1]
        }
        
        matrix[h] = left + above
    }
}

let result = matrix[n - 2]

let end = NSDate()

print(result)

print(end.timeIntervalSinceDate(start) * 1000)