1package spellpuzzle23import (4 "errors"5 "math"6 "math/rand/v2"7 "sort"8)910var errNoPuzzleFound = errors.New("spell puzzle: failed to generate puzzle")1112type GeneratedPuzzle struct {13 Bank string14 Placements []WordPlacement15 BonusWords []string16 AllowedWord []string17}1819type crosswordCell struct {20 Letter rune21 Horizontal bool22 Vertical bool23}2425type crosswordState struct {26 Cells map[Position]crosswordCell27 Placements []WordPlacement28}2930func GeneratePuzzle(mode SpellPuzzleMode) (GeneratedPuzzle, error) {31 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))32 return GeneratePuzzleSeeded(mode, rng)33}3435func GeneratePuzzleSeeded(mode SpellPuzzleMode, rng *rand.Rand) (GeneratedPuzzle, error) {36 seeds := append([]string(nil), seedWordsByLength[mode.BankSize]...)37 if len(seeds) == 0 {38 return GeneratedPuzzle{}, errNoPuzzleFound39 }4041 shuffleStrings(seeds, rng)42 maxAttempts := min(len(seeds), 800)43 for _, bank := range seeds[:maxAttempts] {44 candidates := spellableWords(bank, 3)45 if len(candidates) < mode.BoardWordCount+mode.MinBonusWords {46 continue47 }4849 placements, ok := buildCrossword(bank, candidates, mode.BoardWordCount, rng)50 if !ok {51 continue52 }5354 used := make(map[string]struct{}, len(placements))55 for _, placement := range placements {56 used[placement.Text] = struct{}{}57 }5859 bonusWords := make([]string, 0, len(candidates))60 for _, candidate := range candidates {61 if _, ok := used[candidate]; ok {62 continue63 }64 bonusWords = append(bonusWords, candidate)65 }66 if len(bonusWords) < mode.MinBonusWords {67 continue68 }6970 sort.Strings(bonusWords)71 sort.Strings(candidates)72 scrambledBank := scrambleBank(bank, placements, rng)73 return GeneratedPuzzle{74 Bank: scrambledBank,75 Placements: normalizePlacements(placements),76 BonusWords: bonusWords,77 AllowedWord: candidates,78 }, nil79 }8081 return GeneratedPuzzle{}, errNoPuzzleFound82}8384func buildCrossword(bank string, candidates []string, want int, rng *rand.Rand) ([]WordPlacement, bool) {85 ordered := rankBoardCandidates(candidates)86 if len(ordered) < want {87 return nil, false88 }8990 firstWordCount := min(len(ordered), max(4, want+2))91 firstWords := append([]string(nil), ordered[:firstWordCount]...)92 shuffleStrings(firstWords, rng)9394 for _, firstWord := range firstWords {95 state := crosswordState{96 Cells: map[Position]crosswordCell{},97 }98 firstPlacement := WordPlacement{99 Text: firstWord,100 Start: Position{X: 0, Y: 0},101 Orientation: Horizontal,102 }103 state = applyPlacement(state, firstPlacement)104 used := map[string]struct{}{firstWord: {}}105 if solved, ok := placeRemainingWords(state, ordered, used, want, rng); ok {106 return solved.Placements, true107 }108 }109110 _ = bank111 return nil, false112}113114func placeRemainingWords(state crosswordState, candidates []string, used map[string]struct{}, want int, rng *rand.Rand) (crosswordState, bool) {115 if len(state.Placements) == want {116 return state, true117 }118119 ranked := rankWordsForState(state, candidates, used)120 if len(ranked) == 0 {121 return crosswordState{}, false122 }123124 need := want - len(state.Placements)125 if len(ranked) < need {126 return crosswordState{}, false127 }128129 for _, word := range ranked {130 placements := validPlacements(state, word)131 if len(placements) == 0 {132 continue133 }134 sortPlacements(placements, state)135 limit := min(len(placements), 8)136 for _, placement := range placements[:limit] {137 nextState := applyPlacement(state, placement)138 nextUsed := cloneWordSet(used)139 nextUsed[word] = struct{}{}140 if solved, ok := placeRemainingWords(nextState, candidates, nextUsed, want, rng); ok {141 return solved, true142 }143 }144 }145146 return crosswordState{}, false147}148149func rankBoardCandidates(candidates []string) []string {150 ordered := append([]string(nil), candidates...)151 overlap := make(map[string]int, len(ordered))152 for _, word := range ordered {153 score := 0154 seen := map[rune]struct{}{}155 for _, letter := range word {156 if _, ok := seen[letter]; ok {157 continue158 }159 seen[letter] = struct{}{}160 for _, other := range ordered {161 if word == other {162 continue163 }164 if stringsContainsRune(other, letter) {165 score++166 }167 }168 }169 overlap[word] = score170 }171172 sort.SliceStable(ordered, func(i, j int) bool {173 if len(ordered[i]) != len(ordered[j]) {174 return len(ordered[i]) > len(ordered[j])175 }176 if overlap[ordered[i]] != overlap[ordered[j]] {177 return overlap[ordered[i]] > overlap[ordered[j]]178 }179 return ordered[i] < ordered[j]180 })181 return ordered182}183184func rankWordsForState(state crosswordState, candidates []string, used map[string]struct{}) []string {185 type scoredWord struct {186 Word string187 Score int188 }189190 scored := make([]scoredWord, 0, len(candidates))191 cellPositions := sortedCellPositions(state.Cells)192 for _, word := range candidates {193 if _, ok := used[word]; ok {194 continue195 }196 score := len(word) * 10197 for _, pos := range cellPositions {198 cell := state.Cells[pos]199 if stringsContainsRune(word, cell.Letter) {200 score += 3201 }202 }203 scored = append(scored, scoredWord{Word: word, Score: score})204 }205206 sort.SliceStable(scored, func(i, j int) bool {207 if scored[i].Score != scored[j].Score {208 return scored[i].Score > scored[j].Score209 }210 return scored[i].Word < scored[j].Word211 })212213 result := make([]string, 0, len(scored))214 for _, item := range scored {215 result = append(result, item.Word)216 }217 return result218}219220func validPlacements(state crosswordState, word string) []WordPlacement {221 if len(state.Placements) == 0 {222 return []WordPlacement{{223 Text: word,224 Start: Position{X: 0, Y: 0},225 Orientation: Horizontal,226 }}227 }228229 result := make([]WordPlacement, 0, 16)230 seen := make(map[WordPlacement]struct{})231 for _, pos := range sortedCellPositions(state.Cells) {232 cell := state.Cells[pos]233 for idx, letter := range word {234 if letter != cell.Letter {235 continue236 }237238 if cell.Horizontal && !cell.Vertical {239 placement := WordPlacement{240 Text: word,241 Start: Position{X: pos.X, Y: pos.Y - idx},242 Orientation: Vertical,243 }244 if _, ok := seen[placement]; !ok && placementAllowed(state, placement) {245 seen[placement] = struct{}{}246 result = append(result, placement)247 }248 }249 if cell.Vertical && !cell.Horizontal {250 placement := WordPlacement{251 Text: word,252 Start: Position{X: pos.X - idx, Y: pos.Y},253 Orientation: Horizontal,254 }255 if _, ok := seen[placement]; !ok && placementAllowed(state, placement) {256 seen[placement] = struct{}{}257 result = append(result, placement)258 }259 }260 }261 }262 return result263}264265func placementAllowed(state crosswordState, placement WordPlacement) bool {266 before := placement.Start267 after := placement.Start268 if placement.Orientation == Horizontal {269 before.X--270 after.X += len(placement.Text)271 } else {272 before.Y--273 after.Y += len(placement.Text)274 }275 if _, ok := state.Cells[before]; ok {276 return false277 }278 if _, ok := state.Cells[after]; ok {279 return false280 }281282 intersections := 0283 for idx, letter := range placement.Text {284 pos := placement.Start285 if placement.Orientation == Horizontal {286 pos.X += idx287 } else {288 pos.Y += idx289 }290291 existing, occupied := state.Cells[pos]292 if occupied {293 if existing.Letter != letter {294 return false295 }296 if placement.Orientation == Horizontal && existing.Horizontal {297 return false298 }299 if placement.Orientation == Vertical && existing.Vertical {300 return false301 }302 intersections++303 continue304 }305306 if placement.Orientation == Horizontal {307 if hasCell(state.Cells, Position{X: pos.X, Y: pos.Y - 1}) || hasCell(state.Cells, Position{X: pos.X, Y: pos.Y + 1}) {308 return false309 }310 continue311 }312 if hasCell(state.Cells, Position{X: pos.X - 1, Y: pos.Y}) || hasCell(state.Cells, Position{X: pos.X + 1, Y: pos.Y}) {313 return false314 }315 }316317 return intersections > 0318}319320func applyPlacement(state crosswordState, placement WordPlacement) crosswordState {321 next := crosswordState{322 Cells: cloneCells(state.Cells),323 Placements: append(append([]WordPlacement(nil), state.Placements...), placement),324 }325 if len(state.Placements) == 0 {326 next.Placements = []WordPlacement{placement}327 }328329 for idx, letter := range placement.Text {330 pos := placement.Start331 if placement.Orientation == Horizontal {332 pos.X += idx333 } else {334 pos.Y += idx335 }336 cell := next.Cells[pos]337 cell.Letter = letter338 if placement.Orientation == Horizontal {339 cell.Horizontal = true340 } else {341 cell.Vertical = true342 }343 next.Cells[pos] = cell344 }345 return next346}347348func sortPlacements(placements []WordPlacement, state crosswordState) {349 sort.SliceStable(placements, func(i, j int) bool {350 iScore := placementScore(placements[i], state)351 jScore := placementScore(placements[j], state)352 if iScore != jScore {353 return iScore > jScore354 }355 if placements[i].Start.Y != placements[j].Start.Y {356 return placements[i].Start.Y < placements[j].Start.Y357 }358 if placements[i].Start.X != placements[j].Start.X {359 return placements[i].Start.X < placements[j].Start.X360 }361 if placements[i].Orientation != placements[j].Orientation {362 return placements[i].Orientation < placements[j].Orientation363 }364 return placements[i].Text < placements[j].Text365 })366}367368func placementScore(placement WordPlacement, state crosswordState) int {369 score := 0370 minX, minY, maxX, maxY := boundsForState(state)371 for idx := range len(placement.Text) {372 pos := placement.Start373 if placement.Orientation == Horizontal {374 pos.X += idx375 } else {376 pos.Y += idx377 }378 if existing, ok := state.Cells[pos]; ok {379 if existing.Letter != 0 {380 score += 10381 }382 }383 }384385 nextMinX := min(minX, placement.Start.X)386 nextMinY := min(minY, placement.Start.Y)387 end := placement.Start388 if placement.Orientation == Horizontal {389 end.X += len(placement.Text) - 1390 } else {391 end.Y += len(placement.Text) - 1392 }393 nextMaxX := max(maxX, end.X)394 nextMaxY := max(maxY, end.Y)395 area := (nextMaxX - nextMinX + 1) * (nextMaxY - nextMinY + 1)396 score -= area397 score -= int(math.Abs(float64(placement.Start.X)) + math.Abs(float64(placement.Start.Y)))398 return score399}400401func boundsForState(state crosswordState) (minX, minY, maxX, maxY int) {402 first := true403 for pos := range state.Cells {404 if first {405 minX, maxX = pos.X, pos.X406 minY, maxY = pos.Y, pos.Y407 first = false408 continue409 }410 minX = min(minX, pos.X)411 minY = min(minY, pos.Y)412 maxX = max(maxX, pos.X)413 maxY = max(maxY, pos.Y)414 }415 return minX, minY, maxX, maxY416}417418func cloneCells(cells map[Position]crosswordCell) map[Position]crosswordCell {419 cloned := make(map[Position]crosswordCell, len(cells))420 for pos, cell := range cells {421 cloned[pos] = cell422 }423 return cloned424}425426func cloneWordSet(words map[string]struct{}) map[string]struct{} {427 cloned := make(map[string]struct{}, len(words))428 for word := range words {429 cloned[word] = struct{}{}430 }431 return cloned432}433434func shuffleStrings(items []string, rng *rand.Rand) {435 rng.Shuffle(len(items), func(i, j int) {436 items[i], items[j] = items[j], items[i]437 })438}439440func scrambleBank(bank string, placements []WordPlacement, rng *rand.Rand) string {441 runes := []rune(bank)442 if len(runes) < 2 {443 return bank444 }445446 if hasSinglePermutation(runes) {447 return bank448 }449450 original := string(runes)451 candidate := append([]rune(nil), runes...)452 for range 16 {453 rng.Shuffle(len(candidate), func(i, j int) {454 candidate[i], candidate[j] = candidate[j], candidate[i]455 })456 scrambled := string(candidate)457 if scrambled == original {458 continue459 }460 if matchesPlacedWord(scrambled, placements) {461 continue462 }463 return scrambled464 }465466 for i := 1; i < len(runes); i++ {467 rotated := string(append(append([]rune(nil), runes[i:]...), runes[:i]...))468 if rotated == original {469 continue470 }471 if matchesPlacedWord(rotated, placements) {472 continue473 }474 return rotated475 }476477 return bank478}479480func hasSinglePermutation(runes []rune) bool {481 first := runes[0]482 for _, current := range runes[1:] {483 if current != first {484 return false485 }486 }487 return true488}489490func matchesPlacedWord(candidate string, placements []WordPlacement) bool {491 reversed := reverseWord(candidate)492 for _, placement := range placements {493 if placement.Text == candidate || placement.Text == reversed {494 return true495 }496 }497 return false498}499500func reverseWord(word string) string {501 runes := []rune(word)502 for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {503 runes[i], runes[j] = runes[j], runes[i]504 }505 return string(runes)506}507508func stringsContainsRune(text string, target rune) bool {509 for _, letter := range text {510 if letter == target {511 return true512 }513 }514 return false515}516517func hasCell(cells map[Position]crosswordCell, pos Position) bool {518 _, ok := cells[pos]519 return ok520}521522func sortedCellPositions(cells map[Position]crosswordCell) []Position {523 positions := make([]Position, 0, len(cells))524 for pos := range cells {525 positions = append(positions, pos)526 }527 sort.SliceStable(positions, func(i, j int) bool {528 if positions[i].Y != positions[j].Y {529 return positions[i].Y < positions[j].Y530 }531 return positions[i].X < positions[j].X532 })533 return positions534}