3
\$\begingroup\$

I was given this problem to solve inside a Swift playground. I was vaguely told my answer is correct but not good enough.

/*

 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)
}
\$\endgroup\$
3
\$\begingroup\$

A functional-style solution:

let inputGrid = [
    [0,1,0,0],
    [0,0,0,1],
    [1,0,0,1],
    [0,1,0,1]
]

let n = inputGrid.count // This presumes that the grid is square

let outputGrid = inputGrid.enumerated().map { rowIndex, row -> [Int] in
    return row.enumerated().map { colIndex, _ in
        var nonZeroCount = 0

        for deltaRow in -1...1 {
            for deltaCol in -1...1 {
                let neighborRowIndex = rowIndex + deltaRow
                let neighborColIndex = colIndex + deltaCol

                guard 0..<n ~= neighborRowIndex, 0..<n ~= neighborColIndex else { continue }
                guard (neighborRowIndex, neighborColIndex) != (rowIndex, colIndex) else { continue }

                nonZeroCount += inputGrid[neighborRowIndex][neighborColIndex]
            }
        }
        return nonZeroCount
    }
}

// Print the result
outputGrid.forEach { row in
    print(row.map { String($0) }.joined(separator: " "))
}

What it does:

  • Enumerate through each cell of the inputGrid
  • Enumerate through all its neighbors:
  • guard 0..<n ~= neighborRowIndex, 0..<n ~= neighborColIndex ensures that its neighboring cell has valid address
  • guard (neighborRowIndex, neighborColIndex) != (rowIndex, colIndex) ensures that it's not counting itself
  • Add up the value of those valid neighbors

~= is the pattern matching operator. range ~= number essentially tests if the number is in the range

Why it's \$O(n^2)\$:

  • The two nested enumerated.map() is \$n^2\$
  • The two loops for deltaRow and deltaCol is 9
  • The overall is \$9n^2 => n^2\$
\$\endgroup\$
  • \$\begingroup\$ Correct, and impressive, but not better than the original solution. It's the same algorithm in essence just written out differently. It uses block invocation n^2 times which theoretically would slow down real-time performance as each block is re-executed and added to the execution stack. The original solution requires no function calls inside its loops. I think the ~= notation is nifty. \$\endgroup\$ – andrewz Aug 24 '17 at 4:34
  • \$\begingroup\$ Also, I would say this solution looks simplest, which is a plus. \$\endgroup\$ – andrewz Aug 24 '17 at 5:08
  • \$\begingroup\$ nitpick but, a functional-style with a for loop and counter :)? tsk tsk \$\endgroup\$ – Fluidity Aug 28 '17 at 14:08
  • \$\begingroup\$ @Fluidity What's wrong with a for loop? The function still does not have any side effect. You can rewrite it using reduce at the cost of readability \$\endgroup\$ – Code Different Aug 28 '17 at 22:45
  • \$\begingroup\$ this would be written without state and instead a recursive subfunction in Haskell, F#, etc :P \$\endgroup\$ – Fluidity Aug 29 '17 at 0:38
3
\$\begingroup\$

They were likely looking for something in a functional programming style and you probably needed to demonstrate that your solution is O(n^2).

for example:

 // 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") )
}

func addArrays  (_ A:[Int], _ B:[Int] ) -> [Int]   
{ return zip(A,B).map(+) }

func addMatrices(_ A:[[Int]], _ B:[[Int]] ) -> [[Int]] 
{ return zip(A,B).map(addArrays) }

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

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

let leftRight   : [[Int]] = addMatrices(left,right)                // O(n^2)
let upDown      : [[Int]] = addMatrices(up,down)                   // O(n^2)

let cornersUp   : [[Int]] = emptyLine + leftRight.dropLast()       // O(n)
let cornersDown : [[Int]] = leftRight.dropFirst() + emptyLine      // O(n)

let sides       : [[Int]] = addMatrices(leftRight,upDown)          // O(n^2)
let corners     : [[Int]] = addMatrices(cornersUp,cornersDown)     // O(n^2)

// 6 x O(n) + 5 x O(n^2) ==> O(n^2)
let  neighbourCounts = addMatrices(sides,corners)         // 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

[EDIT] I did a little benchmarking and my functional solution is indeed much slower than traditional (procedural) code which the compiler is much better at optimizing.

I built a procedural solution with systematic additions to see the difference with a similar approach implemented procedurally. I also wanted to know how much overhead the indexing of matrices entails:

optimizations: 
   - use single dimension indexing instead of 2D
   - reuse previous totals from 6 previous cells/counts to minimize indexing
   - each cell's count only references 2 neighbours rather than 8
   - manipulating "previous" and "next" lines as a whole does not cause
   - memory allocation because of COW (Copy on Write)
   - progressively building the result, which need to be done anyway
     is faster than updating it with indexing 

...

let size           = sampleGrid.count
let edge           = sampleGrid.count - 1

var neighbourCounts = sampleGrid
neighbourCounts.removeAll(keepingCapacity:true)  

let emptyLine        = Array(repeating:0, count: size)
var lineCounts:[Int] = []            
var previousLine     = emptyLine
var nextLine:[Int]   = [] 
var count5           = 0
var previous3        = 0
var previousCount    = 0
for (row,currentLine) in sampleGrid.enumerated()              
{  
   nextLine = row < edge ? sampleGrid[row+1] : emptyLine  
   lineCounts.removeAll(keepingCapacity:true)             
   previous3     = 0     
   previousCount = 0                                
   for (col,value) in currentLine.enumerated()        // nested loop --> O(n^2)
   {
      count5         = previous3                      // upLeft, left, downLeft
      previous3      = previousLine[col] + nextLine[col]  
      count5        += previous3                      // up, down
      previous3     += value
      previousCount += previous3                      // upRight, right, downRight
      if col > 0 { lineCounts.append(previousCount) }     
      previousCount  = count5
   }
   lineCounts.append(previousCount)
   neighbourCounts.append(lineCounts)
   previousLine = currentLine
}       

...

               Time for 1000 execution
            ----------------------------
              sample    sample
               3x3       4x4
Functional : 0.01270   0.01665            
Procedural : 0.00142   0.00197             
andrewz's  : 0.00093   0.00132      

               4x4     16x16     32x32
Functional : 0.01591  0.08835   0.22684  (50% 1s)
Procedural : 0.00170  0.00656   0.01841  (50% 1s)
andrewz's  : 0.00123  0.00875   0.03328  (50% 1s)
andrewz's  : 0.00104  0.00377   0.01356  (all 0s)
andrewz's  : 0.00149  0.01217   0.04690  (all 1s)

The functional solution is orders of magnitude slower (as the compiler cannot optimize it efficiently). For procedural solutions the size of the matrix impacts the choice of using a systematic addition of neighbours (my procedural solution) or optimizing on 1s by conditionally "pushing" to neighbours's counts (andrewz's).

There is a noticeable overhead to modifying and accessing an array using indexes. That difference is nowhere near as significant as the one between functional and procedural code however.

\$\endgroup\$
  • \$\begingroup\$ Thanks for reposting your answer. I just learned the 'zip' function. While impressive your answer is less readable and does many mappings which would affect the real time efficiency of the solution. Whereas my answer is clearer IMO and I would argue runs faster because it does simple array lookup and less maps, while the complexity is still satisfied to O(n^2). \$\endgroup\$ – andrewz Aug 23 '17 at 22:30
  • \$\begingroup\$ The other benefits to your solution are 1: you have clearly outlined the complexity of each relevant line, 2: the solution is more compact and fits on the screen \$\endgroup\$ – andrewz Aug 24 '17 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.