Queen's Attack II With Declarative Emphasis

QueensAttack.swift

import Foundation

// ==========================================================================
// My Solution
// ==========================================================================

struct Position {
    let row: Int
    let column: Int
}

enum Direction: CaseIterable {
    case up, down, left, right
    case upLeft, upRight, downLeft, downRight

    // Filter out obstacles that are not in this direction from the given queen
    func filterOutIrrelevantObstacles(for queen: Position) -> (Position) -> Bool {
        switch self {
        case .up:
            return { $0.column == queen.column && $0.row > queen.row }
        case .down:
            return { $0.column == queen.column && $0.row < queen.row }
        case .left:
            return { $0.row == queen.row && $0.column < queen.column }
        case .right:
            return { $0.row == queen.row && $0.column > queen.column }
        case .upLeft:
            return { ($0.row + $0.column) == (queen.row + queen.column) && $0.column < queen.column }
        case .downRight:
            return { ($0.row + $0.column) == (queen.row + queen.column) && $0.column > queen.column }
        case .upRight:
            return { ($0.row - $0.column) == (queen.row - queen.column) && $0.column > queen.column }
        case .downLeft:
            return { ($0.row - $0.column) == (queen.row - queen.column) && $0.column < queen.column }
        }
    }

    // A position at the edge of the board in this direction
    func distantPosition(from queen: Position, size: Int) -> Position {
        switch self {
        case .up:
            return Position(row: size + 1, column: queen.column)
        case .down:
            return Position(row: 0, column: queen.column)
        case .left:
            return Position(row: queen.row, column: 0)
        case .right:
            return Position(row: queen.row, column: size + 1)
        case .downRight:
            return Position(row: 0, column: size + 1)
        case .downLeft:
            return Position(row: 0, column: 0)
        case .upLeft:
            return Position(row: size + 1, column: 0)
        case .upRight:
            return Position(row: size + 1, column: size + 1)
        }
    }

    // Closure to choose the closets of two positions
    var chooseClosest: (_ left: Position, _ right: Position) -> Position {
        switch self {
        case .up, .upLeft, .upRight:
            return { $0.row < $1.row ? $0 : $1 }
        case .down, .left, .right, .downLeft, .downRight:
            return { $0.row > $1.row ? $0 : $1 }
        }
    }

    // The key path(s) to check for shortest distance
    var distanceKeyPaths: [KeyPath<Position, Int>] {
        switch self {
        case .up, .down:
            return [\Position.row]
        case .left, .right:
            return [\Position.column]
        case .upLeft, .downLeft, .upRight, .downRight:
            return [\Position.row,\Position.column]
        }
    }
}

// Complete the queensAttack function below.
func queensAttack(n: Int, k: Int, r_q: Int, c_q: Int, obstacles: [[Int]]) -> Int {
    // Improve names to be more readable
    let queen = Position(row: r_q, column: c_q)
    let obstacles = obstacles
        .map({ Position(row: $0[0], column: $0[1]) })
        // Filter out any irrelevant obstacles
        .filter({
            let sameColumn = $0.column == queen.column
            let sameRow = $0.row == queen.row
            let diagonalTopLeftToBottomRight = ($0.row + $0.column) == (queen.row + queen.column)
            let diagonalBottomLeftToTopRight = ($0.row - $0.column) == (queen.row - queen.column)
            return sameColumn || sameRow || diagonalTopLeftToBottomRight || diagonalBottomLeftToTopRight
        })

    // Calculate the number of open spaces between two rows or two columns
    func openSpacesBetween(_ left: Int, and right: Int) -> Int {
        guard left != right else { return 0 }
        return abs(left - right) - 1
    }

    return Direction.allCases
        .map({ direction in
            let position: Position = obstacles
                .filter(direction.filterOutIrrelevantObstacles(for: queen))
                .reduce(direction.distantPosition(from: queen, size: n), direction.chooseClosest)
            return direction.distanceKeyPaths
                .map({ openSpacesBetween(queen[keyPath: $0], and: position[keyPath: $0]) })
                .reduce(.max, min) as Int
        })
        .reduce(0, +)
}

// ==========================================================================
// Testing
// ==========================================================================

struct TestCase: CustomStringConvertible {
    let n: Int
    let r_q: Int
    let c_q: Int
    let obstacles: [[Int]]

    let expectation: Int

    var description: String {
        enum Kind {
            case obstacle
            case queen
            case none
        }
        var board = [[Kind]](
            repeating: [Kind](repeating: .none, count: self.n),
            count: self.n
        )

        board[r_q - 1][c_q - 1] = .queen

        for next in self.obstacles {
            board[next[0] - 1][next[1] - 1] = .obstacle
        }

        var output = ""
        for row in (1 ... self.n).reversed() {
            output += "\(row)"
            for column in 1 ... self.n {
                output += " "
                switch board[row - 1][column - 1] {
                case .queen:
                    output += "Q"
                case .obstacle:
                    output += "X"
                case .none:
                    output += "_"
                }
            }
            if row != 1 {
                output += "\n"
            }
        }
        output += "\n\n "
        for column in 1 ... self.n {
            output += " \(column)"
        }
        return output
    }
}

let cases = [
    // Central
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [], expectation: 16),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5]], expectation: 15),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5],[4, 2]], expectation: 13),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5],[4, 2],[2, 3]], expectation: 11),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5],[4, 2],[2, 3],[1, 5]], expectation: 10),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5],[4, 2],[2, 3],[1, 5],[3, 5]], expectation: 9),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5],[4, 2],[2, 3],[1, 5],[3, 5],[3, 1]], expectation: 8),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5],[4, 2],[2, 3],[1, 5],[3, 5],[3, 1],[5,3]], expectation: 7),
    TestCase(n: 5, r_q: 3, c_q: 3, obstacles: [[5, 5],[4, 2],[2, 3],[1, 5],[3, 5],[3, 1],[5,3],[1,1]], expectation: 6),

    // Special
    TestCase(n: 1, r_q: 1, c_q: 1, obstacles: [], expectation: 0),
    TestCase(n: 4, r_q: 4, c_q: 4, obstacles: [], expectation: 9),

    // Other
    TestCase(n: 2, r_q: 1, c_q: 1, obstacles: [], expectation: 3),
    TestCase(n: 2, r_q: 1, c_q: 2, obstacles: [], expectation: 3),
    TestCase(n: 2, r_q: 2, c_q: 1, obstacles: [], expectation: 3),
    TestCase(n: 2, r_q: 2, c_q: 2, obstacles: [], expectation: 3),
    TestCase(n: 2, r_q: 1, c_q: 1, obstacles: [[1,2],[2,1],[2,2]], expectation: 0),
    TestCase(n: 2, r_q: 1, c_q: 2, obstacles: [[1,1],[2,1],[2,2]], expectation: 0),
    TestCase(n: 2, r_q: 2, c_q: 1, obstacles: [[1,1],[1,2],[2,2]], expectation: 0),
    TestCase(n: 2, r_q: 2, c_q: 2, obstacles: [[1,1],[1,2],[2,1]], expectation: 0),
]

var successful = true
for (index, next) in cases.enumerated() {
    let result = queensAttack(n: next.n, k: next.obstacles.count, r_q: next.r_q, c_q: next.c_q, obstacles: next.obstacles)
    if result != next.expectation {
        print("\(index) Failed")
        print("-------------------")
        print(next)
        print("Expected \(next.expectation) but got \(result)")
        print("-------------------")
        successful = false
    }
}
if successful {
    print("Success!")
}