1package wordsearch23import (4 "math/rand/v2"5 "sort"6 "strings"7)89type placementStats struct {10 TargetWords int11 PlacedWords int12 FailedWords int13 RandomAttempts int14 FallbackAttempts int15 FallbackUsed int16 FallbackPlaced int17}1819func (s placementStats) SuccessRate() float64 {20 if s.TargetWords == 0 {21 return 122 }23 return float64(s.PlacedWords) / float64(s.TargetWords)24}2526func (s placementStats) AttemptsPerWord() float64 {27 if s.TargetWords == 0 {28 return 029 }30 attempts := s.RandomAttempts + s.FallbackAttempts31 return float64(attempts) / float64(s.TargetWords)32}3334type placementAttemptStats struct {35 RandomAttempts int36 FallbackAttempts int37 UsedFallback bool38}3940type wordBucketSampler struct {41 words []string42 remaining int43 swaps map[int]int44}4546func (s *wordBucketSampler) resolve(pos int) int {47 if s.swaps == nil {48 return pos49 }50 if mapped, ok := s.swaps[pos]; ok {51 return mapped52 }53 return pos54}5556func (s *wordBucketSampler) draw(rng *rand.Rand) string {57 drawPos := rng.IntN(s.remaining)58 wordIndex := s.resolve(drawPos)5960 lastPos := s.remaining - 161 lastIndex := s.resolve(lastPos)6263 if drawPos != lastPos {64 if s.swaps == nil {65 s.swaps = map[int]int{}66 }67 s.swaps[drawPos] = lastIndex68 }6970 if s.swaps != nil {71 delete(s.swaps, lastPos)72 }7374 s.remaining--75 return s.words[wordIndex]76}7778func GenerateWordSearch(width, height, wordCount, minLen, maxLen int, allowedDirs []Direction) (grid, []Word) {79 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))80 return GenerateWordSearchSeeded(width, height, wordCount, minLen, maxLen, allowedDirs, rng)81}8283func GenerateWordSearchSeeded(width, height, wordCount, minLen, maxLen int, allowedDirs []Direction, rng *rand.Rand) (grid, []Word) {84 g, placedWords, _ := generateWordSearchSeededWithStats(85 width,86 height,87 wordCount,88 minLen,89 maxLen,90 allowedDirs,91 rng,92 )93 return g, placedWords94}9596func generateWordSearchSeededWithStats(97 width,98 height,99 wordCount,100 minLen,101 maxLen int,102 allowedDirs []Direction,103 rng *rand.Rand,104) (grid, []Word, placementStats) {105 g := createEmptyGrid(height, width)106 words := selectWordsSeeded(wordCount, minLen, maxLen, rng)107 orderWordsForPlacement(words)108109 placedWords := make([]Word, 0, len(words))110 stats := placementStats{TargetWords: len(words)}111112 for _, wordText := range words {113 word, attemptStats := tryPlaceWordSeededWithFallback(g, wordText, allowedDirs, 100, rng)114115 stats.RandomAttempts += attemptStats.RandomAttempts116 stats.FallbackAttempts += attemptStats.FallbackAttempts117 if attemptStats.UsedFallback {118 stats.FallbackUsed++119 }120121 if word == nil {122 stats.FailedWords++123 continue124 }125126 stats.PlacedWords++127 if attemptStats.UsedFallback {128 stats.FallbackPlaced++129 }130 placedWords = append(placedWords, *word)131 }132133 fillEmptyCellsSeeded(g, rng)134135 return g, placedWords, stats136}137138func selectWordsSeeded(count, minLen, maxLen int, rng *rand.Rand) []string {139 if count <= 0 || minLen > maxLen {140 return nil141 }142143 buckets := make([]wordBucketSampler, 0, maxLen-minLen+1)144 totalAvailable := 0145146 for length := minLen; length <= maxLen; length++ {147 words, ok := wordsByLength[length]148 if !ok || len(words) == 0 {149 continue150 }151152 buckets = append(buckets, wordBucketSampler{153 words: words,154 remaining: len(words),155 })156 totalAvailable += len(words)157 }158159 if totalAvailable == 0 {160 return nil161 }162163 if count > totalAvailable {164 count = totalAvailable165 }166167 selected := make([]string, 0, count)168 for range count {169 bucketIndex := pickBucketByRemaining(buckets, totalAvailable, rng)170 selected = append(selected, buckets[bucketIndex].draw(rng))171 totalAvailable--172 }173174 return selected175}176177func pickBucketByRemaining(buckets []wordBucketSampler, totalRemaining int, rng *rand.Rand) int {178 randomOffset := rng.IntN(totalRemaining)179180 for i := range buckets {181 if randomOffset < buckets[i].remaining {182 return i183 }184 randomOffset -= buckets[i].remaining185 }186187 return len(buckets) - 1188}189190func orderWordsForPlacement(words []string) {191 sort.SliceStable(words, func(i, j int) bool {192 return len(words[i]) > len(words[j])193 })194}195196func tryPlaceWordSeeded(g grid, text string, allowedDirs []Direction, maxAttempts int, rng *rand.Rand) *Word {197 word, _ := tryPlaceWordSeededWithFallback(g, text, allowedDirs, maxAttempts, rng)198 return word199}200201func tryPlaceWordSeededWithFallback(202 g grid,203 text string,204 allowedDirs []Direction,205 maxAttempts int,206 rng *rand.Rand,207) (*Word, placementAttemptStats) {208 word, randomAttempts := tryPlaceWordSeededRandom(g, text, allowedDirs, maxAttempts, rng)209 if word != nil {210 return word, placementAttemptStats{RandomAttempts: randomAttempts}211 }212213 fallbackWord, fallbackAttempts := tryPlaceWordSeededFallback(g, text, allowedDirs, rng)214 return fallbackWord, placementAttemptStats{215 RandomAttempts: randomAttempts,216 FallbackAttempts: fallbackAttempts,217 UsedFallback: fallbackAttempts > 0,218 }219}220221func tryPlaceWordSeededRandom(g grid, text string, allowedDirs []Direction, maxAttempts int, rng *rand.Rand) (*Word, int) {222 text = strings.ToUpper(text)223 if maxAttempts <= 0 || len(text) == 0 || len(allowedDirs) == 0 || len(g) == 0 || len(g[0]) == 0 {224 return nil, 0225 }226227 height := len(g)228 width := len(g[0])229230 for attempt := 1; attempt <= maxAttempts; attempt++ {231 x := rng.IntN(width)232 y := rng.IntN(height)233234 dir := allowedDirs[rng.IntN(len(allowedDirs))]235 dx, dy := dir.Vector()236237 if !wordInBounds(x, y, dx, dy, len(text), width, height) {238 continue239 }240 if !canPlaceWordAt(g, text, x, y, dx, dy) {241 continue242 }243244 placeWordAt(g, text, x, y, dx, dy)245 return newWord(text, x, y, dx, dy, dir), attempt246 }247248 return nil, maxAttempts249}250251func tryPlaceWordSeededFallback(g grid, text string, allowedDirs []Direction, rng *rand.Rand) (*Word, int) {252 text = strings.ToUpper(text)253 if len(text) == 0 || len(allowedDirs) == 0 || len(g) == 0 || len(g[0]) == 0 {254 return nil, 0255 }256257 height := len(g)258 width := len(g[0])259260 dirs := append([]Direction(nil), allowedDirs...)261 rng.Shuffle(len(dirs), func(i, j int) {262 dirs[i], dirs[j] = dirs[j], dirs[i]263 })264265 startX := rng.IntN(width)266 startY := rng.IntN(height)267268 attempts := 0269 for _, dir := range dirs {270 dx, dy := dir.Vector()271 for yStep := range height {272 y := (startY + yStep) % height273 for xStep := range width {274 x := (startX + xStep) % width275 attempts++276277 if !wordInBounds(x, y, dx, dy, len(text), width, height) {278 continue279 }280 if !canPlaceWordAt(g, text, x, y, dx, dy) {281 continue282 }283284 placeWordAt(g, text, x, y, dx, dy)285 return newWord(text, x, y, dx, dy, dir), attempts286 }287 }288 }289290 return nil, attempts291}292293func wordInBounds(x, y, dx, dy, wordLen, width, height int) bool {294 endX := x + dx*(wordLen-1)295 endY := y + dy*(wordLen-1)296 return endX >= 0 && endX < width && endY >= 0 && endY < height297}298299func canPlaceWordAt(g grid, text string, x, y, dx, dy int) bool {300 for i := range len(text) {301 cx := x + dx*i302 cy := y + dy*i303 existing := g.Get(cx, cy)304 want := rune(text[i])305 if existing != ' ' && existing != want {306 return false307 }308 }309 return true310}311312func placeWordAt(g grid, text string, x, y, dx, dy int) {313 for i := range len(text) {314 cx := x + dx*i315 cy := y + dy*i316 g.Set(cx, cy, rune(text[i]))317 }318}319320func newWord(text string, x, y, dx, dy int, dir Direction) *Word {321 endX := x + dx*(len(text)-1)322 endY := y + dy*(len(text)-1)323324 return &Word{325 Text: text,326 Start: Position{X: x, Y: y},327 End: Position{X: endX, Y: endY},328 Direction: dir,329 Found: false,330 }331}332333func fillEmptyCellsSeeded(g grid, rng *rand.Rand) {334 letters := "ABCDEFGHIJKLMNOPQRSTUVWXYZ"335336 for y := range g {337 for x := range g[y] {338 if g[y][x] == ' ' {339 g[y][x] = rune(letters[rng.IntN(len(letters))])340 }341 }342 }343}