crossmate

XD.swift (26545B)

---

 import Foundation
 
 /// Minimal `.xd` decoder. See https://github.com/century-arcade/xd for the
 /// full specification. Supports just enough of the format to parse our
 /// bundled puzzles: metadata, grid (with rebus), and across/down clues.
 struct XD: Sendable {
     static let currentCmVersion = 2
 
     let title: String?
     let publisher: String?
     let author: String?
     let copyright: String?
     let date: Date?
     let cmVersion: Int
     let specialKind: Puzzle.Special?
     let width: Int
     let height: Int
     let cells: [[Cell]]
     let acrossClues: [Clue]
     let downClues: [Clue]
     let relatives: [[ClueRef]]
 
     /// A single clue identified by its number and direction. Used to describe
     /// groups of mutually-related clues (a theme's revealer plus the answers
     /// it references, or a simple "See 14-Across" pair).
     struct ClueRef: Sendable, Hashable {
         let number: Int
         let direction: Puzzle.Direction
     }
 
     /// A single grid cell as it appears in the .xd source. Open cells carry
     /// an optional solution string which may be 1+ characters long once any
     /// `Rebus:` mapping has been applied, plus a flag indicating whether the
     /// cell is "special" (circled or shaded — the kind is per-puzzle and
     /// lives on `XD.specialKind`).
     enum Cell: Sendable, Equatable {
         case block
         case open(solution: String?, acceptedSolutions: Set<String>, isSpecial: Bool)
     }
 
     struct Clue: Sendable, Equatable {
         let number: Int
         let text: String
         let answer: String?
         let metadata: [String: [String]]
 
         var acceptedAnswers: [String] {
             metadata["Accept", default: []].flatMap(Self.parseEscapedTokens)
         }
 
         private static func parseEscapedTokens(_ source: String) -> [String] {
             var tokens: [String] = []
             var current = ""
             var escaping = false
 
             for ch in source {
                 if escaping {
                     current.append(ch)
                     escaping = false
                 } else if ch == "\\" {
                     escaping = true
                 } else if ch.isWhitespace {
                     if !current.isEmpty {
                         tokens.append(current)
                         current = ""
                     }
                 } else {
                     current.append(ch)
                 }
             }
 
             if escaping {
                 current.append("\\")
             }
             if !current.isEmpty {
                 tokens.append(current)
             }
             return tokens
         }
     }
 
     enum ParseError: Error, CustomStringConvertible {
         case missingGrid
         case missingClues
         case raggedGrid
         case malformedClue(String)
         case unknownGridCharacter(Character)
 
         var description: String {
             switch self {
             case .missingGrid:
                 return ".xd source has no grid section"
             case .missingClues:
                 return ".xd source has no clues section"
             case .raggedGrid:
                 return ".xd grid rows have inconsistent widths"
             case .malformedClue(let line):
                 return "malformed .xd clue: \(line)"
             case .unknownGridCharacter(let ch):
                 return "unknown .xd grid character: \(ch)"
             }
         }
     }
 
     static func parse(_ source: String) throws -> XD {
         let sections = splitIntoSections(source)
         guard sections.count >= 2 else { throw ParseError.missingGrid }
         guard sections.count >= 3 else { throw ParseError.missingClues }
 
         let metadata = parseMetadata(sections[0])
         let rebus = parseRebusHeader(metadata["Rebus"])
         let specialKind = parseSpecialHeader(metadata["Special"])
         let relatives = parseRelativesHeader(metadata["Relatives"])
         let (rawCells, width, height) = try parseGrid(sections[1], rebus: rebus)
         let (across, down) = try parseClues(sections[2])
         let cells = applyAcceptedAnswers(cells: rawCells, across: across, down: down)
 
         return XD(
             title: metadata["Title"],
             publisher: metadata["Publisher"],
             author: metadata["Author"],
             copyright: metadata["Copyright"],
             date: parseDateHeader(metadata["Date"]),
             cmVersion: parseCmVersionHeader(metadata["CmVer"]),
             specialKind: specialKind,
             width: width,
             height: height,
             cells: cells,
             acrossClues: across,
             downClues: down,
             relatives: relatives
         )
     }
 
     // MARK: - Sections
 
     /// Splits the source into top-level sections. Per the .xd spec, sections
     /// are delimited either by runs of two or more blank lines, or by
     /// `## SectionName` header lines. We accept both: blank-line runs end the
     /// current section, and a `##` line also ends the current section (the
     /// header line itself is consumed and discarded — section identity comes
     /// from implicit order).
     private static func splitIntoSections(_ source: String) -> [[String]] {
         let lines = source
             .split(separator: "\n", omittingEmptySubsequences: false)
             .map(String.init)
 
         var sections: [[String]] = []
         var current: [String] = []
         var blankRun = 0
 
         func flush() {
             while current.last?.trimmingCharacters(in: .whitespaces).isEmpty == true {
                 current.removeLast()
             }
             while current.first?.trimmingCharacters(in: .whitespaces).isEmpty == true {
                 current.removeFirst()
             }
             if !current.isEmpty {
                 sections.append(current)
             }
             current = []
         }
 
         for rawLine in lines {
             let line = rawLine.trimmingCharacters(in: CharacterSet(charactersIn: "\r"))
             let trimmed = line.trimmingCharacters(in: .whitespaces)
 
             if trimmed.hasPrefix("## ") || trimmed == "##" {
                 flush()
                 blankRun = 0
                 continue
             }
 
             if trimmed.isEmpty {
                 blankRun += 1
                 if blankRun >= 2 {
                     flush()
                 }
                 continue
             }
 
             blankRun = 0
             current.append(line)
         }
         flush()
         return sections
     }
 
     // MARK: - Metadata
 
     private static func parseMetadata(_ lines: [String]) -> [String: String] {
         var dict: [String: String] = [:]
         for line in lines {
             guard let colon = line.firstIndex(of: ":") else { continue }
             let key = line[..<colon].trimmingCharacters(in: .whitespaces)
             let value = line[line.index(after: colon)...].trimmingCharacters(in: .whitespaces)
             if !key.isEmpty {
                 dict[key] = value
             }
         }
         return dict
     }
 
     /// Parses a `Rebus:` header value such as `1=ONE 2=TWO 3=THREE` into a
     /// map from grid placeholder character to its expanded solution string.
     private static func parseRebusHeader(_ value: String?) -> [Character: String] {
         guard let value, !value.isEmpty else { return [:] }
         var map: [Character: String] = [:]
         for entry in value.split(whereSeparator: { $0.isWhitespace }) {
             guard let equals = entry.firstIndex(of: "=") else { continue }
             let key = entry[..<equals]
             let val = entry[entry.index(after: equals)...]
             guard key.count == 1, let keyChar = key.first, !val.isEmpty else { continue }
             map[keyChar] = String(val)
         }
         return map
     }
 
     /// Parses a `Date:` header value as strict ISO `YYYY-MM-DD`. Returns
     /// `nil` if the value is missing, empty, or in any other format.
     private static func parseDateHeader(_ value: String?) -> Date? {
         guard let value else { return nil }
         let trimmed = value.trimmingCharacters(in: .whitespaces)
         guard let match = trimmed.firstMatch(of: /^(\d{4})-(\d{2})-(\d{2})$/),
               let year = Int(match.1),
               let month = Int(match.2),
               let day = Int(match.3)
         else { return nil }
         var comps = DateComponents()
         comps.year = year
         comps.month = month
         comps.day = day
         return Calendar(identifier: .gregorian).date(from: comps)
     }
 
     /// Parses a Crossmate `CmVer:` header. Missing versions are version 1
     /// so legacy sources establish the baseline content version.
     private static func parseCmVersionHeader(_ value: String?) -> Int {
         guard let value else { return 1 }
         let trimmed = value.trimmingCharacters(in: .whitespaces)
         guard let version = Int(trimmed), version >= 1 else { return 1 }
         return version
     }
 
     /// Parses a `Relatives:` header value into groups of cross-referenced
     /// clues. Groups are separated by `;`, tokens within a group by `,`, and
     /// each token is `{number}{A|D}` (e.g. `17A`, `57A`). This is a Crossmate
     /// extension to `.xd`; unknown/invalid tokens are silently dropped.
     /// Single-token groups are allowed so formatted NYT clues can mark their
     /// own answer cells as thematic.
     private static func parseRelativesHeader(_ value: String?) -> [[ClueRef]] {
         guard let value, !value.isEmpty else { return [] }
         var groups: [[ClueRef]] = []
         for groupSlice in value.split(separator: ";") {
             var refs: [ClueRef] = []
             for tokenSlice in groupSlice.split(separator: ",") {
                 let token = tokenSlice.trimmingCharacters(in: .whitespaces)
                 guard let last = token.last else { continue }
                 let direction: Puzzle.Direction
                 switch last {
                 case "A", "a": direction = .across
                 case "D", "d": direction = .down
                 default: continue
                 }
                 guard let number = Int(token.dropLast()), number > 0 else { continue }
                 refs.append(ClueRef(number: number, direction: direction))
             }
             if !refs.isEmpty { groups.append(refs) }
         }
         return groups
     }
 
     /// Parses a `Special:` header value into a `Puzzle.Special` kind. The
     /// .xd spec recognises `shaded` and `circle` as the two values; we accept
     /// either case-insensitively and treat anything else as no special kind.
     private static func parseSpecialHeader(_ value: String?) -> Puzzle.Special? {
         guard let value else { return nil }
         switch value.trimmingCharacters(in: .whitespaces).lowercased() {
         case "shaded": return .shaded
         case "circle", "circled": return .circled
         default: return nil
         }
     }
 
     // MARK: - Grid
 
     private static func parseGrid(
         _ lines: [String],
         rebus: [Character: String]
     ) throws -> (cells: [[Cell]], width: Int, height: Int) {
         var rows: [[Cell]] = []
         var width: Int? = nil
 
         for line in lines {
             let trimmed = line.trimmingCharacters(in: .whitespaces)
             if trimmed.isEmpty { continue }
 
             var row: [Cell] = []
             for ch in trimmed {
                 row.append(try gridCell(for: ch, rebus: rebus))
             }
 
             if let w = width, row.count != w {
                 throw ParseError.raggedGrid
             }
             width = row.count
             rows.append(row)
         }
 
         guard let w = width, !rows.isEmpty else { throw ParseError.missingGrid }
         return (rows, w, rows.count)
     }
 
     private static func gridCell(
         for ch: Character,
         rebus: [Character: String]
     ) throws -> Cell {
         // Blocks: '#' is a normal block; '_' marks a non-existing cell on the
         // edge of an irregularly-shaped grid. Both render as non-playable.
         if ch == "#" || ch == "_" {
             return .block
         }
         // '.' is an open cell with no known solution.
         if ch == "." {
             return .open(solution: nil, acceptedSolutions: [], isSpecial: false)
         }
         // Per the .xd spec, lowercase letters always indicate a special cell
         // (circled or shaded — the kind is in the `Special:` header). They
         // may *also* appear in the Rebus header, in which case the solution
         // is the rebus expansion; otherwise it's the uppercased letter.
         let isLowercaseLetter = ch.isLetter && ch.isLowercase
         if let expansion = rebus[ch] {
             return .open(solution: expansion.uppercased(), acceptedSolutions: [], isSpecial: isLowercaseLetter)
         }
         if ch.isLetter {
             return .open(solution: String(ch).uppercased(), acceptedSolutions: [], isSpecial: isLowercaseLetter)
         }
         throw ParseError.unknownGridCharacter(ch)
     }
 
     // MARK: - Clues
 
     private static func parseClues(
         _ lines: [String]
     ) throws -> (across: [Clue], down: [Clue]) {
         struct ClueKey: Hashable {
             let number: Int
             let direction: Character
         }
 
         var clueTexts: [ClueKey: String] = [:]
         var clueAnswers: [ClueKey: String] = [:]
         var clueOrder: [ClueKey] = []
         var metadataByClue: [ClueKey: [String: [String]]] = [:]
 
         for rawLine in lines {
             let line = rawLine.trimmingCharacters(in: .whitespaces)
             if line.isEmpty { continue }
 
             guard let leading = line.first, leading == "A" || leading == "D" else {
                 throw ParseError.malformedClue(line)
             }
 
             if let match = line.firstMatch(of: /^([AD])(\d+)\s+\^([^:]+):\s*(.*)$/) {
                 guard let number = Int(match.2) else { throw ParseError.malformedClue(line) }
                 let key = ClueKey(number: number, direction: Character(String(match.1)))
                 let metadataKey = String(match.3).trimmingCharacters(in: .whitespaces)
                 guard !metadataKey.isEmpty else { throw ParseError.malformedClue(line) }
                 metadataByClue[key, default: [:]][metadataKey, default: []].append(String(match.4))
                 continue
             }
 
             guard let dot = line.firstIndex(of: ".") else {
                 throw ParseError.malformedClue(line)
             }
 
             let numberSlice = line[line.index(after: line.startIndex)..<dot]
             guard let number = Int(numberSlice) else {
                 throw ParseError.malformedClue(line)
             }
             let key = ClueKey(number: number, direction: leading)
 
             var afterDot = line[line.index(after: dot)...]
                 .trimmingCharacters(in: .whitespaces)
 
             if let tilde = afterDot.range(of: " ~ ", options: .backwards) {
                 let answer = afterDot[tilde.upperBound...]
                     .trimmingCharacters(in: .whitespaces)
                 if !answer.isEmpty {
                     clueAnswers[key] = answer
                 }
                 afterDot = String(afterDot[..<tilde.lowerBound])
                     .trimmingCharacters(in: .whitespaces)
             }
 
             if clueTexts[key] == nil {
                 clueOrder.append(key)
             }
             clueTexts[key] = afterDot
         }
 
         var across: [Clue] = []
         var down: [Clue] = []
         for key in clueOrder {
             let clue = Clue(
                 number: key.number,
                 text: clueTexts[key] ?? "",
                 answer: clueAnswers[key],
                 metadata: metadataByClue[key] ?? [:]
             )
             if key.direction == "A" {
                 across.append(clue)
             } else {
                 down.append(clue)
             }
         }
         return (across, down)
     }
 
     private static func applyAcceptedAnswers(
         cells: [[Cell]],
         across: [Clue],
         down: [Clue]
     ) -> [[Cell]] {
         var cells = cells
         let acrossByNumber = Dictionary(uniqueKeysWithValues: across.map { ($0.number, $0) })
         let downByNumber = Dictionary(uniqueKeysWithValues: down.map { ($0.number, $0) })
         let positionsOutsideExactCellAnswers = positionsOutsideExactCellAnswers(
             cells: cells,
             across: acrossByNumber,
             down: downByNumber
         )
 
         for r in cells.indices {
             for c in cells[r].indices {
                 guard case .open(let solution, let acceptedSolutions, let isSpecial) = cells[r][c] else { continue }
                 let position = Position(row: r, col: c)
                 let effectiveSolution = positionsOutsideExactCellAnswers.contains(position) ? nil : solution
                 var merged = acceptedSolutions
                 if let accepted = acceptedCellValues(
                     atRow: r,
                     col: c,
                     direction: .across,
                     cells: cells,
                     cluesByNumber: acrossByNumber
                 ) {
                     merged.formUnion(accepted)
                 }
                 if let accepted = acceptedCellValues(
                     atRow: r,
                     col: c,
                     direction: .down,
                     cells: cells,
                     cluesByNumber: downByNumber
                 ) {
                     merged.formUnion(accepted)
                 }
                 if effectiveSolution != solution || merged != acceptedSolutions {
                     cells[r][c] = .open(solution: effectiveSolution, acceptedSolutions: merged, isSpecial: isSpecial)
                 }
             }
         }
 
         return cells
     }
 
     private struct Position: Hashable {
         let row: Int
         let col: Int
     }
 
     private static func positionsOutsideExactCellAnswers(
         cells: [[Cell]],
         across: [Int: Clue],
         down: [Int: Clue]
     ) -> Set<Position> {
         var positions: Set<Position> = []
         var seenWords: Set<WordKey> = []
         for r in cells.indices {
             for c in cells[r].indices {
                 positions.formUnion(
                     positionsOutsideExactCellAnswer(
                         fromRow: r,
                         col: c,
                         direction: .across,
                         cells: cells,
                         cluesByNumber: across,
                         seenWords: &seenWords
                     )
                 )
                 positions.formUnion(
                     positionsOutsideExactCellAnswer(
                         fromRow: r,
                         col: c,
                         direction: .down,
                         cells: cells,
                         cluesByNumber: down,
                         seenWords: &seenWords
                     )
                 )
             }
         }
         return positions
     }
 
     private struct WordKey: Hashable {
         let direction: Direction
         let row: Int
         let col: Int
     }
 
     private static func positionsOutsideExactCellAnswer(
         fromRow row: Int,
         col: Int,
         direction: Direction,
         cells: [[Cell]],
         cluesByNumber: [Int: Clue],
         seenWords: inout Set<WordKey>
     ) -> Set<Position> {
         let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells)
         guard let first = word.first else { return [] }
         let key = WordKey(direction: direction, row: first.row, col: first.col)
         guard seenWords.insert(key).inserted,
               word.count > 1,
               let number = clueNumber(forWord: word, cells: cells),
               let clue = cluesByNumber[number]
         else { return [] }
 
         guard let answer = clue.answer else { return [] }
         let solutions = word.compactMap { position -> String? in
             guard case .open(let solution?, _, _) = cells[position.row][position.col] else { return nil }
             return solution
         }
         guard solutions.count == word.count else { return [] }
 
         if normalizedAnswer(answer) == normalizedAnswer(solutions.joined()) {
             return []
         }
 
         let matchingIndices = solutions.indices.filter { normalizedAnswer(answer) == normalizedAnswer(solutions[$0]) }
         guard matchingIndices.count == 1, let matchingIndex = matchingIndices.first else { return [] }
 
         return Set(word.indices.compactMap { index in
             index == matchingIndex ? nil : Position(row: word[index].row, col: word[index].col)
         })
     }
 
     private static func acceptedCellValues(
         atRow row: Int,
         col: Int,
         direction: Direction,
         cells: [[Cell]],
         cluesByNumber: [Int: Clue]
     ) -> Set<String>? {
         let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells)
         guard let wordIndex = word.firstIndex(where: { $0.row == row && $0.col == col }) else { return nil }
         guard let number = clueNumber(forWord: word, cells: cells),
               let clue = cluesByNumber[number],
               !clue.acceptedAnswers.isEmpty else { return nil }
 
         if let solution = solution(atRow: row, col: col, cells: cells),
            let answer = clue.answer,
            normalizedAnswer(answer) == normalizedAnswer(solution) {
             return Set(clue.acceptedAnswers)
         }
 
         if word.count == 1 {
             return Set(clue.acceptedAnswers)
         }
 
         let solutions = word.compactMap { position -> String? in
             guard case .open(let solution?, _, _) = cells[position.row][position.col] else { return nil }
             return solution
         }
         guard solutions.count == word.count else { return nil }
 
         let canonicalAnswer = clue.answer ?? solutions.joined()
         guard canonicalAnswer == solutions.joined() else { return nil }
 
         var accepted: Set<String> = []
         for acceptedAnswer in clue.acceptedAnswers {
             guard let segments = segmentAcceptedAnswer(acceptedAnswer, canonicalSegments: solutions),
                   segments.indices.contains(wordIndex),
                   segments[wordIndex] != solutions[wordIndex] else { continue }
             accepted.insert(segments[wordIndex])
         }
         return accepted
     }
 
     private static func solution(atRow row: Int, col: Int, cells: [[Cell]]) -> String? {
         guard case .open(let solution?, _, _) = cells[row][col] else { return nil }
         return solution
     }
 
     private static func normalizedAnswer(_ value: String) -> String {
         value.precomposedStringWithCanonicalMapping.uppercased()
     }
 
     private static func segmentAcceptedAnswer(
         _ acceptedAnswer: String,
         canonicalSegments: [String]
     ) -> [String]? {
         let accepted = Array(acceptedAnswer)
         let canonical = canonicalSegments.map(Array.init)
 
         for replacedIndex in canonical.indices {
             let prefixLength = canonical[..<replacedIndex].reduce(0) { $0 + $1.count }
             let suffixLength = canonical[canonical.index(after: replacedIndex)...].reduce(0) { $0 + $1.count }
             guard accepted.count >= prefixLength + suffixLength else { continue }
 
             let prefix = canonical[..<replacedIndex].flatMap { $0 }
             let suffix = canonical[canonical.index(after: replacedIndex)...].flatMap { $0 }
             guard accepted.prefix(prefix.count).elementsEqual(prefix) else { continue }
             guard accepted.suffix(suffix.count).elementsEqual(suffix) else { continue }
 
             let replacementEnd = accepted.count - suffixLength
             let replacement = Array(accepted[prefixLength..<replacementEnd])
             guard !replacement.isEmpty, replacement != canonical[replacedIndex] else { continue }
 
             var segments = canonical.map { String($0) }
             segments[replacedIndex] = String(replacement)
             return segments
         }
 
         return nil
     }
 
     private enum Direction: Hashable {
         case across
         case down
 
         var delta: (row: Int, col: Int) {
             switch self {
             case .across: return (0, 1)
             case .down: return (1, 0)
             }
         }
     }
 
     private static func clueNumber(atRow row: Int, col: Int, direction: Direction, cells: [[Cell]]) -> Int? {
         let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells)
         return clueNumber(forWord: word, cells: cells)
     }
 
     private static func clueNumber(forWord word: [(row: Int, col: Int)], cells: [[Cell]]) -> Int? {
         guard let first = word.first else { return nil }
         return computedNumber(atRow: first.row, col: first.col, cells: cells)
     }
 
     private static func wordCells(
         fromRow row: Int,
         col: Int,
         direction: Direction,
         cells: [[Cell]]
     ) -> [(row: Int, col: Int)] {
         guard !isBlock(cells, row, col) else { return [] }
         let delta = direction.delta
         var startRow = row
         var startCol = col
         while isOpen(cells, startRow - delta.row, startCol - delta.col) {
             startRow -= delta.row
             startCol -= delta.col
         }
 
         var result: [(row: Int, col: Int)] = []
         var r = startRow
         var c = startCol
         while isOpen(cells, r, c) {
             result.append((r, c))
             r += delta.row
             c += delta.col
         }
         return result
     }
 
     private static func computedNumber(atRow row: Int, col: Int, cells: [[Cell]]) -> Int? {
         var counter = 1
         for r in cells.indices {
             for c in cells[r].indices {
                 guard isOpen(cells, r, c) else { continue }
                 let startsAcross = !isOpen(cells, r, c - 1) && isOpen(cells, r, c + 1)
                 let startsDown = !isOpen(cells, r - 1, c) && isOpen(cells, r + 1, c)
                 if startsAcross || startsDown {
                     if r == row, c == col { return counter }
                     counter += 1
                 }
             }
         }
         return nil
     }
 
     private static func isOpen(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool {
         guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return false }
         return !isBlock(cells, row, col)
     }
 
     private static func isBlock(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool {
         guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return true }
         if case .block = cells[row][col] { return true }
         return false
     }
 }