XD.swift (39662B)
1 import Foundation 2 3 /// Minimal `.xd` decoder. See https://github.com/century-arcade/xd for the 4 /// full specification. Supports just enough of the format to parse our 5 /// bundled puzzles: metadata, grid (with rebus), and across/down clues. 6 struct XD: Sendable { 7 static let currentCmVersion = 7 8 9 let title: String? 10 let publisher: String? 11 let author: String? 12 let copyright: String? 13 let date: Date? 14 let cmVersion: Int 15 let width: Int 16 let height: Int 17 let cells: [[Cell]] 18 let acrossClues: [Clue] 19 let downClues: [Clue] 20 let relatives: [[ClueRef]] 21 22 /// A single clue identified by its number and direction. Used to describe 23 /// groups of mutually-related clues (a theme's revealer plus the answers 24 /// it references, or a simple "See 14-Across" pair). 25 struct ClueRef: Sendable, Hashable { 26 let number: Int 27 let direction: Puzzle.Direction 28 } 29 30 /// A single grid cell as it appears in the .xd source. Open cells carry 31 /// an optional solution string which may be 1+ characters long once any 32 /// `Rebus:` mapping has been applied, plus an optional per-cell special 33 /// marker. 34 enum Cell: Sendable, Equatable { 35 case block 36 case open(solution: String?, acceptedSolutions: Set<String>, special: Puzzle.Special?) 37 } 38 39 struct Clue: Sendable, Equatable { 40 let number: Int 41 let text: String 42 let answer: String? 43 /// Alternative full-word answers from a slash-separated `~` field 44 /// (`~ CIGAR / PENIS`): the first reading becomes `answer`, the rest 45 /// are recorded here as Schrödinger alternatives. 46 let alternativeAnswers: [String] 47 let metadata: [String: [String]] 48 49 var acceptedAnswers: [String] { 50 alternativeAnswers + metadata["Accept", default: []].flatMap(Self.parseEscapedTokens) 51 } 52 53 private static func parseEscapedTokens(_ source: String) -> [String] { 54 var tokens: [String] = [] 55 var current = "" 56 var escaping = false 57 58 for ch in source { 59 if escaping { 60 current.append(ch) 61 escaping = false 62 } else if ch == "\\" { 63 escaping = true 64 } else if ch.isWhitespace { 65 if !current.isEmpty { 66 tokens.append(current) 67 current = "" 68 } 69 } else { 70 current.append(ch) 71 } 72 } 73 74 if escaping { 75 current.append("\\") 76 } 77 if !current.isEmpty { 78 tokens.append(current) 79 } 80 return tokens 81 } 82 } 83 84 enum ParseError: Error, CustomStringConvertible { 85 case missingGrid 86 case missingClues 87 case raggedGrid 88 case malformedClue(String) 89 case unknownGridCharacter(Character) 90 case clueAnswerMismatch(String) 91 case ambiguousClueAnswer(String) 92 case missingInferredSolution(row: Int, col: Int) 93 94 var description: String { 95 switch self { 96 case .missingGrid: 97 return ".xd source has no grid section" 98 case .missingClues: 99 return ".xd source has no clues section" 100 case .raggedGrid: 101 return ".xd grid rows have inconsistent widths" 102 case .malformedClue(let line): 103 return "malformed .xd clue: \(line)" 104 case .unknownGridCharacter(let ch): 105 return "unknown .xd grid character: \(ch)" 106 case .clueAnswerMismatch(let clue): 107 return ".xd clue answer does not match grid: \(clue)" 108 case .ambiguousClueAnswer(let clue): 109 return ".xd clue answer cannot be unambiguously projected onto grid: \(clue)" 110 case .missingInferredSolution(let row, let col): 111 return ".xd grid cell at row \(row + 1), column \(col + 1) has no inferred solution" 112 } 113 } 114 115 /// A non-technical sentence fragment for the user-facing alert, phrased 116 /// to follow "The puzzle for {date} …". The specifics that matter for a 117 /// bug report — the offending character, the malformed clue line, the 118 /// grid coordinates — stay out of this and ride in `description` to the 119 /// diagnostic log instead. 120 var userFacingReason: String { 121 switch self { 122 case .missingGrid: 123 return "is missing its grid" 124 case .missingClues: 125 return "is missing its clues" 126 case .raggedGrid: 127 return "has a grid Crossmate couldn't read" 128 case .malformedClue: 129 return "has a clue Crossmate couldn't read" 130 case .unknownGridCharacter: 131 return "contains a character Crossmate doesn't support" 132 case .clueAnswerMismatch: 133 return "has an answer that doesn't match its grid" 134 case .ambiguousClueAnswer: 135 return "has an answer Crossmate couldn't place in its grid" 136 case .missingInferredSolution: 137 return "has a square Crossmate couldn't solve" 138 } 139 } 140 } 141 142 static func parse(_ source: String) throws -> XD { 143 let sections = splitIntoSections(source) 144 guard sections.count >= 2 else { throw ParseError.missingGrid } 145 guard sections.count >= 3 else { throw ParseError.missingClues } 146 147 let metadata = parseMetadata(sections[0]) 148 let cmVersion = parseCmVersionHeader(metadata.first("CmVer")) 149 let rebus = parseRebusHeader(metadata.first("Rebus")) 150 let standardSpecial = parseStandardSpecialHeader(metadata.first("Special")) 151 let relatives = parseRelativesHeader(metadata.first("Relatives")) 152 let (rawCells, width, height) = try parseGrid( 153 sections[1], 154 rebus: rebus, 155 standardSpecial: standardSpecial, 156 specialsHeader: metadata.first("Specials") 157 ) 158 let (across, down) = try parseClues(sections[2]) 159 let solvedCells = try applyClueAnswers(cells: rawCells, across: across, down: down) 160 let cells = applyAcceptedAnswers(cells: solvedCells, across: across, down: down) 161 162 return XD( 163 title: metadata.first("Title"), 164 publisher: metadata.first("Publisher"), 165 author: metadata.first("Author"), 166 copyright: metadata.first("Copyright"), 167 date: parseDateHeader(metadata.first("Date")), 168 cmVersion: cmVersion, 169 width: width, 170 height: height, 171 cells: cells, 172 acrossClues: across, 173 downClues: down, 174 relatives: relatives 175 ) 176 } 177 178 // MARK: - Sections 179 180 /// Splits the source into top-level sections. Per the .xd spec, sections 181 /// are delimited either by runs of two or more blank lines, or by 182 /// `## SectionName` header lines. We accept both: blank-line runs end the 183 /// current section, and a `##` line also ends the current section (the 184 /// header line itself is consumed and discarded — section identity comes 185 /// from implicit order). 186 private static func splitIntoSections(_ source: String) -> [[String]] { 187 let lines = source 188 .split(separator: "\n", omittingEmptySubsequences: false) 189 .map(String.init) 190 191 var sections: [[String]] = [] 192 var current: [String] = [] 193 var blankRun = 0 194 195 func flush() { 196 while current.last?.trimmingCharacters(in: .whitespaces).isEmpty == true { 197 current.removeLast() 198 } 199 while current.first?.trimmingCharacters(in: .whitespaces).isEmpty == true { 200 current.removeFirst() 201 } 202 if !current.isEmpty { 203 sections.append(current) 204 } 205 current = [] 206 } 207 208 for rawLine in lines { 209 let line = rawLine.trimmingCharacters(in: CharacterSet(charactersIn: "\r")) 210 let trimmed = line.trimmingCharacters(in: .whitespaces) 211 212 if trimmed.hasPrefix("## ") || trimmed == "##" { 213 flush() 214 blankRun = 0 215 continue 216 } 217 218 if trimmed.isEmpty { 219 blankRun += 1 220 if blankRun >= 2 { 221 flush() 222 } 223 continue 224 } 225 226 blankRun = 0 227 current.append(line) 228 } 229 flush() 230 return sections 231 } 232 233 // MARK: - Metadata 234 235 private struct Metadata { 236 var entries: [String: [String]] = [:] 237 238 func first(_ key: String) -> String? { 239 entries[key]?.first 240 } 241 242 func values(for key: String) -> [String] { 243 entries[key, default: []] 244 } 245 } 246 247 /// Reads a single metadata header value (e.g. `Date`, `Title`) from raw 248 /// `.xd` source without a full parse. Lets a caller name the puzzle that 249 /// failed to parse — the metadata section is independent of the grid/clue 250 /// sections that the parser rejects. 251 static func metadataValue(_ key: String, in source: String) -> String? { 252 guard let header = splitIntoSections(source).first else { return nil } 253 return parseMetadata(header).first(key) 254 } 255 256 private static func parseMetadata(_ lines: [String]) -> Metadata { 257 var metadata = Metadata() 258 for line in lines { 259 guard let colon = line.firstIndex(of: ":") else { continue } 260 let key = line[..<colon].trimmingCharacters(in: .whitespaces) 261 let value = line[line.index(after: colon)...].trimmingCharacters(in: .whitespaces) 262 if !key.isEmpty { 263 metadata.entries[key, default: []].append(value) 264 } 265 } 266 return metadata 267 } 268 269 /// Parses a `Rebus:` header value such as `1=ONE 2=TWO 3=THREE` into a 270 /// map from grid placeholder character to its expanded solution string. 271 private static func parseRebusHeader(_ value: String?) -> [Character: String] { 272 guard let value, !value.isEmpty else { return [:] } 273 var map: [Character: String] = [:] 274 for entry in value.split(whereSeparator: { $0.isWhitespace }) { 275 guard let equals = entry.firstIndex(of: "=") else { continue } 276 let key = entry[..<equals] 277 let val = entry[entry.index(after: equals)...] 278 guard key.count == 1, let keyChar = key.first, !val.isEmpty else { continue } 279 map[keyChar] = unescapeRebusValue(val) 280 } 281 return map 282 } 283 284 /// Reverses `NYTToXDConverter.escapeRebusValue`. A backslash introduces an 285 /// escape: `\\` is a literal backslash, and `\name` is a named escape whose 286 /// name is the following run of letters (currently just `\space` → a space, 287 /// which lets a gap cell's blank fill survive the whitespace-split header). 288 /// An unrecognised escape is preserved verbatim so an older parser never 289 /// silently drops a value a newer writer produced. 290 private static func unescapeRebusValue(_ value: Substring) -> String { 291 guard value.contains("\\") else { return String(value) } 292 var out = "" 293 var i = value.startIndex 294 while i < value.endIndex { 295 guard value[i] == "\\" else { 296 out.append(value[i]) 297 i = value.index(after: i) 298 continue 299 } 300 let next = value.index(after: i) 301 guard next < value.endIndex else { out.append("\\"); break } 302 if value[next] == "\\" { 303 out.append("\\") 304 i = value.index(after: next) 305 continue 306 } 307 var j = next 308 while j < value.endIndex, value[j].isLetter { j = value.index(after: j) } 309 let name = value[next..<j] 310 switch name { 311 case "space": out.append(" ") 312 default: out.append("\\"); out.append(contentsOf: name) 313 } 314 i = j 315 } 316 return out 317 } 318 319 /// Parses a `Date:` header value as strict ISO `YYYY-MM-DD`. Returns 320 /// `nil` if the value is missing, empty, or in any other format. 321 private static func parseDateHeader(_ value: String?) -> Date? { 322 guard let value else { return nil } 323 let trimmed = value.trimmingCharacters(in: .whitespaces) 324 guard let match = trimmed.firstMatch(of: /^(\d{4})-(\d{2})-(\d{2})$/), 325 let year = Int(match.1), 326 let month = Int(match.2), 327 let day = Int(match.3) 328 else { return nil } 329 // Pin to America/New_York: puzzle dates are publication dates in NYT's 330 // timezone, and downstream fetchers (NYTPuzzleFetcher) format the Date 331 // back to a YYYY-MM-DD string in that zone. Without an explicit zone 332 // the system default fires here, which on a device east of NY yields a 333 // Date that formats back to the previous day — wrong puzzle. 334 var calendar = Calendar(identifier: .gregorian) 335 calendar.timeZone = TimeZone(identifier: "America/New_York") ?? .gmt 336 var comps = DateComponents() 337 comps.calendar = calendar 338 comps.timeZone = calendar.timeZone 339 comps.year = year 340 comps.month = month 341 comps.day = day 342 return calendar.date(from: comps) 343 } 344 345 /// Parses a Crossmate `CmVer:` header. Missing versions are version 1 so 346 /// older local fixtures remain identifiable as stale content. 347 private static func parseCmVersionHeader(_ value: String?) -> Int { 348 guard let value else { return 1 } 349 let trimmed = value.trimmingCharacters(in: .whitespaces) 350 guard let version = Int(trimmed), version >= 1 else { return 1 } 351 return version 352 } 353 354 /// Parses a `Relatives:` header value into groups of cross-referenced 355 /// clues. Groups are separated by `;`, tokens within a group by `,`, and 356 /// each token is `{number}{A|D}` (e.g. `17A`, `57A`). This is a Crossmate 357 /// extension to `.xd`; unknown/invalid tokens are silently dropped. 358 /// Single-token groups are allowed so formatted NYT clues can mark their 359 /// own answer cells as thematic. 360 private static func parseRelativesHeader(_ value: String?) -> [[ClueRef]] { 361 guard let value, !value.isEmpty else { return [] } 362 var groups: [[ClueRef]] = [] 363 for groupSlice in value.split(separator: ";") { 364 var refs: [ClueRef] = [] 365 for tokenSlice in groupSlice.split(separator: ",") { 366 let token = tokenSlice.trimmingCharacters(in: .whitespaces) 367 guard let last = token.last else { continue } 368 let direction: Puzzle.Direction 369 switch last { 370 case "A", "a": direction = .across 371 case "D", "d": direction = .down 372 default: continue 373 } 374 guard let number = Int(token.dropLast()), number > 0 else { continue } 375 refs.append(ClueRef(number: number, direction: direction)) 376 } 377 if !refs.isEmpty { groups.append(refs) } 378 } 379 return groups 380 } 381 382 private static func parseSpecialsHeader(_ value: String?) -> [Character: Puzzle.Special] { 383 guard let value, !value.isEmpty else { return [:] } 384 var specials: [Character: Puzzle.Special] = [:] 385 for assignment in value.split(whereSeparator: { $0.isWhitespace }) { 386 guard let equals = assignment.firstIndex(of: "=") else { continue } 387 let symbolPart = assignment[..<equals] 388 let kindPart = assignment[assignment.index(after: equals)...] 389 guard symbolPart.count == 1, let symbol = symbolPart.first else { continue } 390 let kind: Puzzle.Special 391 switch kindPart.lowercased() { 392 case "circle", "circled": kind = .circled 393 case "shaded": kind = .shaded 394 default: continue 395 } 396 specials[symbol] = kind 397 } 398 return specials 399 } 400 401 private static func parseStandardSpecialHeader(_ value: String?) -> Puzzle.Special? { 402 guard let value else { return nil } 403 switch value.trimmingCharacters(in: .whitespaces).lowercased() { 404 case "circle", "circled": return .circled 405 case "shaded": return .shaded 406 default: return nil 407 } 408 } 409 410 // MARK: - Grid 411 412 private static func parseGrid( 413 _ lines: [String], 414 rebus: [Character: String], 415 standardSpecial: Puzzle.Special?, 416 specialsHeader: String? 417 ) throws -> (cells: [[Cell]], width: Int, height: Int) { 418 var gridLines: [String] = [] 419 var width: Int? = nil 420 421 for line in lines { 422 let trimmed = line.trimmingCharacters(in: .whitespaces) 423 if trimmed.isEmpty { continue } 424 425 if let w = width, trimmed.count != w { 426 throw ParseError.raggedGrid 427 } 428 width = trimmed.count 429 gridLines.append(trimmed) 430 } 431 432 guard let w = width, !gridLines.isEmpty else { throw ParseError.missingGrid } 433 434 let specialSymbols = parseSpecialsHeader(specialsHeader) 435 var rows: [[Cell]] = [] 436 for line in gridLines { 437 var row: [Cell] = [] 438 for ch in line { 439 row.append(try gridCell( 440 for: ch, 441 rebus: rebus, 442 standardSpecial: standardSpecial, 443 specialSymbols: specialSymbols 444 )) 445 } 446 rows.append(row) 447 } 448 449 return (rows, w, rows.count) 450 } 451 452 private static func gridCell( 453 for ch: Character, 454 rebus: [Character: String], 455 standardSpecial: Puzzle.Special?, 456 specialSymbols: [Character: Puzzle.Special] 457 ) throws -> Cell { 458 // Blocks: '#' is a normal block; '_' marks a non-existing cell on the 459 // edge of an irregularly-shaped grid. Both render as non-playable. 460 if ch == "#" || ch == "_" { 461 return .block 462 } 463 if let special = specialSymbols[ch] { 464 return .open(solution: nil, acceptedSolutions: [], special: special) 465 } 466 // '.' is an open cell with no known solution. 467 if ch == "." { 468 return .open(solution: nil, acceptedSolutions: [], special: nil) 469 } 470 let lowercaseSpecial = ch.isLetter && ch.isLowercase ? standardSpecial : nil 471 if let expansion = rebus[ch] { 472 return .open(solution: expansion.uppercased(), acceptedSolutions: [], special: lowercaseSpecial) 473 } 474 if ch.isLetter { 475 return .open(solution: String(ch).uppercased(), acceptedSolutions: [], special: lowercaseSpecial) 476 } 477 throw ParseError.unknownGridCharacter(ch) 478 } 479 480 // MARK: - Clues 481 482 private static func parseClues( 483 _ lines: [String] 484 ) throws -> (across: [Clue], down: [Clue]) { 485 struct ClueKey: Hashable { 486 let number: Int 487 let direction: Character 488 } 489 490 var clueTexts: [ClueKey: String] = [:] 491 var clueAnswers: [ClueKey: String] = [:] 492 var clueAlternatives: [ClueKey: [String]] = [:] 493 var clueOrder: [ClueKey] = [] 494 var metadataByClue: [ClueKey: [String: [String]]] = [:] 495 496 for rawLine in lines { 497 let line = rawLine.trimmingCharacters(in: .whitespaces) 498 if line.isEmpty { continue } 499 500 guard let leading = line.first, leading == "A" || leading == "D" else { 501 throw ParseError.malformedClue(line) 502 } 503 504 if let match = line.firstMatch(of: /^([AD])(\d+)\s+\^([^:]+):\s*(.*)$/) { 505 guard let number = Int(match.2) else { throw ParseError.malformedClue(line) } 506 let key = ClueKey(number: number, direction: Character(String(match.1))) 507 let metadataKey = String(match.3).trimmingCharacters(in: .whitespaces) 508 guard !metadataKey.isEmpty else { throw ParseError.malformedClue(line) } 509 metadataByClue[key, default: [:]][metadataKey, default: []].append(String(match.4)) 510 continue 511 } 512 513 guard let dot = line.firstIndex(of: ".") else { 514 throw ParseError.malformedClue(line) 515 } 516 517 let numberSlice = line[line.index(after: line.startIndex)..<dot] 518 guard let number = Int(numberSlice) else { 519 throw ParseError.malformedClue(line) 520 } 521 let key = ClueKey(number: number, direction: leading) 522 523 var afterDot = line[line.index(after: dot)...] 524 .trimmingCharacters(in: .whitespaces) 525 526 if let tilde = afterDot.range(of: " ~ ", options: .backwards) { 527 // A slash-separated answer field (`~ CIGAR / PENIS`) declares a 528 // Schrödinger clue: the first reading is canonical, the rest are 529 // accepted alternatives. A plain field stays a single answer. 530 let readings = afterDot[tilde.upperBound...] 531 .components(separatedBy: " / ") 532 .map { $0.trimmingCharacters(in: .whitespaces) } 533 .filter { !$0.isEmpty } 534 if let canonical = readings.first { 535 clueAnswers[key] = canonical 536 if readings.count > 1 { 537 clueAlternatives[key] = Array(readings.dropFirst()) 538 } 539 } 540 afterDot = String(afterDot[..<tilde.lowerBound]) 541 .trimmingCharacters(in: .whitespaces) 542 } 543 544 if clueTexts[key] == nil { 545 clueOrder.append(key) 546 } 547 clueTexts[key] = afterDot 548 } 549 550 var across: [Clue] = [] 551 var down: [Clue] = [] 552 for key in clueOrder { 553 let clue = Clue( 554 number: key.number, 555 text: clueTexts[key] ?? "", 556 answer: clueAnswers[key], 557 alternativeAnswers: clueAlternatives[key] ?? [], 558 metadata: metadataByClue[key] ?? [:] 559 ) 560 if key.direction == "A" { 561 across.append(clue) 562 } else { 563 down.append(clue) 564 } 565 } 566 return (across, down) 567 } 568 569 private static func applyAcceptedAnswers( 570 cells: [[Cell]], 571 across: [Clue], 572 down: [Clue] 573 ) -> [[Cell]] { 574 var cells = cells 575 let acrossByNumber = Dictionary(uniqueKeysWithValues: across.map { ($0.number, $0) }) 576 let downByNumber = Dictionary(uniqueKeysWithValues: down.map { ($0.number, $0) }) 577 let positionsOutsideExactCellAnswers = positionsOutsideExactCellAnswers( 578 cells: cells, 579 across: acrossByNumber, 580 down: downByNumber 581 ) 582 583 for r in cells.indices { 584 for c in cells[r].indices { 585 guard case .open(let solution, let acceptedSolutions, let special) = cells[r][c] else { continue } 586 let position = Position(row: r, col: c) 587 let effectiveSolution = positionsOutsideExactCellAnswers.contains(position) ? nil : solution 588 var merged = acceptedSolutions 589 if let accepted = acceptedCellValues( 590 atRow: r, 591 col: c, 592 direction: .across, 593 cells: cells, 594 cluesByNumber: acrossByNumber 595 ) { 596 merged.formUnion(accepted) 597 } 598 if let accepted = acceptedCellValues( 599 atRow: r, 600 col: c, 601 direction: .down, 602 cells: cells, 603 cluesByNumber: downByNumber 604 ) { 605 merged.formUnion(accepted) 606 } 607 if effectiveSolution != solution || merged != acceptedSolutions { 608 cells[r][c] = .open(solution: effectiveSolution, acceptedSolutions: merged, special: special) 609 } 610 } 611 } 612 613 return cells 614 } 615 616 private static func applyClueAnswers( 617 cells: [[Cell]], 618 across: [Clue], 619 down: [Clue] 620 ) throws -> [[Cell]] { 621 var cells = cells 622 for clue in across { 623 try applyClueAnswer(clue, direction: .across, cells: &cells) 624 } 625 for clue in down { 626 try applyClueAnswer(clue, direction: .down, cells: &cells) 627 } 628 629 for r in cells.indices { 630 for c in cells[r].indices { 631 if case .open(nil, _, _) = cells[r][c] { 632 throw ParseError.missingInferredSolution(row: r, col: c) 633 } 634 } 635 } 636 return cells 637 } 638 639 private static func applyClueAnswer( 640 _ clue: Clue, 641 direction: Direction, 642 cells: inout [[Cell]] 643 ) throws { 644 guard let answer = clue.answer, 645 let word = wordCells(forClueNumber: clue.number, direction: direction, cells: cells) 646 else { return } 647 guard wordNeedsAnswerProjection(word, cells: cells) else { return } 648 649 let clueID = "\(direction == .across ? "A" : "D")\(clue.number)" 650 let segmentations = segment(answer: answer, over: word, cells: cells, maxResults: 2) 651 guard !segmentations.isEmpty else { 652 throw ParseError.clueAnswerMismatch(clueID) 653 } 654 guard segmentations.count == 1, let segments = segmentations.first else { 655 throw ParseError.ambiguousClueAnswer(clueID) 656 } 657 658 for (position, segment) in zip(word, segments) { 659 guard case .open(let solution, let acceptedSolutions, let special) = cells[position.row][position.col] else { continue } 660 let normalizedSegment = normalizedAnswer(segment) 661 if let solution { 662 guard normalizedAnswer(solution) == normalizedSegment else { 663 throw ParseError.clueAnswerMismatch(clueID) 664 } 665 } else { 666 cells[position.row][position.col] = .open( 667 solution: normalizedSegment, 668 acceptedSolutions: acceptedSolutions, 669 special: special 670 ) 671 } 672 } 673 } 674 675 private static func wordNeedsAnswerProjection( 676 _ word: [(row: Int, col: Int)], 677 cells: [[Cell]] 678 ) -> Bool { 679 word.contains { position in 680 guard case .open(let solution, _, let special) = cells[position.row][position.col] else { 681 return false 682 } 683 return solution == nil || special != nil 684 } 685 } 686 687 private static func segment( 688 answer: String, 689 over word: [(row: Int, col: Int)], 690 cells: [[Cell]], 691 maxResults: Int 692 ) -> [[String]] { 693 let chars = Array(answer) 694 var results: [[String]] = [] 695 696 func recurse(cellIndex: Int, answerIndex: Int, current: [String]) { 697 guard results.count < maxResults else { return } 698 if cellIndex == word.count { 699 if answerIndex == chars.count { 700 results.append(current) 701 } 702 return 703 } 704 guard answerIndex < chars.count else { return } 705 706 let position = word[cellIndex] 707 guard case .open(let solution, _, _) = cells[position.row][position.col] else { return } 708 let remainingCells = word.count - cellIndex - 1 709 710 if let solution { 711 let solutionLength = Array(solution).count 712 let endIndex = answerIndex + solutionLength 713 guard endIndex <= chars.count else { return } 714 let segment = String(chars[answerIndex..<endIndex]) 715 guard normalizedAnswer(segment) == normalizedAnswer(solution) else { return } 716 recurse(cellIndex: cellIndex + 1, answerIndex: endIndex, current: current + [segment]) 717 } else { 718 let maxLength = chars.count - answerIndex - remainingCells 719 guard maxLength >= 1 else { return } 720 for length in 1...maxLength { 721 let endIndex = answerIndex + length 722 let segment = String(chars[answerIndex..<endIndex]) 723 recurse(cellIndex: cellIndex + 1, answerIndex: endIndex, current: current + [segment]) 724 } 725 } 726 } 727 728 recurse(cellIndex: 0, answerIndex: 0, current: []) 729 return results 730 } 731 732 private struct Position: Hashable { 733 let row: Int 734 let col: Int 735 } 736 737 private static func positionsOutsideExactCellAnswers( 738 cells: [[Cell]], 739 across: [Int: Clue], 740 down: [Int: Clue] 741 ) -> Set<Position> { 742 var positions: Set<Position> = [] 743 var seenWords: Set<WordKey> = [] 744 for r in cells.indices { 745 for c in cells[r].indices { 746 positions.formUnion( 747 positionsOutsideExactCellAnswer( 748 fromRow: r, 749 col: c, 750 direction: .across, 751 cells: cells, 752 cluesByNumber: across, 753 seenWords: &seenWords 754 ) 755 ) 756 positions.formUnion( 757 positionsOutsideExactCellAnswer( 758 fromRow: r, 759 col: c, 760 direction: .down, 761 cells: cells, 762 cluesByNumber: down, 763 seenWords: &seenWords 764 ) 765 ) 766 } 767 } 768 return positions 769 } 770 771 private struct WordKey: Hashable { 772 let direction: Direction 773 let row: Int 774 let col: Int 775 } 776 777 private static func positionsOutsideExactCellAnswer( 778 fromRow row: Int, 779 col: Int, 780 direction: Direction, 781 cells: [[Cell]], 782 cluesByNumber: [Int: Clue], 783 seenWords: inout Set<WordKey> 784 ) -> Set<Position> { 785 let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells) 786 guard let first = word.first else { return [] } 787 let key = WordKey(direction: direction, row: first.row, col: first.col) 788 guard seenWords.insert(key).inserted, 789 word.count > 1, 790 let number = clueNumber(forWord: word, cells: cells), 791 let clue = cluesByNumber[number] 792 else { return [] } 793 794 guard let answer = clue.answer else { return [] } 795 let solutions = word.compactMap { position -> String? in 796 guard case .open(let solution?, _, _) = cells[position.row][position.col] else { return nil } 797 return solution 798 } 799 guard solutions.count == word.count else { return [] } 800 801 if normalizedAnswer(answer) == normalizedAnswer(solutions.joined()) { 802 return [] 803 } 804 805 let matchingIndices = solutions.indices.filter { normalizedAnswer(answer) == normalizedAnswer(solutions[$0]) } 806 guard matchingIndices.count == 1, let matchingIndex = matchingIndices.first else { return [] } 807 808 return Set(word.indices.compactMap { index in 809 index == matchingIndex ? nil : Position(row: word[index].row, col: word[index].col) 810 }) 811 } 812 813 private static func acceptedCellValues( 814 atRow row: Int, 815 col: Int, 816 direction: Direction, 817 cells: [[Cell]], 818 cluesByNumber: [Int: Clue] 819 ) -> Set<String>? { 820 let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells) 821 guard let wordIndex = word.firstIndex(where: { $0.row == row && $0.col == col }) else { return nil } 822 guard let number = clueNumber(forWord: word, cells: cells), 823 let clue = cluesByNumber[number], 824 !clue.acceptedAnswers.isEmpty else { return nil } 825 826 if let solution = solution(atRow: row, col: col, cells: cells), 827 let answer = clue.answer, 828 normalizedAnswer(answer) == normalizedAnswer(solution) { 829 return Set(clue.acceptedAnswers) 830 } 831 832 if word.count == 1 { 833 return Set(clue.acceptedAnswers) 834 } 835 836 let solutions = word.compactMap { position -> String? in 837 guard case .open(let solution?, _, _) = cells[position.row][position.col] else { return nil } 838 return solution 839 } 840 guard solutions.count == word.count else { return nil } 841 842 let canonicalAnswer = clue.answer ?? solutions.joined() 843 guard canonicalAnswer == solutions.joined() else { return nil } 844 845 var accepted: Set<String> = [] 846 for acceptedAnswer in clue.acceptedAnswers { 847 guard let segments = segmentAcceptedAnswer(acceptedAnswer, canonicalSegments: solutions), 848 segments.indices.contains(wordIndex), 849 segments[wordIndex] != solutions[wordIndex] else { continue } 850 accepted.insert(segments[wordIndex]) 851 } 852 return accepted 853 } 854 855 private static func solution(atRow row: Int, col: Int, cells: [[Cell]]) -> String? { 856 guard case .open(let solution?, _, _) = cells[row][col] else { return nil } 857 return solution 858 } 859 860 private static func normalizedAnswer(_ value: String) -> String { 861 value.precomposedStringWithCanonicalMapping.uppercased() 862 } 863 864 private static func segmentAcceptedAnswer( 865 _ acceptedAnswer: String, 866 canonicalSegments: [String] 867 ) -> [String]? { 868 let accepted = Array(acceptedAnswer) 869 let canonical = canonicalSegments.map(Array.init) 870 871 // Equal-length alternative: mirror the canonical cell segmentation 872 // exactly. This covers whole-word Schrödinger answers where several 873 // cells differ at once (e.g. CIGAR / PENIS over single-letter cells), 874 // which the single-replacement search below cannot align. 875 let canonicalLength = canonical.reduce(0) { $0 + $1.count } 876 if accepted.count == canonicalLength { 877 var segments: [String] = [] 878 var offset = 0 879 var differs = false 880 for cell in canonical { 881 let slice = accepted[offset..<offset + cell.count] 882 if !slice.elementsEqual(cell) { differs = true } 883 segments.append(String(slice)) 884 offset += cell.count 885 } 886 return differs ? segments : nil 887 } 888 889 for replacedIndex in canonical.indices { 890 let prefixLength = canonical[..<replacedIndex].reduce(0) { $0 + $1.count } 891 let suffixLength = canonical[canonical.index(after: replacedIndex)...].reduce(0) { $0 + $1.count } 892 guard accepted.count >= prefixLength + suffixLength else { continue } 893 894 let prefix = canonical[..<replacedIndex].flatMap { $0 } 895 let suffix = canonical[canonical.index(after: replacedIndex)...].flatMap { $0 } 896 guard accepted.prefix(prefix.count).elementsEqual(prefix) else { continue } 897 guard accepted.suffix(suffix.count).elementsEqual(suffix) else { continue } 898 899 let replacementEnd = accepted.count - suffixLength 900 let replacement = Array(accepted[prefixLength..<replacementEnd]) 901 guard !replacement.isEmpty, replacement != canonical[replacedIndex] else { continue } 902 903 var segments = canonical.map { String($0) } 904 segments[replacedIndex] = String(replacement) 905 return segments 906 } 907 908 return nil 909 } 910 911 private enum Direction: Hashable { 912 case across 913 case down 914 915 var delta: (row: Int, col: Int) { 916 switch self { 917 case .across: return (0, 1) 918 case .down: return (1, 0) 919 } 920 } 921 } 922 923 private static func clueNumber(atRow row: Int, col: Int, direction: Direction, cells: [[Cell]]) -> Int? { 924 let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells) 925 return clueNumber(forWord: word, cells: cells) 926 } 927 928 private static func wordCells( 929 forClueNumber number: Int, 930 direction: Direction, 931 cells: [[Cell]] 932 ) -> [(row: Int, col: Int)]? { 933 var counter = 1 934 for r in cells.indices { 935 for c in cells[r].indices { 936 guard isOpen(cells, r, c) else { continue } 937 let startsAcross = !isOpen(cells, r, c - 1) && isOpen(cells, r, c + 1) 938 let startsDown = !isOpen(cells, r - 1, c) && isOpen(cells, r + 1, c) 939 guard startsAcross || startsDown else { continue } 940 941 if counter == number { 942 switch direction { 943 case .across where startsAcross: 944 return wordCells(fromRow: r, col: c, direction: direction, cells: cells) 945 case .down where startsDown: 946 return wordCells(fromRow: r, col: c, direction: direction, cells: cells) 947 default: 948 return nil 949 } 950 } 951 counter += 1 952 } 953 } 954 return nil 955 } 956 957 private static func clueNumber(forWord word: [(row: Int, col: Int)], cells: [[Cell]]) -> Int? { 958 guard let first = word.first else { return nil } 959 return computedNumber(atRow: first.row, col: first.col, cells: cells) 960 } 961 962 private static func wordCells( 963 fromRow row: Int, 964 col: Int, 965 direction: Direction, 966 cells: [[Cell]] 967 ) -> [(row: Int, col: Int)] { 968 guard !isBlock(cells, row, col) else { return [] } 969 let delta = direction.delta 970 var startRow = row 971 var startCol = col 972 while isOpen(cells, startRow - delta.row, startCol - delta.col) { 973 startRow -= delta.row 974 startCol -= delta.col 975 } 976 977 var result: [(row: Int, col: Int)] = [] 978 var r = startRow 979 var c = startCol 980 while isOpen(cells, r, c) { 981 result.append((r, c)) 982 r += delta.row 983 c += delta.col 984 } 985 return result 986 } 987 988 private static func computedNumber(atRow row: Int, col: Int, cells: [[Cell]]) -> Int? { 989 var counter = 1 990 for r in cells.indices { 991 for c in cells[r].indices { 992 guard isOpen(cells, r, c) else { continue } 993 let startsAcross = !isOpen(cells, r, c - 1) && isOpen(cells, r, c + 1) 994 let startsDown = !isOpen(cells, r - 1, c) && isOpen(cells, r + 1, c) 995 if startsAcross || startsDown { 996 if r == row, c == col { return counter } 997 counter += 1 998 } 999 } 1000 } 1001 return nil 1002 } 1003 1004 private static func isOpen(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool { 1005 guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return false } 1006 return !isBlock(cells, row, col) 1007 } 1008 1009 private static func isBlock(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool { 1010 guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return true } 1011 if case .block = cells[row][col] { return true } 1012 return false 1013 } 1014 }