1package nurikabe23import (4 "context"5 "errors"6 "fmt"7 "math"8 "math/rand/v2"9 "sort"10 "sync"11 "time"12)1314const (15 generationHardTimeout = 10 * time.Second16 uniquenessMinRemainingBudget = 250 * time.Millisecond17 frontierBiasSampleCount = 718)1920type generationBudget struct {21 attempts int22 solvabilityNodes int23 uniquenessNodes int24 uniquenessProbeLimit int25}2627type islandProfile struct {28 baseSeaCoverage float6429 seaJitterRatio float6430 minSeaCoverage float6431 maxSeaCoverage float6432 minAverageSize float6433 maxSingletonRatio float6434 minLargestIsland int35 maxLargestIsland int36}3738type candidateState struct {39 width, height int40 sea [][]bool41 labels [][]int42 frontier []point43 frontierPos [][]int4445 seaCount int46 sea2x2Count int47 nextLabel int48 componentSize map[int]int49 sizeHistogram map[int]int50 singletons int51 largestIsland int52}5354type candidateStats struct {55 clueCount int56 totalLand int57 singletonCount int58 singletonRatio float6459 largestIsland int60 averageIsland float6461 sizeEntropy float6462 normalizedSpread float6463 fragmentPenalty float6464 clueDistance float6465}6667type candidateResult struct {68 attemptID int69 puzzle Puzzle70 stats candidateStats71 score float6472 clueKey string73}7475type attemptSeed struct {76 attemptID int77 seedA uint6478 seedB uint6479}8081type attemptOutcome struct {82 attemptID int83 candidate *candidateResult84 err error85}8687type uniquenessJob struct {88 clueKey string89 puzzle Puzzle90}9192type uniquenessOutcome struct {93 clueKey string94 count int95 err error96}9798func Generate(mode NurikabeMode) (Puzzle, error) {99 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))100 return GenerateSeededWithContext(context.Background(), mode, rng)101}102103func GenerateWithContext(ctx context.Context, mode NurikabeMode) (Puzzle, error) {104 rng := rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))105 return GenerateSeededWithContext(ctx, mode, rng)106}107108func GenerateSeeded(mode NurikabeMode, rng *rand.Rand) (Puzzle, error) {109 return GenerateSeededWithContext(context.Background(), mode, rng)110}111112func GenerateSeededWithContext(ctx context.Context, mode NurikabeMode, rng *rand.Rand) (Puzzle, error) {113 if rng == nil {114 return Puzzle{}, fmt.Errorf("nil RNG")115 }116 if mode.Width <= 0 || mode.Height <= 0 {117 return Puzzle{}, fmt.Errorf("invalid mode size %dx%d", mode.Width, mode.Height)118 }119 if mode.MaxIslandSize <= 0 {120 return Puzzle{}, fmt.Errorf("invalid max island size: %d", mode.MaxIslandSize)121 }122 if ctx == nil {123 ctx = context.Background()124 }125126 timeboxedCtx, cancel := context.WithTimeout(ctx, generationHardTimeout)127 defer cancel()128 deadline, _ := timeboxedCtx.Deadline()129130 area := mode.Width * mode.Height131 clueTarget := int(math.Round(float64(area) * mode.ClueDensity))132 clueTarget = min(max(clueTarget, 2), area-2)133134 profile := modeIslandProfile(mode)135 budget := modeGenerationBudget(mode)136 workerCount := candidateWorkerCount(mode)137 uniquenessWorkers := uniquenessWorkerCount(mode)138139 masterA := rng.Uint64()140 masterB := rng.Uint64()141142 attemptCh := make(chan attemptSeed)143 candidateCh := make(chan attemptOutcome, workerCount*2)144 uniqueCh := make(chan uniquenessJob, budget.uniquenessProbeLimit)145 uniqueResultCh := make(chan uniquenessOutcome, budget.uniquenessProbeLimit)146147 var candidateWG sync.WaitGroup148 for range workerCount {149 candidateWG.Add(1)150 go func() {151 defer candidateWG.Done()152 candidateWorker(timeboxedCtx, mode, clueTarget, profile, attemptCh, candidateCh)153 }()154 }155156 var uniqueWG sync.WaitGroup157 for range uniquenessWorkers {158 uniqueWG.Add(1)159 go func() {160 defer uniqueWG.Done()161 uniquenessWorker(timeboxedCtx, budget, uniqueCh, uniqueResultCh)162 }()163 }164 go func() {165 uniqueWG.Wait()166 close(uniqueResultCh)167 }()168169 bestSolvable := candidateResult{}170 haveBestSolvable := false171 bestUnique := candidateResult{}172 haveBestUnique := false173174 pendingUniqueByKey := map[string]candidateResult{}175 knownUniqueByKey := map[string]uniquenessOutcome{}176 uniquenessScheduled := 0177178 handleUniqueResult := func(result uniquenessOutcome) {179 knownUniqueByKey[result.clueKey] = result180 candidate, ok := pendingUniqueByKey[result.clueKey]181 delete(pendingUniqueByKey, result.clueKey)182 if !ok {183 return184 }185 if result.err != nil {186 if errors.Is(result.err, context.Canceled) ||187 errors.Is(result.err, context.DeadlineExceeded) {188 return189 }190 return191 }192 if result.count == 1 && (!haveBestUnique || betterCandidate(candidate, bestUnique)) {193 bestUnique = candidate194 haveBestUnique = true195 }196 }197198 drainUnique := func() {199 for {200 select {201 case result, ok := <-uniqueResultCh:202 if !ok {203 return204 }205 handleUniqueResult(result)206 default:207 return208 }209 }210 }211212 attemptID := 0213outer:214 for attemptID < budget.attempts {215 if err := timeboxedCtx.Err(); err != nil {216 break217 }218 drainUnique()219220 roundSize := min(workerCount, budget.attempts-attemptID)221 dispatched := 0222 for i := range roundSize {223 seedA, seedB := deriveAttemptSeeds(masterA, masterB, attemptID+i)224 job := attemptSeed{attemptID: attemptID + i, seedA: seedA, seedB: seedB}225 select {226 case attemptCh <- job:227 dispatched++228 case <-timeboxedCtx.Done():229 break outer230 }231 }232233 outcomes := make([]attemptOutcome, 0, dispatched)234 for len(outcomes) < dispatched {235 select {236 case out := <-candidateCh:237 outcomes = append(outcomes, out)238 case <-timeboxedCtx.Done():239 break outer240 }241 }242243 sort.Slice(outcomes, func(i, j int) bool {244 return outcomes[i].attemptID < outcomes[j].attemptID245 })246247 for _, out := range outcomes {248 if out.candidate == nil {249 continue250 }251 candidate := *out.candidate252 if !haveBestSolvable || betterCandidate(candidate, bestSolvable) {253 bestSolvable = candidate254 haveBestSolvable = true255 }256257 if knownResult, ok := knownUniqueByKey[candidate.clueKey]; ok {258 if knownResult.err == nil &&259 knownResult.count == 1 &&260 (!haveBestUnique || betterCandidate(candidate, bestUnique)) {261 bestUnique = candidate262 haveBestUnique = true263 }264 continue265 }266267 if pendingCandidate, ok := pendingUniqueByKey[candidate.clueKey]; ok {268 if betterCandidate(candidate, pendingCandidate) {269 pendingUniqueByKey[candidate.clueKey] = candidate270 }271 continue272 }273274 if shouldProbeUniqueness(candidate, haveBestSolvable, bestSolvable, uniquenessScheduled, budget, deadline) {275 job := uniquenessJob{276 clueKey: candidate.clueKey,277 puzzle: candidate.puzzle,278 }279 pendingUniqueByKey[candidate.clueKey] = candidate280 select {281 case uniqueCh <- job:282 uniquenessScheduled++283 case <-timeboxedCtx.Done():284 break outer285 }286 }287 }288289 drainUnique()290 attemptID += dispatched291 }292293 close(attemptCh)294 candidateWG.Wait()295 close(uniqueCh)296 for result := range uniqueResultCh {297 handleUniqueResult(result)298 }299300 if haveBestUnique {301 return bestUnique.puzzle, nil302 }303 if haveBestSolvable {304 return bestSolvable.puzzle, nil305 }306307 if err := timeboxedCtx.Err(); err != nil {308 if errors.Is(err, context.Canceled) {309 return Puzzle{}, fmt.Errorf("nurikabe generation canceled: %w", err)310 }311 return Puzzle{}, fmt.Errorf("nurikabe generation timed out: %w", err)312 }313314 return Puzzle{}, fmt.Errorf("unable to generate solvable nurikabe puzzle for mode %q within constraints", mode.Title())315}316317func candidateWorker(318 ctx context.Context,319 mode NurikabeMode,320 clueTarget int,321 profile islandProfile,322 attemptCh <-chan attemptSeed,323 candidateCh chan<- attemptOutcome,324) {325 for {326 select {327 case <-ctx.Done():328 return329 case attempt, ok := <-attemptCh:330 if !ok {331 return332 }333334 rng := rand.New(rand.NewPCG(attempt.seedA, attempt.seedB))335 candidate, err := buildCandidateByCarving(mode, clueTarget, profile, rng, attempt.attemptID)336 out := attemptOutcome{attemptID: attempt.attemptID, err: err}337 if err == nil {338 candidateCopy := candidate339 out.candidate = &candidateCopy340 }341342 select {343 case candidateCh <- out:344 case <-ctx.Done():345 return346 }347 }348 }349}350351func uniquenessWorker(352 ctx context.Context,353 budget generationBudget,354 uniqueCh <-chan uniquenessJob,355 uniqueResultCh chan<- uniquenessOutcome,356) {357 for {358 select {359 case <-ctx.Done():360 return361 case job, ok := <-uniqueCh:362 if !ok {363 return364 }365366 count, _, err := CountSolutionsContext(ctx, job.puzzle, 2, budget.uniquenessNodes)367 result := uniquenessOutcome{clueKey: job.clueKey, count: count, err: err}368 select {369 case uniqueResultCh <- result:370 case <-ctx.Done():371 return372 }373 }374 }375}376377func buildCandidateByCarving(378 mode NurikabeMode,379 clueTarget int,380 profile islandProfile,381 rng *rand.Rand,382 attemptID int,383) (candidateResult, error) {384 start := point{rng.IntN(mode.Width), rng.IntN(mode.Height)}385 state := newCandidateState(mode.Width, mode.Height, start)386387 targetSea := chooseTargetSeaCells(mode, profile, rng)388 for state.seaCount < targetSea {389 candidate, ok := state.popFrontier(rng)390 if !ok {391 return candidateResult{}, fmt.Errorf("frontier exhausted")392 }393 if !state.canCarve(candidate) {394 continue395 }396 if !state.carve(candidate) {397 continue398 }399 }400401 components := state.components()402 stats := state.stats(components, clueTarget)403 if !stats.meetsProfile(mode, profile, clueTarget) {404 return candidateResult{}, fmt.Errorf("distribution out of bounds")405 }406407 clues := make(clueGrid, mode.Height)408 for y := range mode.Height {409 clues[y] = make([]int, mode.Width)410 }411 for _, component := range components {412 if len(component) == 0 {413 continue414 }415 clueCell := component[rng.IntN(len(component))]416 clues[clueCell.y][clueCell.x] = len(component)417 }418419 puzzle := Puzzle{Width: mode.Width, Height: mode.Height, Clues: clues}420 if err := validateClues(puzzle.Clues, puzzle.Width, puzzle.Height); err != nil {421 return candidateResult{}, err422 }423424 completed := state.completedGrid(clues)425 if !isSolvedGrid(completed, clues) {426 return candidateResult{}, fmt.Errorf("constructed board failed solved validation")427 }428429 stats.clueCount = len(components)430 stats.clueDistance = clueDistance(stats.clueCount, clueTarget)431432 candidate := candidateResult{433 attemptID: attemptID,434 puzzle: puzzle,435 stats: stats,436 score: scoreCandidate(mode, stats),437 clueKey: serializeClues(clues),438 }439440 return candidate, nil441}442443func newCandidateState(width, height int, start point) *candidateState {444 sea := make([][]bool, height)445 labels := make([][]int, height)446 frontierPos := make([][]int, height)447 for y := range height {448 sea[y] = make([]bool, width)449 labels[y] = make([]int, width)450 frontierPos[y] = make([]int, width)451 for x := range width {452 labels[y][x] = 1453 frontierPos[y][x] = -1454 }455 }456457 state := &candidateState{458 width: width,459 height: height,460 sea: sea,461 labels: labels,462 frontier: make([]point, 0, width*height),463 frontierPos: frontierPos,464 componentSize: map[int]int{1: width * height},465 sizeHistogram: map[int]int{width * height: 1},466 singletons: 1,467 largestIsland: width * height,468 nextLabel: 2,469 }470 if width*height > 1 {471 state.singletons = 0472 }473 state.carve(start)474 return state475}476477func (s *candidateState) inBounds(p point) bool {478 return p.x >= 0 && p.x < s.width && p.y >= 0 && p.y < s.height479}480481func (s *candidateState) canCarve(p point) bool {482 if !s.inBounds(p) || s.sea[p.y][p.x] {483 return false484 }485 if s.newSeaSquaresFromCarve(p) > 0 {486 return false487 }488 return true489}490491func (s *candidateState) carve(p point) bool {492 if !s.canCarve(p) {493 return false494 }495496 oldLabel := s.labels[p.y][p.x]497 if oldLabel < 0 {498 return false499 }500501 deltaSquares := s.newSeaSquaresFromCarve(p)502 s.sea[p.y][p.x] = true503 s.labels[p.y][p.x] = -1504 s.seaCount++505 s.sea2x2Count += deltaSquares506 s.removeFrontier(p)507508 oldSize := s.componentSize[oldLabel]509 s.removeComponent(oldLabel)510511 neighbors := s.landNeighborsWithLabel(p, oldLabel)512 sort.Slice(neighbors, func(i, j int) bool {513 if neighbors[i].y != neighbors[j].y {514 return neighbors[i].y < neighbors[j].y515 }516 return neighbors[i].x < neighbors[j].x517 })518 neighbors = dedupePoints(neighbors)519520 switch len(neighbors) {521 case 0:522 // Entire component removed.523 case 1:524 s.setComponent(oldLabel, oldSize-1)525 default:526 s.relabelSplit(oldLabel, neighbors)527 }528529 for _, d := range dirs {530 n := point{x: p.x + d.x, y: p.y + d.y}531 if !s.inBounds(n) || s.sea[n.y][n.x] {532 continue533 }534 s.addFrontier(n)535 }536537 return true538}539540func dedupePoints(in []point) []point {541 if len(in) < 2 {542 return in543 }544 out := in[:1]545 for i := 1; i < len(in); i++ {546 if in[i] != in[i-1] {547 out = append(out, in[i])548 }549 }550 return out551}552553func (s *candidateState) landNeighborsWithLabel(p point, label int) []point {554 neighbors := make([]point, 0, 4)555 for _, d := range dirs {556 n := point{x: p.x + d.x, y: p.y + d.y}557 if !s.inBounds(n) {558 continue559 }560 if s.labels[n.y][n.x] == label {561 neighbors = append(neighbors, n)562 }563 }564 return neighbors565}566567func (s *candidateState) relabelSplit(oldLabel int, seeds []point) {568 visited := make([][]bool, s.height)569 for y := range s.height {570 visited[y] = make([]bool, s.width)571 }572573 componentIndex := 0574 for _, seed := range seeds {575 if visited[seed.y][seed.x] || s.labels[seed.y][seed.x] != oldLabel {576 continue577 }578579 newLabel := oldLabel580 if componentIndex > 0 {581 newLabel = s.nextLabel582 s.nextLabel++583 }584585 queue := []point{seed}586 visited[seed.y][seed.x] = true587 cells := make([]point, 0, 16)588 for len(queue) > 0 {589 cell := queue[0]590 queue = queue[1:]591 cells = append(cells, cell)592593 for _, d := range dirs {594 n := point{x: cell.x + d.x, y: cell.y + d.y}595 if !s.inBounds(n) || visited[n.y][n.x] || s.labels[n.y][n.x] != oldLabel {596 continue597 }598 visited[n.y][n.x] = true599 queue = append(queue, n)600 }601 }602603 if newLabel != oldLabel {604 for _, cell := range cells {605 s.labels[cell.y][cell.x] = newLabel606 }607 }608 s.setComponent(newLabel, len(cells))609 componentIndex++610 }611}612613func (s *candidateState) newSeaSquaresFromCarve(p point) int {614 count := 0615 for dy := -1; dy <= 0; dy++ {616 for dx := -1; dx <= 0; dx++ {617 x0 := p.x + dx618 y0 := p.y + dy619 if x0 < 0 || y0 < 0 || x0+1 >= s.width || y0+1 >= s.height {620 continue621 }622623 allSea := true624 for yy := y0; yy <= y0+1; yy++ {625 for xx := x0; xx <= x0+1; xx++ {626 if xx == p.x && yy == p.y {627 continue628 }629 if !s.sea[yy][xx] {630 allSea = false631 break632 }633 }634 if !allSea {635 break636 }637 }638 if allSea {639 count++640 }641 }642 }643 return count644}645646func (s *candidateState) addFrontier(p point) {647 if !s.inBounds(p) || s.sea[p.y][p.x] || s.frontierPos[p.y][p.x] >= 0 {648 return649 }650 idx := len(s.frontier)651 s.frontier = append(s.frontier, p)652 s.frontierPos[p.y][p.x] = idx653}654655func (s *candidateState) removeFrontier(p point) {656 if !s.inBounds(p) {657 return658 }659 idx := s.frontierPos[p.y][p.x]660 if idx < 0 || idx >= len(s.frontier) {661 return662 }663664 last := len(s.frontier) - 1665 tail := s.frontier[last]666 s.frontier[idx] = tail667 s.frontierPos[tail.y][tail.x] = idx668 s.frontier = s.frontier[:last]669 s.frontierPos[p.y][p.x] = -1670}671672func (s *candidateState) popFrontier(rng *rand.Rand) (point, bool) {673 if len(s.frontier) == 0 {674 return point{}, false675 }676677 bestIdx := -1678 bestScore := -1679 samples := min(frontierBiasSampleCount, len(s.frontier))680 for range samples {681 idx := rng.IntN(len(s.frontier))682 score := s.frontierPriorityScore(s.frontier[idx])683 if score > bestScore || (score == bestScore && rng.IntN(2) == 0) {684 bestScore = score685 bestIdx = idx686 }687 }688689 if bestIdx < 0 {690 bestIdx = rng.IntN(len(s.frontier))691 }692693 picked := s.frontier[bestIdx]694 s.removeFrontier(picked)695 return picked, true696}697698func (s *candidateState) frontierPriorityScore(p point) int {699 if !s.inBounds(p) || s.sea[p.y][p.x] {700 return 0701 }702703 label := s.labels[p.y][p.x]704 componentSize := s.componentSize[label]705 sameLabelNeighbors := len(s.landNeighborsWithLabel(p, label))706707 // Favor carving from larger components; local degree nudges toward useful splits.708 return componentSize*16 + sameLabelNeighbors*3709}710711func (s *candidateState) removeComponent(label int) {712 size, ok := s.componentSize[label]713 if !ok {714 return715 }716 delete(s.componentSize, label)717 s.sizeHistogram[size]--718 if s.sizeHistogram[size] <= 0 {719 delete(s.sizeHistogram, size)720 }721 if size == 1 {722 s.singletons--723 }724 if size == s.largestIsland {725 s.recomputeLargestIsland()726 }727}728729func (s *candidateState) setComponent(label, size int) {730 if size <= 0 {731 return732 }733 s.componentSize[label] = size734 s.sizeHistogram[size]++735 if size == 1 {736 s.singletons++737 }738 if size > s.largestIsland {739 s.largestIsland = size740 }741}742743func (s *candidateState) recomputeLargestIsland() {744 largest := 0745 for size := range s.sizeHistogram {746 if size > largest {747 largest = size748 }749 }750 s.largestIsland = largest751}752753func (s *candidateState) components() [][]point {754 byLabel := map[int][]point{}755 labels := make([]int, 0, len(s.componentSize))756 for label := range s.componentSize {757 labels = append(labels, label)758 }759 sort.Ints(labels)760761 for y := 0; y < s.height; y++ {762 for x := 0; x < s.width; x++ {763 label := s.labels[y][x]764 if label < 0 {765 continue766 }767 byLabel[label] = append(byLabel[label], point{x: x, y: y})768 }769 }770771 components := make([][]point, 0, len(labels))772 for _, label := range labels {773 component := byLabel[label]774 if len(component) == 0 {775 continue776 }777 components = append(components, component)778 }779 return components780}781782func (s *candidateState) completedGrid(clues clueGrid) grid {783 g := newGrid(s.width, s.height, islandCell)784 for y := 0; y < s.height; y++ {785 for x := 0; x < s.width; x++ {786 if s.sea[y][x] {787 g[y][x] = seaCell788 continue789 }790 if clues[y][x] > 0 {791 g[y][x] = islandCell792 }793 }794 }795 return g796}797798func (s *candidateState) stats(components [][]point, clueTarget int) candidateStats {799 stats := candidateStats{}800 if len(components) == 0 {801 return stats802 }803804 sizes := make([]int, 0, len(components))805 total := 0806 for _, component := range components {807 size := len(component)808 sizes = append(sizes, size)809 total += size810 if size == 1 {811 stats.singletonCount++812 }813 if size > stats.largestIsland {814 stats.largestIsland = size815 }816 }817818 stats.clueCount = len(components)819 stats.totalLand = total820 stats.singletonRatio = float64(stats.singletonCount) / float64(max(1, len(components)))821 stats.averageIsland = float64(total) / float64(len(components))822 stats.sizeEntropy = componentSizeEntropy(sizes)823 stats.normalizedSpread = normalizedSpread(sizes)824 stats.fragmentPenalty = fragmentPenalty(len(components), clueTarget)825 stats.clueDistance = clueDistance(len(components), clueTarget)826827 return stats828}829830func componentSizeEntropy(sizes []int) float64 {831 if len(sizes) == 0 {832 return 0833 }834 freq := map[int]int{}835 for _, size := range sizes {836 freq[size]++837 }838 keys := make([]int, 0, len(freq))839 for size := range freq {840 keys = append(keys, size)841 }842 sort.Ints(keys)843844 denom := float64(len(sizes))845 entropy := 0.0846 for _, size := range keys {847 count := freq[size]848 p := float64(count) / denom849 entropy -= p * math.Log(p)850 }851 return entropy852}853854func normalizedSpread(sizes []int) float64 {855 if len(sizes) == 0 {856 return 0857 }858 mean := 0.0859 for _, size := range sizes {860 mean += float64(size)861 }862 mean /= float64(len(sizes))863 if mean == 0 {864 return 0865 }866 variance := 0.0867 for _, size := range sizes {868 d := float64(size) - mean869 variance += d * d870 }871 variance /= float64(len(sizes))872 return math.Sqrt(variance) / mean873}874875func fragmentPenalty(clueCount, clueTarget int) float64 {876 if clueTarget <= 0 {877 return 0878 }879 delta := math.Abs(float64(clueCount - clueTarget))880 return delta / float64(clueTarget)881}882883func clueDistance(clueCount, clueTarget int) float64 {884 if clueTarget <= 0 {885 return 0886 }887 return math.Abs(float64(clueCount-clueTarget)) / float64(clueTarget)888}889890func (s candidateStats) meetsProfile(mode NurikabeMode, profile islandProfile, clueTarget int) bool {891 if s.clueCount < 2 {892 return false893 }894 if s.singletonRatio > profile.maxSingletonRatio {895 return false896 }897 if s.averageIsland < profile.minAverageSize {898 return false899 }900 if s.largestIsland < profile.minLargestIsland {901 return false902 }903 maxLargest := mode.MaxIslandSize * 2904 if profile.maxLargestIsland > 0 {905 maxLargest = min(maxLargest, profile.maxLargestIsland)906 }907 if s.largestIsland > maxLargest {908 return false909 }910911 tol := max(2, clueTarget/2)912 if s.clueCount < max(2, clueTarget-tol) || s.clueCount > clueTarget+tol {913 return false914 }915916 return true917}918919func scoreCandidate(mode NurikabeMode, stats candidateStats) float64 {920 score := 0.0921 score += stats.sizeEntropy * 3.2922 score += stats.normalizedSpread * 1.3923 score -= stats.singletonRatio * 2.6924 score -= stats.fragmentPenalty * 1.6925 score -= stats.clueDistance * 0.9926 score += min(1.5, float64(stats.largestIsland)/float64(max(1, mode.MaxIslandSize))) * 0.4927 idealLargest := float64(max(mode.Width, mode.Height)) * 1.45928 if stats.largestIsland > int(math.Round(idealLargest)) {929 oversize := (float64(stats.largestIsland) - idealLargest) / max(1.0, idealLargest)930 score -= oversize * 1.2931 }932 return score933}934935func betterCandidate(a, b candidateResult) bool {936 if d := a.score - b.score; math.Abs(d) > 1e-9 {937 return d > 0938 }939 if a.stats.singletonCount != b.stats.singletonCount {940 return a.stats.singletonCount < b.stats.singletonCount941 }942 if a.attemptID != b.attemptID {943 return a.attemptID < b.attemptID944 }945 return a.clueKey < b.clueKey946}947948func shouldProbeUniqueness(949 candidate candidateResult,950 haveBestSolvable bool,951 bestSolvable candidateResult,952 scheduled int,953 budget generationBudget,954 deadline time.Time,955) bool {956 if scheduled >= budget.uniquenessProbeLimit {957 return false958 }959 if time.Until(deadline) < uniquenessMinRemainingBudget {960 return false961 }962 if scheduled < 3 {963 return true964 }965 if !haveBestSolvable {966 return true967 }968 return candidate.score >= bestSolvable.score-0.8969}970971func chooseTargetSeaCells(mode NurikabeMode, profile islandProfile, rng *rand.Rand) int {972 area := mode.Width * mode.Height973 targetSea := int(math.Round(float64(area) * profile.baseSeaCoverage))974 jitter := int(math.Round(float64(area) * profile.seaJitterRatio))975 if jitter > 0 {976 targetSea += rng.IntN(2*jitter+1) - jitter977 }978979 minSea := max(1, int(math.Round(float64(area)*profile.minSeaCoverage)))980 maxSea := min(area-1, int(math.Round(float64(area)*profile.maxSeaCoverage)))981 if targetSea < minSea {982 targetSea = minSea983 }984 if targetSea > maxSea {985 targetSea = maxSea986 }987988 return targetSea989}990991func deriveAttemptSeeds(masterA, masterB uint64, attemptID int) (uint64, uint64) {992 id := uint64(attemptID + 1)993 seedA := splitmix64(masterA ^ (id * 0x9e3779b97f4a7c15))994 seedB := splitmix64(masterB ^ (id * 0xbf58476d1ce4e5b9))995 return seedA, seedB996}997998func splitmix64(x uint64) uint64 {999 x += 0x9e3779b97f4a7c151000 x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b91001 x = (x ^ (x >> 27)) * 0x94d049bb133111eb1002 return x ^ (x >> 31)1003}10041005func candidateWorkerCount(mode NurikabeMode) int {1006 switch mode.Title() {1007 case "Mini":1008 return 11009 case "Easy":1010 return 21011 case "Medium":1012 return 21013 case "Hard":1014 return 41015 case "Expert":1016 return 41017 default:1018 return 21019 }1020}10211022func uniquenessWorkerCount(mode NurikabeMode) int {1023 switch mode.Title() {1024 case "Mini":1025 return 11026 case "Easy":1027 return 11028 case "Medium":1029 return 21030 case "Hard":1031 return 41032 case "Expert":1033 return 51034 default:1035 return 21036 }1037}10381039func modeIslandProfile(mode NurikabeMode) islandProfile {1040 switch mode.Title() {1041 case "Mini":1042 return islandProfile{1043 baseSeaCoverage: 0.51,1044 seaJitterRatio: 0.05,1045 minSeaCoverage: 0.40,1046 maxSeaCoverage: 0.62,1047 minAverageSize: 1.85,1048 maxSingletonRatio: 0.63,1049 minLargestIsland: 3,1050 maxLargestIsland: 0,1051 }1052 case "Easy":1053 return islandProfile{1054 baseSeaCoverage: 0.55,1055 seaJitterRatio: 0.05,1056 minSeaCoverage: 0.42,1057 maxSeaCoverage: 0.64,1058 minAverageSize: 1.95,1059 maxSingletonRatio: 0.56,1060 minLargestIsland: 4,1061 maxLargestIsland: 0,1062 }1063 case "Medium":1064 return islandProfile{1065 baseSeaCoverage: 0.58,1066 seaJitterRatio: 0.05,1067 minSeaCoverage: 0.44,1068 maxSeaCoverage: 0.65,1069 minAverageSize: 1.95,1070 maxSingletonRatio: 0.58,1071 minLargestIsland: 5,1072 maxLargestIsland: 0,1073 }1074 case "Hard":1075 return islandProfile{1076 baseSeaCoverage: 0.60,1077 seaJitterRatio: 0.04,1078 minSeaCoverage: 0.44,1079 maxSeaCoverage: 0.67,1080 minAverageSize: 1.8,1081 maxSingletonRatio: 0.72,1082 minLargestIsland: 4,1083 maxLargestIsland: 15,1084 }1085 case "Expert":1086 return islandProfile{1087 baseSeaCoverage: 0.62,1088 seaJitterRatio: 0.04,1089 minSeaCoverage: 0.44,1090 maxSeaCoverage: 0.68,1091 minAverageSize: 1.7,1092 maxSingletonRatio: 0.78,1093 minLargestIsland: 4,1094 maxLargestIsland: 17,1095 }1096 default:1097 return islandProfile{1098 baseSeaCoverage: 0.55,1099 seaJitterRatio: 0.05,1100 minSeaCoverage: 0.42,1101 maxSeaCoverage: 0.65,1102 minAverageSize: 2.1,1103 maxSingletonRatio: 0.48,1104 minLargestIsland: 4,1105 maxLargestIsland: 0,1106 }1107 }1108}11091110func modeGenerationBudget(mode NurikabeMode) generationBudget {1111 switch mode.Title() {1112 case "Mini":1113 return generationBudget{attempts: 320, solvabilityNodes: 25000, uniquenessNodes: 60000, uniquenessProbeLimit: 6}1114 case "Easy":1115 return generationBudget{attempts: 400, solvabilityNodes: 45000, uniquenessNodes: 100000, uniquenessProbeLimit: 8}1116 case "Medium":1117 return generationBudget{attempts: 500, solvabilityNodes: 70000, uniquenessNodes: 140000, uniquenessProbeLimit: 10}1118 case "Hard":1119 return generationBudget{attempts: 420, solvabilityNodes: 70000, uniquenessNodes: 120000, uniquenessProbeLimit: 8}1120 case "Expert":1121 return generationBudget{attempts: 320, solvabilityNodes: 70000, uniquenessNodes: 100000, uniquenessProbeLimit: 6}1122 default:1123 return generationBudget{attempts: 400, solvabilityNodes: 45000, uniquenessNodes: 100000, uniquenessProbeLimit: 8}1124 }1125}