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