Dynamic Programming with field of spikes in Swift

dynamic-programming.swift

let field = [0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1]

var memo:[Int:[Int:Bool]] = [0:[:]]


func bounce(startingSpeed:Int, startingIndex:Int, field:[Int]) -> Bool {

    // Many base cases. We must still be on the runway.
    // We must land on a place with 0 (no spikes)
    // Use a double dictionary as the memo. Store true/false. 1 dimension for each changing intput!!!!
    
    if let cached = memo[startingIndex], let result = cached[startingSpeed] {
        print("MEMO'd: \(startingIndex) , \(startingSpeed)")
        return result
    }
    
    guard startingIndex <= field.count-1
        else {
            print("failed here");
            memo[startingIndex, default:[:]][startingSpeed] = false
            return false
            
    }
    
    guard field[startingIndex] == 0
        else {
            print("spikes");
            memo[startingIndex, default:[:]][startingSpeed] = false
            return false
    }
    
    guard startingIndex >= 0
        else {
            print("less than");
            memo[startingIndex, default:[:]][startingSpeed] = false
            return false
        }
    
    if startingSpeed == 0 {
        memo[startingIndex, default:[:]][startingSpeed] = true
            return true
    }
    
    let same = bounce(startingSpeed: startingSpeed, startingIndex: startingIndex+startingSpeed, field: field)
    let plus = bounce(startingSpeed: startingSpeed+1, startingIndex: startingIndex+startingSpeed+1, field: field)
    let minus = bounce(startingSpeed: startingSpeed-1, startingIndex: startingIndex+startingSpeed-1, field: field)
    
    return same || plus || minus
}

print(bounce(startingSpeed: 6, startingIndex: 0, field: field))

http://blog.refdash.com/dynamic-programming-tutorial-example/