Backtracking / Dynamic programming exercise - Go from start to finish in a matrix accumulating the least possible sum of inner elements

MinimizeSum.swift

import Foundation

func min(a: Int, b: Int) -> Int {
    return a < b ? a : b
}

func adjacentSpots(board: [[Int]], start: [Int]) -> [[Int]] {
    let i = start[0]
    let j = start[1]
    var ret: [[Int]] = []
    
    
    if i + 1 < board.count {
        ret.append([i+1, j])
    }
    
    if j + 1 < board.count {
        ret.append([i, j+1])
    }
    
    return ret
}

func btApproach(board: [[Int]], start: [Int], end: [Int], currentSolution: [[Int]], currentSum: Int, optimalSolution: inout [[Int]], optimalSum: inout Int) {
    let i = start[0]
    let j = start[1]
    
    var solution = currentSolution
    solution.append(start)
    let sum = currentSum + board[i][j]
    
    if start == end {
        if sum < optimalSum {
            optimalSolution = solution
            optimalSum = sum
        }
    } else {
        let goTo = adjacentSpots(board: board, start: start)
        goTo.forEach { (adj) in
            btApproach(board: board, start: adj, end: end, currentSolution: solution, currentSum: sum, optimalSolution: &optimalSolution, optimalSum: &optimalSum)
        }
    }
}

func btWrapper(board: [[Int]], start: [Int], end: [Int]) -> Int {
    var solution: [[Int]] = []
    var sum: Int = 999999
    
    btApproach(board: board, start: start, end: end, currentSolution: [], currentSum: 0, optimalSolution: &solution, optimalSum: &sum)
    
    return sum
}

func naiveRecursive(board: [[Int]], start: [Int], end: [Int]) -> Int {
    if start == end {
        return board[start[0]][start[1]]
    }
    
    if start[0] + 1 >= board.count && start[1] + 1 >= board.count {
        return board[start[0]][start[1]]
    } else if start[0] + 1 >= board.count && start[1] + 1 < board.count {
        return board[start[0]][start[1]] + naiveRecursive(board: board, start: [start[0], start[1] + 1], end: end)
    } else if start[0] + 1 < board.count && start[1] + 1 >= board.count {
        return board[start[0]][start[1]] + naiveRecursive(board: board, start: [start[0] + 1, start[1]], end: end)
    }
    
    return board[start[0]][start[1]] + min(naiveRecursive(board: board, start: [start[0] + 1, start[1]], end: end), naiveRecursive(board: board, start: [start[0], start[1] + 1], end: end))
}

func memoizedSolution(board: [[Int]], start: [Int], end: [Int], memoized: inout [[Int]]) -> Int {
    var solution: Int
    
    if memoized[start[0]][start[1]] != -1 {
        return memoized[start[0]][start[1]]
    }
    
    if start == end {
        solution = board[start[0]][start[1]]
    } else {
        if start[0] + 1 >= board.count && start[1] + 1 >= board.count {
            solution = board[start[0]][start[1]]
        } else if start[0] + 1 >= board.count && start[1] + 1 < board.count {
            solution = board[start[0]][start[1]] + memoizedSolution(board: board, start: [start[0], start[1] + 1], end: end, memoized: &memoized)
        } else if start[0] + 1 < board.count && start[1] + 1 >= board.count {
            solution = board[start[0]][start[1]] + memoizedSolution(board: board, start: [start[0] + 1, start[1]], end: end, memoized: &memoized)
        } else {
            solution = board[start[0]][start[1]] + min(memoizedSolution(board: board, start: [start[0] + 1, start[1]], end: end, memoized: &memoized), memoizedSolution(board: board, start: [start[0], start[1] + 1], end: end, memoized: &memoized))
        }
    }
    
    memoized[start[0]][start[1]] = solution
    return solution
}

func bottomUpSolution(board: [[Int]]) -> Int {
    var calc: [[Int]] = Array.init(repeating: Array.init(repeating: -1, count: board.count), count: board.count)
    
    for i in 0...calc.count - 1 {
        for j in 0...calc.count - 1 {
            if i == 0 && j == 0 {
                calc[i][j] = board[i][j]
            } else if i == 0 && j > 0 {
                calc[i][j] = board[i][j] + calc[i][j-1]
            } else if i > 0 && j == 0 {
                calc[i][j] = board[i][j] + calc[i-1][j]
            } else {
                calc[i][j] = board[i][j] + min(calc[i-1][j], calc[i][j-1])
            }
        }
    }
    
    return calc[calc.count - 1][calc.count - 1];
}

let board = [[2,8,3,4],
             [5,3,4,5],
             [1,2,2,1],
             [3,4,6,5]]
var memo = Array.init(repeating: Array.init(repeating: -1, count: 4), count: 4)

btWrapper(board: board, start: [0,0], end: [3,3])
naiveRecursive(board: board, start: [0,0], end: [3,3])
memoizedSolution(board: board, start: [0,0], end: [3,3], memoized: &memo)
bottomUpSolution(board: board)