1package takuzuplus23import (4 "image"5 "math"6 "math/rand/v2"7)89const (10 endpointZeroProvided = iota11 endpointOneProvided12 endpointTwoProvided13 endpointClassCount14)1516type ratioBand struct {17 Min float6418 Max float6419}2021type relationProfile struct {22 MinRelations int23 MaxRelations int2425 EndpointBands [endpointClassCount]ratioBand26 EndpointWeights [endpointClassCount]int2728 MinSpacing int29 MinRegions int30}3132type relationMetrics struct {33 Total int34 EndpointCounts [endpointClassCount]int35 SameCount int36 DifferentCount int37 HorizontalCount int38 VerticalCount int39 RegionMask uint840 OccupiedRegions int41 Positions []image.Point42 MinExistingGap int43 HasAnyRelations bool44}4546func (p relationProfile) targetCount(rng *rand.Rand) int {47 if p.MaxRelations <= p.MinRelations {48 return p.MinRelations49 }50 return p.MinRelations + rng.IntN(p.MaxRelations-p.MinRelations+1)51}5253func relationProfiles() []relationProfile {54 return []relationProfile{55 {56 MinRelations: 2,57 MaxRelations: 4,58 EndpointBands: [endpointClassCount]ratioBand{59 {Min: 0.00, Max: 0.05},60 {Min: 0.70, Max: 0.85},61 {Min: 0.15, Max: 0.30},62 },63 EndpointWeights: [endpointClassCount]int{0, 10, 5},64 MinSpacing: 2,65 },66 {67 MinRelations: 3,68 MaxRelations: 5,69 EndpointBands: [endpointClassCount]ratioBand{70 {Min: 0.00, Max: 0.05},71 {Min: 0.65, Max: 0.80},72 {Min: 0.20, Max: 0.35},73 },74 EndpointWeights: [endpointClassCount]int{0, 9, 5},75 MinSpacing: 2,76 },77 {78 MinRelations: 4,79 MaxRelations: 6,80 EndpointBands: [endpointClassCount]ratioBand{81 {Min: 0.05, Max: 0.15},82 {Min: 0.60, Max: 0.75},83 {Min: 0.15, Max: 0.30},84 },85 EndpointWeights: [endpointClassCount]int{3, 9, 4},86 MinRegions: 3,87 },88 {89 MinRelations: 6,90 MaxRelations: 8,91 EndpointBands: [endpointClassCount]ratioBand{92 {Min: 0.10, Max: 0.15},93 {Min: 0.60, Max: 0.70},94 {Min: 0.15, Max: 0.25},95 },96 EndpointWeights: [endpointClassCount]int{4, 8, 3},97 MinRegions: 3,98 },99 {100 MinRelations: 8,101 MaxRelations: 11,102 EndpointBands: [endpointClassCount]ratioBand{103 {Min: 0.10, Max: 0.20},104 {Min: 0.60, Max: 0.70},105 {Min: 0.10, Max: 0.25},106 },107 EndpointWeights: [endpointClassCount]int{5, 8, 2},108 MinRegions: 3,109 },110 {111 MinRelations: 10,112 MaxRelations: 14,113 EndpointBands: [endpointClassCount]ratioBand{114 {Min: 0.15, Max: 0.20},115 {Min: 0.55, Max: 0.65},116 {Min: 0.15, Max: 0.30},117 },118 EndpointWeights: [endpointClassCount]int{5, 7, 3},119 MinRegions: 3,120 },121 {122 MinRelations: 13,123 MaxRelations: 18,124 EndpointBands: [endpointClassCount]ratioBand{125 {Min: 0.15, Max: 0.20},126 {Min: 0.55, Max: 0.65},127 {Min: 0.15, Max: 0.30},128 },129 EndpointWeights: [endpointClassCount]int{5, 7, 3},130 MinRegions: 3,131 },132 }133}134135func relationPenalty(profile relationProfile, size int, rels relations, provided [][]bool) int {136 metrics := analyzeRelations(rels, provided, size)137 penalty := 0138139 switch {140 case metrics.Total < profile.MinRelations:141 penalty += 1000 * (profile.MinRelations - metrics.Total)142 case metrics.Total > profile.MaxRelations:143 penalty += 1000 * (metrics.Total - profile.MaxRelations)144 }145146 if metrics.Total == 0 {147 return penalty148 }149150 for class, band := range profile.EndpointBands {151 if !ratioWithinBand(metrics.EndpointCounts[class], metrics.Total, band) {152 penalty += bandPenalty(metrics.EndpointCounts[class], metrics.Total, band)153 }154 }155156 if metrics.Total >= 5 {157 balanceBand := ratioBand{Min: 0.40, Max: 0.60}158 if !ratioWithinBand(metrics.SameCount, metrics.Total, balanceBand) {159 penalty += bandPenalty(metrics.SameCount, metrics.Total, balanceBand)160 }161 if !ratioWithinBand(metrics.HorizontalCount, metrics.Total, balanceBand) {162 penalty += bandPenalty(metrics.HorizontalCount, metrics.Total, balanceBand)163 }164 }165166 if profile.MinSpacing > 0 && metrics.Total > 1 && metrics.MinExistingGap < profile.MinSpacing {167 penalty += 250 * (profile.MinSpacing - metrics.MinExistingGap)168 }169170 if profile.MinRegions > 0 && metrics.OccupiedRegions < profile.MinRegions {171 penalty += 400 * (profile.MinRegions - metrics.OccupiedRegions)172 }173174 return penalty175}176177func analyzeRelations(rels relations, provided [][]bool, size int) relationMetrics {178 metrics := relationMetrics{179 MinExistingGap: math.MaxInt,180 }181182 appendPosition := func(pos image.Point) {183 for _, prior := range metrics.Positions {184 dist := abs(pos.X-prior.X) + abs(pos.Y-prior.Y)185 if dist < metrics.MinExistingGap {186 metrics.MinExistingGap = dist187 }188 }189 metrics.Positions = append(metrics.Positions, pos)190 metrics.RegionMask |= relationRegionBit(size, pos)191 }192193 for y, row := range rels.horizontal {194 for x, rel := range row {195 if rel == relationNone {196 continue197 }198 metrics.Total++199 metrics.HasAnyRelations = true200 metrics.HorizontalCount++201 if rel == relationSame {202 metrics.SameCount++203 } else {204 metrics.DifferentCount++205 }206 class := endpointClass(boolInt(provided[y][x]) + boolInt(provided[y][x+1]))207 metrics.EndpointCounts[class]++208 appendPosition(horizontalRelationPosition(x, y))209 }210 }211212 for y, row := range rels.vertical {213 for x, rel := range row {214 if rel == relationNone {215 continue216 }217 metrics.Total++218 metrics.HasAnyRelations = true219 metrics.VerticalCount++220 if rel == relationSame {221 metrics.SameCount++222 } else {223 metrics.DifferentCount++224 }225 class := endpointClass(boolInt(provided[y][x]) + boolInt(provided[y+1][x]))226 metrics.EndpointCounts[class]++227 appendPosition(verticalRelationPosition(x, y))228 }229 }230231 if metrics.MinExistingGap == math.MaxInt {232 metrics.MinExistingGap = profileDistanceUnset()233 }234 metrics.OccupiedRegions = bitsSet(metrics.RegionMask)235236 return metrics237}238239func ratioWithinBand(count, total int, band ratioBand) bool {240 if total == 0 {241 return band.Min <= 0242 }243 actual := float64(count) / float64(total)244 slack := 1.0 / float64(total)245 return actual >= maxFloat(0, band.Min-slack) && actual <= minFloat(1, band.Max+slack)246}247248func bandPenalty(count, total int, band ratioBand) int {249 if total == 0 {250 return 0251 }252 actual := float64(count) / float64(total)253 switch {254 case actual < band.Min:255 return int(math.Ceil((band.Min - actual) * 1000))256 case actual > band.Max:257 return int(math.Ceil((actual - band.Max) * 1000))258 default:259 return 0260 }261}262263func relationRegionBit(size int, pos image.Point) uint8 {264 if size <= 0 {265 return 0266 }267 cut := size268 regionX := 0269 regionY := 0270 if pos.X >= cut {271 regionX = 1272 }273 if pos.Y >= cut {274 regionY = 1275 }276 return 1 << uint(regionY*2+regionX)277}278279func horizontalRelationPosition(x, y int) image.Point {280 return image.Pt(2*x+1, 2*y)281}282283func verticalRelationPosition(x, y int) image.Point {284 return image.Pt(2*x, 2*y+1)285}286287func endpointClass(providedCount int) int {288 switch providedCount {289 case 0:290 return endpointZeroProvided291 case 1:292 return endpointOneProvided293 default:294 return endpointTwoProvided295 }296}297298func bitsSet(mask uint8) int {299 count := 0300 for mask > 0 {301 count += int(mask & 1)302 mask >>= 1303 }304 return count305}306307func profileDistanceUnset() int {308 return math.MaxInt / 2309}310311func minFloat(a, b float64) float64 {312 if a < b {313 return a314 }315 return b316}317318func maxFloat(a, b float64) float64 {319 if a > b {320 return a321 }322 return b323}324325func boolInt(v bool) int {326 if v {327 return 1328 }329 return 0330}331332func abs(v int) int {333 if v < 0 {334 return -v335 }336 return v337}