Puzzle.swift (12714B)
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 "special" cells (lowercase letters in `.xd`) should be drawn. 15 /// A puzzle can use circles or shading, but not both at once. 16 enum Special: Sendable, Hashable { 17 case circled 18 case shaded 19 } 20 21 let title: String 22 let publisher: String? 23 let author: String? 24 let date: Date? 25 let specialKind: Special? 26 let width: Int 27 let height: Int 28 let cells: [[Cell]] 29 let acrossClues: [Clue] 30 let downClues: [Clue] 31 /// Cross-reference clue groups, sourced from prose like "See 11-Down" / 32 /// "With X- and Y-Down" — connections the constructor explicitly 33 /// surfaced in the clue text, safe to highlight as a navigation aid. 34 /// Stored as clue identifiers (not cell positions) so `relatedCells` can 35 /// gate on the cursor's reading direction: only when the focus cell's 36 /// current-direction word is itself one of the group's clues. 37 /// Themer/revealer links from `XD.relatives` are intentionally not 38 /// represented here so the UI doesn't reveal trick relationships before 39 /// the solver works them out. 40 let crossReferenceGroups: [Set<ClueRef>] 41 42 struct ClueRef: Hashable, Sendable { 43 let number: Int 44 let direction: Direction 45 } 46 47 struct Cell: Sendable, Hashable { 48 let row: Int 49 let col: Int 50 let isBlock: Bool 51 let isSpecial: Bool 52 let number: Int? 53 let solution: String? 54 let acceptedSolutions: Set<String> 55 56 func accepts(_ entry: String) -> Bool { 57 guard !entry.isEmpty else { return false } 58 let normalizedEntry = Self.normalizedAnswer(entry) 59 if let solution, normalizedEntry == Self.normalizedAnswer(solution) { 60 return true 61 } 62 return acceptedSolutions.contains(normalizedEntry) 63 } 64 65 static func normalizedAnswer(_ value: String) -> String { 66 value.precomposedStringWithCanonicalMapping.uppercased() 67 } 68 } 69 70 struct Clue: Sendable, Hashable, Identifiable { 71 let number: Int 72 let text: String 73 var id: Int { number } 74 } 75 76 enum LoadError: Error { 77 case notFound(String) 78 } 79 80 init(xd: XD) { 81 self.title = xd.title ?? "Untitled" 82 self.publisher = xd.publisher 83 self.author = xd.author 84 self.date = xd.date 85 self.specialKind = xd.specialKind 86 self.width = xd.width 87 self.height = xd.height 88 89 // Clue numbering is computed from grid topology rather than carried 90 // in the source, since .xd has no per-cell number field. A cell is 91 // numbered if it begins an across or down word — i.e. its preceding 92 // neighbour in that direction is a block (or the edge) and its 93 // following neighbour is open. 94 var cells: [[Cell]] = [] 95 cells.reserveCapacity(xd.height) 96 var counter = 1 97 for r in 0..<xd.height { 98 var rowCells: [Cell] = [] 99 rowCells.reserveCapacity(xd.width) 100 for c in 0..<xd.width { 101 switch xd.cells[r][c] { 102 case .block: 103 rowCells.append(Cell(row: r, col: c, isBlock: true, isSpecial: false, number: nil, solution: nil, acceptedSolutions: [])) 104 case .open(let solution, let acceptedSolutions, let isSpecial): 105 let leftBlock = c == 0 || Self.isBlock(xd.cells, r, c - 1) 106 let rightOpen = c + 1 < xd.width && !Self.isBlock(xd.cells, r, c + 1) 107 let topBlock = r == 0 || Self.isBlock(xd.cells, r - 1, c) 108 let bottomOpen = r + 1 < xd.height && !Self.isBlock(xd.cells, r + 1, c) 109 let startsWord = (leftBlock && rightOpen) || (topBlock && bottomOpen) 110 let number: Int? 111 if startsWord { 112 number = counter 113 counter += 1 114 } else { 115 number = nil 116 } 117 let normalizedAccepted = Set(acceptedSolutions.map { Cell.normalizedAnswer($0) }) 118 rowCells.append(Cell(row: r, col: c, isBlock: false, isSpecial: isSpecial, number: number, solution: solution, acceptedSolutions: normalizedAccepted)) 119 } 120 } 121 cells.append(rowCells) 122 } 123 self.cells = cells 124 let acrossClues = xd.acrossClues.map { Clue(number: $0.number, text: $0.text) } 125 let downClues = xd.downClues.map { Clue(number: $0.number, text: $0.text) } 126 self.acrossClues = acrossClues 127 self.downClues = downClues 128 self.crossReferenceGroups = Self.buildCrossReferenceGroups( 129 across: acrossClues, 130 down: downClues 131 ) 132 } 133 134 /// Derives cross-reference groups from the clue text itself. NYT-style 135 /// prose like `See 11-Down` or `With 31- and 43-Down, …` is the only 136 /// signal we trust — the constructor explicitly pointed the solver at 137 /// these connections, so highlighting them isn't a spoiler. Groups are 138 /// connected components: any clues mentioned together (transitively) 139 /// land in the same set as `(number, direction)` identifiers. 140 private static func buildCrossReferenceGroups( 141 across: [Clue], 142 down: [Clue] 143 ) -> [Set<ClueRef>] { 144 struct Entry { let ref: ClueRef; let text: String } 145 var entries: [Entry] = [] 146 var indexByRef: [ClueRef: Int] = [:] 147 for clue in across { 148 let ref = ClueRef(number: clue.number, direction: .across) 149 indexByRef[ref] = entries.count 150 entries.append(Entry(ref: ref, text: clue.text)) 151 } 152 for clue in down { 153 let ref = ClueRef(number: clue.number, direction: .down) 154 indexByRef[ref] = entries.count 155 entries.append(Entry(ref: ref, text: clue.text)) 156 } 157 158 var adjacency: [Int: Set<Int>] = [:] 159 for (i, entry) in entries.enumerated() { 160 guard let refs = parseCrossReferences(in: entry.text) else { continue } 161 for ref in refs { 162 guard let j = indexByRef[ref], j != i else { continue } 163 adjacency[i, default: []].insert(j) 164 adjacency[j, default: []].insert(i) 165 } 166 } 167 168 var visited: Set<Int> = [] 169 var groups: [Set<ClueRef>] = [] 170 for start in adjacency.keys.sorted() { 171 guard !visited.contains(start) else { continue } 172 var component: Set<ClueRef> = [] 173 var stack = [start] 174 while let node = stack.popLast() { 175 guard visited.insert(node).inserted else { continue } 176 component.insert(entries[node].ref) 177 for n in adjacency[node, default: []] where !visited.contains(n) { 178 stack.append(n) 179 } 180 } 181 if component.count >= 2 { groups.append(component) } 182 } 183 return groups 184 } 185 186 /// Pulls `(number, direction)` pairs out of `See …-Down`, 187 /// `With X- and Y-Down`, revealer-style `X-, Y- or Z-Across`, 188 /// and mixed-direction prose like `X-Across and Y-Down`. 189 /// A trailing `Across`/`Down` applies to every number in that list 190 /// segment, matching NYT's convention. 191 private static func parseCrossReferences(in text: String) -> [ClueRef]? { 192 var refs: [ClueRef] = [] 193 var seen: Set<ClueRef> = [] 194 195 func append(_ newRefs: [ClueRef]?) { 196 guard let newRefs else { return } 197 for ref in newRefs where seen.insert(ref).inserted { 198 refs.append(ref) 199 } 200 } 201 202 let listPattern = /([\d\s,\-&\/]+?(?:(?:and|or)\s+[\d\s,\-&\/]+?)?)(Across|Down)\b/ 203 for match in text.matches(of: listPattern) { 204 guard String(match.1).contains(/\d+\s*-/) else { continue } 205 append(clueRefs(numbersText: String(match.1), directionText: String(match.2))) 206 } 207 if !refs.isEmpty { 208 return refs 209 } 210 211 let anchoredPattern = /\b(?:See|With)\s+([\d\s,\-&\/]+?(?:(?:and|or)\s+[\d\s,\-&\/]+?)?)(Across|Down)\b/ 212 if let match = text.firstMatch(of: anchoredPattern) { 213 append(clueRefs(numbersText: String(match.1), directionText: String(match.2))) 214 } 215 return refs.isEmpty ? nil : refs 216 } 217 218 private static func clueRefs(numbersText: String, directionText: String) -> [ClueRef]? { 219 let direction: Direction = directionText == "Across" ? .across : .down 220 let numbers = numbersText.matches(of: /\d+/).compactMap { Int($0.0) } 221 guard !numbers.isEmpty else { return nil } 222 return numbers.map { ClueRef(number: $0, direction: direction) } 223 } 224 225 private static func findCell(in cells: [[Cell]], numbered number: Int) -> Cell? { 226 for row in cells { 227 for cell in row where cell.number == number { 228 return cell 229 } 230 } 231 return nil 232 } 233 234 /// Returns the cell labelled with the given clue number, if any. 235 func cell(numbered number: Int) -> Cell? { 236 for row in cells { 237 for cell in row where cell.number == number { 238 return cell 239 } 240 } 241 return nil 242 } 243 244 /// Returns every open cell that belongs to the word containing 245 /// `(row, col)` in the given direction. Empty if the starting cell is a 246 /// block, off-grid, or has no neighbour in that direction (a "word" of 247 /// length 1 isn't really a word). 248 func wordCells(atRow row: Int, col: Int, direction: Direction) -> [Cell] { 249 guard row >= 0, row < height, col >= 0, col < width else { return [] } 250 guard !cells[row][col].isBlock else { return [] } 251 let (dr, dc): (Int, Int) = direction == .across ? (0, 1) : (1, 0) 252 var startRow = row 253 var startCol = col 254 while startRow - dr >= 0, startRow - dr < height, 255 startCol - dc >= 0, startCol - dc < width, 256 !cells[startRow - dr][startCol - dc].isBlock { 257 startRow -= dr 258 startCol -= dc 259 } 260 var result: [Cell] = [] 261 var r = startRow 262 var c = startCol 263 while r >= 0, r < height, c >= 0, c < width, !cells[r][c].isBlock { 264 result.append(cells[r][c]) 265 r += dr 266 c += dc 267 } 268 return result.count > 1 ? result : [] 269 } 270 271 /// Returns the cells of every clue cross-referenced from the focus 272 /// word. Gated on direction: only fires when the focus cell's word in 273 /// the *current* direction is itself one of the cross-referenced 274 /// clues. Reading the same cell in the opposite direction (where it 275 /// belongs to a different word) returns nothing. 276 func relatedCells(atRow row: Int, col: Int, direction: Direction) -> Set<GridPosition> { 277 let focusWord = wordCells(atRow: row, col: col, direction: direction) 278 guard let start = focusWord.first, let number = start.number else { return [] } 279 let focusClue = ClueRef(number: number, direction: direction) 280 var related: Set<GridPosition> = [] 281 for group in crossReferenceGroups where group.contains(focusClue) { 282 for clue in group where clue != focusClue { 283 guard let startCell = cell(numbered: clue.number) else { continue } 284 var r = startCell.row 285 var c = startCell.col 286 while r >= 0, r < height, c >= 0, c < width, !cells[r][c].isBlock { 287 related.insert(GridPosition(row: r, col: c)) 288 switch clue.direction { 289 case .across: c += 1 290 case .down: r += 1 291 } 292 } 293 } 294 } 295 return related 296 } 297 298 private static func isBlock(_ cells: [[XD.Cell]], _ row: Int, _ col: Int) -> Bool { 299 if case .block = cells[row][col] { return true } 300 return false 301 } 302 303 static func load(resource: String) throws -> Puzzle { 304 guard let url = Bundle.main.url(forResource: resource, withExtension: "xd") else { 305 throw LoadError.notFound("\(resource).xd") 306 } 307 let source = try String(contentsOf: url, encoding: .utf8) 308 let xd = try XD.parse(source) 309 return Puzzle(xd: xd) 310 } 311 }