← All repositories

crossmate

A collaborative crossword app for iPhone and iPad

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


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        // No converter-version header: Crossmake generates puzzles rather than
1197        // converting an external source, so there is nothing to re-convert. The
1198        // app treats the absent header as version 1 and never acts on it for a
1199        // non-NYT puzzle.
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}