XD.swift (64173B)
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 /// Version of the source→XD conversion (`NYTToXDConverter` / 8 /// `PUZToXDConverter`) that produced a persisted XD source. Written into the 9 /// `ConVer:` header and compared by `NYTPuzzleUpgrader` to decide whether an 10 /// owned NYT game should be re-fetched and re-converted. Only bumped when a 11 /// converter changes; puzzles generated in-house (Crossmake, bundled) carry 12 /// no converter version at all. 13 static let currentConverterVersion = 12 14 15 /// Version of the XD→Puzzle/Core Data processing (`XD.parse`, `Puzzle(xd:)`, 16 /// and the cached summary fields). Held on the game entity, never 17 /// serialized, and compared by `GameStore.preparePuzzleForLoad` to decide 18 /// whether a game must be reparsed and its cache refreshed. Bumped only when 19 /// that processing changes. 20 static let currentParserVersion = 11 21 22 /// Upper bound on a `.xd` source handed to `parse`. The largest puzzle we 23 /// ship is ~3 KB, so this is ~80× real content — no genuine puzzle is ever 24 /// rejected, but it caps parse cost and memory on an untrusted source (a 25 /// synced Game asset, an invite payload, an imported file). Does not replace 26 /// the algorithmic fix in `segment`; it bounds the general boundary cost. 27 static let maxSourceBytes = 262_144 28 29 /// Upper bound on a single clue's text. The longest real clue is under 100 30 /// characters. The overall source cap alone doesn't tame per-clue cost: 31 /// `XDMarkup.segments` rescans to end-of-string for every unclosed markup 32 /// span (O(n²) in one clue) and `parseCrossReferences` runs a backtracking 33 /// regex, so a single oversized clue under the source cap is still costly. 34 static let maxClueTextLength = 1_024 35 36 /// Upper bound on the grid's width and height, checked before any cell 37 /// storage is allocated. The byte cap alone admits a ~262,000-cell 38 /// single-row grid whose answer-application passes each walk the whole 39 /// row; the biggest genuine crossword we know of (NYT's annual Super Mega) 40 /// is 50×50, so 128 rejects nothing real while keeping every per-word pass 41 /// trivially small. 42 static let maxGridDimension = 128 43 44 /// Upper bound on distinct clues. A dense `maxGridDimension` grid tops out 45 /// around 5,000 words; real published puzzles stay under 800. Bounds the 46 /// per-clue answer-projection work that follows parsing. 47 static let maxClueCount = 8_192 48 49 /// Upper bound on one clue's combined alternative/`Accept` answers. Each 50 /// accepted answer is segmented against its whole word, so an unbounded 51 /// list is a work multiplier; genuine Schrödinger clues carry a handful. 52 static let maxAcceptedAnswersPerClue = 32 53 54 /// Upper bound on a single `Rebus:` expansion. Cell solutions feed the 55 /// joined-word strings that answer projection and accepted-answer 56 /// segmentation compare against, so one multi-kilobyte expansion inflates 57 /// every pass over its word. Real rebus fills are a word or two. An 58 /// over-long entry is dropped, so a grid that references it fails closed 59 /// with `unknownGridCharacter`. 60 static let maxRebusValueLength = 64 61 62 /// Upper bound on definition lines in the `## Decorations` section. Parsing is 63 /// linear in the source, which `maxSourceBytes` already bounds, so this 64 /// exists only to cap the per-character dictionary a malformed source can 65 /// grow. A design grid can reference at most `maxGridDimension²` distinct 66 /// characters, and real decorations use a few dozen. 67 static let maxDecorationDefinitions = 4_096 68 69 /// Single-character grid placeholders for multi-letter (rebus) fills, used 70 /// by every converter that *writes* `.xd`. The grid is one character per 71 /// cell, so a cell whose fill is longer than one letter shows one of these 72 /// and is expanded via the `Rebus:` header (the `1` in `1=LW`). The spec 73 /// allows "digits, most symbols, and printable unicode characters" here; we 74 /// take digits first (the conventional, readable encoding) then the ASCII 75 /// symbols, where "most" excludes the characters the grid/header parser 76 /// already reserves — letters (grid fill), `#`/`_`/`.` (block/empty), 77 /// `@`/`*` (`Specials:` markers), and `=`/space (`Rebus:` `key=value` 78 /// syntax, split on whitespace by `parseRebusHeader`). We stop at ASCII 79 /// rather than walking into unicode; real puzzles use a handful of distinct 80 /// fills, nowhere near the ceiling. (Walking ASCII naïvely from `'1'` 81 /// overflows into `=` by the 13th key, producing an unparseable `==VALUE` 82 /// entry and a rejected grid char.) 83 static let rebusPlaceholders: [Character] = { 84 let reserved: Set<Character> = ["#", "_", ".", "@", "*", "=", " "] 85 let symbols = (UInt8(33)...UInt8(126)) 86 .map { Character(UnicodeScalar($0)) } 87 .filter { !$0.isLetter && !$0.isNumber && !reserved.contains($0) } 88 return Array("123456789") + symbols 89 }() 90 91 let title: String? 92 let publisher: String? 93 let author: String? 94 let copyright: String? 95 let date: Date? 96 let converterVersion: Int 97 let width: Int 98 let height: Int 99 let cells: [[Cell]] 100 let acrossClues: [Clue] 101 let downClues: [Clue] 102 let relatives: [[ClueRef]] 103 /// Per-cell decoration layers from the `## Decorations` section, in the order 104 /// their definition lines appeared — which is also the order they paint. 105 /// Empty for the (overwhelmingly common) source that has no such section. 106 let decorations: [GridPosition: [Decoration]] 107 108 /// A single clue identified by its number and direction. Used to describe 109 /// groups of mutually-related clues (a theme's revealer plus the answers 110 /// it references, or a simple "See 14-Across" pair). 111 struct ClueRef: Sendable, Hashable { 112 let number: Int 113 let direction: Puzzle.Direction 114 } 115 116 /// A single grid cell as it appears in the .xd source. Open cells carry 117 /// an optional solution string which may be 1+ characters long once any 118 /// `Rebus:` mapping has been applied, plus an optional per-cell special 119 /// marker. 120 enum Cell: Sendable, Equatable { 121 case block 122 case open(solution: String?, acceptedSolutions: Set<String>, special: Puzzle.Special?) 123 } 124 125 /// Decoration layers are format-independent, so they live on `Puzzle` 126 /// alongside `Special`; this alias keeps the parser's references short. 127 typealias Decoration = Puzzle.Decoration 128 129 struct Clue: Sendable, Equatable { 130 let number: Int 131 let text: String 132 let answer: String? 133 /// Alternative full-word answers from a slash-separated `~` field 134 /// (`~ CIGAR / PENIS`): the first reading becomes `answer`, the rest 135 /// are recorded here as Schrödinger alternatives. 136 let alternativeAnswers: [String] 137 let metadata: [String: [String]] 138 139 var acceptedAnswers: [String] { 140 alternativeAnswers + metadata["Accept", default: []].flatMap(Self.parseEscapedTokens) 141 } 142 143 private static func parseEscapedTokens(_ source: String) -> [String] { 144 var tokens: [String] = [] 145 var current = "" 146 var escaping = false 147 148 for ch in source { 149 if escaping { 150 current.append(ch) 151 escaping = false 152 } else if ch == "\\" { 153 escaping = true 154 } else if ch.isWhitespace { 155 if !current.isEmpty { 156 tokens.append(current) 157 current = "" 158 } 159 } else { 160 current.append(ch) 161 } 162 } 163 164 if escaping { 165 current.append("\\") 166 } 167 if !current.isEmpty { 168 tokens.append(current) 169 } 170 return tokens 171 } 172 } 173 174 enum ParseError: Error, CustomStringConvertible { 175 case missingGrid 176 case missingClues 177 case raggedGrid 178 case sourceTooLarge 179 case gridTooLarge 180 case tooManyClues 181 case tooManyAcceptedAnswers(String) 182 case malformedClue(String) 183 case unknownGridCharacter(Character) 184 case unsupportedAnswerCharacter(Character) 185 case clueAnswerMismatch(String) 186 case ambiguousClueAnswer(String) 187 case missingInferredSolution(row: Int, col: Int) 188 case decorationGridMismatch(expected: String, found: String) 189 case unknownDecorationCharacter(Character) 190 case malformedDecoration(String) 191 case tooManyDecorations 192 193 var description: String { 194 switch self { 195 case .missingGrid: 196 return ".xd source has no grid section" 197 case .missingClues: 198 return ".xd source has no clues section" 199 case .raggedGrid: 200 return ".xd grid rows have inconsistent widths" 201 case .sourceTooLarge: 202 return ".xd source exceeds the maximum allowed size" 203 case .gridTooLarge: 204 return ".xd grid exceeds the maximum supported dimensions" 205 case .tooManyClues: 206 return ".xd source has more clues than the maximum supported" 207 case .tooManyAcceptedAnswers(let clue): 208 return ".xd clue has more accepted answers than the maximum supported: \(clue)" 209 case .malformedClue(let line): 210 return "malformed .xd clue: \(line)" 211 case .unknownGridCharacter(let ch): 212 return "unknown .xd grid character: \(ch)" 213 case .unsupportedAnswerCharacter(let ch): 214 return "unsupported non-ASCII answer character: \(ch)" 215 case .clueAnswerMismatch(let clue): 216 return ".xd clue answer does not match grid: \(clue)" 217 case .ambiguousClueAnswer(let clue): 218 return ".xd clue answer cannot be unambiguously projected onto grid: \(clue)" 219 case .missingInferredSolution(let row, let col): 220 return ".xd grid cell at row \(row + 1), column \(col + 1) has no inferred solution" 221 case .decorationGridMismatch(let expected, let found): 222 return ".xd decoration design grid is \(found), but the puzzle grid is \(expected)" 223 case .unknownDecorationCharacter(let ch): 224 return "unknown .xd decoration design character: \(ch)" 225 case .malformedDecoration(let line): 226 return "malformed .xd decoration definition: \(line)" 227 case .tooManyDecorations: 228 return ".xd has more decoration definitions than the maximum supported" 229 } 230 } 231 232 /// A non-technical sentence fragment for the user-facing alert, phrased 233 /// to follow "The puzzle for {date} …". The specifics that matter for a 234 /// bug report — the offending character, the malformed clue line, the 235 /// grid coordinates — stay out of this and ride in `description` to the 236 /// diagnostic log instead. 237 var userFacingReason: String { 238 switch self { 239 case .missingGrid: 240 return "is missing its grid" 241 case .missingClues: 242 return "is missing its clues" 243 case .raggedGrid: 244 return "has a grid Crossmate couldn't read" 245 case .sourceTooLarge: 246 return "is too large for Crossmate to open" 247 case .gridTooLarge: 248 return "has a grid too large for Crossmate to open" 249 case .tooManyClues: 250 return "has too many clues for Crossmate to open" 251 case .tooManyAcceptedAnswers: 252 return "has a clue with more alternative answers than Crossmate supports" 253 case .malformedClue: 254 return "has a clue Crossmate couldn't read" 255 case .unknownGridCharacter, .unsupportedAnswerCharacter: 256 return "contains a character Crossmate doesn't support" 257 case .clueAnswerMismatch: 258 return "has an answer that doesn't match its grid" 259 case .ambiguousClueAnswer: 260 return "has an answer Crossmate couldn't place in its grid" 261 case .missingInferredSolution: 262 return "has a square Crossmate couldn't solve" 263 case .decorationGridMismatch, .unknownDecorationCharacter, .malformedDecoration, .tooManyDecorations: 264 return "has decoration Crossmate couldn't read" 265 } 266 } 267 } 268 269 static func parse(_ source: String) throws -> XD { 270 guard source.utf8.count <= maxSourceBytes else { 271 throw ParseError.sourceTooLarge 272 } 273 let allSections = splitIntoSections(source) 274 // Named optional sections are lifted out first so they can appear in any 275 // order (or not at all) without disturbing the positional three that 276 // every `.xd` source has carried since v1. 277 let decorationsSection = allSections.first { isNamed($0, "Decorations") } 278 let sections = allSections.filter { !isNamed($0, "Decorations") }.map(\.lines) 279 guard sections.count >= 2 else { throw ParseError.missingGrid } 280 guard sections.count >= 3 else { throw ParseError.missingClues } 281 282 let metadata = parseMetadata(sections[0]) 283 // `ConVer:` is the current token; `CmVer:` is the legacy name kept for 284 // sources persisted or synced before the rename (and older peers still 285 // emit it). Read the new token first, fall back to the old. 286 let converterVersion = parseConverterVersionHeader( 287 metadata.first("ConVer") ?? metadata.first("CmVer") 288 ) 289 let rebus = parseRebusHeader(metadata.first("Rebus")) 290 let standardSpecial = parseStandardSpecialHeader(metadata.first("Special")) 291 let relatives = parseRelativesHeader(metadata.first("Relatives")) 292 let (rawCells, width, height) = try parseGrid( 293 sections[1], 294 rebus: rebus, 295 standardSpecial: standardSpecial, 296 specialsHeader: metadata.first("Specials") 297 ) 298 let (across, down) = try parseClues(sections[2]) 299 // Clue numbering is pure grid topology (block layout), which never 300 // changes once the grid is parsed — so compute it once here instead of 301 // re-deriving a cell's number with a full grid rescan inside the 302 // per-cell answer-application passes below (which made those passes 303 // O(cells²)). 304 let numbering = Numbering.build(rawCells) 305 let solvedCells = try applyClueAnswers(cells: rawCells, across: across, down: down, numbering: numbering) 306 let cells = applyAcceptedAnswers(cells: solvedCells, across: across, down: down, numbering: numbering) 307 try validateASCIIEntryOptions(cells: cells) 308 // Parsed last: the design grid is validated against the puzzle's own 309 // dimensions, which aren't known until the grid section is parsed. 310 let decorations = try parseDecorations(decorationsSection?.lines, width: width, height: height) 311 312 return XD( 313 title: metadata.first("Title"), 314 publisher: metadata.first("Publisher"), 315 author: metadata.first("Author"), 316 copyright: metadata.first("Copyright"), 317 date: parseDateHeader(metadata.first("Date")), 318 converterVersion: converterVersion, 319 width: width, 320 height: height, 321 cells: cells, 322 acrossClues: across, 323 downClues: down, 324 relatives: relatives, 325 decorations: decorations 326 ) 327 } 328 329 private static func isNamed(_ section: Section, _ name: String) -> Bool { 330 section.name?.caseInsensitiveCompare(name) == .orderedSame 331 } 332 333 private static func validateASCIIEntryOptions(cells: [[Cell]]) throws { 334 for row in cells { 335 for cell in row { 336 guard case .open(let solution, let acceptedSolutions, _) = cell else { continue } 337 if let solution, isASCIIAnswer(solution) { continue } 338 if acceptedSolutions.contains(where: isASCIIAnswer) { continue } 339 if let solution, let ch = firstNonASCIICharacter(in: solution) { 340 throw ParseError.unsupportedAnswerCharacter(ch) 341 } 342 for accepted in acceptedSolutions { 343 if let ch = firstNonASCIICharacter(in: accepted) { 344 throw ParseError.unsupportedAnswerCharacter(ch) 345 } 346 } 347 } 348 } 349 } 350 351 private static func isASCIIAnswer(_ value: String) -> Bool { 352 !value.isEmpty && value.unicodeScalars.allSatisfy(\.isASCII) 353 } 354 355 private static func firstNonASCIICharacter(in value: String) -> Character? { 356 value.first { character in 357 character.unicodeScalars.contains { !$0.isASCII } 358 } 359 } 360 361 // MARK: - Sections 362 363 /// One top-level section of the source, with the `## Name` label that 364 /// introduced it (if any). The first three sections are still identified by 365 /// order — metadata, grid, clues — because the vast majority of `.xd` 366 /// sources carry no labels at all. Optional sections that arrive later 367 /// (`## Decorations`) are found by name instead, so their position can't matter 368 /// and an unrecognised label is simply skipped rather than shifting the 369 /// positional three. 370 private struct Section { 371 let name: String? 372 let lines: [String] 373 } 374 375 /// Splits the source into top-level sections. Per the .xd spec, sections 376 /// are delimited either by runs of two or more blank lines, or by 377 /// `## SectionName` header lines. We accept both: blank-line runs end the 378 /// current section, and a `##` line also ends the current section (the 379 /// header line is consumed, and its label attaches to the section that 380 /// *follows* it). 381 private static func splitIntoSections(_ source: String) -> [Section] { 382 let lines = source 383 .split(separator: "\n", omittingEmptySubsequences: false) 384 .map(String.init) 385 386 var sections: [Section] = [] 387 var current: [String] = [] 388 var currentName: String? = nil 389 var blankRun = 0 390 391 func flush() { 392 while current.last?.trimmingCharacters(in: .whitespaces).isEmpty == true { 393 current.removeLast() 394 } 395 while current.first?.trimmingCharacters(in: .whitespaces).isEmpty == true { 396 current.removeFirst() 397 } 398 if !current.isEmpty { 399 sections.append(Section(name: currentName, lines: current)) 400 } 401 current = [] 402 currentName = nil 403 } 404 405 for rawLine in lines { 406 let line = rawLine.trimmingCharacters(in: CharacterSet(charactersIn: "\r")) 407 let trimmed = line.trimmingCharacters(in: .whitespaces) 408 409 // The test is deliberately `"## "` (with the trailing space) or a 410 // bare `"##"`, never `hasPrefix("##")`: `#` is the block character, 411 // so an all-block grid row such as `###` would otherwise be 412 // mistaken for a section header and split the grid in two. 413 if trimmed.hasPrefix("## ") || trimmed == "##" { 414 flush() 415 let label = trimmed.dropFirst(2).trimmingCharacters(in: .whitespaces) 416 currentName = label.isEmpty ? nil : label 417 blankRun = 0 418 continue 419 } 420 421 if trimmed.isEmpty { 422 blankRun += 1 423 if blankRun >= 2 { 424 flush() 425 } 426 continue 427 } 428 429 blankRun = 0 430 current.append(line) 431 } 432 flush() 433 return sections 434 } 435 436 // MARK: - Metadata 437 438 private struct Metadata { 439 var entries: [String: [String]] = [:] 440 441 func first(_ key: String) -> String? { 442 entries[key]?.first 443 } 444 445 func values(for key: String) -> [String] { 446 entries[key, default: []] 447 } 448 } 449 450 /// Reads a single metadata header value (e.g. `Date`, `Title`) from raw 451 /// `.xd` source without a full parse. Lets a caller name the puzzle that 452 /// failed to parse — the metadata section is independent of the grid/clue 453 /// sections that the parser rejects. 454 static func metadataValue(_ key: String, in source: String) -> String? { 455 guard let header = splitIntoSections(source).first else { return nil } 456 return parseMetadata(header.lines).first(key) 457 } 458 459 private static func parseMetadata(_ lines: [String]) -> Metadata { 460 var metadata = Metadata() 461 for line in lines { 462 guard let colon = line.firstIndex(of: ":") else { continue } 463 let key = line[..<colon].trimmingCharacters(in: .whitespaces) 464 let value = line[line.index(after: colon)...].trimmingCharacters(in: .whitespaces) 465 if !key.isEmpty { 466 metadata.entries[key, default: []].append(value) 467 } 468 } 469 return metadata 470 } 471 472 /// Parses a `Rebus:` header value such as `1=ONE 2=TWO 3=THREE` into a 473 /// map from grid placeholder character to its expanded solution string. 474 private static func parseRebusHeader(_ value: String?) -> [Character: String] { 475 guard let value, !value.isEmpty else { return [:] } 476 var map: [Character: String] = [:] 477 for entry in value.split(whereSeparator: { $0.isWhitespace }) { 478 guard let equals = entry.firstIndex(of: "=") else { continue } 479 let key = entry[..<equals] 480 let val = entry[entry.index(after: equals)...] 481 guard key.count == 1, let keyChar = key.first, !val.isEmpty, 482 val.count <= maxRebusValueLength else { continue } 483 map[keyChar] = unescapeRebusValue(val) 484 } 485 return map 486 } 487 488 /// Reverses `NYTToXDConverter.escapeRebusValue`. A backslash introduces an 489 /// escape: `\\` is a literal backslash, and `\name` is a named escape whose 490 /// name is the following run of letters (currently just `\space` → a space, 491 /// which lets a gap cell's blank fill survive the whitespace-split header). 492 /// An unrecognised escape is preserved verbatim so an older parser never 493 /// silently drops a value a newer writer produced. 494 private static func unescapeRebusValue(_ value: Substring) -> String { 495 guard value.contains("\\") else { return String(value) } 496 var out = "" 497 var i = value.startIndex 498 while i < value.endIndex { 499 guard value[i] == "\\" else { 500 out.append(value[i]) 501 i = value.index(after: i) 502 continue 503 } 504 let next = value.index(after: i) 505 guard next < value.endIndex else { out.append("\\"); break } 506 if value[next] == "\\" { 507 out.append("\\") 508 i = value.index(after: next) 509 continue 510 } 511 var j = next 512 while j < value.endIndex, value[j].isLetter { j = value.index(after: j) } 513 let name = value[next..<j] 514 switch name { 515 case "space": out.append(" ") 516 default: out.append("\\"); out.append(contentsOf: name) 517 } 518 i = j 519 } 520 return out 521 } 522 523 /// Parses a `Date:` header value as strict ISO `YYYY-MM-DD`. Returns 524 /// `nil` if the value is missing, empty, or in any other format. 525 private static func parseDateHeader(_ value: String?) -> Date? { 526 guard let value else { return nil } 527 let trimmed = value.trimmingCharacters(in: .whitespaces) 528 guard let match = trimmed.firstMatch(of: /^(\d{4})-(\d{2})-(\d{2})$/), 529 let year = Int(match.1), 530 let month = Int(match.2), 531 let day = Int(match.3) 532 else { return nil } 533 // Pin to America/New_York: puzzle dates are publication dates in NYT's 534 // timezone, and downstream fetchers (NYTPuzzleFetcher) format the Date 535 // back to a YYYY-MM-DD string in that zone. Without an explicit zone 536 // the system default fires here, which on a device east of NY yields a 537 // Date that formats back to the previous day — wrong puzzle. 538 var calendar = Calendar(identifier: .gregorian) 539 calendar.timeZone = TimeZone(identifier: "America/New_York") ?? .gmt 540 var comps = DateComponents() 541 comps.calendar = calendar 542 comps.timeZone = calendar.timeZone 543 comps.year = year 544 comps.month = month 545 comps.day = day 546 return calendar.date(from: comps) 547 } 548 549 /// Parses a Crossmate converter-version header (`ConVer:`, or the legacy 550 /// `CmVer:`). A missing or unconverted source is version 1, which keeps 551 /// generated puzzles (no header) and older fixtures identifiable as 552 /// non-current — harmless, since only owned NYT games act on this value. 553 private static func parseConverterVersionHeader(_ value: String?) -> Int { 554 guard let value else { return 1 } 555 let trimmed = value.trimmingCharacters(in: .whitespaces) 556 guard let version = Int(trimmed), version >= 1 else { return 1 } 557 return version 558 } 559 560 /// Returns `source` with its converter-version header set to `version`, 561 /// rewriting an existing `ConVer:`/`CmVer:` line in place, or inserting a 562 /// `ConVer:` line after the title if none is present. Only the metadata 563 /// block — the lines before the first blank line — is inspected, so the grid 564 /// and clues are never touched. Used by the upgrader to record that a 565 /// structurally-diverged NYT source has been evaluated at the current 566 /// converter version without disturbing the grid the player is solving. 567 static func settingConverterVersionHeader(in source: String, to version: Int) -> String { 568 var lines = source.components(separatedBy: "\n") 569 let newLine = "ConVer: \(version)" 570 for i in lines.indices { 571 let trimmed = lines[i].trimmingCharacters(in: .whitespaces) 572 if trimmed.isEmpty { break } // end of the metadata block 573 if trimmed.hasPrefix("ConVer:") || trimmed.hasPrefix("CmVer:") { 574 lines[i] = newLine 575 return lines.joined(separator: "\n") 576 } 577 } 578 // No existing header: insert after the first metadata line (the title). 579 lines.insert(newLine, at: lines.isEmpty ? 0 : 1) 580 return lines.joined(separator: "\n") 581 } 582 583 /// Parses a `Relatives:` header value into groups of cross-referenced 584 /// clues. Groups are separated by `;`, tokens within a group by `,`, and 585 /// each token is `{number}{A|D}` (e.g. `17A`, `57A`). This is a Crossmate 586 /// extension to `.xd`; unknown/invalid tokens are silently dropped. 587 /// Single-token groups are allowed so formatted NYT clues can mark their 588 /// own answer cells as thematic. 589 private static func parseRelativesHeader(_ value: String?) -> [[ClueRef]] { 590 guard let value, !value.isEmpty else { return [] } 591 var groups: [[ClueRef]] = [] 592 for groupSlice in value.split(separator: ";") { 593 var refs: [ClueRef] = [] 594 for tokenSlice in groupSlice.split(separator: ",") { 595 let token = tokenSlice.trimmingCharacters(in: .whitespaces) 596 guard let last = token.last else { continue } 597 let direction: Puzzle.Direction 598 switch last { 599 case "A", "a": direction = .across 600 case "D", "d": direction = .down 601 default: continue 602 } 603 guard let number = Int(token.dropLast()), number > 0 else { continue } 604 refs.append(ClueRef(number: number, direction: direction)) 605 } 606 if !refs.isEmpty { groups.append(refs) } 607 } 608 return groups 609 } 610 611 private static func parseSpecialsHeader(_ value: String?) -> [Character: Puzzle.Special] { 612 guard let value, !value.isEmpty else { return [:] } 613 var specials: [Character: Puzzle.Special] = [:] 614 for assignment in value.split(whereSeparator: { $0.isWhitespace }) { 615 guard let equals = assignment.firstIndex(of: "=") else { continue } 616 let symbolPart = assignment[..<equals] 617 let kindPart = assignment[assignment.index(after: equals)...] 618 guard symbolPart.count == 1, let symbol = symbolPart.first else { continue } 619 let kind: Puzzle.Special 620 switch kindPart.lowercased() { 621 case "circle", "circled": kind = .circled 622 case "shaded": kind = .shaded 623 default: continue 624 } 625 specials[symbol] = kind 626 } 627 return specials 628 } 629 630 private static func parseStandardSpecialHeader(_ value: String?) -> Puzzle.Special? { 631 guard let value else { return nil } 632 switch value.trimmingCharacters(in: .whitespaces).lowercased() { 633 case "circle", "circled": return .circled 634 case "shaded": return .shaded 635 default: return nil 636 } 637 } 638 639 // MARK: - Grid 640 641 private static func parseGrid( 642 _ lines: [String], 643 rebus: [Character: String], 644 standardSpecial: Puzzle.Special?, 645 specialsHeader: String? 646 ) throws -> (cells: [[Cell]], width: Int, height: Int) { 647 var gridLines: [String] = [] 648 var width: Int? = nil 649 650 for line in lines { 651 let trimmed = line.trimmingCharacters(in: .whitespaces) 652 if trimmed.isEmpty { continue } 653 654 // Both dimensions are bounded here, before any Cell storage is 655 // allocated: the source-byte cap alone still admits a single 656 // ~262,000-cell row (or column) that the answer-application 657 // passes would then walk per word. 658 guard trimmed.count <= maxGridDimension, gridLines.count < maxGridDimension else { 659 throw ParseError.gridTooLarge 660 } 661 if let w = width, trimmed.count != w { 662 throw ParseError.raggedGrid 663 } 664 width = trimmed.count 665 gridLines.append(trimmed) 666 } 667 668 guard let w = width, !gridLines.isEmpty else { throw ParseError.missingGrid } 669 670 let specialSymbols = parseSpecialsHeader(specialsHeader) 671 var rows: [[Cell]] = [] 672 for line in gridLines { 673 var row: [Cell] = [] 674 for ch in line { 675 row.append(try gridCell( 676 for: ch, 677 rebus: rebus, 678 standardSpecial: standardSpecial, 679 specialSymbols: specialSymbols 680 )) 681 } 682 rows.append(row) 683 } 684 685 return (rows, w, rows.count) 686 } 687 688 private static func gridCell( 689 for ch: Character, 690 rebus: [Character: String], 691 standardSpecial: Puzzle.Special?, 692 specialSymbols: [Character: Puzzle.Special] 693 ) throws -> Cell { 694 // Blocks: '#' is a normal block; '_' marks a non-existing cell on the 695 // edge of an irregularly-shaped grid. Both render as non-playable. 696 if ch == "#" || ch == "_" { 697 return .block 698 } 699 // '.' is an open cell with no known solution. 700 if ch == "." { 701 return .open(solution: nil, acceptedSolutions: [], special: nil) 702 } 703 let lowercaseSpecial = ch.isLetter && ch.isLowercase ? standardSpecial : nil 704 if let expansion = rebus[ch] { 705 return .open( 706 solution: expansion.uppercased(), 707 acceptedSolutions: [], 708 special: specialSymbols[ch] ?? lowercaseSpecial 709 ) 710 } 711 if let special = specialSymbols[ch] { 712 return .open(solution: nil, acceptedSolutions: [], special: special) 713 } 714 if ch.isLetter { 715 return .open(solution: String(ch).uppercased(), acceptedSolutions: [], special: lowercaseSpecial) 716 } 717 throw ParseError.unknownGridCharacter(ch) 718 } 719 720 // MARK: - Decorations 721 722 /// Parses the optional `## Decorations` section: a design grid of the same 723 /// dimensions as the puzzle, plus `<char>. <kind>=<value> [before|after]` 724 /// definition lines. 725 /// 726 /// The two line kinds are told apart by whitespace — a definition line 727 /// always has some (at minimum the space after `<char>.`) and a design-grid 728 /// line never does — so the section reads correctly whichever order they 729 /// appear in, and the blank line between them is decorative. 730 private static func parseDecorations( 731 _ lines: [String]?, 732 width: Int, 733 height: Int 734 ) throws -> [GridPosition: [Decoration]] { 735 guard let lines, !lines.isEmpty else { return [:] } 736 737 var gridLines: [String] = [] 738 var definitionLines: [String] = [] 739 for line in lines { 740 let trimmed = line.trimmingCharacters(in: .whitespaces) 741 if trimmed.isEmpty { continue } 742 if trimmed.contains(where: \.isWhitespace) { 743 definitionLines.append(trimmed) 744 } else { 745 gridLines.append(trimmed) 746 } 747 } 748 749 guard definitionLines.count <= maxDecorationDefinitions else { 750 throw ParseError.tooManyDecorations 751 } 752 753 // A design grid that doesn't match the puzzle can't be interpreted at 754 // all — unlike a bad definition line, which costs only its own layer — 755 // so a mismatch fails the parse instead of being cropped or padded into 756 // a shape that would silently decorate the wrong squares. 757 guard gridLines.count == height, gridLines.allSatisfy({ $0.count == width }) else { 758 let found = gridLines.isEmpty 759 ? "empty" 760 : "\(gridLines.map(\.count).max() ?? 0)×\(gridLines.count)" 761 throw ParseError.decorationGridMismatch(expected: "\(width)×\(height)", found: found) 762 } 763 764 var definedCharacters: Set<Character> = [] 765 var decorationsByCharacter: [Character: [Decoration]] = [:] 766 for line in definitionLines { 767 let (key, decoration) = try parseDecorationDefinition(line) 768 // The character counts as defined even when its kind isn't one we 769 // understand, so a source written against a newer spec revision 770 // still resolves its design grid instead of failing outright. 771 definedCharacters.insert(key) 772 if let decoration { 773 decorationsByCharacter[key, default: []].append(decoration) 774 } 775 } 776 777 var result: [GridPosition: [Decoration]] = [:] 778 for (row, line) in gridLines.enumerated() { 779 for (col, ch) in line.enumerated() { 780 if ch == "." { continue } 781 guard definedCharacters.contains(ch) else { 782 throw ParseError.unknownDecorationCharacter(ch) 783 } 784 guard let layers = decorationsByCharacter[ch], !layers.isEmpty else { continue } 785 result[GridPosition(row: row, col: col)] = layers 786 } 787 } 788 return result 789 } 790 791 /// Parses one `<char>. <kind>=<value> [before|after]` line into the design 792 /// character it defines plus the layer it declares. Returns a `nil` layer 793 /// for a structurally sound line whose kind we don't recognise, so a single 794 /// unknown kind costs one layer rather than the whole section. 795 private static func parseDecorationDefinition( 796 _ line: String 797 ) throws -> (key: Character, decoration: Decoration?) { 798 guard let key = line.first, 799 let dot = line.firstIndex(of: "."), 800 line.distance(from: line.startIndex, to: dot) == 1 else { 801 throw ParseError.malformedDecoration(line) 802 } 803 var body = line[line.index(after: dot)...].trimmingCharacters(in: .whitespaces) 804 guard !body.isEmpty else { throw ParseError.malformedDecoration(line) } 805 806 // The phase keyword is stripped off the end rather than tokenised out of 807 // a whitespace split, so a value can itself contain spaces 808 // (`text=NEW YORK`) without needing an escape. 809 var phase = Decoration.Phase.before 810 for (keyword, candidate) in [("after", Decoration.Phase.after), ("before", Decoration.Phase.before)] 811 where body.hasSuffix(" " + keyword) { 812 phase = candidate 813 body = String(body.dropLast(keyword.count + 1)).trimmingCharacters(in: .whitespaces) 814 break 815 } 816 817 guard let equals = body.firstIndex(of: "=") else { 818 throw ParseError.malformedDecoration(line) 819 } 820 let kind = String(body[..<equals]).lowercased() 821 let value = String(body[body.index(after: equals)...]) 822 guard !value.isEmpty else { throw ParseError.malformedDecoration(line) } 823 824 guard let content = decorationContent(kind: kind, value: value) else { 825 return (key, nil) 826 } 827 return (key, Decoration(content: content, phase: phase)) 828 } 829 830 private static func decorationContent(kind: String, value: String) -> Decoration.Content? { 831 switch kind { 832 case "mark": 833 switch value.lowercased() { 834 case "circle", "circled": return .mark(.circled) 835 case "shaded": return .mark(.shaded) 836 default: return nil 837 } 838 case "bg": return decorationColor(layer: .background, value: value) 839 case "fg": return decorationColor(layer: .foreground, value: value) 840 case "text": return .text(value) 841 case "data": return decorationData(value) 842 default: return nil 843 } 844 } 845 846 /// Splits a `bg` / `fg` value into its appearance variants: a lone colour 847 /// applies to both, `<light>;<dark>` gives one for each. More than two parts 848 /// (or an empty one) is malformed and yields no layer rather than a guess at 849 /// which variant was meant. 850 private static func decorationColor( 851 layer: Decoration.ColorLayer, 852 value: String 853 ) -> Decoration.Content? { 854 let parts = value 855 .split(separator: ";", omittingEmptySubsequences: false) 856 .map { $0.trimmingCharacters(in: .whitespaces) } 857 guard (1...2).contains(parts.count), parts.allSatisfy({ !$0.isEmpty }) else { 858 return nil 859 } 860 return .color(layer: layer, light: parts[0], dark: parts.count == 2 ? parts[1] : nil) 861 } 862 863 /// Splits a `data` value's `<mime-type>[;<encoding>],<payload>` descriptor. 864 /// Base64's alphabet contains no comma, so splitting on the first one is 865 /// unambiguous however large the payload. An omitted encoding defaults to 866 /// base64, matching the data-URI convention the syntax borrows from. 867 private static func decorationData(_ value: String) -> Decoration.Content? { 868 guard let comma = value.firstIndex(of: ",") else { return nil } 869 let descriptor = value[..<comma] 870 let payload = String(value[value.index(after: comma)...]) 871 guard !payload.isEmpty else { return nil } 872 let parts = descriptor.split(separator: ";", maxSplits: 1, omittingEmptySubsequences: false) 873 let mimeType = String(parts[0]) 874 guard !mimeType.isEmpty else { return nil } 875 let encoding = parts.count > 1 && !parts[1].isEmpty ? String(parts[1]) : "base64" 876 return .data(mimeType: mimeType, encoding: encoding, payload: payload) 877 } 878 879 // MARK: - Clues 880 881 private static func parseClues( 882 _ lines: [String] 883 ) throws -> (across: [Clue], down: [Clue]) { 884 struct ClueKey: Hashable { 885 let number: Int 886 let direction: Character 887 } 888 889 var clueTexts: [ClueKey: String] = [:] 890 var clueAnswers: [ClueKey: String] = [:] 891 var clueAlternatives: [ClueKey: [String]] = [:] 892 var clueOrder: [ClueKey] = [] 893 var metadataByClue: [ClueKey: [String: [String]]] = [:] 894 895 for rawLine in lines { 896 let line = rawLine.trimmingCharacters(in: .whitespaces) 897 if line.isEmpty { continue } 898 899 guard let leading = line.first, leading == "A" || leading == "D" else { 900 throw ParseError.malformedClue(line) 901 } 902 903 // The metadata-clue form is `A1 ^Format: value`; the `^` marker is 904 // what distinguishes it from an ordinary `A1. clue` line. Gate the 905 // regex on its presence so the common case (no `^`) skips the 906 // per-line match entirely — the pattern requires `\^` anyway, so a 907 // line without it can never match. 908 if line.contains("^"), 909 let match = line.firstMatch(of: /^([AD])(\d+)\s+\^([^:]+):\s*(.*)$/) { 910 guard let number = Int(match.2) else { throw ParseError.malformedClue(line) } 911 let key = ClueKey(number: number, direction: Character(String(match.1))) 912 let metadataKey = String(match.3).trimmingCharacters(in: .whitespaces) 913 guard !metadataKey.isEmpty else { throw ParseError.malformedClue(line) } 914 // Metadata values feed post-parse work (`Accept` values are 915 // segmented against their whole word), so they get the same 916 // length budget as clue text. 917 guard match.4.count <= maxClueTextLength else { 918 throw ParseError.malformedClue(line) 919 } 920 metadataByClue[key, default: [:]][metadataKey, default: []].append(String(match.4)) 921 continue 922 } 923 924 guard let dot = line.firstIndex(of: ".") else { 925 throw ParseError.malformedClue(line) 926 } 927 928 let numberSlice = line[line.index(after: line.startIndex)..<dot] 929 guard let number = Int(numberSlice) else { 930 throw ParseError.malformedClue(line) 931 } 932 let key = ClueKey(number: number, direction: leading) 933 934 var afterDot = line[line.index(after: dot)...] 935 .trimmingCharacters(in: .whitespaces) 936 937 if let tilde = afterDot.range(of: " ~ ", options: .backwards) { 938 // A slash-separated answer field (`~ CIGAR / PENIS`) declares a 939 // Schrödinger clue: the first reading is canonical, the rest are 940 // accepted alternatives. A plain field stays a single answer. 941 let readings = afterDot[tilde.upperBound...] 942 .components(separatedBy: " / ") 943 .map { $0.trimmingCharacters(in: .whitespaces) } 944 .filter { !$0.isEmpty } 945 // Answers are segmented over their word cell-by-cell, so an 946 // unbounded reading is a work (and memo-table) multiplier. 947 guard readings.allSatisfy({ $0.count <= maxClueTextLength }) else { 948 throw ParseError.malformedClue(line) 949 } 950 if let canonical = readings.first { 951 clueAnswers[key] = canonical 952 if readings.count > 1 { 953 clueAlternatives[key] = Array(readings.dropFirst()) 954 } 955 } 956 afterDot = String(afterDot[..<tilde.lowerBound]) 957 .trimmingCharacters(in: .whitespaces) 958 } 959 960 guard afterDot.count <= maxClueTextLength else { 961 throw ParseError.malformedClue(line) 962 } 963 964 if clueTexts[key] == nil { 965 guard clueOrder.count < maxClueCount else { 966 throw ParseError.tooManyClues 967 } 968 clueOrder.append(key) 969 } 970 clueTexts[key] = afterDot 971 } 972 973 var across: [Clue] = [] 974 var down: [Clue] = [] 975 for key in clueOrder { 976 let clue = Clue( 977 number: key.number, 978 text: clueTexts[key] ?? "", 979 answer: clueAnswers[key], 980 alternativeAnswers: clueAlternatives[key] ?? [], 981 metadata: metadataByClue[key] ?? [:] 982 ) 983 guard clue.acceptedAnswers.count <= maxAcceptedAnswersPerClue else { 984 throw ParseError.tooManyAcceptedAnswers("\(key.direction)\(key.number)") 985 } 986 if key.direction == "A" { 987 across.append(clue) 988 } else { 989 down.append(clue) 990 } 991 } 992 return (across, down) 993 } 994 995 /// Applies exact-cell-answer projections and `Accept`/alternative answers. 996 /// Both passes are word-scoped: each maximal open run is visited once, its 997 /// clue resolved once, and its accepted answers segmented once. (The former 998 /// per-cell passes re-walked the containing word — and re-segmented every 999 /// accepted answer — from each of its cells, making a long open row 1000 /// quadratic before a game could be created.) 1001 private static func applyAcceptedAnswers( 1002 cells: [[Cell]], 1003 across: [Clue], 1004 down: [Clue], 1005 numbering: Numbering 1006 ) -> [[Cell]] { 1007 let acrossByNumber = Dictionary(uniqueKeysWithValues: across.map { ($0.number, $0) }) 1008 let downByNumber = Dictionary(uniqueKeysWithValues: down.map { ($0.number, $0) }) 1009 1010 var outsideExactCellAnswers: Set<Position> = [] 1011 var acceptedByPosition: [Position: Set<String>] = [:] 1012 for direction in [Direction.across, .down] { 1013 let cluesByNumber = direction == .across ? acrossByNumber : downByNumber 1014 for word in openWords(direction: direction, cells: cells) { 1015 guard let first = word.first, 1016 let number = numbering.number(atRow: first.row, col: first.col), 1017 let clue = cluesByNumber[number] 1018 else { continue } 1019 collectPositionsOutsideExactCellAnswer( 1020 word: word, 1021 clue: clue, 1022 cells: cells, 1023 into: &outsideExactCellAnswers 1024 ) 1025 collectAcceptedCellValues( 1026 word: word, 1027 clue: clue, 1028 cells: cells, 1029 into: &acceptedByPosition 1030 ) 1031 } 1032 } 1033 1034 var result = cells 1035 for r in result.indices { 1036 for c in result[r].indices { 1037 guard case .open(let solution, let acceptedSolutions, let special) = result[r][c] else { continue } 1038 let position = Position(row: r, col: c) 1039 let effectiveSolution = outsideExactCellAnswers.contains(position) ? nil : solution 1040 var merged = acceptedSolutions 1041 if let accepted = acceptedByPosition[position] { 1042 merged.formUnion(accepted) 1043 } 1044 if effectiveSolution != solution || merged != acceptedSolutions { 1045 result[r][c] = .open(solution: effectiveSolution, acceptedSolutions: merged, special: special) 1046 } 1047 } 1048 } 1049 return result 1050 } 1051 1052 private static func applyClueAnswers( 1053 cells: [[Cell]], 1054 across: [Clue], 1055 down: [Clue], 1056 numbering: Numbering 1057 ) throws -> [[Cell]] { 1058 var cells = cells 1059 for clue in across { 1060 try applyClueAnswer(clue, direction: .across, cells: &cells, numbering: numbering) 1061 } 1062 for clue in down { 1063 try applyClueAnswer(clue, direction: .down, cells: &cells, numbering: numbering) 1064 } 1065 1066 for r in cells.indices { 1067 for c in cells[r].indices { 1068 if case .open(nil, _, _) = cells[r][c] { 1069 throw ParseError.missingInferredSolution(row: r, col: c) 1070 } 1071 } 1072 } 1073 return cells 1074 } 1075 1076 private static func applyClueAnswer( 1077 _ clue: Clue, 1078 direction: Direction, 1079 cells: inout [[Cell]], 1080 numbering: Numbering 1081 ) throws { 1082 guard let answer = clue.answer, 1083 let word = wordCells(forClueNumber: clue.number, direction: direction, cells: cells, numbering: numbering) 1084 else { return } 1085 guard wordNeedsAnswerProjection(word, cells: cells) else { return } 1086 1087 let clueID = "\(direction == .across ? "A" : "D")\(clue.number)" 1088 let segmentations = segment(answer: answer, over: word, cells: cells, maxResults: 2) 1089 guard !segmentations.isEmpty else { 1090 throw ParseError.clueAnswerMismatch(clueID) 1091 } 1092 guard segmentations.count == 1, let segments = segmentations.first else { 1093 throw ParseError.ambiguousClueAnswer(clueID) 1094 } 1095 1096 for (position, segment) in zip(word, segments) { 1097 guard case .open(let solution, let acceptedSolutions, let special) = cells[position.row][position.col] else { continue } 1098 let normalizedSegment = normalizedAnswer(segment) 1099 if let solution { 1100 guard normalizedAnswer(solution) == normalizedSegment else { 1101 throw ParseError.clueAnswerMismatch(clueID) 1102 } 1103 } else { 1104 cells[position.row][position.col] = .open( 1105 solution: normalizedSegment, 1106 acceptedSolutions: acceptedSolutions, 1107 special: special 1108 ) 1109 } 1110 } 1111 } 1112 1113 private static func wordNeedsAnswerProjection( 1114 _ word: [(row: Int, col: Int)], 1115 cells: [[Cell]] 1116 ) -> Bool { 1117 word.contains { position in 1118 guard case .open(let solution, _, let special) = cells[position.row][position.col] else { 1119 return false 1120 } 1121 return solution == nil || special != nil 1122 } 1123 } 1124 1125 private static func segment( 1126 answer: String, 1127 over word: [(row: Int, col: Int)], 1128 cells: [[Cell]], 1129 maxResults: Int 1130 ) -> [[String]] { 1131 let chars = Array(answer) 1132 1133 // The set of valid segmentations of the answer suffix from a given 1134 // `(cellIndex, answerIndex)` state is independent of how that state was 1135 // reached, so we memoize it. Without this, a crafted answer that admits 1136 // no valid segmentation over many free cells walks the entire 1137 // C(answer-1, cells-1) composition tree — a sub-1KB puzzle can drive 1138 // minutes-to-hours of work on the main actor during invite accept. 1139 // Memoizing collapses that to an O(word × answer) word-break DP. 1140 var memo: [Int: [[String]]] = [:] 1141 1142 func solve(cellIndex: Int, answerIndex: Int) -> [[String]] { 1143 if cellIndex == word.count { 1144 return answerIndex == chars.count ? [[]] : [] 1145 } 1146 guard answerIndex < chars.count else { return [] } 1147 1148 let key = cellIndex * (chars.count + 1) + answerIndex 1149 if let cached = memo[key] { return cached } 1150 1151 let position = word[cellIndex] 1152 guard case .open(let solution, _, _) = cells[position.row][position.col] else { 1153 memo[key] = [] 1154 return [] 1155 } 1156 let remainingCells = word.count - cellIndex - 1 1157 1158 var results: [[String]] = [] 1159 // Prepend `segment` to every valid completion of the remaining 1160 // cells, capped at `maxResults`. Each subproblem is itself capped at 1161 // `maxResults`, which is sufficient because the caller never needs 1162 // more than that many total. 1163 func extend(length: Int) { 1164 let endIndex = answerIndex + length 1165 guard endIndex <= chars.count else { return } 1166 let segment = String(chars[answerIndex..<endIndex]) 1167 for suffix in solve(cellIndex: cellIndex + 1, answerIndex: endIndex) { 1168 results.append([segment] + suffix) 1169 if results.count >= maxResults { break } 1170 } 1171 } 1172 1173 if let solution { 1174 let solutionLength = Array(solution).count 1175 let endIndex = answerIndex + solutionLength 1176 if endIndex <= chars.count, 1177 normalizedAnswer(String(chars[answerIndex..<endIndex])) == normalizedAnswer(solution) { 1178 extend(length: solutionLength) 1179 } 1180 } else { 1181 let maxLength = chars.count - answerIndex - remainingCells 1182 if maxLength >= 1 { 1183 for length in 1...maxLength { 1184 extend(length: length) 1185 if results.count >= maxResults { break } 1186 } 1187 } 1188 } 1189 1190 memo[key] = results 1191 return results 1192 } 1193 1194 return solve(cellIndex: 0, answerIndex: 0) 1195 } 1196 1197 private struct Position: Hashable { 1198 let row: Int 1199 let col: Int 1200 } 1201 1202 /// Enumerates every maximal run of open cells in the given direction, 1203 /// including single-cell runs (which can still carry a crossing clue's 1204 /// number). Each cell belongs to exactly one run per direction, so 1205 /// iterating runs covers the grid linearly. 1206 private static func openWords(direction: Direction, cells: [[Cell]]) -> [[Position]] { 1207 let delta = direction.delta 1208 var words: [[Position]] = [] 1209 for r in cells.indices { 1210 for c in cells[r].indices { 1211 guard isOpen(cells, r, c), !isOpen(cells, r - delta.row, c - delta.col) else { continue } 1212 var word: [Position] = [] 1213 var row = r 1214 var col = c 1215 while isOpen(cells, row, col) { 1216 word.append(Position(row: row, col: col)) 1217 row += delta.row 1218 col += delta.col 1219 } 1220 words.append(word) 1221 } 1222 } 1223 return words 1224 } 1225 1226 /// The exact-cell-answer projection: when a multi-cell word's clue answer 1227 /// matches exactly one cell's inferred solution, every other cell of that 1228 /// word loses its inferred solution (the answer lives wholly in that cell). 1229 private static func collectPositionsOutsideExactCellAnswer( 1230 word: [Position], 1231 clue: Clue, 1232 cells: [[Cell]], 1233 into positions: inout Set<Position> 1234 ) { 1235 guard word.count > 1, let answer = clue.answer else { return } 1236 let solutions = word.compactMap { solution(atRow: $0.row, col: $0.col, cells: cells) } 1237 guard solutions.count == word.count else { return } 1238 1239 let normalized = normalizedAnswer(answer) 1240 if normalized == normalizedAnswer(solutions.joined()) { return } 1241 1242 let matchingIndices = solutions.indices.filter { normalized == normalizedAnswer(solutions[$0]) } 1243 guard matchingIndices.count == 1, let matchingIndex = matchingIndices.first else { return } 1244 1245 for index in word.indices where index != matchingIndex { 1246 positions.insert(word[index]) 1247 } 1248 } 1249 1250 /// Distributes a clue's accepted answers onto the cells of its word: a 1251 /// single-cell word (or a cell holding the entire answer) accepts each 1252 /// alternative whole; otherwise each alternative is segmented against the 1253 /// word's canonical solutions and only the differing cell values are kept. 1254 private static func collectAcceptedCellValues( 1255 word: [Position], 1256 clue: Clue, 1257 cells: [[Cell]], 1258 into accepted: inout [Position: Set<String>] 1259 ) { 1260 let acceptedAnswers = clue.acceptedAnswers 1261 guard !acceptedAnswers.isEmpty else { return } 1262 1263 if word.count == 1, let position = word.first { 1264 accepted[position, default: []].formUnion(acceptedAnswers) 1265 return 1266 } 1267 1268 let solutions = word.map { solution(atRow: $0.row, col: $0.col, cells: cells) } 1269 let complete = solutions.compactMap { $0 } 1270 1271 var segmentations: [[String]] = [] 1272 if complete.count == word.count, 1273 (clue.answer ?? complete.joined()) == complete.joined() { 1274 for acceptedAnswer in acceptedAnswers { 1275 if let segments = segmentAcceptedAnswer(acceptedAnswer, canonicalSegments: complete) { 1276 segmentations.append(segments) 1277 } 1278 } 1279 } 1280 1281 for (index, position) in word.enumerated() { 1282 if let solution = solutions[index], let answer = clue.answer, 1283 normalizedAnswer(answer) == normalizedAnswer(solution) { 1284 accepted[position, default: []].formUnion(acceptedAnswers) 1285 continue 1286 } 1287 for segments in segmentations 1288 where segments.indices.contains(index) && segments[index] != complete[index] { 1289 accepted[position, default: []].insert(segments[index]) 1290 } 1291 } 1292 } 1293 1294 private static func solution(atRow row: Int, col: Int, cells: [[Cell]]) -> String? { 1295 guard case .open(let solution?, _, _) = cells[row][col] else { return nil } 1296 return solution 1297 } 1298 1299 private static func normalizedAnswer(_ value: String) -> String { 1300 value.precomposedStringWithCanonicalMapping.uppercased() 1301 } 1302 1303 private static func segmentAcceptedAnswer( 1304 _ acceptedAnswer: String, 1305 canonicalSegments: [String] 1306 ) -> [String]? { 1307 let accepted = Array(acceptedAnswer) 1308 let canonical = canonicalSegments.map(Array.init) 1309 1310 // Equal-length alternative: mirror the canonical cell segmentation 1311 // exactly. This covers whole-word Schrödinger answers where several 1312 // cells differ at once (e.g. CIGAR / PENIS over single-letter cells), 1313 // which the single-replacement search below cannot align. 1314 let canonicalLength = canonical.reduce(0) { $0 + $1.count } 1315 if accepted.count == canonicalLength { 1316 var segments: [String] = [] 1317 var offset = 0 1318 var differs = false 1319 for cell in canonical { 1320 let slice = accepted[offset..<offset + cell.count] 1321 if !slice.elementsEqual(cell) { differs = true } 1322 segments.append(String(slice)) 1323 offset += cell.count 1324 } 1325 return differs ? segments : nil 1326 } 1327 1328 for replacedIndex in canonical.indices { 1329 let prefixLength = canonical[..<replacedIndex].reduce(0) { $0 + $1.count } 1330 let suffixLength = canonical[canonical.index(after: replacedIndex)...].reduce(0) { $0 + $1.count } 1331 guard accepted.count >= prefixLength + suffixLength else { continue } 1332 1333 let prefix = canonical[..<replacedIndex].flatMap { $0 } 1334 let suffix = canonical[canonical.index(after: replacedIndex)...].flatMap { $0 } 1335 guard accepted.prefix(prefix.count).elementsEqual(prefix) else { continue } 1336 guard accepted.suffix(suffix.count).elementsEqual(suffix) else { continue } 1337 1338 let replacementEnd = accepted.count - suffixLength 1339 let replacement = Array(accepted[prefixLength..<replacementEnd]) 1340 guard !replacement.isEmpty, replacement != canonical[replacedIndex] else { continue } 1341 1342 var segments = canonical.map { String($0) } 1343 segments[replacedIndex] = String(replacement) 1344 return segments 1345 } 1346 1347 return nil 1348 } 1349 1350 private enum Direction: Hashable { 1351 case across 1352 case down 1353 1354 var delta: (row: Int, col: Int) { 1355 switch self { 1356 case .across: return (0, 1) 1357 case .down: return (1, 0) 1358 } 1359 } 1360 } 1361 1362 private static func wordCells( 1363 forClueNumber number: Int, 1364 direction: Direction, 1365 cells: [[Cell]], 1366 numbering: Numbering 1367 ) -> [(row: Int, col: Int)]? { 1368 guard let start = numbering.start(forNumber: number) else { return nil } 1369 switch direction { 1370 case .across where start.startsAcross: 1371 return wordCells(fromRow: start.row, col: start.col, direction: direction, cells: cells) 1372 case .down where start.startsDown: 1373 return wordCells(fromRow: start.row, col: start.col, direction: direction, cells: cells) 1374 default: 1375 return nil 1376 } 1377 } 1378 1379 private static func wordCells( 1380 fromRow row: Int, 1381 col: Int, 1382 direction: Direction, 1383 cells: [[Cell]] 1384 ) -> [(row: Int, col: Int)] { 1385 guard !isBlock(cells, row, col) else { return [] } 1386 let delta = direction.delta 1387 var startRow = row 1388 var startCol = col 1389 while isOpen(cells, startRow - delta.row, startCol - delta.col) { 1390 startRow -= delta.row 1391 startCol -= delta.col 1392 } 1393 1394 var result: [(row: Int, col: Int)] = [] 1395 var r = startRow 1396 var c = startCol 1397 while isOpen(cells, r, c) { 1398 result.append((r, c)) 1399 r += delta.row 1400 c += delta.col 1401 } 1402 return result 1403 } 1404 1405 /// Precomputed clue numbering for one grid. Built once per parse from the 1406 /// block topology, then queried in O(1) by the answer-application passes — 1407 /// replacing the former per-cell full-grid rescans that made those passes 1408 /// O(cells²). The counter walk here mirrors the .xd numbering convention: 1409 /// row-major, incrementing at every cell that starts an across or down word. 1410 private struct Numbering { 1411 /// Start cell → its clue number. 1412 private let numberByPosition: [Position: Int] 1413 /// Clue number → its start cell and which directions it opens. 1414 private let startByNumber: [Int: (row: Int, col: Int, startsAcross: Bool, startsDown: Bool)] 1415 1416 static func build(_ cells: [[Cell]]) -> Numbering { 1417 var numberByPosition: [Position: Int] = [:] 1418 var startByNumber: [Int: (row: Int, col: Int, startsAcross: Bool, startsDown: Bool)] = [:] 1419 var counter = 1 1420 for r in cells.indices { 1421 for c in cells[r].indices { 1422 guard isOpen(cells, r, c) else { continue } 1423 let startsAcross = !isOpen(cells, r, c - 1) && isOpen(cells, r, c + 1) 1424 let startsDown = !isOpen(cells, r - 1, c) && isOpen(cells, r + 1, c) 1425 guard startsAcross || startsDown else { continue } 1426 numberByPosition[Position(row: r, col: c)] = counter 1427 startByNumber[counter] = (r, c, startsAcross, startsDown) 1428 counter += 1 1429 } 1430 } 1431 return Numbering(numberByPosition: numberByPosition, startByNumber: startByNumber) 1432 } 1433 1434 func number(atRow row: Int, col: Int) -> Int? { 1435 numberByPosition[Position(row: row, col: col)] 1436 } 1437 1438 func start(forNumber number: Int) -> (row: Int, col: Int, startsAcross: Bool, startsDown: Bool)? { 1439 startByNumber[number] 1440 } 1441 } 1442 1443 private static func isOpen(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool { 1444 guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return false } 1445 return !isBlock(cells, row, col) 1446 } 1447 1448 private static func isBlock(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool { 1449 guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return true } 1450 if case .block = cells[row][col] { return true } 1451 return false 1452 } 1453 }