Puzzle.swift (18402B)
1 import Foundation 2 3 /// Normalized in-memory representation of a crossword. Independent of the 4 /// source format so the rest of the app doesn't have to know how it was 5 /// loaded. 6 struct Puzzle: Sendable { 7 enum Direction: Sendable, Equatable { 8 case across 9 case down 10 11 var opposite: Direction { self == .across ? .down : .across } 12 } 13 14 /// How a special cell should be drawn. 15 enum Special: Sendable, Hashable { 16 case circled 17 case shaded 18 } 19 20 let title: String 21 let publisher: String? 22 let author: String? 23 let copyright: String? 24 let date: Date? 25 let width: Int 26 let height: Int 27 let cells: [[Cell]] 28 let acrossClues: [Clue] 29 let downClues: [Clue] 30 /// Cross-reference clue groups, sourced from prose like "See 11-Down" / 31 /// "With X- and Y-Down" — connections the constructor explicitly 32 /// surfaced in the clue text, safe to highlight as a navigation aid. 33 /// Stored as clue identifiers (not cell positions) so `relatedCells` can 34 /// gate on the cursor's reading direction: only when the focus cell's 35 /// current-direction word is itself one of the group's clues. 36 /// Themer/revealer links from `XD.relatives` are intentionally not 37 /// represented here so the UI doesn't reveal trick relationships before 38 /// the solver works them out. 39 let crossReferenceGroups: [Set<ClueRef>] 40 41 /// Maps each clue number to the position of its numbered start cell. 42 /// Built once so callers (`cell(numbered:)`, the per-render 43 /// `relatedCells`, the cross-reference walk) resolve a clue's origin 44 /// by O(1) lookup instead of re-scanning the grid every time. 45 let numberStarts: [Int: GridPosition] 46 47 /// Maps each cell that belongs to a cross-referenced clue to the 48 /// index of its group within `crossReferenceGroups`. Unlike 49 /// `relatedCells`, this is focus-independent: callers mark these 50 /// squares passively (always visible), and the group index lets each 51 /// distinct cross-reference set carry its own visual pattern. A cell 52 /// shared by clues in two groups keeps the first group encountered. 53 /// Built once at init. 54 let cellGroups: [GridPosition: Int] 55 56 struct ClueRef: Hashable, Sendable { 57 let number: Int 58 let direction: Direction 59 } 60 61 struct Cell: Sendable, Hashable { 62 let row: Int 63 let col: Int 64 let isBlock: Bool 65 let special: Special? 66 let number: Int? 67 let solution: String? 68 let acceptedSolutions: Set<String> 69 70 /// Whether this cell's correct state is to be left empty — its solution 71 /// is a literal blank, the "gap" square of a themer like NYT's "THE GAP" 72 /// puzzle, where crossing words read straight through a deliberately 73 /// empty cell. The custom keyboard can't type a space, so a gap is 74 /// solved by entering nothing. 75 var expectsBlank: Bool { 76 guard let solution else { return false } 77 return !solution.isEmpty && solution.allSatisfy(\.isWhitespace) 78 } 79 80 func accepts(_ entry: String) -> Bool { 81 let normalizedEntry = Self.normalizedAnswer(entry) 82 if normalizedEntry.isEmpty { 83 // An empty entry is correct only for a gap cell; every other 84 // cell still needs a fill. 85 return expectsBlank 86 } 87 if let solution, normalizedEntry == Self.normalizedAnswer(solution) { 88 return true 89 } 90 return acceptedSolutions.contains(normalizedEntry) 91 } 92 93 static func normalizedAnswer(_ value: String) -> String { 94 value.precomposedStringWithCanonicalMapping.uppercased() 95 } 96 } 97 98 struct Clue: Sendable, Hashable, Identifiable { 99 let number: Int 100 /// The clue as plain prose, with any `.xd` inline markup stripped. Used 101 /// wherever a clue is treated as text (cross-reference parsing, 102 /// measurement, accessibility); `attributedText` carries the rendered 103 /// form for display. 104 let text: String 105 let attributedText: AttributedString 106 var id: Int { number } 107 } 108 109 enum LoadError: Error { 110 case notFound(String) 111 } 112 113 init(xd: XD) { 114 self.title = xd.title ?? "Untitled" 115 self.publisher = xd.publisher 116 self.author = xd.author 117 self.copyright = xd.copyright 118 self.date = xd.date 119 self.width = xd.width 120 self.height = xd.height 121 122 // Clue numbering is computed from grid topology rather than carried 123 // in the source, since .xd has no per-cell number field. A cell is 124 // numbered if it begins an across or down word — i.e. its preceding 125 // neighbour in that direction is a block (or the edge) and its 126 // following neighbour is open. 127 var cells: [[Cell]] = [] 128 cells.reserveCapacity(xd.height) 129 var counter = 1 130 for r in 0..<xd.height { 131 var rowCells: [Cell] = [] 132 rowCells.reserveCapacity(xd.width) 133 for c in 0..<xd.width { 134 switch xd.cells[r][c] { 135 case .block: 136 rowCells.append(Cell(row: r, col: c, isBlock: true, special: nil, number: nil, solution: nil, acceptedSolutions: [])) 137 case .open(let solution, let acceptedSolutions, let special): 138 let leftBlock = c == 0 || Self.isBlock(xd.cells, r, c - 1) 139 let rightOpen = c + 1 < xd.width && !Self.isBlock(xd.cells, r, c + 1) 140 let topBlock = r == 0 || Self.isBlock(xd.cells, r - 1, c) 141 let bottomOpen = r + 1 < xd.height && !Self.isBlock(xd.cells, r + 1, c) 142 let startsWord = (leftBlock && rightOpen) || (topBlock && bottomOpen) 143 let number: Int? 144 if startsWord { 145 number = counter 146 counter += 1 147 } else { 148 number = nil 149 } 150 let normalizedAccepted = Set(acceptedSolutions.map { Cell.normalizedAnswer($0) }) 151 rowCells.append(Cell(row: r, col: c, isBlock: false, special: special, number: number, solution: solution, acceptedSolutions: normalizedAccepted)) 152 } 153 } 154 cells.append(rowCells) 155 } 156 self.cells = cells 157 let acrossClues = xd.acrossClues.map { 158 Clue(number: $0.number, text: XDMarkup.stripped($0.text), attributedText: XDMarkup.attributed($0.text)) 159 } 160 let downClues = xd.downClues.map { 161 Clue(number: $0.number, text: XDMarkup.stripped($0.text), attributedText: XDMarkup.attributed($0.text)) 162 } 163 self.acrossClues = acrossClues 164 self.downClues = downClues 165 let groups = Self.buildCrossReferenceGroups( 166 across: acrossClues, 167 down: downClues 168 ) 169 self.crossReferenceGroups = groups 170 let numberStarts = Self.buildNumberStarts(cells) 171 self.numberStarts = numberStarts 172 self.cellGroups = Self.buildCellGroups( 173 groups: groups, 174 starts: numberStarts, 175 cells: cells 176 ) 177 } 178 179 /// Indexes every numbered start cell by its clue number. There is 180 /// exactly one numbered cell per number, so a plain dictionary is a 181 /// faithful, scan-free replacement for `cell(numbered:)`. 182 private static func buildNumberStarts( 183 _ cells: [[Cell]] 184 ) -> [Int: GridPosition] { 185 var starts: [Int: GridPosition] = [:] 186 for row in cells { 187 for cell in row { 188 if let number = cell.number { 189 starts[number] = GridPosition(row: cell.row, col: cell.col) 190 } 191 } 192 } 193 return starts 194 } 195 196 /// Walks the run of cells for a clue, starting at `start` and 197 /// advancing in `direction` until a block or the grid edge. The 198 /// single source of truth for "which cells does this clue occupy", 199 /// shared by `relatedCells` and the cross-reference index so the two 200 /// can't drift apart. 201 private static func runCells( 202 from start: GridPosition, 203 direction: Direction, 204 cells: [[Cell]] 205 ) -> [GridPosition] { 206 let height = cells.count 207 let width = cells.first?.count ?? 0 208 var positions: [GridPosition] = [] 209 var r = start.row 210 var c = start.col 211 while r >= 0, r < height, c >= 0, c < width, !cells[r][c].isBlock { 212 positions.append(GridPosition(row: r, col: c)) 213 switch direction { 214 case .across: c += 1 215 case .down: r += 1 216 } 217 } 218 return positions 219 } 220 221 /// Walks every clue in every cross-reference group from its numbered 222 /// start cell, tagging each visited cell with its group's index. Has 223 /// no focus gate, so the result is stable for the whole puzzle. Group 224 /// order follows `crossReferenceGroups`; the first group to claim a 225 /// shared cell wins, keeping the mapping deterministic. 226 private static func buildCellGroups( 227 groups: [Set<ClueRef>], 228 starts: [Int: GridPosition], 229 cells: [[Cell]] 230 ) -> [GridPosition: Int] { 231 guard !groups.isEmpty else { return [:] } 232 var result: [GridPosition: Int] = [:] 233 for (index, group) in groups.enumerated() { 234 for clue in group { 235 guard let start = starts[clue.number] else { continue } 236 for pos in runCells( 237 from: start, 238 direction: clue.direction, 239 cells: cells 240 ) where result[pos] == nil { 241 result[pos] = index 242 } 243 } 244 } 245 return result 246 } 247 248 /// Derives cross-reference groups from the clue text itself. NYT-style 249 /// prose like `See 11-Down` or `With 31- and 43-Down, …` is the only 250 /// signal we trust — the constructor explicitly pointed the solver at 251 /// these connections, so highlighting them isn't a spoiler. Groups are 252 /// connected components: any clues mentioned together (transitively) 253 /// land in the same set as `(number, direction)` identifiers. 254 private static func buildCrossReferenceGroups( 255 across: [Clue], 256 down: [Clue] 257 ) -> [Set<ClueRef>] { 258 struct Entry { let ref: ClueRef; let text: String } 259 var entries: [Entry] = [] 260 var indexByRef: [ClueRef: Int] = [:] 261 for clue in across { 262 let ref = ClueRef(number: clue.number, direction: .across) 263 indexByRef[ref] = entries.count 264 entries.append(Entry(ref: ref, text: clue.text)) 265 } 266 for clue in down { 267 let ref = ClueRef(number: clue.number, direction: .down) 268 indexByRef[ref] = entries.count 269 entries.append(Entry(ref: ref, text: clue.text)) 270 } 271 272 var adjacency: [Int: Set<Int>] = [:] 273 for (i, entry) in entries.enumerated() { 274 guard let refs = parseCrossReferences(in: entry.text) else { continue } 275 for ref in refs { 276 guard let j = indexByRef[ref], j != i else { continue } 277 adjacency[i, default: []].insert(j) 278 adjacency[j, default: []].insert(i) 279 } 280 } 281 282 var visited: Set<Int> = [] 283 var groups: [Set<ClueRef>] = [] 284 for start in adjacency.keys.sorted() { 285 guard !visited.contains(start) else { continue } 286 var component: Set<ClueRef> = [] 287 var stack = [start] 288 while let node = stack.popLast() { 289 guard visited.insert(node).inserted else { continue } 290 component.insert(entries[node].ref) 291 for n in adjacency[node, default: []] where !visited.contains(n) { 292 stack.append(n) 293 } 294 } 295 if component.count >= 2 { groups.append(component) } 296 } 297 return groups 298 } 299 300 /// Pulls `(number, direction)` pairs out of `See …-Down`, 301 /// `With X- and Y-Down`, revealer-style `X-, Y- or Z-Across`, 302 /// and mixed-direction prose like `X-Across and Y-Down`. 303 /// A trailing `Across`/`Down` applies to every number in that list 304 /// segment, matching NYT's convention. 305 private static func parseCrossReferences(in text: String) -> [ClueRef]? { 306 var refs: [ClueRef] = [] 307 var seen: Set<ClueRef> = [] 308 309 func append(_ newRefs: [ClueRef]?) { 310 guard let newRefs else { return } 311 for ref in newRefs where seen.insert(ref).inserted { 312 refs.append(ref) 313 } 314 } 315 316 let listPattern = /([\d\s,\-&\/]+?(?:(?:and|or)\s+[\d\s,\-&\/]+?)?)(Across|Down)\b/ 317 for match in text.matches(of: listPattern) { 318 guard String(match.1).contains(/\d+\s*-/) else { continue } 319 append(clueRefs(numbersText: String(match.1), directionText: String(match.2))) 320 } 321 if !refs.isEmpty { 322 return refs 323 } 324 325 let anchoredPattern = /\b(?:See|With)\s+([\d\s,\-&\/]+?(?:(?:and|or)\s+[\d\s,\-&\/]+?)?)(Across|Down)\b/ 326 if let match = text.firstMatch(of: anchoredPattern) { 327 append(clueRefs(numbersText: String(match.1), directionText: String(match.2))) 328 } 329 return refs.isEmpty ? nil : refs 330 } 331 332 private static func clueRefs(numbersText: String, directionText: String) -> [ClueRef]? { 333 let direction: Direction = directionText == "Across" ? .across : .down 334 let numbers = numbersText.matches(of: /\d+/).compactMap { Int($0.0) } 335 guard !numbers.isEmpty else { return nil } 336 return numbers.map { ClueRef(number: $0, direction: direction) } 337 } 338 339 private static func findCell(in cells: [[Cell]], numbered number: Int) -> Cell? { 340 for row in cells { 341 for cell in row where cell.number == number { 342 return cell 343 } 344 } 345 return nil 346 } 347 348 /// Returns the cell labelled with the given clue number, if any. 349 /// Resolved via the prebuilt `numberStarts` index, so this is an O(1) 350 /// lookup rather than a grid scan. 351 func cell(numbered number: Int) -> Cell? { 352 guard let pos = numberStarts[number] else { return nil } 353 return cells[pos.row][pos.col] 354 } 355 356 /// Returns every open cell that belongs to the word containing 357 /// `(row, col)` in the given direction. Empty if the starting cell is a 358 /// block, off-grid, or has no neighbour in that direction (a "word" of 359 /// length 1 isn't really a word). 360 func wordCells(atRow row: Int, col: Int, direction: Direction) -> [Cell] { 361 guard row >= 0, row < height, col >= 0, col < width else { return [] } 362 guard !cells[row][col].isBlock else { return [] } 363 let (dr, dc): (Int, Int) = direction == .across ? (0, 1) : (1, 0) 364 var startRow = row 365 var startCol = col 366 while startRow - dr >= 0, startRow - dr < height, 367 startCol - dc >= 0, startCol - dc < width, 368 !cells[startRow - dr][startCol - dc].isBlock { 369 startRow -= dr 370 startCol -= dc 371 } 372 var result: [Cell] = [] 373 var r = startRow 374 var c = startCol 375 while r >= 0, r < height, c >= 0, c < width, !cells[r][c].isBlock { 376 result.append(cells[r][c]) 377 r += dr 378 c += dc 379 } 380 return result.count > 1 ? result : [] 381 } 382 383 /// Returns the clue for the word containing `(row, col)` in the given 384 /// direction, or `nil` if the cell isn't part of a numbered word. 385 func clue(atRow row: Int, col: Int, direction: Direction) -> Clue? { 386 guard let number = wordCells(atRow: row, col: col, direction: direction).first?.number else { 387 return nil 388 } 389 let clues = direction == .across ? acrossClues : downClues 390 return clues.first { $0.number == number } 391 } 392 393 /// Returns the canonical cursor track for a focused cell: the start cell 394 /// of the answer slot in `direction`, paired with that direction. This is 395 /// the low-frequency collaborative presence value persisted to CloudKit; 396 /// the exact focused square remains local cursor-reticle state. 397 func cursorTrack(atRow row: Int, col: Int, direction: Direction) -> PlayerSelection? { 398 guard let start = wordCells(atRow: row, col: col, direction: direction).first else { 399 return nil 400 } 401 return PlayerSelection(row: start.row, col: start.col, direction: direction) 402 } 403 404 /// Returns the cells of every clue cross-referenced from the focus 405 /// word. Gated on direction: only fires when the focus cell's word in 406 /// the *current* direction is itself one of the cross-referenced 407 /// clues. Reading the same cell in the opposite direction (where it 408 /// belongs to a different word) returns nothing. 409 func relatedCells(atRow row: Int, col: Int, direction: Direction) -> Set<GridPosition> { 410 let focusWord = wordCells(atRow: row, col: col, direction: direction) 411 guard let start = focusWord.first, let number = start.number else { return [] } 412 let focusClue = ClueRef(number: number, direction: direction) 413 var related: Set<GridPosition> = [] 414 for group in crossReferenceGroups where group.contains(focusClue) { 415 for clue in group where clue != focusClue { 416 guard let start = numberStarts[clue.number] else { continue } 417 related.formUnion(Self.runCells( 418 from: start, 419 direction: clue.direction, 420 cells: cells 421 )) 422 } 423 } 424 return related 425 } 426 427 private static func isBlock(_ cells: [[XD.Cell]], _ row: Int, _ col: Int) -> Bool { 428 if case .block = cells[row][col] { return true } 429 return false 430 } 431 432 static func load(resource: String) throws -> Puzzle { 433 guard let url = Bundle.main.url(forResource: resource, withExtension: "xd") else { 434 throw LoadError.notFound("\(resource).xd") 435 } 436 let source = try String(contentsOf: url, encoding: .utf8) 437 let xd = try XD.parse(source) 438 return Puzzle(xd: xd) 439 } 440 }