← All repositories

crossmate

A collaborative crossword app for iPhone and iPad

git clone https://code.inqk.net/crossmate.git


Crossmate/Models/Puzzle.swift (23455B)

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