算法 - 下三角填充（ Swift 学习 & 过渡设计）

最近在学习 Swift，正好拿算法入手，以期在实际编码过程中，能有更多的对 Swift 编程思想的体会。另外，这个月快过完了，又得交公粮了，就用“下三角矩阵填充的 Swift 实现”对付一下吧🥴

矩阵下三角填充，在矩阵中按照自然数递增填充数，使得矩阵中下三角被填满。如图
原理图
下三角填充算不上什么难的算法，但本着学习 Swift 的目的，所以下面过渡设计了一番，实现了通用的任意方向的三角的填充算法。

  • 定义矩阵和坐标，新增根据填充方向获取下一个待填充点坐标的函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    typealias Matrix = [[Int]]
    struct Coordinate {
        var x:Int!, y:Int!
        init(x:Int, y:Int) {
            self.x = x; self.y = y
        }
        
        func next(direction:Direction) -> Coordinate {
            switch direction {
                case .up:
                    return Coordinate(x: self.x-1, y: self.y)
                case .down_left:
                    return Coordinate(x: self.x + 1, y: self.y - 1)
                case .right:
                    return Coordinate(x: self.x, y: self.y + 1)
                case .down:
                    return Coordinate(x: self.x + 1, y: self.y)
                case .down_right:
                    return Coordinate(x: self.x + 1, y: self.y + 1)
                case .left:
                    return Coordinate(x: self.x, y: self.y - 1)
                case .up_left:
                    return Coordinate(x: self.x - 1, y: self.y - 1)
                case .up_right:
                    return Coordinate(x: self.x - 1, y: self.y + 1)
            }
        }
    }

  • 定义矩阵填充时的开始位置，和根据位置翻译成具体坐标的函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    extension Matrix {
        enum InitPosition {
            case UpLeft
            case UpRight
            case DownLeft
            case DownRight
            
        }
        
        func translateCoor(from position:InitPosition) -> Coordinate {
            switch position {
                case .UpLeft:
                    return Coordinate(x: 0, y: 0)
                case .UpRight:
                    return Coordinate(x: 0, y: self[0].count - 1)
                case .DownLeft:
                    return Coordinate(x: self.count - 1, y: 0)
                case .DownRight:
                    return Coordinate(x: self.count - 1, y: self[0].count - 1)
            }
        }
        
        func valueTest(_ coordinate:Coordinate) throws {
            guard coordinate.y < self.count else {
                throw MatrixError.UpperOutRangeY
            }
            guard coordinate.y >= 0 else {
                throw MatrixError.FloorOutRangeY
            }
            guard coordinate.x < self[0].count else {
                throw MatrixError.UpperOutRangeX
            }
            guard coordinate.x >= 0 else {
                throw MatrixError.FloorOutRangeX
            }
            guard self[coordinate.x][coordinate.y] == 0 else {
                throw MatrixError.InvalidItemValue
            }
        }
    }
  • 面向错误（异常）编程，定义通用的错误枚举
    1
    2
    3
    4
    5
    6
    7
    8
    9
    enum MatrixError: Error {
        case TooShortLength
        case InvalidItemValue
        
        case UpperOutRangeY
        case UpperOutRangeX
        case FloorOutRangeY
        case FloorOutRangeX
    }
  • 定义填充方向。根据初始规定的填充方向和填充起始坐标，决定需要转向时，应该是朝哪个方向转向
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    enum Direction {
        case up
        case down
        case down_left
        case up_left
        case right
        case left
        case down_right
        case up_right
        
        mutating func next(initDirection: Direction, initPosition: Matrix.InitPosition) {
            switch (initDirection, initPosition) {
            case (Direction.up, Matrix.InitPosition.DownLeft):
                    switch self {
                    case .up: self = .down_right;case .down_right: self = .left;case .left: self = .up
                        default:break
                    }
            case (Direction.up, Matrix.InitPosition.DownRight):
                switch self {
                case .up: self = .down_left;case .down_left: self = .right;case .right: self = .up
                    default:break
                }
            case (Direction.down, Matrix.InitPosition.UpRight):
                switch self {
                case .down: self = .left;case .left: self = .up_right;case .up_right: self = .down
                    default:break
                }
            case (Direction.down, Matrix.InitPosition.UpLeft):
                switch self {
                case .down: self = .right;case .right: self = .up_left;case .up_left: self = .down
                    default:break
                }
            case (Direction.left, Matrix.InitPosition.UpRight):
                switch self {
                case .left: self = .down_right;case .down_right: self = .up;case .up: self = .left
                    default:break
                }
            case (Direction.left, Matrix.InitPosition.DownRight):
                switch self {
                case .left: self = .up;case .up: self = .down_right;case .down_right: self = .left
                    default:break
                }
            case (Direction.right, Matrix.InitPosition.DownLeft):
                switch self {
                case .right: self = .up;case .up: self = .down_left;case .down_left: self = .right
                    default:break
                }
            case (Direction.right, Matrix.InitPosition.UpLeft):
                switch self {
                case .right: self = .down_left;case .down_left: self = .up;case .up: self = .right
                    default:break
                }
            case (Direction.up_left, Matrix.InitPosition.DownRight):
                switch self {
                case .up_left: self = .down;case .down: self = .right;case .right: self = .up_left
                    default:break
                }
            case (Direction.up_right, Matrix.InitPosition.DownLeft):
                switch self {
                case .up_right: self = .down;case .down: self = .left;case .left: self = .up_right
                    default:break
                }
            case (Direction.down_right, Matrix.InitPosition.UpLeft):
                switch self {
                case .down_right: self = .left;case .left: self = .up;case .up: self = .down_right
                    default:break
                }
            case (Direction.down_left, Matrix.InitPosition.UpRight):
                switch self {
                case .down_left: self = .right;case .right: self = .up;case .up: self = .down_left
                    default:break
                }
            default:
                break
            }
        }
    }
  • 定义 TriangleMatrix 对象
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    class TriangleMatrix {
        var matrix:Matrix!
        var length:Int!
        var initPosition: Matrix.InitPosition?
        var initDirection: Direction?
        // 记录最大值，决定递归的停止条件
        var maxVal:Int {
            get {
                return (self.length + 1)*self.length / 2 + self.startValue - 1
            }
        }
        var startValue:Int!
        // 初始化方法，需要每个维度的长度，和起始填充数的值
        init(length: Int, startValue:Int) throws {
            guard length >= 3 else {
                throw MatrixError.TooShortLength
            }
            self.startValue = startValue
            self.length = length
            self.matrix = TriangleMatrix.dim(length, TriangleMatrix.dim(length, 0))
        }
        // 重置，方便进行下一次填充
        func refresh() {
            for x in 0 ..< self.matrix.count {
                for y in 0 ..< self.matrix[x].count {
                    self.matrix[x][y] = 0
                }
            }
            self.startValue = 1
        }
        
        func print() {
            for array in matrix {
                for item in array {
                    let str = String(format: "%4d", item)
                    Swift.print(str, terminator:"")
                }
                Swift.print("\n", terminator:"")
            }
        }
        // 快捷生成多维数组的方法
        static func dim<T>(_ count:Int, _ value:T) -> [T] {
            return [T](repeating: value, count: count)
        }
        // 递归填充，面向异常编程
        private func input(start:inout Coordinate, value:inout Int, direction:inout Direction) {
            // 尝试计算下一个位置，根据位置是否合法判断是否需要转向
            var newCoordinate = start.next(direction: direction)
            do {
                try self.matrix.valueTest(newCoordinate)
            } catch is MatrixError {
                direction.next(initDirection: self.initDirection!, initPosition: self.initPosition!)
                newCoordinate = start.next(direction: direction)
            } catch {
                Swift.print(error)
            }
            
            self.matrix[start.x][start.y] = value
            if value < self.maxVal {
                value += 1
                input(start: &newCoordinate, value: &value, direction: &direction)
            }
        }
        // 对外接口
        func doInput(direction: Direction = .right,
                     startPosition: Matrix.InitPosition = .UpLeft){
            var startVal = self.startValue!
            
            self.initPosition = startPosition
            self.initDirection = direction
            var startCoor = self.matrix.translateCoor(from: startPosition)
            var startDirect = direction
            
            input(start: &startCoor, value: &startVal, direction: &startDirect)
        }
    }
  • 测试代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    var matrix = try TriangleMatrix(length: 10, startValue: 1)
    matrix.doInput()
    matrix.print()

    matrix.refresh()
    matrix.doInput(direction: .up_left, startPosition: .DownRight)
    matrix.print()

    matrix.refresh()
    matrix.doInput(direction: .left, startPosition: .UpRight)
    matrix.print()

    matrix.refresh()
    matrix.doInput(direction: .down_left, startPosition: .UpRight)
    matrix.print()
  • 输出结果
    输出

后记：初识 Swift 时，诟病于她一页代码半页关键字，一旦开始去了解和学习这门语言时，那是“真香”！，不同于 OC，很多既有的编程模式在 Swift 中都可以用很少的代码去表达出来，让开发者有更多精力专注于具体业务而不是语言本身。在函数式语言中，Swift 和 Python 在提倡的简单、精练的理念上有很多共同点，对于我这样有一些 Python 基础的人，用起 Swift 有种相见恨晚的感觉。后面的 Swift 学习曲线可能比较陡峭，但就像瑞士军刀相比于普通小刀，虽然看起来更复杂了，但是可以做到的事情也增多了，期待！