README.md

Island Counter

A common interview question is the island counter problem. You process of a matrix which values which are land or sea. Your goal is to count the number of islands. And islands are defined by land which is connected to grid positions. This can be done by square directions or also including diagonal directions.

Below is one example of a matrix which includes 3 islands.

let terrain: Terrain = [
    [.land, .sea, .land],
    [.sea, .sea, .sea],
    [.sea, .land, .land]
]

Below is my implementation in Swift. It uses enums and a typealias to define the types and support functionality directly relevant to the type. The typealias is named Terrain is simply an array or arrays where the element is a TerrainType which is an enum. The cases include land and sea as well as marked versions of those cases. A computed property indicates if the value is marked.

The Terrain type has a type extension which adds useful computed properties as well as subscript support. A struct called Position is used with the subscript support. It makes it easy to access a value by Position and check if the position with the isInBounds function and mark it with the markPosition function.

The Position type supports the + operator to add a Direction which is an enum. By adding a direction to a position it adjusts the x and y values appropriately. The Direction type includes a position property which uses the current case to calculate a value. This type also has a computed property for squareDirections which excludes the diagonal directions.

All of this support then makes the implementation much simpler. The findIslands function will iterate over every possible position, even if the matrix is not square. Each position is checked and when land is found it will call the findIsland at that position, mark it and then call consumeIsland which will check every position in each given direction. When creating the instance of this IslandCounter there is an option for includeDiagonal to use just the square directions or all of them. That changes which directions the consume function will use. And each time the consume function finds connected land it calls itself again recursively. It also marks the sea positions since they can be skipped when the returning to the loops in the findIslands function. A simple count property is incremented each time an unmarked land position is found. Once all positions have been checked the count is returned.

Debugging

There is also an option to enable debugging when the IslandCounter instance is created. When enabled the terrain is printed out after each island has been consumed. It should show visually that each position has been marked including the sea positions which were checked on the edges. Since the terrain is represented with emojies it is printed out with fixed widths making it easy to visually understand the current state.

Testing

Tests are also included in this Swift Playground and run with a test observer which prints the results. The features in the supporting types are tested and then various scenarios with different instances of Terrain.

Notes on Coding Style

One convention used with this code matches what is apparently the internal style at Apple. Instead of immediately returning a computed value it is set to a local variable and then returned. The benefits here are that it allows a developer to set a breakpoint on the return to view the local variable before it is returned. And a side effect, intentional or not, is that it actually increases code coverage. This code also declares the result variable without a value which is returned at the end of the function. This undefined value must be defined on all code paths or it won't compile. This technique ensures the result is set intentionally instead of mistakenly using a default value. And this coding style also helps with increasing code coverage. When early returns are used there can be gaps in code coverage even when logically all lines of code are reached. Something about how code coverage is implemented with Xcode works better with this coding style instead of using early returns.

Playground.swift

import Foundation

@frozen
enum TerrainType: CustomStringConvertible {
    case land
    case sea
    case markedLand
    case markedSea

    var description: String {
        let result: String
        switch self {
            case .land:
                result = "🏝"
            case .sea:
                result = "🌊"
            case .markedLand:
                result = "🌴"
            case .markedSea:
                result = "💧"
        }
        return result
    }

    var isMarked: Bool {
        let result = self == .markedLand || self == .markedSea
        return result
    }
}

typealias Terrain = [[TerrainType]]

// support the matrix logic
extension Array where Element == [TerrainType] {
    // human-friendly chart of the terrain
    var chart: String {
        map {
            $0.map {
                String(describing: $0)
            }.joined(separator: " ")
        }.joined(separator: "\n")
    }

    subscript(position: Position) -> TerrainType? {
        get {
            guard isInBounds(position: position) else { return nil }
            let result = self[position.x][position.y]
            return result
        }
        set {
            guard let value = newValue else { return }
            self[position.x][position.y] = value
        }
    }

    func isInBounds(position: Position) -> Bool {
        guard position.x >= 0, position.x < count else { return false }
        let row = self[position.x]
        let result = position.y >= 0 && position.y < row.count
        return result
    }

    mutating func markPosition(position: Position) {
        guard let terrainType = self[position] else { return }
        if terrainType == .land {
            self[position] = .markedLand
        } else if terrainType == .sea {
            self[position] = .markedSea
        }
    }
}

struct Position {
    let x: Int
    let y: Int

    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }

    static func +(lhs: Position, rhs: Direction) -> Position {
        let rightPosition = rhs.position
        let result = Position(lhs.x + rightPosition.x, lhs.y + rightPosition.y)
        return result
    }
}

extension Position: Equatable {}

@frozen
enum Direction: CaseIterable {
    case up
    case down
    case left
    case right

    case upLeft
    case upRight
    case downLeft
    case downRight

    static var squareDirections: [Direction] {
        let result: [Direction] = [.up, .down, .left, .right]
        return result
    }

    var position: Position {
        let result: Position
        switch self {
            case .up:
                result = Position(-1, 0)
            case .down:
                result = Position(1, 0)
            case .left:
                result = Position(0, -1)
            case .right:
                result = Position(0, 1)
            case .upLeft:
                result = Position(-1, -1)
            case .upRight:
                result = Position(-1, 1)
            case .downLeft:
                result = Position(1, -1)
            case .downRight:
                result = Position(1, 1)
        }
        return result
    }
}

class IslandCounter {
    // Optimization: positions will be marked in place in the matrix
    var terrain: Terrain
    var count: Int = 0
    let includeDiagonal: Bool
    let enableDebugging: Bool

    init(terrain: Terrain, includeDiagonal: Bool = false, enableDebugging: Bool = false) {
        // assumes each array in the matrix has the same number of elements
        self.terrain = terrain
        self.includeDiagonal = includeDiagonal
        self.enableDebugging = enableDebugging
    }

    var directions: [Direction] {
        let result: [Direction] = includeDiagonal ? Direction.allCases : Direction.squareDirections
        return result
    }

    func consumeIsland(position: Position) {
        directions.forEach { direction in
            let nextPosition = position + direction
            if let terrainType = terrain[nextPosition], !terrainType.isMarked {
                // Optimization: mark the sea positions since those won't lead to an island
                terrain.markPosition(position: nextPosition)
                if terrainType == .land {
                    // recursively look for more
                    consumeIsland(position: nextPosition)
                }
            }
        }
    }

    func findIsland(position: Position) {
        if let terrainType = terrain[position] {
            terrain.markPosition(position: position)
            if terrainType == .land {
                count += 1
                consumeIsland(position: position)
                if enableDebugging {
                    print("\(terrain.chart)\n")
                }
            }
        }
    }

    func findIslands() -> Int {
        terrain.indices.forEach { x in
            terrain[x].indices.forEach { y in
                let position = Position(x, y)
                if let terrainType = terrain[position],
                    !terrainType.isMarked {
                    findIsland(position: position)
                }
            }
        }

        print(terrain.chart)
        return count
    }
}

import XCTest

public class TestObserver: NSObject, XCTestObservation {
    public static func observe() {
        let observer = TestObserver()
        XCTestObservationCenter.shared.addTestObserver(observer)
    }
    public func testCase(_ testCase: XCTestCase, didFailWithDescription description: String, inFile filePath: String?, atLine lineNumber: Int) {
        print("🚫 \(description) line:\(lineNumber)")
    }
    public func testCaseDidFinish(_ testCase: XCTestCase) {
        if testCase.testRun?.hasSucceeded == true {
            print("✅ \(testCase)")
        }
    }
}

class IslandCounterTests: XCTestCase {
    func testBasicTerrain() {
        let terrain: Terrain = [
            [.land, .sea],
            [.sea, .sea]
        ]
        print("\(terrain.chart)\n")
        let counter = IslandCounter(terrain: terrain)
        let count = counter.findIslands()
        XCTAssertEqual(count, 1)
    }

    func testPositionAddition() {
        XCTAssertTrue(Position(0,0) + .downRight == Position(1,1))
        XCTAssertTrue(Position(2,2) + .upLeft == Position(1,1))
        XCTAssertTrue(Position(0,2) + .downLeft == Position(1,1))
        XCTAssertTrue(Position(2,0) + .upRight == Position(1,1))
    }

    func testNavigatingGoodTerrain() {
        let terrain: Terrain = [
            [.land, .sea, .land],
            [.sea, .sea, .sea],
            [.sea, .sea, .land]
        ]
        print("\(terrain.chart)\n")

        XCTAssertEqual(TerrainType.land, terrain[Position(0,0)])
        XCTAssertEqual(TerrainType.land, terrain[Position(0,2)])
        XCTAssertEqual(TerrainType.sea, terrain[Position(1,1)])
        XCTAssertEqual(TerrainType.land, terrain[Position(2,2)])

        XCTAssertEqual(TerrainType.sea, terrain[Position(0,0) + .down])
        XCTAssertEqual(TerrainType.land, terrain[Position(1,2) + .up])
        XCTAssertEqual(TerrainType.sea, terrain[Position(1,1) + .left])
        XCTAssertEqual(TerrainType.sea, terrain[Position(2,2) + .left])

        XCTAssertEqual(TerrainType.sea, terrain[Position(0,0) + .downRight])
        XCTAssertEqual(TerrainType.sea, terrain[Position(1,2) + .downLeft])
        XCTAssertEqual(TerrainType.land, terrain[Position(1,1) + .upRight])
        XCTAssertEqual(TerrainType.sea, terrain[Position(2,1) + .upLeft])
    }

    func testNavigatingBadTerrain() {
        let terrain: Terrain = [
            [.land, .sea, .land],
            [.sea, .sea, .sea],
            [.sea, .sea, .land]
        ]
        print("\(terrain.chart)\n")

        XCTAssertNil(terrain[Position(0,0) + .up])
        XCTAssertNil(terrain[Position(0,0) + .upLeft])
        XCTAssertNil(terrain[Position(0,0) + .upRight])
        XCTAssertNil(terrain[Position(2,2) + .down])
        XCTAssertNil(terrain[Position(2,2) + .downRight])
        XCTAssertNil(terrain[Position(2,2) + .downLeft])
    }

    func testTerrainWithNoIsland() {
        let terrain: Terrain = [
            [.sea, .sea, .sea, .sea],
            [.sea, .sea, .sea, .sea],
            [.sea, .sea, .sea, .sea],
            [.sea, .sea, .sea, .sea]
        ]
        print("\(terrain.chart)\n")
        let counter = IslandCounter(terrain: terrain)
        let count = counter.findIslands()
        XCTAssertEqual(count, 0)
    }

    func testTerrainWithOneIsland() {
        let terrain: Terrain = [
            [.land, .land, .sea, .sea],
            [.land, .land, .sea, .sea],
            [.sea, .sea, .sea, .sea],
            [.sea, .sea, .sea, .sea]
        ]
        print("\(terrain.chart)\n")
        let counter = IslandCounter(terrain: terrain)
        let count = counter.findIslands()
        XCTAssertEqual(count, 1)
    }

    func testTerrainWithTwoIslands() {
        let terrain: Terrain = [
            [.land, .land, .sea, .sea],
            [.land, .land, .sea, .sea],
            [.sea, .sea, .sea, .sea],
            [.sea, .sea, .sea, .land]
        ]
        print("\(terrain.chart)\n")
        let counter = IslandCounter(terrain: terrain)
        let count = counter.findIslands()
        XCTAssertEqual(count, 2)
    }

    func testTerrainWithComplexIsland() {
        let terrain: Terrain = [
            [.land, .land, .sea, .sea],
            [.sea, .land, .sea, .sea],
            [.land, .land, .land, .sea],
            [.sea, .sea, .land, .sea]
        ]
        print("\(terrain.chart)\n")
        let counter = IslandCounter(terrain: terrain)
        let count = counter.findIslands()
        XCTAssertEqual(count, 1)
    }

    func testTerrainWithDiagonalIsland() {
        let terrain: Terrain = [
            [.land, .land, .sea, .sea, .sea],
            [.sea, .land, .sea, .sea, .sea, .sea, .land],
            [.land, .land, .land, .land, .sea],
            [.sea, .sea, .land, .sea, .land, .sea, .land],
            [.land, .sea, .land, .sea, .land, .sea, .land],
            [.land, .sea, .land, .sea, .land, .land, .land],
            [.land]
        ]
        print("\(terrain.chart)\n")
        let counter = IslandCounter(terrain: terrain, includeDiagonal: true)
        let count = counter.findIslands()
        XCTAssertEqual(count, 3)
    }
}

// MARK: Run Tests

TestObserver.observe()
IslandCounterTests.defaultTestSuite.run()