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