1package nonogram23import (4 "context"5 "crypto/sha256"6 "encoding/binary"7 "errors"8 "math"9 "math/rand/v2"10 "strconv"1112 "github.com/FelineStateMachine/puzzletea/difficulty"13 "github.com/FelineStateMachine/puzzletea/game"14)1516var (17 _ game.EloSpawner = NonogramMode{}18 _ game.CancellableEloSpawner = NonogramMode{}19)2021func (n NonogramMode) SpawnElo(seed string, elo difficulty.Elo) (game.Gamer, difficulty.Report, error) {22 return n.SpawnEloContext(context.Background(), seed, elo)23}2425func (n NonogramMode) SpawnEloContext(ctx context.Context, seed string, elo difficulty.Elo) (game.Gamer, difficulty.Report, error) {26 if err := difficulty.ValidateElo(elo); err != nil {27 return nil, difficulty.Report{}, err28 }2930 mode := nonogramModeForElo(n, elo)31 var bestHints Hints32 var bestReport difficulty.Report33 haveBest := false34 for candidate := range difficulty.CandidateCount(elo) {35 if err := ctx.Err(); err != nil {36 return nil, difficulty.Report{}, err37 }38 candidateSeed := nonogramCandidateSeed(seed, candidate)39 hints := GenerateRandomTomographySeededFastContext(ctx, mode, nonogramEloRNG(candidateSeed, elo))40 if len(hints.rows) == 0 || len(hints.cols) == 0 {41 continue42 }43 report := nonogramDifficultyReport(elo, mode, hints)44 if difficulty.BetterCandidate(report, bestReport, elo, haveBest) {45 bestHints = hints46 bestReport = report47 haveBest = true48 }49 }50 if !haveBest {51 if err := ctx.Err(); err != nil {52 return nil, difficulty.Report{}, err53 }54 return nil, difficulty.Report{}, errors.New("unable to generate Elo nonogram")55 }5657 gamer, err := New(mode, bestHints)58 if err != nil {59 return nil, difficulty.Report{}, err60 }61 return gamer, bestReport, nil62}6364func nonogramModeForElo(base NonogramMode, elo difficulty.Elo) NonogramMode {65 score := difficulty.Score01(elo)6667 density := 0.66 - score*0.266869 mode := base70 mode.Density = density71 return mode72}7374func nonogramEloRNG(seed string, elo difficulty.Elo) *rand.Rand {75 sum := sha256.Sum256([]byte("nonogram\x00" + seed + "\x00" + strconv.Itoa(int(elo))))76 return rand.New(rand.NewPCG(77 binary.LittleEndian.Uint64(sum[0:8]),78 binary.LittleEndian.Uint64(sum[8:16]),79 ))80}8182func nonogramCandidateSeed(seed string, candidate int) string {83 if candidate == 0 {84 return seed85 }86 return seed + "\x00candidate:" + strconv.Itoa(candidate)87}8889func nonogramDifficultyReport(target difficulty.Elo, mode NonogramMode, hints Hints) difficulty.Report {90 metrics := nonogramDifficultyMetrics(mode, hints)91 return difficulty.Report{92 TargetElo: target,93 ActualElo: nonogramActualElo(metrics),94 Confidence: difficulty.ConfidenceMedium,95 Metrics: metrics,96 }97}9899func nonogramDifficultyMetrics(mode NonogramMode, hints Hints) difficulty.Metrics {100 cells := mode.Width * mode.Height101 filled := 0102 rowRuns := 0103 colRuns := 0104 rowPossibilities := 0105 colPossibilities := 0106 maxLinePossibilities := 0107108 for _, row := range hints.rows {109 filled += hintSum(row)110 rowRuns += nonzeroHintCount(row)111 possibilities := len(generateLinePossibilities(mode.Width, row))112 rowPossibilities += possibilities113 maxLinePossibilities = max(maxLinePossibilities, possibilities)114 }115 for _, col := range hints.cols {116 colRuns += nonzeroHintCount(col)117 possibilities := len(generateLinePossibilities(mode.Height, col))118 colPossibilities += possibilities119 maxLinePossibilities = max(maxLinePossibilities, possibilities)120 }121122 totalLines := len(hints.rows) + len(hints.cols)123 totalPossibilities := rowPossibilities + colPossibilities124 return difficulty.Metrics{125 "width": float64(mode.Width),126 "height": float64(mode.Height),127 "cells": float64(cells),128 "density": nonogramRatio(filled, cells),129 "target_density": mode.Density,130 "row_runs": float64(rowRuns),131 "col_runs": float64(colRuns),132 "total_runs": float64(rowRuns + colRuns),133 "avg_runs_per_line": nonogramRatio(rowRuns+colRuns, totalLines),134 "line_possibilities": float64(totalPossibilities),135 "avg_line_possibilities": nonogramRatio(totalPossibilities, totalLines),136 "max_line_possibilities": float64(maxLinePossibilities),137 }138}139140func nonogramActualElo(metrics difficulty.Metrics) difficulty.Elo {141 metricScore := 0.34*normalizeNonogramMetric(metrics["cells"], 25, 225) +142 0.24*normalizeNonogramMetric(metrics["avg_line_possibilities"], 1, 120) +143 0.18*normalizeNonogramMetric(metrics["max_line_possibilities"], 1, 600) +144 0.14*(1-normalizeNonogramMetric(metrics["density"], 0.35, 0.72)) +145 0.10*normalizeNonogramMetric(metrics["avg_runs_per_line"], 1, 5)146 targetScore := normalizeNonogramMetric(0.66-metrics["target_density"], 0, 0.26)147 score := 0.70*targetScore + 0.30*metricScore148149 return difficulty.ClampElo(difficulty.Elo(math.Round(score * float64(difficulty.SoftCapElo))))150}151152func hintSum(hint []int) int {153 total := 0154 for _, v := range hint {155 total += v156 }157 return total158}159160func nonzeroHintCount(hint []int) int {161 if len(hint) == 1 && hint[0] == 0 {162 return 0163 }164 return len(hint)165}166167func nonogramRatio(numerator, denominator int) float64 {168 if denominator == 0 {169 return 0170 }171 return float64(numerator) / float64(denominator)172}173174func normalizeNonogramMetric(value, low, high float64) float64 {175 if high <= low || value <= low {176 return 0177 }178 if value >= high {179 return 1180 }181 return (value - low) / (high - low)182}