swift - 这个矩阵相邻单元格计数的解决方案有什么问题？ ( swift )

Question

我被要求在 Swift Playground 中解决这个问题。有人告诉我我的答案是正确的，但还不够好(是的，非常模糊)。

/*

 Write a Swift playground that takes an n x n grid of integers. Each integer can be either 1 or 0.

 The playground then outputs an n x n grid where each block indicates the number of 1's around that block, (excluding the block itself) . For Block 0 on row 0, surrounding blocks are (0,1) (1,0) and (1,1). Similary for block (1,1) all the blocks around it are to be counted as surrounding blocks.

 Requirements:

 Make sure your solution works for any size grid.
 Spend an hour and a half coding the logic and another hour cleaning your code (adding comments,  cleaning variable and function names).

 Optimize your functions to be O(n^2).

 Your output lines should not have any trailing or leading whitespaces.

 Please use hard coded example input constants below.

 Examples:

 Input Grid:

 let sampleGrid = [[0,1,0], [0,0,0], [1,0,0]]

 Console Output:

 1 0 1
 2 2 1
 0 1 0

 /////////////////

 Input Grid:

 let sampleGrid = [[0,1,0,0], [0,0,0,1], [1,0,0,1],[0,1,0,1]]

 Console Output:

 1 0 2 1
 2 2 3 1
 1 2 4 2
 2 1 3 1

 */

/// An *Error* type
struct ComputationError : Error {
    /// The message of the error
    let message : String
}

/// This function computes a matrix result from the input *matrix*
/// where an integer value represents the number of adjacent cells
/// in the input *matrix* having a 1.
///
/// The algorithm is O(n^2), if n is the side length of the matrix:
///
///  for each row in rows of matrix
///   for each column in columns of matrix
///    for each matrix[row][column] cell if equal to 1
///     add a 1 to adjacent (valid) cell in result matrix
///
/// - Parameter matrix: input square matrix with values of 0 or 1 only
/// - Returns: a matrix of equal size to input matrix with computed adjacency values
/// - Throws: throws a ComputationError is the matrix is of invalid size or has invalid values (something other than 1 or 0)
func compute(matrix:[[Int]]) throws -> [[Int]] {

    // The number of rows in matrix, which should equal the number of columns, ie side length, or n
    let side = matrix.count

    // The resulting matrix to return
    var result:[[Int]] = []

    // Initialize the result matrix
    for _ in 0..<side {
        result.append(Array<Int>(repeating: 0, count: side))
    }

    // A convenience constant to refer to the last element in a row or column
    let last = side-1

    // Iterate over rows in matrix
    for row in 0..<side {
        if matrix[row].count < side {
            throw ComputationError(message:"Invalid number of columns (\(matrix[row].count)), should match number of rows (\(side))")
        }
        // Iterate over columns in matrix
        for column in 0..<side {
            // Consider this cell if it is 1, otherwise skip
            // If it is 1, then add a 1 to all valid adjacent cells
            // in result matrix.
            if matrix[row][column] == 1 {
                if 0 < row {
                    if 0 < column {
                        result[row-1][column-1] += 1
                    }
                    result[row-1][column] += 1
                    if column < last {
                        result[row-1][column+1] += 1
                    }
                }
                if 0 < column {
                    result[row][column-1] += 1
                }
                if column < last {
                    result[row][column+1] += 1
                }
                if row < last {
                    if 0 < column {
                        result[row+1][column-1] += 1
                    }
                    result[row+1][column] += 1
                    if column < last {
                        result[row+1][column+1] += 1
                    }
                }
            }
            else if matrix[row][column] == 0 {
                // ok
            }
                // If value is neither 0 or 1 throw an error
            else {
                throw ComputationError(message:"Invalid value (\(matrix[row][column])) encountered at row \(row) and column \(column)")
            }
        }
    }

    return result
}

/// Print *matrix* to console by iterating over each row in the
/// matrix and each column in the row, regardless of the count
/// of columns in the row.  The output is row-wise and a single
/// space delimits columns, with no leading or trailing whitespace.
///
/// - Parameter matrix: an array of array of Int
func print(matrix:[[Int]]) {

    let rows = matrix.count

    for row in 0..<rows {
        let columns = matrix[row].count
        var line = ""
        for column in 0..<columns {
            if 0 < column {
                line += " "
            }
            line += "\(matrix[row][column])"
        }
        print(line)
    }

}

do {
    print(matrix:try compute(matrix: [[0,1,0], [0,0,0], [1,0,0]]))
}
catch let error {
    print(error)
}

do {
    print()
    print(matrix:try compute(matrix: [[0,1,0,0], [0,0,0,1], [1,0,0,1],[0,1,0,1]]))
}
catch let error {
    print(error)
}

// test for exception
do {
    print()
    print(matrix:try compute(matrix: [[0,1], [0,0,0], [1,0,0]]))
}
catch let error {
    print(error)
}

// test for exception
do {
    print()
    print(matrix:try compute(matrix: [[0,1,0], [3,0,0], [1,0,0]]))
}
catch let error {
    print(error)
}

Answer 1

他们可能正在寻找函数式编程风格的东西，而您可能需要证明您的解决方案是 O(n^2)。

例如:

 // let sampleGrid = [[0,1,0], [0,0,0], [1,0,0]]
 let sampleGrid = [[0,1,0,0], [0,0,0,1], [1,0,0,1],[0,1,0,1]]

 func printMatrix(_ m:[[Any]])
 {
    print( m.map{ $0.map{"\($0)"}.joined(separator:" ")}.joined(separator:"\n") )
 }

 let emptyLine  = [Array(repeating:0, count:sampleGrid.first!.count)]

 let left  = sampleGrid.map{ [0] + $0.dropLast()  }   // O(n)
 let right = sampleGrid.map{ $0.dropFirst() + [0] }   // O(n)
 let up    = emptyLine + sampleGrid.dropLast()        // O(n)
 let down  = sampleGrid.dropFirst() + emptyLine       // O(n)

 let leftRight   = zip(left,right).map{zip($0,$1).map{$0+$1}} // O(n^2)
 let upDown      = zip(up,down).map{zip($0,$1).map{$0+$1}}    // O(n^2)

 let cornersUp   = emptyLine + leftRight.dropLast()   // O(n)
 let cornersDown = leftRight.dropFirst() + emptyLine  // O(n)

 let sides   = zip(leftRight,upDown).map{zip($0,$1).map{$0+$1}}      // O(n^2)
 let corners = zip(cornersUp,cornersDown).map{zip($0,$1).map{$0+$1}} // O(n^2)

 // 6 x O(n) + 5 x O(n^2) ==> O(n^2)
 let neighbourCounts = zip(sides,corners).map{zip($0,$1).map{$0+$1}}  // O(n^2) 

 print("SampleGrid:")
 printMatrix(sampleGrid)
 print("\nNeighbour counts:")
 printMatrix(neighbourCounts)

...

SampleGrid:
0 1 0 0
0 0 0 1
1 0 0 1
0 1 0 1

Neighbour counts:
1 0 2 1
2 2 3 1
1 2 4 2
2 1 3 1