Crossmate/Models/XD.swift (64173B)
1import Foundation
2
3
4
5
6struct XD: Sendable {
7
8
9
10
11
12
13 static let currentConverterVersion = 13
14
15
16
17
18
19
20 static let currentParserVersion = 11
21
22
23
24
25
26
27 static let maxSourceBytes = 262_144
28
29
30
31
32
33
34 static let maxClueTextLength = 1_024
35
36
37
38
39
40
41
42 static let maxGridDimension = 128
43
44
45
46
47 static let maxClueCount = 8_192
48
49
50
51
52 static let maxAcceptedAnswersPerClue = 32
53
54
55
56
57
58
59
60 static let maxRebusValueLength = 64
61
62
63
64
65
66
67 static let maxDecorationDefinitions = 4_096
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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
104
105
106 let decorations: [GridPosition: [Decoration]]
107
108
109
110
111 struct ClueRef: Sendable, Hashable {
112 let number: Int
113 let direction: Puzzle.Direction
114 }
115
116
117
118
119
120 enum Cell: Sendable, Equatable {
121 case block
122 case open(solution: String?, acceptedSolutions: Set<String>, special: Puzzle.Special?)
123 }
124
125
126
127 typealias Decoration = Puzzle.Decoration
128
129 struct Clue: Sendable, Equatable {
130 let number: Int
131 let text: String
132 let answer: String?
133
134
135
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
233
234
235
236
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
275
276
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
284
285
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
300
301
302
303
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
309
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
362
363
364
365
366
367
368
369
370 private struct Section {
371 let name: String?
372 let lines: [String]
373 }
374
375
376
377
378
379
380
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
410
411
412
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
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
451
452
453
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
473
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
489
490
491
492
493
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
524
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
534
535
536
537
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
550
551
552
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
561
562
563
564
565
566
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 }
573 if trimmed.hasPrefix("ConVer:") || trimmed.hasPrefix("CmVer:") {
574 lines[i] = newLine
575 return lines.joined(separator: "\n")
576 }
577 }
578
579 lines.insert(newLine, at: lines.isEmpty ? 0 : 1)
580 return lines.joined(separator: "\n")
581 }
582
583
584
585
586
587
588
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
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
655
656
657
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
695
696 if ch == "#" || ch == "_" {
697 return .block
698 }
699
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
721
722
723
724
725
726
727
728
729
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
754
755
756
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
769
770
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
792
793
794
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
807
808
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
847
848
849
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
864
865
866
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
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
904
905
906
907
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
915
916
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
939
940
941 let readings = afterDot[tilde.upperBound...]
942 .components(separatedBy: " / ")
943 .map { $0.trimmingCharacters(in: .whitespaces) }
944 .filter { !$0.isEmpty }
945
946
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
996
997
998
999
1000
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
1134
1135
1136
1137
1138
1139
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
1160
1161
1162
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
1203
1204
1205
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
1227
1228
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
1251
1252
1253
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
1311
1312
1313
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
1406
1407
1408
1409
1410 private struct Numbering {
1411
1412 private let numberByPosition: [Position: Int]
1413
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}