main.swift (41315B)
1 import Foundation 2 3 let gridSize = 15 4 let letters = Array("ABCDEFGHIJKLMNOPQRSTUVWXYZ".utf8) 5 let allLettersMask: UInt32 = (1 << 26) - 1 6 let 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 12 struct 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 32 struct GridEntry: Decodable { 33 let grid: [String] 34 let date: String 35 } 36 37 struct 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 48 struct Word { 49 let text: String 50 let bytes: [UInt8] 51 let score: Int 52 } 53 54 struct WordBucket { 55 let words: [Word] 56 let indexesByPositionAndLetter: [[UInt8: [Int]]] 57 } 58 59 struct 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 87 struct 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 105 struct Dictionary { 106 let bucketsByLength: [Int: WordBucket] 107 let scoresByText: [String: Int] 108 let profilesByText: [String: WordProfile] 109 } 110 111 struct PuzzleState { 112 var board: [UInt8?] 113 var options: [UInt32] 114 } 115 116 struct GeneratorError: Error, CustomStringConvertible { 117 let description: String 118 } 119 120 struct 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 136 func 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 221 func 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 247 func 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 253 func 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 260 func 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 268 func 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 279 func vowelCount(_ bytes: [UInt8]) -> Int { 280 bytes.filter { $0 == 65 || $0 == 69 || $0 == 73 || $0 == 79 || $0 == 85 }.count 281 } 282 283 func 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 293 func 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 300 func 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 319 func 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 348 func 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 363 func isLowUsageFill(_ profile: WordProfile) -> Bool { 364 guard let threshold = lowUsageThreshold(length: profile.length) else { 365 return false 366 } 367 return profile.count < threshold 368 } 369 370 func 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 396 func 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 403 func 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 431 func 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 445 func 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 466 func 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 528 func 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 598 func 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 630 func 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 674 func bit(for letter: UInt8) -> UInt32 { 675 1 << UInt32(letter - 65) 676 } 677 678 func popcount(_ mask: UInt32) -> Int { 679 Int(mask.nonzeroBitCount) 680 } 681 682 func allowedLetters(from mask: UInt32) -> [UInt8] { 683 letters.filter { mask & bit(for: $0) != 0 } 684 } 685 686 func 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 699 func 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 722 func 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 755 func 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 794 func 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 801 func 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 821 func 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 829 func 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 842 func 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 921 func 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 943 func wordText(for slot: Slot, state: PuzzleState) -> String { 944 String(bytes: slot.cells.map { state.board[$0] ?? 63 }, encoding: .utf8) ?? "" 945 } 946 947 func ratio(_ part: Int, _ whole: Int) -> Double { 948 Double(part) / Double(max(whole, 1)) 949 } 950 951 func 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 965 func 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 1018 func 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 1098 func 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 1137 func 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 1157 func 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 1182 func 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 1192 func 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 // Keep in step with XD.currentCmVersion in the app; Crossmake is a 1197 // standalone package and can't reference that symbol directly. 1198 "CmVer: 5", 1199 "Revision: 1", 1200 "Bundle: cm-basic", 1201 "Author: \(options.author)", 1202 "Publisher: Crossmate", 1203 "Date: \(ISO8601DateFormatter().string(from: Date()).prefix(10))", 1204 "Copyright: Generated", 1205 "Grid Index: \(gridIndex)", 1206 "Seed: \(options.seed)", 1207 "Fill Score: \(fillScore)", 1208 "", 1209 "" 1210 ] 1211 1212 for row in 0..<gridSize { 1213 var rowBytes: [UInt8] = [] 1214 for column in 0..<gridSize { 1215 let cell = row * gridSize + column 1216 rowBytes.append(black[cell] ? 35 : (state.board[cell] ?? 63)) 1217 } 1218 lines.append(String(bytes: rowBytes, encoding: .utf8) ?? "") 1219 } 1220 1221 lines.append("") 1222 lines.append("") 1223 1224 let across = slots 1225 .filter { $0.direction == .across } 1226 .sorted { (numbers[$0.cells[0]] ?? 0) < (numbers[$1.cells[0]] ?? 0) } 1227 let down = slots 1228 .filter { $0.direction == .down } 1229 .sorted { (numbers[$0.cells[0]] ?? 0) < (numbers[$1.cells[0]] ?? 0) } 1230 1231 for slot in across { 1232 let number = numbers[slot.cells[0]] ?? 0 1233 lines.append("A\(number). [No clue] ~ \(wordText(for: slot, state: state))") 1234 } 1235 1236 lines.append("") 1237 1238 for slot in down { 1239 let number = numbers[slot.cells[0]] ?? 0 1240 lines.append("D\(number). [No clue] ~ \(wordText(for: slot, state: state))") 1241 } 1242 1243 lines.append("") 1244 return lines.joined(separator: "\n") 1245 } 1246 1247 func run() throws { 1248 let options = try parseOptions(CommandLine.arguments) 1249 let dictionary = try loadDictionary( 1250 path: options.wordsPath, 1251 countsPath: options.countsPath, 1252 qualityPath: options.qualityPath, 1253 badWordsPath: options.badWordsPath 1254 ) 1255 let (black, gridIndex) = try loadGrid(options: options) 1256 let slots = buildSlots(black: black) 1257 var rng = RandomNumberGenerator64(seed: options.seed) 1258 1259 guard let state = solve( 1260 black: black, 1261 slots: slots, 1262 dictionary: dictionary, 1263 timeout: options.timeout, 1264 breadth: options.breadth, 1265 optimizeFill: options.optimizeFill, 1266 maxAnswerUsages: options.maxAnswerUsages, 1267 rng: &rng 1268 ) else { 1269 throw GeneratorError(description: "Could not fill the grid within \(options.timeout) seconds. Try a different --seed, --grid-index, or --breadth.") 1270 } 1271 let selectedFillScore = fillScore(state: state, slots: slots, dictionary: dictionary) 1272 if let minFillScore = options.minFillScore, selectedFillScore < minFillScore { 1273 throw GeneratorError(description: "Best fill score \(selectedFillScore) was below --min-fill-score \(minFillScore). Try a different --seed, --grid-index, or more timeout.") 1274 } 1275 1276 if options.fillReport { 1277 fputs("Selected fill score: \(selectedFillScore)\n", stderr) 1278 printFillReport(state: state, slots: slots, dictionary: dictionary) 1279 } 1280 1281 let xd = exportXD(state: state, black: black, slots: slots, options: options, gridIndex: gridIndex, fillScore: selectedFillScore) 1282 let outputURL = URL(fileURLWithPath: options.outputPath) 1283 let outputDirectory = outputURL.deletingLastPathComponent() 1284 if outputDirectory.path != "." { 1285 try FileManager.default.createDirectory(at: outputDirectory, withIntermediateDirectories: true) 1286 } 1287 try xd.write(to: outputURL, atomically: true, encoding: .utf8) 1288 print("Wrote \(options.outputPath)") 1289 } 1290 1291 do { 1292 try run() 1293 } catch { 1294 fputs("Fillmake: \(error)\n", stderr) 1295 exit(1) 1296 }