1// Package judge classifies candidate commits as forced or guess by running2// the rules over revealed information only: the known cells of the revealed3// tiles, propagated to a fixpoint with optional bifurcation.4package judge56import (7 "fmt"8 "time"910 "mosaic-engine/rules"11)1213// ShapeSpec is a revealed tile: a union of rectangles (local coordinates)14// placed at (x0, y0) on the board.15type ShapeSpec struct {16 X0 int `json:"x0"`17 Y0 int `json:"y0"`18 W int `json:"w"`19 H int `json:"h"`20 Rects [][4]int `json:"rects"`21}2223type Input struct {24 G int `json:"G"`25 Shapes []ShapeSpec `json:"shapes"` // revealed tiles26 Known [][2]int `json:"known"` // [global id, value]27 Candidates [][2]int `json:"candidates"` // [global id, value]28 Depth int `json:"depth"`29}3031type Result struct {32 ID int `json:"id"`33 V int `json:"v"`34 Class string `json:"class"` // forced | guess | contradiction | known35 Rules []string `json:"rules"`36}3738type Output struct {39 Ms float64 `json:"ms"`40 Results []Result `json:"results"`41 Steps int `json:"steps"`42}4344func Judge(in Input) (*Output, error) {45 start := time.Now()46 if in.G < 4 {47 return nil, fmt.Errorf("bad size G=%d", in.G)48 }49 b := rules.NewBoard(in.G, in.G)50 for _, w := range in.Shapes {51 sh := rules.Shape{X0: w.X0, Y0: w.Y0, W: w.W, H: w.H, Rects: w.Rects}52 if w.X0 < 0 || w.Y0 < 0 || w.X0+w.W > in.G || w.Y0+w.H > in.G {53 return nil, fmt.Errorf("shape at (%d,%d) %dx%d outside the %dx%d board", w.X0, w.Y0, w.W, w.H, in.G, in.G)54 }55 if err := sh.Valid(); err != nil {56 return nil, fmt.Errorf("shape at (%d,%d): %w", w.X0, w.Y0, err)57 }58 b.Shapes = append(b.Shapes, sh)59 }60 for _, k := range in.Known {61 if k[0] < 0 || k[0] >= in.G*in.G || k[1] < 0 || k[1] > 1 {62 return nil, fmt.Errorf("bad known cell %v", k)63 }64 b.Cells[k[0]] = rules.Cell(k[1])65 }66 if err := b.Validate(rules.All); err != nil {67 return nil, fmt.Errorf("known cells violate rules: %w", err)68 }69 known := map[int]rules.Cell{}70 for _, k := range in.Known {71 known[k[0]] = rules.Cell(k[1])72 }73 steps, ok := b.Propagate(rules.All, in.Depth)74 if !ok {75 return nil, fmt.Errorf("known cells lead to a contradiction")76 }77 forced := map[int]rules.Step{}78 for _, s := range steps {79 forced[b.Idx(s.X, s.Y)] = s80 }81 out := &Output{Steps: len(steps)}82 for _, c := range in.Candidates {83 if c[0] < 0 || c[0] >= in.G*in.G || c[1] < 0 || c[1] > 1 {84 return nil, fmt.Errorf("bad candidate %v", c)85 }86 r := Result{ID: c[0], V: c[1], Rules: []string{}}87 if v, isKnown := known[c[0]]; isKnown {88 r.Rules = []string{"seam"}89 if v == rules.Cell(c[1]) {90 r.Class = "known"91 } else {92 r.Class = "contradiction"93 }94 } else if s, isForced := forced[c[0]]; isForced {95 r.Rules = s.Rules96 if s.V == rules.Cell(c[1]) {97 r.Class = "forced"98 } else {99 r.Class = "contradiction"100 }101 } else {102 r.Class = "guess"103 }104 out.Results = append(out.Results, r)105 }106 out.Ms = float64(time.Since(start).Microseconds()) / 1000107 return out, nil108}