22
\$\begingroup\$

This is my attempt to solve the August 2016 Community Challenge in Swift. I tried to implement the algorithm described by @200_success:

  1. Each Cell keeps track of which Basin it belongs to; each Cell is initially assume to be in its own Basin. Each Basin has a sink, or lowest Cell, which acts as a "representative element" of the Basin, as well as a member count. Topography keeps track of all Basins.
  2. For each Basin, find lowest of the sink's neighbours. If the lowest is not already a member of this Basin, transfer its cells into the lowest neighbour's Basin, and notify Topography that the higher basin no longer exists.
  3. Repeat step 2 until no further action is necessary.
  4. Have Topography enumerate the Basins and their counts.

The code is Swift 3 and requires Xcode 8 beta 4.

Cell.swift

import Swift

class Cell {
    let elevation: Int
    var lowerCell: Cell?
    weak var basin: Basin?

    init(elevation: Int) {
        self.elevation = elevation
    }

    /// Compare the elevation of the (currently) lowest neighbor with that of
    /// the other cell, and update `lowerCell` if necessary. Returns `true`
    /// if other cell was lower, and `false` otherwise.
    @discardableResult
    func updateLowerCell(with other: Cell) -> Bool {
        if other.elevation < (lowerCell?.elevation) ?? elevation {
            lowerCell = other
            return true
        }
        return false
    }
}

Basin.swift

import Swift

/// A basin consists of a "sink" and zero or more cells which eventually flow
/// into the sink.
class Basin {
    var cells: [Cell]
    var sink: Cell

    init(cell: Cell) {
        cells = [cell]
        sink = cell
        cell.basin = self
    }

    func join(with other: Basin) {
        precondition(other !== self, "Basin must not be joined with itself")
        for cell in other.cells {
            cell.basin = self
        }
        cells.append(contentsOf: other.cells)
        other.cells.removeAll()
    }
}

Topography.swift

import Swift

/// A topography is a collection of basins. The union of all the
/// basins cells is always the complete grid.
struct Topography {
    var basins: [Basin]

    /// Create topography from a sequence of cells. Initially, each basin
    /// consists of a single cell.
    init<S: Sequence>(cells: S)
        where S.Iterator.Element == Cell {
            basins = cells.map(Basin.init)
    }

    /// Create topography from 2D elevation map.
    init(elevationData: [[Int]]) {
        // Create `[[Cell]]` array from `elevationData`.
        let grid = elevationData.map { levelRow in
            levelRow.map(Cell.init)
        }

        // Find the lowest neighbor for each cell: left/right ...
        for gridRow in grid {
            for (leftCell, rightCell) in zip(gridRow, gridRow.dropFirst()) {
                if !leftCell.updateLowerCell(with: rightCell) {
                    rightCell.updateLowerCell(with: leftCell)
                }
            }
        }
        // ... and top/down.
        for (upperRow, lowerRow) in zip(grid, grid.dropFirst()) {
            for (upperCell, lowerCell) in zip(upperRow, lowerRow) {
                if !upperCell.updateLowerCell(with: lowerCell) {
                    lowerCell.updateLowerCell(with: upperCell)
                }
            }
        }

        self.init(cells: grid.flatten())
    }

    /// Join each basin with the next one that it is flowing into.
    mutating func joinBasins() {
        basins = basins.filter { basin in
            if let otherBasin = basin.sink.lowerCell?.basin, otherBasin !== basin {
                otherBasin.join(with: basin)
                return false
            } else {
                return true
            }
        }
    }

    /// Sizes of all basins, sorted in decreasing order.
    func basinSizes() -> [Int] {
        return basins.map { $0.cells.count }.sorted(by: >)
    }
}

RainfallSolver.swift

import Swift

/// Wrapper type with a single static method to solve the Rainfall problem.
struct RainfallSolver {

    static func solve(elevationData: [[Int]]) -> [Int] {
        var topo = Topography(elevationData: elevationData)
        topo.joinBasins()
        return topo.basinSizes()
    }
}

The main program in main.swift which reads the elevation data (as in the specified input format) from standard input and prints the solution to standard output.

import Foundation

func readIntegers() -> [Int] {
    let line = readLine(strippingNewline: true)!
    let comps = line.components(separatedBy: CharacterSet.whitespaces).filter { !$0.isEmpty }
    return comps.map { Int($0)! }
}

func readElevationData() -> [[Int]] {
    let dimension = readIntegers().first!
    let elevationData = (0..<dimension).map { _ in readIntegers() }
    return elevationData
}

let elevationData = readElevationData()
let solution = RainfallSolver.solve(elevationData: elevationData)
// Print solution as space-separated list:
print(solution.map(String.init).joined(separator: " "))

Finally, unit tests with the four given examples from Rainfall challenge in RainfallTests.swift. All tests pass.

import XCTest

class RainfallTests: XCTestCase {

    func testExample1() {
        let solution = RainfallSolver.solve(elevationData: [
            [ 1, 5, 2 ],
            [ 2, 4, 7 ],
            [ 3, 6, 9 ]
            ])
        XCTAssertEqual(solution, [ 7, 2 ])
    }

    func testExample2() {
        let solution = RainfallSolver.solve(elevationData: [
            [ 1 ]
            ])
        XCTAssertEqual(solution, [ 1 ])
    }

    func testExample3() {
        let solution = RainfallSolver.solve(elevationData: [
            [ 1, 0, 2, 5, 8 ],
            [ 2, 3, 4, 7, 9 ],
            [ 3, 5, 7, 8, 9 ],
            [ 1, 2, 5, 4, 3 ],
            [ 3, 3, 5, 2, 1 ]
            ])
        XCTAssertEqual(solution, [ 11, 7, 7 ])
    }

    func testExample4() {
        let solution = RainfallSolver.solve(elevationData: [
            [ 0, 2, 1, 3 ],
            [ 2, 1, 0, 4 ],
            [ 3, 3, 3, 3 ],
            [ 5, 5, 2, 1 ]
            ])
        XCTAssertEqual(solution, [ 7, 5, 4 ])
    }
}

Remarks:

  • Cell and Basin are defined as classes because there are references between instances of these types. In particular, the reference from a cell to its containing basin is a weak reference to avoid retain cycles. All other types are structs (value types).

  • A cell does not know its coordinates. The cells are stored in a 2D grid only temporarily in init(elevationData: [[Int]]), in order to determine the lowest neighbours. After that, the actual geometry is not used anymore.

  • In joinBasins(), each of the initial (single-cell) basins is visited exactly once, and potentially joined with a "lower basin" as described in step #2 of the algorithm.

    In the first version of this program, I repeated step #2 until no more basins are joined. However, after observing that the second pass never joined additional basins, I convinced myself that a single pass is sufficient. This was verified with the given examples and additional randomly created grids.

  • readElevationData() in main.swift expects the data in the specified input format and will crash otherwise. However, an arbitrary amount of whitespace is accepted as separator between the integers and not just a single space character, this turned out to be convenient for my test cases. A detailed error reporting is omitted.

  • The code actually works with rectangular maps, not only with quadratic maps.

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

I think this code is great. Using weak references to refer to a Basin is a great way to prevent retain cycles with automatic reference counting. One suggestion I have is to make Topography a class, because it refers to a class. Other suggestions are in the code, marked with "CR". You can use this snippet of code:

/// A topography is a collection of basins. The union of all the
/// basins cells is always the complete grid.
class Topography {
    var basins: [Basin]

    /// Create topography from a sequence of cells. Initially, each basin
    /// consists of a single cell.
    init<S: Sequence>(cells: S)
        where S.Element == Cell { // CR: `S.Iterator.Element` is the same as `S.Element`
            basins = cells.map(Basin.init)
    }

    /// Create topography from 2D elevation map.
    convenience init(elevationData: [[Int]]) { // CR: This calls the designated initializer, so it should be a convenience initializer.
        // Create `[[Cell]]` array from `elevationData`.
        let grid = elevationData.map { $0.map(Cell.init) } // CR: `levelRow in` clutters code, implicit names are better for simple lambdas.

        // Find the lowest neighbor for each cell: left/right ...
        for gridRow in grid {
            for (leftCell, rightCell) in zip(gridRow, gridRow.dropFirst()) {
                if !leftCell.updateLowerCell(with: rightCell) {
                    rightCell.updateLowerCell(with: leftCell)
                }
            }
        }
        // ... and top/down.
        for (upperRow, lowerRow) in zip(grid, grid.dropFirst()) {
            for (upperCell, lowerCell) in zip(upperRow, lowerRow) {
                if !upperCell.updateLowerCell(with: lowerCell) {
                    lowerCell.updateLowerCell(with: upperCell)
                }
            }
        }

        self.init(cells: grid.flatten())
    }

    /// Join each basin with the next one that it is flowing into.
    func joinBasins() -> Bool { // CR: classes are mutable by default, also, included return type
        basins = basins.filter { basin in
            if let otherBasin = basin.sink.lowerCell?.basin, otherBasin !== basin {
                otherBasin.join(with: basin)
                return false
            }
            return true // CR: Removed else, `return` exits
        }
    }

    /// Sizes of all basins, sorted in decreasing order.
    func basinSizes() -> [Int] {
        return basins.map { $0.cells.count }.sorted(by: >)
    }
}
```
\$\endgroup\$
1
  • \$\begingroup\$ Cell and Basin are defined as classes because there are references between instances of these types, but that is not the case for Topography. I don't see yet why Topography should be made a class instead of a struct. A general rule (I think) is: use value types (structs) unless there is a reason not to do so. “... because it refers to a class” is not sufficient reason IMO. \$\endgroup\$
    – Martin R
    Jul 30, 2022 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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