GridSilhouette.swift (6558B)
1 import Foundation 2 3 /// Encodes a crossword's block layout — its grid "silhouette" — into a compact, 4 /// URL-safe path segment for a share link, and back. The segment lets the link 5 /// worker render a preview of the actual grid (and, later, lets the app paint a 6 /// placeholder the instant a link is tapped) without any CloudKit round-trip. 7 /// 8 /// Wire format: `<tag><size…><payload>` 9 /// - `tag` case selects geometry and symmetry. Lowercase `s`/`f` are square 10 /// grids carrying a single side digit; uppercase `S`/`F` are 11 /// rectangular grids carrying a width digit then a height digit. 12 /// `s`/`S` mean the grid is 180°-rotationally symmetric (only the 13 /// first ⌈N/2⌉ cells are stored, since the rest mirror them); `f`/`F` 14 /// are a full dump of every cell. 15 /// - `size…` each dimension as a single base-36 digit (`f` = 15, `l` = 21), so 16 /// sides are bounded to 2…35. 17 /// - `payload` the cell bits, row-major, MSB-first, `1` = block, as base64url 18 /// without padding. Each character therefore carries six cells. 19 /// 20 /// A symmetric 15×15 lands in ~22 characters (`s` `f` + 20); the full fallback 21 /// for an asymmetric 15×15 is ~40. The 180° mirror partner of cell `k` in a 22 /// `w×h` grid is `n-1-k` regardless of the dimensions, so the symmetric packing 23 /// and the rectangular case share the same reconstruction. See 24 /// `GridSilhouetteTests`. 25 enum GridSilhouette { 26 static let minSide = 2 27 /// A single base-36 size digit tops out at 35. 28 static let maxSide = 35 29 30 struct Grid: Equatable { 31 let width: Int 32 let height: Int 33 /// Row-major, `true` = block. 34 let blocks: [Bool] 35 36 init(width: Int, height: Int, blocks: [Bool]) { 37 self.width = width 38 self.height = height 39 self.blocks = blocks 40 } 41 42 /// Convenience for the common square case. 43 init(side: Int, blocks: [Bool]) { 44 self.init(width: side, height: side, blocks: blocks) 45 } 46 } 47 48 /// Encodes a square grid, or `nil` when the side falls outside 49 /// `minSide...maxSide` or the block count doesn't match. A thin shim over 50 /// `encode(width:height:blocks:)` for the square call sites and tests. 51 static func encode(side: Int, blocks: [Bool]) -> String? { 52 encode(width: side, height: side, blocks: blocks) 53 } 54 55 /// Encodes a grid, or `nil` when either dimension falls outside 56 /// `minSide...maxSide` or `blocks` doesn't hold exactly `width * height` 57 /// cells. A square grid uses the compact lowercase single-digit form; a 58 /// rectangular grid uses the uppercase two-digit form. 59 static func encode(width: Int, height: Int, blocks: [Bool]) -> String? { 60 guard (minSide...maxSide).contains(width), (minSide...maxSide).contains(height), 61 blocks.count == width * height else { 62 return nil 63 } 64 let n = blocks.count 65 let symmetric = (0..<(n / 2)).allSatisfy { blocks[$0] == blocks[n - 1 - $0] } 66 let stored = symmetric ? Array(blocks.prefix((n + 1) / 2)) : blocks 67 let payload = Self.base64URLEncode(Self.packBits(stored)) 68 if width == height { 69 let tag = symmetric ? "s" : "f" 70 return tag + String(width, radix: 36) + payload 71 } 72 let tag = symmetric ? "S" : "F" 73 return tag + String(width, radix: 36) + String(height, radix: 36) + payload 74 } 75 76 /// Reverses `encode`, or `nil` when the segment is malformed. 77 static func decode(_ segment: String) -> Grid? { 78 let chars = Array(segment) 79 guard let tag = chars.first else { return nil } 80 81 let width: Int 82 let height: Int 83 let payload: ArraySlice<Character> 84 switch tag { 85 case "s", "f": 86 guard chars.count >= 2, 87 let side = Int(String(chars[1]), radix: 36), 88 (minSide...maxSide).contains(side) else { return nil } 89 width = side 90 height = side 91 payload = chars[2...] 92 case "S", "F": 93 guard chars.count >= 3, 94 let w = Int(String(chars[1]), radix: 36), (minSide...maxSide).contains(w), 95 let h = Int(String(chars[2]), radix: 36), (minSide...maxSide).contains(h) else { return nil } 96 width = w 97 height = h 98 payload = chars[3...] 99 default: 100 return nil 101 } 102 103 let n = width * height 104 let symmetric = tag == "s" || tag == "S" 105 let storedCount = symmetric ? (n + 1) / 2 : n 106 guard let bytes = Self.base64URLDecode(String(payload)) else { return nil } 107 guard bytes.count == (storedCount + 7) / 8 else { return nil } 108 let bits = Self.unpackBits(bytes, count: storedCount) 109 guard bits.count == storedCount else { return nil } 110 111 var blocks = [Bool](repeating: false, count: n) 112 for k in 0..<n { 113 // The stored half holds cells 0..<⌈N/2⌉; every later cell mirrors 114 // its 180°-rotation partner, which lands inside the stored half. 115 blocks[k] = k < storedCount ? bits[k] : bits[n - 1 - k] 116 } 117 return Grid(width: width, height: height, blocks: blocks) 118 } 119 120 // MARK: - Bit packing 121 122 private static func packBits(_ bits: [Bool]) -> [UInt8] { 123 var bytes = [UInt8](repeating: 0, count: (bits.count + 7) / 8) 124 for (i, bit) in bits.enumerated() where bit { 125 bytes[i / 8] |= UInt8(0x80) >> (i % 8) 126 } 127 return bytes 128 } 129 130 private static func unpackBits(_ bytes: [UInt8], count: Int) -> [Bool] { 131 guard bytes.count * 8 >= count else { return [] } 132 return (0..<count).map { i in 133 bytes[i / 8] & (UInt8(0x80) >> (i % 8)) != 0 134 } 135 } 136 137 // MARK: - base64url 138 139 static func base64URLEncode(_ bytes: [UInt8]) -> String { 140 Data(bytes).base64EncodedString() 141 .replacingOccurrences(of: "+", with: "-") 142 .replacingOccurrences(of: "/", with: "_") 143 .replacingOccurrences(of: "=", with: "") 144 } 145 146 static func base64URLDecode(_ string: String) -> [UInt8]? { 147 var s = string 148 .replacingOccurrences(of: "-", with: "+") 149 .replacingOccurrences(of: "_", with: "/") 150 let remainder = s.count % 4 151 if remainder != 0 { s += String(repeating: "=", count: 4 - remainder) } 152 guard let data = Data(base64Encoded: s) else { return nil } 153 return [UInt8](data) 154 } 155 }