1package shikaku23import (4 "crypto/sha256"5 "encoding/binary"6 "errors"7 "math"8 "math/rand/v2"9 "strconv"1011 "github.com/FelineStateMachine/puzzletea/difficulty"12 "github.com/FelineStateMachine/puzzletea/game"13)1415var _ game.EloSpawner = ShikakuMode{}1617type shikakuEloSolveStats struct {18 Nodes int19 Branches int20 MaxDepth int21}2223func (s ShikakuMode) SpawnElo(seed string, elo difficulty.Elo) (game.Gamer, difficulty.Report, error) {24 if err := difficulty.ValidateElo(elo); err != nil {25 return nil, difficulty.Report{}, err26 }2728 mode := shikakuModeForElo(s, elo)29 var bestPuzzle Puzzle30 var bestReport difficulty.Report31 haveBest := false32 var lastErr error33 for candidate := range difficulty.CandidateCount(elo) {34 puzzle, err := GeneratePuzzleSeeded(mode.Width, mode.Height, mode.MaxRectSize, shikakuEloRNG(shikakuCandidateSeed(seed, candidate), elo))35 if err != nil {36 lastErr = err37 continue38 }39 report := scoreShikakuElo(elo, mode, puzzle)40 if difficulty.BetterCandidate(report, bestReport, elo, haveBest) {41 bestPuzzle = puzzle42 bestReport = report43 haveBest = true44 }45 }46 if !haveBest {47 if lastErr == nil {48 lastErr = errors.New("unable to generate Elo shikaku")49 }50 return nil, difficulty.Report{}, lastErr51 }52 return New(mode, bestPuzzle), bestReport, nil53}5455func shikakuModeForElo(base ShikakuMode, elo difficulty.Elo) ShikakuMode {56 score := difficulty.Score01(elo)57 maxRectSize := 5 + int(math.Round(score*15))58 mode := base59 mode.MaxRectSize = min(maxRectSize, max(1, mode.Width*mode.Height))60 return mode61}6263func shikakuEloRNG(seed string, elo difficulty.Elo) *rand.Rand {64 sum := sha256.Sum256([]byte("shikaku\x00" + seed + "\x00" + strconv.Itoa(int(elo))))65 return rand.New(rand.NewPCG(66 binary.LittleEndian.Uint64(sum[0:8]),67 binary.LittleEndian.Uint64(sum[8:16]),68 ))69}7071func shikakuCandidateSeed(seed string, candidate int) string {72 if candidate == 0 {73 return seed74 }75 return seed + "\x00candidate:" + strconv.Itoa(candidate)76}7778func scoreShikakuElo(target difficulty.Elo, mode ShikakuMode, puzzle Puzzle) difficulty.Report {79 solutions, stats := countShikakuSolutionsWithEloStats(puzzle, 2)80 metrics := shikakuDifficultyMetrics(mode, puzzle, solutions, stats)81 confidence := difficulty.ConfidenceHigh82 if solutions != 1 {83 confidence = difficulty.ConfidenceMedium84 }85 return difficulty.Report{86 TargetElo: target,87 ActualElo: shikakuActualElo(metrics),88 Confidence: confidence,89 Metrics: metrics,90 }91}9293func shikakuDifficultyMetrics(94 mode ShikakuMode,95 puzzle Puzzle,96 solutions int,97 stats shikakuEloSolveStats,98) difficulty.Metrics {99 cells := puzzle.Width * puzzle.Height100 clueCount := len(puzzle.Clues)101 metrics := difficulty.Metrics{102 "width": float64(puzzle.Width),103 "height": float64(puzzle.Height),104 "cells": float64(cells),105 "clue_count": float64(clueCount),106 "max_rect_size": float64(mode.MaxRectSize),107 "solution_count": float64(solutions),108 "solver_nodes": float64(stats.Nodes),109 "branches": float64(stats.Branches),110 "max_depth": float64(stats.MaxDepth),111 }112 if cells == 0 || clueCount == 0 {113 return metrics114 }115116 totalCandidates := 0117 maxCandidates := 0118 for _, clue := range puzzle.Clues {119 if clue.Value == 1 {120 metrics["singleton_clues"]++121 }122 if float64(clue.Value) > metrics["largest_clue"] {123 metrics["largest_clue"] = float64(clue.Value)124 }125 candidateCount := len((&puzzle).CandidateRectanglesForClue(clue.ID))126 totalCandidates += candidateCount127 if candidateCount > maxCandidates {128 maxCandidates = candidateCount129 }130 }131 metrics["average_rect_area"] = float64(cells) / float64(clueCount)132 metrics["clue_density"] = float64(clueCount) / float64(cells)133 metrics["singleton_ratio"] = metrics["singleton_clues"] / float64(clueCount)134 metrics["candidate_count"] = float64(totalCandidates)135 metrics["average_candidates"] = float64(totalCandidates) / float64(clueCount)136 metrics["max_candidates"] = float64(maxCandidates)137138 return metrics139}140141func countShikakuSolutionsWithEloStats(puzzle Puzzle, limit int) (int, shikakuEloSolveStats) {142 if limit <= 0 || puzzle.Width <= 0 || puzzle.Height <= 0 {143 return 0, shikakuEloSolveStats{}144 }145146 candidates := make(map[int][]Rectangle, len(puzzle.Clues))147 for _, clue := range puzzle.Clues {148 candidates[clue.ID] = (&puzzle).CandidateRectanglesForClue(clue.ID)149 if len(candidates[clue.ID]) == 0 {150 return 0, shikakuEloSolveStats{}151 }152 }153154 covered := make([][]bool, puzzle.Height)155 for y := range puzzle.Height {156 covered[y] = make([]bool, puzzle.Width)157 }158 placed := make(map[int]bool, len(puzzle.Clues))159 stats := shikakuEloSolveStats{}160 count := countShikakuSolutionsRec(puzzle, candidates, covered, placed, 0, limit, 0, &stats)161 return count, stats162}163164func countShikakuSolutionsRec(165 puzzle Puzzle,166 candidates map[int][]Rectangle,167 covered [][]bool,168 placed map[int]bool,169 coveredCells int,170 limit int,171 depth int,172 stats *shikakuEloSolveStats,173) int {174 stats.Nodes++175 if depth > stats.MaxDepth {176 stats.MaxDepth = depth177 }178 if len(placed) == len(puzzle.Clues) {179 if coveredCells == puzzle.Width*puzzle.Height {180 return 1181 }182 return 0183 }184185 clueID, choices := shikakuNextEloChoices(puzzle, candidates, covered, placed)186 if len(choices) == 0 {187 return 0188 }189190 total := 0191 for _, rect := range choices {192 stats.Branches++193 placed[clueID] = true194 markShikakuCovered(covered, rect, true)195 total += countShikakuSolutionsRec(196 puzzle,197 candidates,198 covered,199 placed,200 coveredCells+rect.Area(),201 limit-total,202 depth+1,203 stats,204 )205 markShikakuCovered(covered, rect, false)206 delete(placed, clueID)207 if total >= limit {208 return total209 }210 }211 return total212}213214func shikakuNextEloChoices(215 puzzle Puzzle,216 candidates map[int][]Rectangle,217 covered [][]bool,218 placed map[int]bool,219) (int, []Rectangle) {220 bestID := -1221 var best []Rectangle222 for _, clue := range puzzle.Clues {223 if placed[clue.ID] {224 continue225 }226 choices := make([]Rectangle, 0, len(candidates[clue.ID]))227 for _, rect := range candidates[clue.ID] {228 if shikakuRectAvailable(covered, rect) {229 choices = append(choices, rect)230 }231 }232 if bestID == -1 || len(choices) < len(best) {233 bestID = clue.ID234 best = choices235 if len(best) == 0 {236 break237 }238 }239 }240 return bestID, best241}242243func shikakuRectAvailable(covered [][]bool, rect Rectangle) bool {244 for y := rect.Y; y < rect.Y+rect.H; y++ {245 for x := rect.X; x < rect.X+rect.W; x++ {246 if covered[y][x] {247 return false248 }249 }250 }251 return true252}253254func markShikakuCovered(covered [][]bool, rect Rectangle, value bool) {255 for y := rect.Y; y < rect.Y+rect.H; y++ {256 for x := rect.X; x < rect.X+rect.W; x++ {257 covered[y][x] = value258 }259 }260}261262func shikakuActualElo(metrics difficulty.Metrics) difficulty.Elo {263 metricScore := 0.30*normalizeShikakuMetric(metrics["cells"], 25, 144) +264 0.20*normalizeShikakuMetric(metrics["average_candidates"], 1.5, 8.0) +265 0.20*normalizeShikakuMetric(math.Log10(metrics["solver_nodes"]+1), 1.0, 3.2) +266 0.15*normalizeShikakuMetric(metrics["branches"], 8, 80) +267 0.10*normalizeShikakuMetric(metrics["max_rect_size"], 5, 20) +268 0.05*(1-normalizeShikakuMetric(metrics["clue_density"], 0.18, 0.55))269 targetScore := normalizeShikakuMetric(metrics["max_rect_size"], 5, 20)270 score := 0.55*targetScore + 0.45*metricScore271 if metrics["solution_count"] != 1 {272 score *= 0.85273 }274 return difficulty.ClampElo(difficulty.Elo(math.Round(score * float64(difficulty.SoftCapElo))))275}276277func normalizeShikakuMetric(value, low, high float64) float64 {278 if high <= low || value <= low {279 return 0280 }281 if value >= high {282 return 1283 }284 return (value - low) / (high - low)285}