Solving the 15-puzzle in Swift: A Look at Algorithms and Speed

Algorithms and optimization can sound daunting, but are a really interesting programming problem. In this talk, we'll be looking at writing a solver for a puzzle, improving it along the way by making it more performant.

Transcript

1. SOLVING THE 15 PUZZLE IN SWIFT A Look at Algorithms and Speed 1 — @basthomas
2. SOLVING THE 15 PUZZLE IN SWIFT A Look at Algorithms and Speed A Look at Algorithms and Performance 2 — @basthomas
3. WHAT IS A 15 PUZZLE? 3 — @basthomas
4. | 1| 2| 3| 4| | 5| 6| 7| 8| | 9|10|11|12| |13|14|15| | 4 — @basthomas
5. | 1| 6| 2| 3| | |10| 7| 4| | 5| 9|11| 8| |13|14|15|12| 5 — @basthomas
6. | 1| 6| 2| 3| | 5|10| 7| 4| | | 9|11| 8| |13|14|15|12| 6 — @basthomas
7. | 1| 6| 2| 3| | 5|10| 7| 4| | 9| |11| 8| |13|14|15|12| 7 — @basthomas
8. | 1| 6| 2| 3| | 5| | 7| 4| | 9|10|11| 8| |13|14|15|12| 8 — @basthomas
9. | 1| | 2| 3| | 5| 6| 7| 4| | 9|10|11| 8| |13|14|15|12| 9 — @basthomas
10. | 1| 2| | 3| | 5| 6| 7| 4| | 9|10|11| 8| |13|14|15|12| 10 — @basthomas
11. | 1| 2| 3| | | 5| 6| 7| 4| | 9|10|11| 8| |13|14|15|12| 11 — @basthomas
12. | 1| 2| 3| 4| | 5| 6| 7| | | 9|10|11| 8| |13|14|15|12| 12 — @basthomas
13. | 1| 2| 3| 4| | 5| 6| 7| 8| | 9|10|11| | |13|14|15|12| 13 — @basthomas
14. | 1| 2| 3| 4| | 5| 6| 7| 8| | 9|10|11|12| |13|14|15| | 14 — @basthomas
15. BEFORE WE START, SOME HISTORY 15 — @basthomas
16. TVOS... DOES ANYONE STILL REMEMBER THAT? (OUTSIDE OF THE US) 16 — @basthomas
17. THIS WAS 4(!) YEARS AGO 17 — @basthomas
18. 18 — @basthomas
19. UICollectionView HOUSES SOME VERY, VERY COOL APIS 19 — @basthomas
20. FAST-FORWARD TO JANUARY THIS YEAR 20 — @basthomas
21. START... SOMEWHERE 21 — @basthomas
22. START... WITH THE SOLUTION 22 — @basthomas
23. struct Solution<Problem> { struct Step<T> { let step: T } let steps: [Step<Problem>] var input: Step<Problem> { return steps.first! } var output: Step<Problem> { return steps.last! } init(steps: [Step<Problem>]) { precondition(steps.count > 0, "Solution must contain at least one step.") self.steps = steps } } 23 — @basthomas
24. let solution = Solution<Int>( steps: Solution.Step(step: 1), Solution.Step(step: 2), Solution.Step(step: 3) ) print(solution.input) // Step<Int>(step: 1) print(solution.output) // Step<Int>(step: 3) 24 — @basthomas
25. COMFORMING TO Collection 25 — @basthomas
26. struct Solution<Problem>: Collection { var startIndex: Int { return steps.startIndex } var endIndex: Int { return steps.endIndex } subscript(i: Int) -> Step<Problem> { return steps[i] } func index(after i: Int) -> Int { return steps.index(after: i) } } 26 — @basthomas
27. for step in solution { print(step) } 27 — @basthomas
28. BUT NOW WHAT? 28 — @basthomas
29. LAYING IT (ALL) OUT 29 — @basthomas
30. struct Board { struct Position {} enum Tile { case empty, number(Int) } func next() func position(for tile: Tile) -> Position func tile(at position: Position) -> Tile func swap(_ aTile: Tile, with bTile: Tile) -> Bool func move(tile: Tile) -> Bool func shuffle(moves: Int = 50) func adjacentPositions(to position: Position) -> [Position] func solve() -> Solution<Board> } 30 — @basthomas
31. struct Position: CustomStringConvertible, Equatable { let row: Int let column: Int func isAdjacent(to position: Position, in board: Board) -> Bool { return board.adjacentPositions(to: self) .filter { $0 == position } .isEmpty == false } var description: String { return "row: \(row), column: \(column)" } } 31 — @basthomas
32. func isAdjacent(to position: Position, in board: Board) -> Bool { return board.adjacentPositions(to: self) - .filter { $0 == position } - .isEmpty == false + .first { $0 == position } != nil } 32 — @basthomas
33. IT'S MAGICAL 33 — @basthomas
34. IT'S MAGICAL THAT IT IS NOT. 34 — @basthomas
35. LET'S LOOK AT A Tile 35 — @basthomas
36. enum Tile: Equatable, ExpressibleByIntegerLiteral { case empty, number(Int) private static let emptyValue = -1 init(integerLiteral value: Int) { if value == Tile.emptyValue { self = .empty } else { self = .number(value) } } var intValue: Int { switch self { case .empty: return Tile.emptyValue case .number(let number): return number } } } 36 — @basthomas
37. NOW IT'S ALMOST TIME FOR THE REAL DEAL... 37 — @basthomas
38. init(rows: Int) { precondition(rows > 1, "A puzzle should at least be 2x2") var _board: [[Tile]] = [] for row in 0..<rows { _board.append([]) for column in 0..<rows { let number = (row * rows) + column + 1 if row == rows - 1 && column == rows - 1 { _board[row].append(.empty) } else { _board[row].append(.number(number)) } } } } 38 — @basthomas
39. init(rows: Int) { precondition(rows > 1, "A puzzle should at least be 2x2") var _board: [[Tile]] = [] for row in 0..<rows { _board.append([]) for column in 0..<rows { let number = (row * rows) + column + 1 if row == rows - 1 && column == rows - 1 { _board[row].append(.empty) } else { _board[row].append(.number(number)) } } } } 38 — @basthomas
40. init(rows: Int) { precondition(rows > 1, "A puzzle should at least be 2x2") var _board: [[Tile]] = [] for row in 0..<rows { _board.append([]) for column in 0..<rows { let number = (row * rows) + column + 1 if row == rows - 1 && column == rows - 1 { _board[row].append(.empty) } else { _board[row].append(.number(number)) } } } } 38 — @basthomas
41. init(rows: Int) { precondition(rows > 1, "A puzzle should at least be 2x2") var _board: [[Tile]] = [] for row in 0..<rows { _board.append([]) for column in 0..<rows { let number = (row * rows) + column + 1 if row == rows - 1 && column == rows - 1 { _board[row].append(.empty) } else { _board[row].append(.number(number)) } } } } 38 — @basthomas
42. init(rows: Int) { precondition(rows > 1, "A puzzle should at least be 2x2") var _board: [[Tile]] = [] for row in 0..<rows { _board.append([]) for column in 0..<rows { let number = (row * rows) + column + 1 if row == rows - 1 && column == rows - 1 { _board[row].append(.empty) } else { _board[row].append(.number(number)) } } } } 38 — @basthomas
43. init(rows: Int) { precondition(rows > 1, "A puzzle should at least be 2x2") var _board: [[Tile]] = [] for row in 0..<rows { _board.append([]) for column in 0..<rows { let number = (row * rows) + column + 1 if row == rows - 1 && column == rows - 1 { _board[row].append(.empty) } else { _board[row].append(.number(number)) } } } } 38 — @basthomas
44. ALGORITHMS? 39 — @basthomas
45. SPEED? SCALE? PERFORMANCE..? 40 — @basthomas
46. WHAT IS PERFORMANCE? 41 — @basthomas
47. PERFORMANCE, NOUN per·for·mance / pərˈfɔr məns / per-fawr-muh ns a: the execution of an action b: something accomplished 42 — @basthomas
48. MAYBE IT'S NOT JUST ABOUT SPEED AND SCALE 43 — @basthomas
49. PERFORMANCE IS A MINDSET 44 — @basthomas
50. WHERE TO START? 45 — @basthomas
51. @discardableResult mutating func solve() -> Solution<Board> { var boards: [Board] = [] repeat { next() boards.append(self) } while isSolved == false return Solution(steps: boards.map(Solution.Step.init)) } 46 — @basthomas
52. private func adjacentPositions(to position: Position) -> [Position] { var adjacentPositions: [Position] = [] var positions: [Position] { return initialBoard .flatMap { $0 } .map(position(for:)) } /// ??? precondition( adjacentPositions.count <= 4, "Can't have more than four adjacent positions, got \(adjacentPositions)" ) precondition( adjacentPositions.count >= 2, "Must have at least two adjacent positions, got \(adjacentPositions)" ) return adjacentPositions } 47 — @basthomas
53. private func adjacentPositions(to position: Position) -> [Position] { var adjacentPositions: [Position] = [] var positions: [Position] { return initialBoard .flatMap { $0 } .map(position(for:)) } /// ??? precondition( adjacentPositions.count <= 4, "Can't have more than four adjacent positions, got \(adjacentPositions)" ) precondition( adjacentPositions.count >= 2, "Must have at least two adjacent positions, got \(adjacentPositions)" ) return adjacentPositions } 47 — @basthomas
54. private func adjacentPositions(to position: Position) -> [Position] { var adjacentPositions: [Position] = [] var positions: [Position] { return initialBoard .flatMap { $0 } .map(position(for:)) } /// ??? precondition( adjacentPositions.count <= 4, "Can't have more than four adjacent positions, got \(adjacentPositions)" ) precondition( adjacentPositions.count >= 2, "Must have at least two adjacent positions, got \(adjacentPositions)" ) return adjacentPositions } 47 — @basthomas
55. private func adjacentPositions(to position: Position) -> [Position] { var adjacentPositions: [Position] = [] var positions: [Position] { return initialBoard .flatMap { $0 } .map(position(for:)) } /// ??? precondition( adjacentPositions.count <= 4, "Can't have more than four adjacent positions, got \(adjacentPositions)" ) precondition( adjacentPositions.count >= 2, "Must have at least two adjacent positions, got \(adjacentPositions)" ) return adjacentPositions } 47 — @basthomas
56. private func adjacentPositions(to position: Position) -> [Position] { var adjacentPositions: [Position] = [] var positions: [Position] { return initialBoard .flatMap { $0 } .map(position(for:)) } /// ??? precondition( adjacentPositions.count <= 4, "Can't have more than four adjacent positions, got \(adjacentPositions)" ) precondition( adjacentPositions.count >= 2, "Must have at least two adjacent positions, got \(adjacentPositions)" ) return adjacentPositions } 47 — @basthomas
57. for loopingPosition in positions where position != loopingPosition { switch loopingPosition { case Position(row: position.row, column: position.column - 1): fallthrough // above case Position(row: position.row - 1, column: position.column): fallthrough // left case Position(row: position.row + 1, column: position.column): fallthrough // below case Position(row: position.row, column: position.column + 1): precondition(adjacentPositions.contains(loopingPosition) == false) adjacentPositions.append(loopingPosition) // right default: continue // no match } } 48 — @basthomas
58. for loopingPosition in positions where position != loopingPosition { switch loopingPosition { case Position(row: position.row, column: position.column - 1): fallthrough // above case Position(row: position.row - 1, column: position.column): fallthrough // left case Position(row: position.row + 1, column: position.column): fallthrough // below case Position(row: position.row, column: position.column + 1): precondition(adjacentPositions.contains(loopingPosition) == false) adjacentPositions.append(loopingPosition) // right default: continue // no match } } 48 — @basthomas
59. for loopingPosition in positions where position != loopingPosition { switch loopingPosition { case Position(row: position.row, column: position.column - 1): fallthrough // above case Position(row: position.row - 1, column: position.column): fallthrough // left case Position(row: position.row + 1, column: position.column): fallthrough // below case Position(row: position.row, column: position.column + 1): precondition(adjacentPositions.contains(loopingPosition) == false) adjacentPositions.append(loopingPosition) // right default: continue // no match } } 48 — @basthomas
60. for loopingPosition in positions where position != loopingPosition { switch loopingPosition { case Position(row: position.row, column: position.column - 1): fallthrough // above case Position(row: position.row - 1, column: position.column): fallthrough // left case Position(row: position.row + 1, column: position.column): fallthrough // below case Position(row: position.row, column: position.column + 1): precondition(adjacentPositions.contains(loopingPosition) == false) adjacentPositions.append(loopingPosition) // right default: continue // no match } } 48 — @basthomas
61. for loopingPosition in positions where position != loopingPosition { switch loopingPosition { case Position(row: position.row, column: position.column - 1): fallthrough // above case Position(row: position.row - 1, column: position.column): fallthrough // left case Position(row: position.row + 1, column: position.column): fallthrough // below case Position(row: position.row, column: position.column + 1): precondition(adjacentPositions.contains(loopingPosition) == false) adjacentPositions.append(loopingPosition) // right default: continue // no match } } 48 — @basthomas
62. for loopingPosition in positions where position != loopingPosition { switch loopingPosition { case Position(row: position.row, column: position.column - 1): fallthrough // above case Position(row: position.row - 1, column: position.column): fallthrough // left case Position(row: position.row + 1, column: position.column): fallthrough // below case Position(row: position.row, column: position.column + 1): precondition(adjacentPositions.contains(loopingPosition) == false) adjacentPositions.append(loopingPosition) // right default: continue // no match } } 48 — @basthomas
63. mutating func shuffle(moves: Int = 50) { for _ in 1...moves { let adjacentToEmpty = adjacentPositions(to: position(for: .empty)) precondition( adjacentToEmpty.count >= 2, "Should always have at least two positions adjacent to empty" ) // Remove the previously moved tile, so we do not move a tile // back-and-forth. That would be rather pointless. let adjacentWithoutPrevious = adjacentToEmpty .filter { $0 != position(for: _previouslyShuffledTile) } let randomAdjacent = adjacentWithoutPrevious.randomElement()! let randomTile = tile(at: randomAdjacent) move(tile: randomTile) _previouslyShuffledTile = randomTile } } 49 — @basthomas
64. mutating func shuffle(moves: Int = 50) { for _ in 1...moves { let adjacentToEmpty = adjacentPositions(to: position(for: .empty)) precondition( adjacentToEmpty.count >= 2, "Should always have at least two positions adjacent to empty" ) // Remove the previously moved tile, so we do not move a tile // back-and-forth. That would be rather pointless. let adjacentWithoutPrevious = adjacentToEmpty .filter { $0 != position(for: _previouslyShuffledTile) } let randomAdjacent = adjacentWithoutPrevious.randomElement()! let randomTile = tile(at: randomAdjacent) move(tile: randomTile) _previouslyShuffledTile = randomTile } } 49 — @basthomas
65. mutating func shuffle(moves: Int = 50) { for _ in 1...moves { let adjacentToEmpty = adjacentPositions(to: position(for: .empty)) precondition( adjacentToEmpty.count >= 2, "Should always have at least two positions adjacent to empty" ) // Remove the previously moved tile, so we do not move a tile // back-and-forth. That would be rather pointless. let adjacentWithoutPrevious = adjacentToEmpty .filter { $0 != position(for: _previouslyShuffledTile) } let randomAdjacent = adjacentWithoutPrevious.randomElement()! let randomTile = tile(at: randomAdjacent) move(tile: randomTile) _previouslyShuffledTile = randomTile } } 49 — @basthomas
66. mutating func shuffle(moves: Int = 50) { for _ in 1...moves { let adjacentToEmpty = adjacentPositions(to: position(for: .empty)) precondition( adjacentToEmpty.count >= 2, "Should always have at least two positions adjacent to empty" ) // Remove the previously moved tile, so we do not move a tile // back-and-forth. That would be rather pointless. let adjacentWithoutPrevious = adjacentToEmpty .filter { $0 != position(for: _previouslyShuffledTile) } let randomAdjacent = adjacentWithoutPrevious.randomElement()! let randomTile = tile(at: randomAdjacent) move(tile: randomTile) _previouslyShuffledTile = randomTile } } 49 — @basthomas
67. mutating func shuffle(moves: Int = 50) { for _ in 1...moves { let adjacentToEmpty = adjacentPositions(to: position(for: .empty)) precondition( adjacentToEmpty.count >= 2, "Should always have at least two positions adjacent to empty" ) // Remove the previously moved tile, so we do not move a tile // back-and-forth. That would be rather pointless. let adjacentWithoutPrevious = adjacentToEmpty .filter { $0 != position(for: _previouslyShuffledTile) } let randomAdjacent = adjacentWithoutPrevious.randomElement()! let randomTile = tile(at: randomAdjacent) move(tile: randomTile) _previouslyShuffledTile = randomTile } } 49 — @basthomas
68. REWIRING YOUR BRAIN 50 — @basthomas
69. BRANCH... AND BOUND 51 — @basthomas
70. BRANCH... AND BOUND ▸ What are the options? 51 — @basthomas
71. BRANCH... AND BOUND ▸ What are the options? ▸ Is there a best option? 51 — @basthomas
72. BRANCH... AND BOUND ▸ What are the options? ▸ Is there a best option? ▸ Do it again 51 — @basthomas
73. mutating func next() { let currentBoard = self.currentBoard let adjacentToEmpty = adjacentPositions(to: position(for: .empty)) let boardOptions = adjacentToEmpty.map { position -> (board: [[Tile]], moved: Tile, validPositions: Int) in let tileToMove = tile(at: position) move(tile: tileToMove) defer { self.currentBoard = currentBoard } return (self.currentBoard, tileToMove, validPositions) }.filter { $0.moved != _previousNextTile } let amountOfValidPositionsList = boardOptions.map { $0.validPositions } let largestAmountOfValidPositions = amountOfValidPositionsList.max() precondition(largestAmountOfValidPositions != nil, "No maximum valid positions found in \(boardOptions)") let nextBestSteps = amountOfValidPositionsList.filter { $0 == largestAmountOfValidPositions } let bestStepIndex = boardOptions.firstIndex { $0.validPositions == nextBestSteps.first } precondition(bestStepIndex != nil, "Should always have an index for the next best step") let bestOption = boardOptions[bestStepIndex!] self.currentBoard = bestOption.board _previousNextTile = bestOption.moved } 52 — @basthomas
74. let currentBoard = self.currentBoard let adjacentToEmpty = adjacentPositions(to: position(for: .empty)) 53 — @basthomas
75. let boardOptions = adjacentToEmpty.map { position -> (board: [[Tile]], moved: Tile, validPositions: Int) in let tileToMove = tile(at: position) move(tile: tileToMove) defer { self.currentBoard = currentBoard } return (self.currentBoard, tileToMove, validPositions) }.filter { $0.moved != _previousNextTile } 54 — @basthomas
76. let amountOfValidPositionsList = boardOptions.map { $0.validPositions } let largestAmountOfValidPositions = amountOfValidPositionsList.max() precondition( largestAmountOfValidPositions != nil, "No maximum valid positions found in \(boardOptions)" ) 55 — @basthomas
77. let nextBestSteps = amountOfValidPositionsList.filter { $0 == largestAmountOfValidPositions } let bestStepIndex = boardOptions.firstIndex { $0.validPositions == nextBestSteps.first } precondition(bestStepIndex != nil, "Should always have an index for the next best step") let bestOption = boardOptions[bestStepIndex!] self.currentBoard = bestOption.board _previousNextTile = bestOption.moved 56 — @basthomas
78. AN EXAMPLE 57 — @basthomas
79. | 1| 2| 3| 4| | 5|10| 6|11| | 9|14| 8| 7| |13| |15|12| 58 — @basthomas
80. ADJACENT POSITIONS 59 — @basthomas
81. ADJACENT POSITIONS ▸ 13 59 — @basthomas
82. ADJACENT POSITIONS ▸ 13 ▸ 14 59 — @basthomas
83. ADJACENT POSITIONS ▸ 13 ▸ 14 ▸ 15 59 — @basthomas
84. VALID POSITIONS 60 — @basthomas
85. VALID POSITIONS ▸ 13 (right) > 7 60 — @basthomas
86. VALID POSITIONS ▸ 13 (right) > 7 ▸ 14 (down) > 9 60 — @basthomas
87. VALID POSITIONS ▸ 13 (right) > 7 ▸ 14 (down) > 9 ▸ 15 (left) > 7 60 — @basthomas
88. VALID POSITIONS ▸ 13 (right) > 7 ▸ 14 (down) > 9 ▸ 15 (left) > 7 ▸ ... and repeat 60 — @basthomas
89. BE YOUR OWN BEST FRIEND ... AND FAIL EARLY 61 — @basthomas
90. But this will never happen! 62 — @basthomas
91. BREAK UP THE PUZZLE... IN PIECES 63 — @basthomas
92. START SOMEWHERE 64 — @basthomas
93. MAKE YOUR "EDGE" CASES EXPLICIT LET THE COMPILER HELP 65 — @basthomas
94. SOLVING THE 15 PUZZLE IN SWIFT A Look at Algorithms and Speed 66 — @basthomas