Code Challenge #54 - Lattice Paths (Playground w/ markup)

LatticePaths.swift

//: # Code Challenge #54
//: ## Lattice Paths
//:
//: It may not be the most clever or direct solution, but the problem can be modeled
//: using Pascal's Triangle (https://en.wikipedia.org/wiki/Pascal's_triangle). For a square grid 
//: of dimension `N`, the number of paths can be found at the 'central' position of row `2 * N + 1` of 
//: Pascal's Triangle.
import Swift

/// The size of the grid, measured in nodes per edge.
let gridDimension = 20

/// The number of iterations of Pascal's triangle we need to compute to find our answer.
/// I'm not doing 2 * N + 1 because the seed value below is already the first row.
let maxRowCount = 2 * gridDimension

/// The seed of Pascal's Triangle is a row with a single value of 1.
var row: [Int] = [1]

//: ## Calculate a row of Pascal's Triangle.
//: This is our workhorse method that generates each succeeding row of Pascal's Triangle.
/// The `nextRow(for:)` method takes the value of any row of a Pascal's Triangle
/// and computes the next row.
/// - Parameter for: The existing row of the Pascal's Triangle upon which the next row
///                  will be calculated.
/// - Returns: `[Int]` representing the next row of the Pascal's Triangle.
func nextRow(for row: [Int]) -> [Int] {
    /// Each succeeding row of Pascal's triangle is 1 element wider than the last.
    let nextRowCount = row.count + 1
    
    /// Our accumulator for the next row's values.
    var nextRow: [Int] = []
    
    for i in 0..<nextRowCount {
        
        if i == 0 || i == nextRowCount - 1 {
            // The first and last positions of each row of Pascal's Triangle are always 1.
            nextRow.append(1)
        } else {
            // All other
            nextRow.append(row[i - 1] + row[i])
        }
    }
    return nextRow
}

//: ## Calculate the answer.
//: All we need to do now is to repeatedly call our `nextRow(for:)` method the required
//: number of times to achieve the desired answer.
print("[0] \(row)")
for i in 1...maxRowCount {
    row = nextRow(for: row)
    print("[\(i)] \(row)")
}
//: Now that we have the appropriate row of Pascal's Triangle, simply read out the "center"
//: value, which corresponds to the number at index `gridDimension`.
print("Paths: \(row[gridDimension])")
// Answer: 137,846,528,820