Swift Hackerrank 2D Array

Question

I solved this question in Swift, but was wondering if there is a better way or if my code can be improved:

Given a 6x6 2D Array:

1 1 1 0 0 0 
0 1 0 0 0 0 
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

We define an hourglass in to be a subset of values with indices falling in this pattern in's graphical representation:

a b c 
 d
e f g 

There are hourglasses in, and an hourglass sum is the sum of an hourglass' values.

import Foundation
var inputAsArray = [Int]()
for _ in 0...5 {
 inputAsArray += readLine()!.componentsSeparatedByString(" ").map{ Int(0ドル)! }
}
//var inputAsArray = [
// 1, 1, 1, 0, 0, 0,
// 0, 1, 0, 0, 0, 0,
// 1, 1, 1, 0, 0, 0,
// 0, 9, 2, -4, -4, 0,
// 0, 0, 0, -2, 0, 0,
// 0, 0, -1, -2, -4, 0
//]
// method creates all possible "hourglasses" and returns a nested array of hourglasses
typealias hourglass = [Int]
private func hourGlasses(input: [Int]) -> [hourglass] {
 var hourglasses = [hourglass]() // initializes hourglass to hold array of hourglass
 for index in 0..<22 { // there are 36 indexes (6x6) but we +14 in the loop below when creating the hourglass so we only need to go up to 24. We can't make hourglass with 23 and 24, so we go up to 22
 guard [4,5,10,11,16,17].indexOf(index) == nil else {continue} // continue to next iteration because we can't create hourglass with the last 2 indexes from the right wall
 hourglasses.append([ // creates the hourglass array
 input[index], input[index+1], input[index+2],
 input[index+7],
 input[index+12], input[index+13], input[index+14],
 ])
 }
 return hourglasses
}
// method takes in array of input and sends it to hourGlasses to make a nested array. Then it finds the largest sum by using reduce over the nested array
private func maxHourglassSum(input: [Int]) -> Int {
 let hourglasses: [hourglass] = hourGlasses(input)
 // reduce the nested arrays to get sum in each. then compare that sum to maxSum
 var maxSum = Int?() // set to optional instead of 0 because all numbers in input can be negative
 for singleHourglass in hourglasses {
 let singleHourglassSum = singleHourglass.reduce(0, combine: +) // reduce adds up sum for a single hourglass
 if maxSum == nil || singleHourglassSum > maxSum {
 maxSum = singleHourglassSum
 }
 }
 return maxSum!
}
print(maxHourglassSum(inputAsArray))

Answer 1

Your code works correctly, but can be improved (simplified and made clearer and faster).

Let't start with

func hourGlasses(input: [Int]) -> [hourglass] {
 var hourglasses = [hourglass]() // initializes hourglass to hold array of hourglass
 for index in 0..<22 { // there are 36 indexes (6x6) but we +14 in the loop below when creating the hourglass so we only need to go up to 24. We can't make hourglass with 23 and 24, so we go up to 22
 guard [4,5,10,11,16,17].indexOf(index) == nil else {continue} // continue to next iteration 
 // ...
}

• There are far too many magic numbers.
• The fact that extened comments are necessary indicates that the approach it be too complicated.
• I would consider this usage of guard a bit artificial.
• Membership in a collection can be checked with contains(), you don't need the actual index.

How would you extend this to 15x20 arrays? – Better iterate over the permitted rows and columns:

for row in 0 ..< 4 {
 for col in 0 ..< 4 {
 index = row * 4 + col
 // ...
 }
}

Even better, replace the integer literals by descriptive constants:

let numRows = 6
let numCols = 6
for row in 0 ..< numRows - 2 {
 for col in 0 ..< numCols - 2 {
 let index = row * numCols + col
 // ...
 }
}

Your hourGlasses() function computes an array of arrays. Then in maxHourglassSum(), the sum of each inner array is computed and the maximal element determined.

It is more effective to sum the values of an "hour glass" immediately instead of storing it as an array. To compute the maximum value, use the existing method maxElement().

func hourGlassSum(input: [Int], atIndex index: Int) -> Int {
 var sum = input[index] + input[index + 1] + input[index + 2]
 sum += input[index + numCols + 1]
 sum += input[index + 2*numCols] + input[index + 2*numCols + 1] + input[index + 2*numCols + 2]
 return sum
}
func maxHourglassSum(input: [Int]) -> Int {
 var values: [Int] = []
 for row in 0 ..< numRows - 2 {
 for col in 0 ..< numCols - 2 {
 let index = row * numCols + col
 values.append(hourGlassSum(input, atIndex: index))
 }
 }
 return values.maxElement()!
}

(Remark: The sum of is computed in three separate steps because otherwise the compiler fails with an "Expression is too complex ..." error.)

This is short, clear, works with other dimentions as well, and is faster than your original code. If even more speed is required then you can compute the maximum "on the fly" instead of storing the values in an array first:

func maxHourglassSum(input: [Int]) -> Int {
 var maxSum = -100 // Any initial value < -9*7 = -63
 for row in 0 ..< numRows - 2 {
 for col in 0 ..< numCols - 2 {
 let index = row * numCols + col
 let sum = hourGlassSum(input, atIndex: index)
 if sum > maxSum {
 maxSum = sum
 }
 }
 }
 return maxSum
}

More suggestions: If you plan to use the code for other shapes as well then use an array with the indices describing the shape:

let hourGlassShape = [0, 1, 2, 7, 12, 13, 14]
func hourGlassSum(input: [Int], atIndex index: Int) -> Int {
 return hourGlassShape.reduce(0) { 0ドル + input[index + 1ドル] }
}

Finally: The challenge is called "2D Array", so you might want to work with a two-dimensional (i.e. a nested) array in Swift as well:

let inputArray2D = [
 [ 1, 1, 1, 0, 0, 0 ],
 [ 0, 1, 0, 0, 0, 0 ],
 [ 1, 1, 1, 0, 0, 0 ],
 [ 0, 0, 2, 4, 4, 0 ],
 [ 0, 0, 0, 2, 0, 0 ],
 [ 0, 0, 1, 2, 4, 0 ]
]

The sum calculation for a single hourglass then becomes more intuitive:

var sum = input[row][col] + input[row][col + 1]] + input[row][col + 2]
sum += input[row + 1][col + 1]
sum += input[row + 2][col] + input[row + 2][col + 1] + input[row + 2][col + 2]

Test code:

var sum = 0
let startTime = NSDate()
for _ in 1 ... 100 {
 sum += maxHourglassSum(inputAsArray)
}
let endTime = NSDate()
print(endTime.timeIntervalSinceDate(startTime) * 1000.0, "ms")

Results (on a MacBook, compiled in Release mode):

• Original code: 0.8 ms
• First variation: 0.25 ms
• Second variation: 0.008 ms

The values did not change significantly when using a 2D (nested) array instead of a 1D (simple) array.

• Clefairy: Thanks for showing multiple ways of approaching the solution and for going in depth! Much appreciated :D