GridSilhouette.swift (6487B)
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 let bits = Self.unpackBits(bytes, count: storedCount) 108 guard bits.count == storedCount else { return nil } 109 110 var blocks = [Bool](repeating: false, count: n) 111 for k in 0..<n { 112 // The stored half holds cells 0..<⌈N/2⌉; every later cell mirrors 113 // its 180°-rotation partner, which lands inside the stored half. 114 blocks[k] = k < storedCount ? bits[k] : bits[n - 1 - k] 115 } 116 return Grid(width: width, height: height, blocks: blocks) 117 } 118 119 // MARK: - Bit packing 120 121 private static func packBits(_ bits: [Bool]) -> [UInt8] { 122 var bytes = [UInt8](repeating: 0, count: (bits.count + 7) / 8) 123 for (i, bit) in bits.enumerated() where bit { 124 bytes[i / 8] |= UInt8(0x80) >> (i % 8) 125 } 126 return bytes 127 } 128 129 private static func unpackBits(_ bytes: [UInt8], count: Int) -> [Bool] { 130 guard bytes.count * 8 >= count else { return [] } 131 return (0..<count).map { i in 132 bytes[i / 8] & (UInt8(0x80) >> (i % 8)) != 0 133 } 134 } 135 136 // MARK: - base64url 137 138 static func base64URLEncode(_ bytes: [UInt8]) -> String { 139 Data(bytes).base64EncodedString() 140 .replacingOccurrences(of: "+", with: "-") 141 .replacingOccurrences(of: "/", with: "_") 142 .replacingOccurrences(of: "=", with: "") 143 } 144 145 static func base64URLDecode(_ string: String) -> [UInt8]? { 146 var s = string 147 .replacingOccurrences(of: "-", with: "+") 148 .replacingOccurrences(of: "_", with: "/") 149 let remainder = s.count % 4 150 if remainder != 0 { s += String(repeating: "=", count: 4 - remainder) } 151 guard let data = Data(base64Encoded: s) else { return nil } 152 return [UInt8](data) 153 } 154 }