Crossmake/Sources/Fillmake/main.swift (41415B)
1import Foundation
2
3let gridSize = 15
4let letters = Array("ABCDEFGHIJKLMNOPQRSTUVWXYZ".utf8)
5let allLettersMask: UInt32 = (1 << 26) - 1
6let letterWeights: [UInt8: Int] = [
7 65: 9, 66: 2, 67: 2, 68: 4, 69: 12, 70: 2, 71: 3, 72: 2, 73: 9,
8 74: 1, 75: 1, 76: 4, 77: 2, 78: 6, 79: 8, 80: 2, 81: 1, 82: 6,
9 83: 4, 84: 6, 85: 4, 86: 2, 87: 2, 88: 1, 89: 2, 90: 1
10]
11
12struct Options {
13 var wordsPath = "Generated/word_list.json"
14 var gridsPath: String?
15 var countsPath = "Generated/answer_counts.json"
16 var qualityPath = "Generated/word_quality.json"
17 var badWordsPath = "Data/bad_words.json"
18 var outputPath = "Generated/fillmake.xd"
19 var gridIndex = 1
20 var gridDate: String?
21 var seed: UInt64 = UInt64(Date().timeIntervalSince1970)
22 var timeout: TimeInterval = 30
23 var breadth = 15
24 var title = "Crossmate Puzzle"
25 var author = "Fillmake"
26 var optimizeFill = false
27 var fillReport = false
28 var minFillScore: Int?
29 var maxAnswerUsages = 2
30}
31
32struct GridEntry: Decodable {
33 let grid: [String]
34 let date: String
35}
36
37struct Slot {
38 enum Direction {
39 case across
40 case down
41 }
42
43 let id: Int
44 let cells: [Int]
45 let direction: Direction
46}
47
48struct Word {
49 let text: String
50 let bytes: [UInt8]
51 let score: Int
52}
53
54struct WordBucket {
55 let words: [Word]
56 let indexesByPositionAndLetter: [[UInt8: [Int]]]
57}
58
59struct WordQuality: Decodable {
60 let count: Int?
61 let badClueCount: Int?
62 let obscureNameClueCount: Int?
63 let fillBlankCount: Int?
64 let foreignLanguageClueCount: Int?
65 let cluePartCount: Int?
66 let continuationClueCount: Int?
67 let themeClueCount: Int?
68 let latestSeen: String?
69 let sampleClues: [String]?
70 let rejectionReason: String?
71
72 enum CodingKeys: String, CodingKey {
73 case count
74 case badClueCount = "bad_clue_count"
75 case obscureNameClueCount = "obscure_name_clue_count"
76 case fillBlankCount = "fill_blank_count"
77 case foreignLanguageClueCount = "foreign_language_clue_count"
78 case cluePartCount = "clue_part_count"
79 case continuationClueCount = "continuation_clue_count"
80 case themeClueCount = "theme_clue_count"
81 case latestSeen = "latest_seen"
82 case sampleClues = "sample_clues"
83 case rejectionReason = "rejection_reason"
84 }
85}
86
87struct WordProfile {
88 let text: String
89 let length: Int
90 let score: Int
91 let count: Int
92 let badClueCount: Int
93 let obscureNameClueCount: Int
94 let fillBlankCount: Int
95 let foreignLanguageClueCount: Int
96 let cluePartCount: Int
97 let continuationClueCount: Int
98 let themeClueCount: Int
99 let latestSeen: String?
100 let sampleClues: [String]
101 let freshnessScore: Int
102 let rejectionReason: String?
103}
104
105struct Dictionary {
106 let bucketsByLength: [Int: WordBucket]
107 let scoresByText: [String: Int]
108 let profilesByText: [String: WordProfile]
109}
110
111struct PuzzleState {
112 var board: [UInt8?]
113 var options: [UInt32]
114}
115
116struct GeneratorError: Error, CustomStringConvertible {
117 let description: String
118}
119
120struct RandomNumberGenerator64: RandomNumberGenerator {
121 private var state: UInt64
122
123 init(seed: UInt64) {
124 self.state = seed == 0 ? 0x9E3779B97F4A7C15 : seed
125 }
126
127 mutating func next() -> UInt64 {
128 state &+= 0x9E3779B97F4A7C15
129 var z = state
130 z = (z ^ (z >> 30)) &* 0xBF58476D1CE4E5B9
131 z = (z ^ (z >> 27)) &* 0x94D049BB133111EB
132 return z ^ (z >> 31)
133 }
134}
135
136func parseOptions(_ arguments: [String]) throws -> Options {
137 var options = Options()
138 var index = 1
139
140 func requireValue(_ name: String) throws -> String {
141 guard index + 1 < arguments.count else {
142 throw GeneratorError(description: "Missing value for \(name)")
143 }
144 index += 1
145 return arguments[index]
146 }
147
148 while index < arguments.count {
149 let arg = arguments[index]
150 switch arg {
151 case "--words":
152 options.wordsPath = try requireValue(arg)
153 case "--grids":
154 options.gridsPath = try requireValue(arg)
155 case "--counts":
156 options.countsPath = try requireValue(arg)
157 case "--quality":
158 options.qualityPath = try requireValue(arg)
159 case "--bad-words":
160 options.badWordsPath = try requireValue(arg)
161 case "--output", "-o":
162 options.outputPath = try requireValue(arg)
163 case "--grid-index":
164 let value = try requireValue(arg)
165 guard let parsed = Int(value), parsed >= 0 else {
166 throw GeneratorError(description: "--grid-index must be a non-negative integer")
167 }
168 options.gridIndex = parsed
169 case "--grid-date":
170 options.gridDate = try requireValue(arg)
171 case "--seed":
172 let value = try requireValue(arg)
173 guard let parsed = UInt64(value) else {
174 throw GeneratorError(description: "--seed must be an unsigned integer")
175 }
176 options.seed = parsed
177 case "--timeout":
178 let value = try requireValue(arg)
179 guard let parsed = Double(value), parsed > 0 else {
180 throw GeneratorError(description: "--timeout must be a positive number of seconds")
181 }
182 options.timeout = parsed
183 case "--breadth":
184 let value = try requireValue(arg)
185 guard let parsed = Int(value), parsed > 0 else {
186 throw GeneratorError(description: "--breadth must be a positive integer")
187 }
188 options.breadth = parsed
189 case "--title":
190 options.title = try requireValue(arg)
191 case "--author":
192 options.author = try requireValue(arg)
193 case "--optimize-fill":
194 options.optimizeFill = true
195 case "--fill-report":
196 options.fillReport = true
197 case "--min-fill-score":
198 let value = try requireValue(arg)
199 guard let parsed = Int(value) else {
200 throw GeneratorError(description: "--min-fill-score must be an integer")
201 }
202 options.minFillScore = parsed
203 case "--max-answer-usages":
204 let value = try requireValue(arg)
205 guard let parsed = Int(value), parsed > 0 else {
206 throw GeneratorError(description: "--max-answer-usages must be a positive integer")
207 }
208 options.maxAnswerUsages = parsed
209 case "--help", "-h":
210 printUsage()
211 exit(0)
212 default:
213 throw GeneratorError(description: "Unknown argument: \(arg)")
214 }
215 index += 1
216 }
217
218 return options
219}
220
221func printUsage() {
222 print("""
223 Usage: Fillmake [options]
224
225 Options:
226 -o, --output PATH Output XD file path. Default: Generated/fillmake.xd
227 --words PATH Word list JSON path. Default: Generated/word_list.json
228 --grids PATH Grid list JSON path. Default: bundled grid_list.json
229 --counts PATH Optional answer frequency JSON path. Default: Generated/answer_counts.json
230 --quality PATH Optional word quality metadata JSON path. Default: Generated/word_quality.json
231 --bad-words PATH Optional JSON list of blocked words. Default: Data/bad_words.json
232 --grid-index N Zero-based grid index. Default: 1
233 --grid-date YYYY-MM-DD Select the first grid with this date.
234 --seed N Deterministic random seed.
235 --timeout SECONDS Stop after this many seconds. Default: 30
236 --breadth N Randomly try from the top N scored candidates. Default: 15
237 --title TEXT XD title metadata.
238 --author TEXT XD author metadata.
239 --optimize-fill Keep searching until timeout and return the best-scored fill found.
240 --fill-report Print the weakest entries in the selected fill.
241 --min-fill-score N Reject the selected fill if its final score is below N.
242 --max-answer-usages N Reject fills using one answer more than N times. Default: 2
243 -h, --help Show this help.
244 """)
245}
246
247func loadJSON<T: Decodable>(_ type: T.Type, from path: String) throws -> T {
248 let url = URL(fileURLWithPath: path)
249 let data = try Data(contentsOf: url)
250 return try JSONDecoder().decode(T.self, from: data)
251}
252
253func loadOptionalJSON<T: Decodable>(_ type: T.Type, from path: String) throws -> T? {
254 guard FileManager.default.fileExists(atPath: path) else {
255 return nil
256 }
257 return try loadJSON(type, from: path)
258}
259
260func loadBundledJSON<T: Decodable>(_ type: T.Type, resource: String, extension resourceExtension: String) throws -> T {
261 guard let url = Bundle.module.url(forResource: resource, withExtension: resourceExtension) else {
262 throw GeneratorError(description: "Bundled resource not found: \(resource).\(resourceExtension)")
263 }
264 let data = try Data(contentsOf: url)
265 return try JSONDecoder().decode(T.self, from: data)
266}
267
268func normalizedGridDate(_ value: String) -> String {
269 let parts = value.split(separator: "/")
270 if parts.count == 3,
271 let month = Int(parts[0]),
272 let day = Int(parts[1]),
273 let year = Int(parts[2]) {
274 return String(format: "%04d-%02d-%02d", year, month, day)
275 }
276 return value
277}
278
279func vowelCount(_ bytes: [UInt8]) -> Int {
280 bytes.filter { $0 == 65 || $0 == 69 || $0 == 73 || $0 == 79 || $0 == 85 }.count
281}
282
283func hasRunOfThree(_ bytes: [UInt8]) -> Bool {
284 guard bytes.count >= 3 else {
285 return false
286 }
287 for index in 2..<bytes.count where bytes[index] == bytes[index - 1] && bytes[index] == bytes[index - 2] {
288 return true
289 }
290 return false
291}
292
293func year(fromISODate value: String?) -> Int? {
294 guard let value, value.count >= 4 else {
295 return nil
296 }
297 return Int(value.prefix(4))
298}
299
300func freshnessScore(latestSeen: String?) -> Int {
301 guard let year = year(fromISODate: latestSeen) else {
302 return 0
303 }
304 if year >= 2015 {
305 return 55
306 }
307 if year >= 2010 {
308 return 35
309 }
310 if year >= 2000 {
311 return 15
312 }
313 if year < 1985 {
314 return -25
315 }
316 return 0
317}
318
319func usageAdjustment(length: Int, frequency: Int) -> Int {
320 guard frequency > 0 else {
321 return 0
322 }
323
324 switch length {
325 case ...3:
326 if frequency >= 100 { return 70 }
327 if frequency >= 50 { return 35 }
328 return -70
329 case 4:
330 if frequency >= 100 { return 60 }
331 if frequency >= 50 { return 30 }
332 if frequency < 20 { return -55 }
333 case 5:
334 if frequency >= 50 { return 45 }
335 if frequency >= 20 { return 20 }
336 if frequency < 10 { return -35 }
337 case 6...7:
338 if frequency >= 30 { return 25 }
339 if frequency < 5 { return -30 }
340 default:
341 if frequency >= 10 { return 15 }
342 if frequency == 1 { return -15 }
343 }
344
345 return 0
346}
347
348func lowUsageThreshold(length: Int) -> Int? {
349 switch length {
350 case ...3:
351 return 50
352 case 4:
353 return 20
354 case 5:
355 return 10
356 case 6...7:
357 return 5
358 default:
359 return nil
360 }
361}
362
363func isLowUsageFill(_ profile: WordProfile) -> Bool {
364 guard let threshold = lowUsageThreshold(length: profile.length) else {
365 return false
366 }
367 return profile.count < threshold
368}
369
370func isObscureShortFill(_ profile: WordProfile) -> Bool {
371 guard profile.length <= 4 else {
372 return false
373 }
374
375 let badRatio = ratio(profile.badClueCount, profile.count)
376 let obscureRatio = ratio(profile.obscureNameClueCount, profile.count)
377 let blankRatio = ratio(profile.fillBlankCount, profile.count)
378 let foreignRatio = ratio(profile.foreignLanguageClueCount, profile.count)
379
380 if isLowUsageFill(profile) {
381 return true
382 }
383 if profile.length <= 3 && profile.count < 80 {
384 return true
385 }
386 if profile.score < 130 {
387 return true
388 }
389
390 return badRatio >= 0.18
391 || obscureRatio >= 0.18
392 || blankRatio >= 0.25
393 || foreignRatio >= 0.18
394}
395
396func sampleCluesContain(_ profile: WordProfile, patterns: [String]) -> Bool {
397 profile.sampleClues.contains { clue in
398 let normalized = clue.lowercased()
399 return patterns.contains { normalized.contains($0) }
400 }
401}
402
403func isThemeOrQuoteFragment(_ profile: WordProfile) -> Bool {
404 if profile.continuationClueCount > 0 || profile.themeClueCount > 0 || profile.cluePartCount > 0 {
405 return true
406 }
407
408 let text = profile.text
409 if text.hasPrefix("IFA") || text.hasPrefix("IFAT") || text.hasPrefix("ITSREALLY") {
410 return true
411 }
412 if profile.length >= 8 && sampleCluesContain(profile, patterns: ["-across", "-down"]) {
413 return true
414 }
415
416 return sampleCluesContain(profile, patterns: [
417 "start of",
418 "end of",
419 "middle of",
420 "part of",
421 "continuation of",
422 "quote",
423 "quip",
424 "reason the",
425 "17-across",
426 "58-across",
427 "39-down"
428 ])
429}
430
431func isAwkwardMediumFill(_ profile: WordProfile) -> Bool {
432 guard (5...7).contains(profile.length) else {
433 return false
434 }
435
436 if profile.count <= 8 {
437 return true
438 }
439 if ratio(profile.fillBlankCount, profile.count) >= 0.35 {
440 return true
441 }
442 return false
443}
444
445func isNoveltyOneOff(_ profile: WordProfile) -> Bool {
446 guard profile.length >= 8, profile.count == 1 else {
447 return false
448 }
449
450 if isThemeOrQuoteFragment(profile) {
451 return true
452 }
453
454 return sampleCluesContain(profile, patterns: [
455 "guinness",
456 "world record",
457 "record at",
458 "#",
459 "dumbest",
460 "largest",
461 "longest",
462 "smallest"
463 ])
464}
465
466func qualityScore(text: String, bytes: [UInt8], count: Int?, quality: WordQuality?) -> Int {
467 let length = bytes.count
468 let frequency = count ?? 0
469 var score = length * 12
470
471 if frequency > 0 {
472 score += min(80, frequency * 4)
473 score += usageAdjustment(length: length, frequency: frequency)
474 } else {
475 score -= length >= 8 ? 30 : 80
476 }
477
478 if length >= 8 {
479 score += min(80, (length - 7) * 14)
480 }
481 if (5...7).contains(length) && frequency <= 2 {
482 score -= 70
483 }
484 if length == 4 && frequency < 10 {
485 score -= 60
486 }
487 if length <= 3 && frequency < 25 {
488 score -= 80
489 }
490
491 let vowels = vowelCount(bytes)
492 if vowels == 0 {
493 score -= 90
494 } else if length >= 5 && Double(vowels) / Double(length) < 0.22 {
495 score -= 35
496 }
497 if hasRunOfThree(bytes) {
498 score -= 110
499 }
500
501 if let quality {
502 let evidenceCount = max(quality.count ?? frequency, 1)
503 let badRatio = Double(quality.badClueCount ?? 0) / Double(evidenceCount)
504 let obscureRatio = Double(quality.obscureNameClueCount ?? 0) / Double(evidenceCount)
505 let blankRatio = Double(quality.fillBlankCount ?? 0) / Double(evidenceCount)
506
507 if quality.rejectionReason != nil {
508 score -= length >= 8 ? 80 : 140
509 }
510 if length <= 4 {
511 score -= Int(badRatio * 100)
512 score -= Int(obscureRatio * 70)
513 score -= Int(blankRatio * 45)
514 } else if length <= 7 {
515 score -= Int(badRatio * 45)
516 score -= Int(obscureRatio * 35)
517 score -= Int(blankRatio * 20)
518 } else {
519 score -= Int(badRatio * 20)
520 score -= Int(obscureRatio * 15)
521 }
522 }
523
524 let letterScore = bytes.reduce(0) { $0 + (letterWeights[$1] ?? 0) }
525 return score + letterScore + freshnessScore(latestSeen: quality?.latestSeen)
526}
527
528func loadDictionary(path: String, countsPath: String, qualityPath: String, badWordsPath: String) throws -> Dictionary {
529 let rawWords = try loadJSON([String].self, from: path)
530 let counts = try loadOptionalJSON([String: Int].self, from: countsPath) ?? [:]
531 let quality = try loadOptionalJSON([String: WordQuality].self, from: qualityPath) ?? [:]
532 let badWords = Set((try loadOptionalJSON([String].self, from: badWordsPath) ?? []).map { $0.uppercased() })
533 var seen = Set<String>()
534 var grouped: [Int: [Word]] = [:]
535 var scoresByText: [String: Int] = [:]
536 var profilesByText: [String: WordProfile] = [:]
537
538 for rawWord in rawWords {
539 let upper = rawWord.uppercased()
540 let bytes = Array(upper.utf8)
541 guard (2...gridSize).contains(bytes.count), bytes.allSatisfy({ $0 >= 65 && $0 <= 90 }) else {
542 continue
543 }
544 guard !badWords.contains(upper) else {
545 continue
546 }
547 guard seen.insert(upper).inserted else {
548 continue
549 }
550 let key = upper.lowercased()
551 let wordQuality = quality[key]
552 let frequency = counts[key] ?? wordQuality?.count ?? 0
553 let score = qualityScore(text: upper, bytes: bytes, count: counts[key], quality: wordQuality)
554 grouped[bytes.count, default: []].append(Word(text: upper, bytes: bytes, score: score))
555 scoresByText[upper] = score
556 profilesByText[upper] = WordProfile(
557 text: upper,
558 length: bytes.count,
559 score: score,
560 count: frequency,
561 badClueCount: wordQuality?.badClueCount ?? 0,
562 obscureNameClueCount: wordQuality?.obscureNameClueCount ?? 0,
563 fillBlankCount: wordQuality?.fillBlankCount ?? 0,
564 foreignLanguageClueCount: wordQuality?.foreignLanguageClueCount ?? 0,
565 cluePartCount: wordQuality?.cluePartCount ?? 0,
566 continuationClueCount: wordQuality?.continuationClueCount ?? 0,
567 themeClueCount: wordQuality?.themeClueCount ?? 0,
568 latestSeen: wordQuality?.latestSeen,
569 sampleClues: wordQuality?.sampleClues ?? [],
570 freshnessScore: freshnessScore(latestSeen: wordQuality?.latestSeen),
571 rejectionReason: wordQuality?.rejectionReason
572 )
573 }
574
575 var bucketsByLength: [Int: WordBucket] = [:]
576 for length in grouped.keys {
577 grouped[length]?.sort {
578 if $0.score != $1.score {
579 return $0.score > $1.score
580 }
581 return $0.text < $1.text
582 }
583 guard let words = grouped[length] else {
584 continue
585 }
586 var indexesByPositionAndLetter = Array(repeating: [UInt8: [Int]](), count: length)
587 for (index, word) in words.enumerated() {
588 for (position, letter) in word.bytes.enumerated() {
589 indexesByPositionAndLetter[position][letter, default: []].append(index)
590 }
591 }
592 bucketsByLength[length] = WordBucket(words: words, indexesByPositionAndLetter: indexesByPositionAndLetter)
593 }
594
595 return Dictionary(bucketsByLength: bucketsByLength, scoresByText: scoresByText, profilesByText: profilesByText)
596}
597
598func loadGrid(options: Options) throws -> ([Bool], Int) {
599 let grids: [GridEntry]
600 if let gridsPath = options.gridsPath {
601 grids = try loadJSON([GridEntry].self, from: gridsPath)
602 } else {
603 grids = try loadBundledJSON([GridEntry].self, resource: "grid_list", extension: "json")
604 }
605
606 let entry: GridEntry
607 let gridIndex: Int
608 if let date = options.gridDate {
609 let normalizedDate = normalizedGridDate(date)
610 guard let matchIndex = grids.firstIndex(where: { $0.date == normalizedDate }) else {
611 throw GeneratorError(description: "No grid found for date \(date)")
612 }
613 entry = grids[matchIndex]
614 gridIndex = matchIndex
615 } else {
616 guard options.gridIndex < grids.count else {
617 throw GeneratorError(description: "--grid-index \(options.gridIndex) is out of range; found \(grids.count) grids")
618 }
619 entry = grids[options.gridIndex]
620 gridIndex = options.gridIndex
621 }
622
623 guard entry.grid.count == gridSize * gridSize else {
624 throw GeneratorError(description: "Grid \(entry.date) has \(entry.grid.count) cells, expected \(gridSize * gridSize)")
625 }
626
627 return (entry.grid.map { $0 == "." }, gridIndex)
628}
629
630func buildSlots(black: [Bool]) -> [Slot] {
631 var slots: [Slot] = []
632
633 for row in 0..<gridSize {
634 var column = 0
635 while column < gridSize {
636 let cell = row * gridSize + column
637 if black[cell] {
638 column += 1
639 continue
640 }
641 var cells: [Int] = []
642 while column < gridSize && !black[row * gridSize + column] {
643 cells.append(row * gridSize + column)
644 column += 1
645 }
646 if cells.count > 1 {
647 slots.append(Slot(id: slots.count, cells: cells, direction: .across))
648 }
649 }
650 }
651
652 for column in 0..<gridSize {
653 var row = 0
654 while row < gridSize {
655 let cell = row * gridSize + column
656 if black[cell] {
657 row += 1
658 continue
659 }
660 var cells: [Int] = []
661 while row < gridSize && !black[row * gridSize + column] {
662 cells.append(row * gridSize + column)
663 row += 1
664 }
665 if cells.count > 1 {
666 slots.append(Slot(id: slots.count, cells: cells, direction: .down))
667 }
668 }
669 }
670
671 return slots
672}
673
674func bit(for letter: UInt8) -> UInt32 {
675 1 << UInt32(letter - 65)
676}
677
678func popcount(_ mask: UInt32) -> Int {
679 Int(mask.nonzeroBitCount)
680}
681
682func allowedLetters(from mask: UInt32) -> [UInt8] {
683 letters.filter { mask & bit(for: $0) != 0 }
684}
685
686func matches(_ word: Word, slot: Slot, state: PuzzleState) -> Bool {
687 for (offset, cell) in slot.cells.enumerated() {
688 let char = word.bytes[offset]
689 if let existing = state.board[cell], existing != char {
690 return false
691 }
692 if state.options[cell] & bit(for: char) == 0 {
693 return false
694 }
695 }
696 return true
697}
698
699func intersectSorted(_ lhs: [Int], _ rhs: [Int]) -> [Int] {
700 var result: [Int] = []
701 result.reserveCapacity(min(lhs.count, rhs.count))
702 var leftIndex = 0
703 var rightIndex = 0
704
705 while leftIndex < lhs.count && rightIndex < rhs.count {
706 let left = lhs[leftIndex]
707 let right = rhs[rightIndex]
708 if left == right {
709 result.append(left)
710 leftIndex += 1
711 rightIndex += 1
712 } else if left < right {
713 leftIndex += 1
714 } else {
715 rightIndex += 1
716 }
717 }
718
719 return result
720}
721
722func candidates(for slot: Slot, state: PuzzleState, dictionary: Dictionary) -> [Word] {
723 guard let bucket = dictionary.bucketsByLength[slot.cells.count] else {
724 return []
725 }
726
727 var indexedMatches: [Int]?
728 for (offset, cell) in slot.cells.enumerated() {
729 guard let existing = state.board[cell] else {
730 continue
731 }
732 guard let letterMatches = bucket.indexesByPositionAndLetter[offset][existing] else {
733 return []
734 }
735 if let current = indexedMatches {
736 indexedMatches = intersectSorted(current, letterMatches)
737 if indexedMatches?.isEmpty == true {
738 return []
739 }
740 } else {
741 indexedMatches = letterMatches
742 }
743 }
744
745 let words: [Word]
746 if let indexedMatches {
747 words = indexedMatches.map { bucket.words[$0] }
748 } else {
749 words = bucket.words
750 }
751
752 return words.filter { matches($0, slot: slot, state: state) }
753}
754
755func propagate(_ input: PuzzleState, slots: [Slot], dictionary: Dictionary) -> PuzzleState? {
756 var state = input
757 var changed = true
758
759 while changed {
760 changed = false
761 for slot in slots {
762 let words = candidates(for: slot, state: state, dictionary: dictionary)
763 if words.isEmpty {
764 return nil
765 }
766
767 var allowed = Array(repeating: UInt32(0), count: slot.cells.count)
768 for word in words {
769 for (offset, char) in word.bytes.enumerated() {
770 allowed[offset] |= bit(for: char)
771 }
772 }
773
774 for (offset, cell) in slot.cells.enumerated() {
775 let next = state.options[cell] & allowed[offset]
776 if next == 0 {
777 return nil
778 }
779 if next != state.options[cell] {
780 state.options[cell] = next
781 changed = true
782 }
783 if popcount(next) == 1, state.board[cell] == nil {
784 state.board[cell] = allowedLetters(from: next)[0]
785 changed = true
786 }
787 }
788 }
789 }
790
791 return state
792}
793
794func isSolved(_ state: PuzzleState, black: [Bool]) -> Bool {
795 for cell in 0..<black.count where !black[cell] && state.board[cell] == nil {
796 return false
797 }
798 return true
799}
800
801func bestSlot(in state: PuzzleState, slots: [Slot], dictionary: Dictionary) -> (Slot, [Word])? {
802 var best: (Slot, [Word])?
803
804 for slot in slots where slot.cells.contains(where: { state.board[$0] == nil }) {
805 let words = candidates(for: slot, state: state, dictionary: dictionary)
806 if words.isEmpty {
807 return (slot, [])
808 }
809 if let current = best {
810 if words.count < current.1.count || (words.count == current.1.count && slot.cells.count > current.0.cells.count) {
811 best = (slot, words)
812 }
813 } else {
814 best = (slot, words)
815 }
816 }
817
818 return best
819}
820
821func candidateOrder(_ words: [Word], breadth: Int, rng: inout RandomNumberGenerator64) -> [Word] {
822 let prefix = Array(words.prefix(max(1, min(breadth, words.count)))).shuffled(using: &rng)
823 if words.count <= prefix.count {
824 return prefix
825 }
826 return prefix + words.dropFirst(prefix.count)
827}
828
829func placing(_ word: Word, in slot: Slot, state: PuzzleState) -> PuzzleState? {
830 var next = state
831 for (offset, cell) in slot.cells.enumerated() {
832 let char = word.bytes[offset]
833 if let existing = next.board[cell], existing != char {
834 return nil
835 }
836 next.board[cell] = char
837 next.options[cell] = bit(for: char)
838 }
839 return next
840}
841
842func solve(
843 black: [Bool],
844 slots: [Slot],
845 dictionary: Dictionary,
846 timeout: TimeInterval,
847 breadth: Int,
848 optimizeFill: Bool,
849 maxAnswerUsages: Int,
850 rng: inout RandomNumberGenerator64
851) -> PuzzleState? {
852 var initial = PuzzleState(
853 board: Array(repeating: nil, count: gridSize * gridSize),
854 options: black.map { $0 ? 0 : allLettersMask }
855 )
856 for cell in 0..<black.count where black[cell] {
857 initial.board[cell] = nil
858 }
859
860 let startedAt = Date()
861 let deadline = startedAt.addingTimeInterval(timeout)
862 var attempts = 0
863 var bestSolved: PuzzleState?
864 var bestSolvedScore = Int.min
865
866 func search(_ state: PuzzleState) -> PuzzleState? {
867 if Date() >= deadline {
868 return nil
869 }
870 attempts += 1
871
872 guard let propagated = propagate(state, slots: slots, dictionary: dictionary) else {
873 return nil
874 }
875 if isSolved(propagated, black: black) {
876 guard repeatedAnswers(in: propagated, slots: slots, maxUsage: maxAnswerUsages).isEmpty else {
877 return nil
878 }
879 if optimizeFill {
880 let score = fillScore(state: propagated, slots: slots, dictionary: dictionary)
881 if score > bestSolvedScore {
882 bestSolved = propagated
883 bestSolvedScore = score
884 }
885 return nil
886 }
887 return propagated
888 }
889 guard let (slot, slotCandidates) = bestSlot(in: propagated, slots: slots, dictionary: dictionary), !slotCandidates.isEmpty else {
890 return nil
891 }
892
893 for word in candidateOrder(slotCandidates, breadth: breadth, rng: &rng) {
894 guard let next = placing(word, in: slot, state: propagated) else {
895 continue
896 }
897 if let solved = search(next) {
898 return solved
899 }
900 }
901
902 return nil
903 }
904
905 let result = search(initial)
906 if let result {
907 return result
908 }
909 if let bestSolved {
910 let elapsed = Date().timeIntervalSince(startedAt)
911 fputs("Searched \(attempts) nodes in \(String(format: "%.2f", elapsed)) seconds and kept best fill score \(bestSolvedScore).\n", stderr)
912 return bestSolved
913 }
914 if result == nil {
915 let elapsed = Date().timeIntervalSince(startedAt)
916 fputs("Stopped after \(attempts) search nodes in \(String(format: "%.2f", elapsed)) seconds.\n", stderr)
917 }
918 return nil
919}
920
921func clueNumberGrid(black: [Bool]) -> [Int?] {
922 var numbers = Array<Int?>(repeating: nil, count: gridSize * gridSize)
923 var nextNumber = 1
924
925 for row in 0..<gridSize {
926 for column in 0..<gridSize {
927 let cell = row * gridSize + column
928 if black[cell] {
929 continue
930 }
931 let startsAcross = (column == 0 || black[cell - 1]) && column + 1 < gridSize && !black[cell + 1]
932 let startsDown = (row == 0 || black[cell - gridSize]) && row + 1 < gridSize && !black[cell + gridSize]
933 if startsAcross || startsDown {
934 numbers[cell] = nextNumber
935 nextNumber += 1
936 }
937 }
938 }
939
940 return numbers
941}
942
943func wordText(for slot: Slot, state: PuzzleState) -> String {
944 String(bytes: slot.cells.map { state.board[$0] ?? 63 }, encoding: .utf8) ?? ""
945}
946
947func ratio(_ part: Int, _ whole: Int) -> Double {
948 Double(part) / Double(max(whole, 1))
949}
950
951func isPartialish(_ profile: WordProfile) -> Bool {
952 let text = profile.text
953 if text.hasPrefix("INA") && profile.length >= 5 {
954 return true
955 }
956 if text.hasPrefix("IHAVE") || text.hasPrefix("WEARE") || text.hasPrefix("ITIS") || text.hasPrefix("ITSA") {
957 return true
958 }
959 if text.hasPrefix("RATED") || text.hasSuffix("IN") && profile.length >= 5 {
960 return true
961 }
962 return false
963}
964
965func weaknessReasons(for profile: WordProfile) -> [String] {
966 var reasons: [String] = []
967 let blankRatio = ratio(profile.fillBlankCount, profile.count)
968 let foreignRatio = ratio(profile.foreignLanguageClueCount, profile.count)
969
970 if profile.score < 90 {
971 reasons.append("low score \(profile.score)")
972 }
973 if profile.freshnessScore < 0 {
974 reasons.append("last seen \(profile.latestSeen ?? "unknown")")
975 }
976 if profile.length <= 4 && profile.score < 115 {
977 reasons.append("weak short fill")
978 }
979 if (5...7).contains(profile.length) && profile.count <= 8 && profile.score < 145 {
980 reasons.append("rare medium fill")
981 }
982 if profile.length >= 6 && profile.count <= 3 && profile.score < 180 {
983 reasons.append("low frequency \(profile.count)")
984 }
985 if isLowUsageFill(profile) {
986 reasons.append("low usage count \(profile.count)")
987 }
988 if isObscureShortFill(profile) {
989 reasons.append("obscure short fill")
990 }
991 if isAwkwardMediumFill(profile) {
992 reasons.append("awkward medium fill")
993 }
994 if profile.fillBlankCount >= 2 && blankRatio >= 0.5 {
995 reasons.append("fill-in clue dependent")
996 }
997 if profile.foreignLanguageClueCount >= 2 && foreignRatio >= 0.5 {
998 reasons.append("mostly foreign-language clues")
999 }
1000 if profile.cluePartCount > 0 {
1001 reasons.append("part-of-longer-answer clues")
1002 }
1003 if isThemeOrQuoteFragment(profile) {
1004 reasons.append("theme/quote fragment")
1005 }
1006 if isNoveltyOneOff(profile) {
1007 reasons.append("novelty one-off")
1008 }
1009 if isPartialish(profile) {
1010 reasons.append("phrase fragment")
1011 }
1012 if let rejectionReason = profile.rejectionReason {
1013 reasons.append(rejectionReason)
1014 }
1015 return reasons
1016}
1017
1018func concentrationPenalty(for profiles: [WordProfile]) -> Int {
1019 var weakShort = 0
1020 var lowFrequencyLong = 0
1021 var blankDependent = 0
1022 var heavyBlankDependent = 0
1023 var partialish = 0
1024 var rejected = 0
1025 var severeLowFrequency = 0
1026 var rareMedium = 0
1027 var veryWeakShort = 0
1028 var lowUsageFill = 0
1029 var obscureShort = 0
1030 var awkwardMedium = 0
1031 var themeOrQuoteFragment = 0
1032 var noveltyOneOff = 0
1033
1034 for profile in profiles {
1035 if isThemeOrQuoteFragment(profile) {
1036 themeOrQuoteFragment += 1
1037 }
1038 if isNoveltyOneOff(profile) {
1039 noveltyOneOff += 1
1040 }
1041 if isLowUsageFill(profile) {
1042 lowUsageFill += 1
1043 }
1044 if isObscureShortFill(profile) {
1045 obscureShort += 1
1046 }
1047 if isAwkwardMediumFill(profile) {
1048 awkwardMedium += 1
1049 }
1050 if profile.length <= 4 && profile.score < 115 {
1051 weakShort += 1
1052 }
1053 if profile.length <= 3 && profile.score < 65 {
1054 veryWeakShort += 1
1055 }
1056 if (5...7).contains(profile.length) && profile.count <= 8 && profile.score < 145 {
1057 rareMedium += 1
1058 }
1059 if profile.length >= 6 && profile.count <= 3 && profile.score < 180 {
1060 lowFrequencyLong += 1
1061 }
1062 if profile.length >= 6 && profile.count <= 1 && profile.score < 180 {
1063 severeLowFrequency += 1
1064 }
1065 if profile.fillBlankCount >= 2 && ratio(profile.fillBlankCount, profile.count) >= 0.5 {
1066 blankDependent += 1
1067 }
1068 if profile.fillBlankCount >= 3 && ratio(profile.fillBlankCount, profile.count) >= 0.65 {
1069 heavyBlankDependent += 1
1070 }
1071 if isPartialish(profile) {
1072 partialish += 1
1073 }
1074 if profile.rejectionReason != nil {
1075 rejected += 1
1076 }
1077 }
1078
1079 return max(0, weakShort - 6) * 85
1080 + max(0, veryWeakShort - 2) * 90
1081 + max(0, rareMedium - 2) * 95
1082 + max(0, lowUsageFill - 4) * 90
1083 + max(0, obscureShort - 1) * 170
1084 + max(0, obscureShort - 3) * 130
1085 + max(0, obscureShort - 6) * 120
1086 + max(0, awkwardMedium - 2) * 120
1087 + max(0, awkwardMedium - 5) * 90
1088 + max(0, lowFrequencyLong - 3) * 80
1089 + severeLowFrequency * 40
1090 + themeOrQuoteFragment * 150
1091 + noveltyOneOff * 75
1092 + max(0, blankDependent - 1) * 110
1093 + heavyBlankDependent * 80
1094 + max(0, partialish - 2) * 95
1095 + rejected * 150
1096}
1097
1098func entryPenalty(for profile: WordProfile) -> Int {
1099 var penalty = 0
1100
1101 if (5...7).contains(profile.length) && profile.score < 90 {
1102 penalty += 220
1103 } else if (5...7).contains(profile.length) && profile.score < 115 && profile.count <= 8 {
1104 penalty += 120
1105 }
1106 if profile.length <= 3 && profile.score < 65 {
1107 penalty += 80
1108 }
1109 if isLowUsageFill(profile) {
1110 if profile.length <= 4 {
1111 penalty += 90
1112 } else if profile.length <= 5 {
1113 penalty += 55
1114 } else {
1115 penalty += 30
1116 }
1117 }
1118 if isThemeOrQuoteFragment(profile) {
1119 penalty += 170
1120 }
1121 if isAwkwardMediumFill(profile) {
1122 penalty += 60
1123 }
1124 if isNoveltyOneOff(profile) {
1125 penalty += 60
1126 }
1127 if profile.fillBlankCount >= 3 && ratio(profile.fillBlankCount, profile.count) >= 0.65 {
1128 penalty += 120
1129 }
1130 if profile.rejectionReason != nil {
1131 penalty += 200
1132 }
1133
1134 return penalty
1135}
1136
1137func fillScore(state: PuzzleState, slots: [Slot], dictionary: Dictionary) -> Int {
1138 var score = 0
1139 var seen = Set<String>()
1140 var profiles: [WordProfile] = []
1141
1142 for slot in slots {
1143 let word = wordText(for: slot, state: state)
1144 score += dictionary.scoresByText[word] ?? 0
1145 if let profile = dictionary.profilesByText[word] {
1146 profiles.append(profile)
1147 score -= entryPenalty(for: profile)
1148 }
1149 if !seen.insert(word).inserted {
1150 score -= 500
1151 }
1152 }
1153
1154 return score - concentrationPenalty(for: profiles)
1155}
1156
1157func printFillReport(state: PuzzleState, slots: [Slot], dictionary: Dictionary) {
1158 let profiles = slots.compactMap { dictionary.profilesByText[wordText(for: $0, state: state)] }
1159 let weakEntries = profiles
1160 .map { profile in (profile, weaknessReasons(for: profile)) }
1161 .filter { !$0.1.isEmpty }
1162 .sorted {
1163 if $0.0.score != $1.0.score {
1164 return $0.0.score < $1.0.score
1165 }
1166 return $0.0.text < $1.0.text
1167 }
1168 .prefix(12)
1169
1170 guard !weakEntries.isEmpty else {
1171 fputs("Fill report: no weak entries flagged.\n", stderr)
1172 return
1173 }
1174
1175 fputs("Fill report: weakest entries\n", stderr)
1176 for (profile, reasons) in weakEntries {
1177 let latestSeen = profile.latestSeen ?? "unknown"
1178 fputs(" \(profile.text): score \(profile.score), count \(profile.count), latest \(latestSeen), \(reasons.joined(separator: "; "))\n", stderr)
1179 }
1180}
1181
1182func repeatedAnswers(in state: PuzzleState, slots: [Slot], maxUsage: Int) -> [String: Int] {
1183 var counts: [String: Int] = [:]
1184
1185 for slot in slots {
1186 counts[wordText(for: slot, state: state), default: 0] += 1
1187 }
1188
1189 return counts.filter { $0.value > maxUsage }
1190}
1191
1192func exportXD(state: PuzzleState, black: [Bool], slots: [Slot], options: Options, gridIndex: Int, fillScore: Int) -> String {
1193 let numbers = clueNumberGrid(black: black)
1194 var lines: [String] = [
1195 "Title: \(options.title)",
1196
1197
1198
1199
1200 "Revision: 1",
1201 "Bundle: cm-basic",
1202 "Author: \(options.author)",
1203 "Publisher: Crossmate",
1204 "Date: \(ISO8601DateFormatter().string(from: Date()).prefix(10))",
1205 "Copyright: Generated",
1206 "Grid Index: \(gridIndex)",
1207 "Seed: \(options.seed)",
1208 "Fill Score: \(fillScore)",
1209 "",
1210 ""
1211 ]
1212
1213 for row in 0..<gridSize {
1214 var rowBytes: [UInt8] = []
1215 for column in 0..<gridSize {
1216 let cell = row * gridSize + column
1217 rowBytes.append(black[cell] ? 35 : (state.board[cell] ?? 63))
1218 }
1219 lines.append(String(bytes: rowBytes, encoding: .utf8) ?? "")
1220 }
1221
1222 lines.append("")
1223 lines.append("")
1224
1225 let across = slots
1226 .filter { $0.direction == .across }
1227 .sorted { (numbers[$0.cells[0]] ?? 0) < (numbers[$1.cells[0]] ?? 0) }
1228 let down = slots
1229 .filter { $0.direction == .down }
1230 .sorted { (numbers[$0.cells[0]] ?? 0) < (numbers[$1.cells[0]] ?? 0) }
1231
1232 for slot in across {
1233 let number = numbers[slot.cells[0]] ?? 0
1234 lines.append("A\(number). [No clue] ~ \(wordText(for: slot, state: state))")
1235 }
1236
1237 lines.append("")
1238
1239 for slot in down {
1240 let number = numbers[slot.cells[0]] ?? 0
1241 lines.append("D\(number). [No clue] ~ \(wordText(for: slot, state: state))")
1242 }
1243
1244 lines.append("")
1245 return lines.joined(separator: "\n")
1246}
1247
1248func run() throws {
1249 let options = try parseOptions(CommandLine.arguments)
1250 let dictionary = try loadDictionary(
1251 path: options.wordsPath,
1252 countsPath: options.countsPath,
1253 qualityPath: options.qualityPath,
1254 badWordsPath: options.badWordsPath
1255 )
1256 let (black, gridIndex) = try loadGrid(options: options)
1257 let slots = buildSlots(black: black)
1258 var rng = RandomNumberGenerator64(seed: options.seed)
1259
1260 guard let state = solve(
1261 black: black,
1262 slots: slots,
1263 dictionary: dictionary,
1264 timeout: options.timeout,
1265 breadth: options.breadth,
1266 optimizeFill: options.optimizeFill,
1267 maxAnswerUsages: options.maxAnswerUsages,
1268 rng: &rng
1269 ) else {
1270 throw GeneratorError(description: "Could not fill the grid within \(options.timeout) seconds. Try a different --seed, --grid-index, or --breadth.")
1271 }
1272 let selectedFillScore = fillScore(state: state, slots: slots, dictionary: dictionary)
1273 if let minFillScore = options.minFillScore, selectedFillScore < minFillScore {
1274 throw GeneratorError(description: "Best fill score \(selectedFillScore) was below --min-fill-score \(minFillScore). Try a different --seed, --grid-index, or more timeout.")
1275 }
1276
1277 if options.fillReport {
1278 fputs("Selected fill score: \(selectedFillScore)\n", stderr)
1279 printFillReport(state: state, slots: slots, dictionary: dictionary)
1280 }
1281
1282 let xd = exportXD(state: state, black: black, slots: slots, options: options, gridIndex: gridIndex, fillScore: selectedFillScore)
1283 let outputURL = URL(fileURLWithPath: options.outputPath)
1284 let outputDirectory = outputURL.deletingLastPathComponent()
1285 if outputDirectory.path != "." {
1286 try FileManager.default.createDirectory(at: outputDirectory, withIntermediateDirectories: true)
1287 }
1288 try xd.write(to: outputURL, atomically: true, encoding: .utf8)
1289 print("Wrote \(options.outputPath)")
1290}
1291
1292do {
1293 try run()
1294} catch {
1295 fputs("Fillmake: \(error)\n", stderr)
1296 exit(1)
1297}