1package pack23import (4 "encoding/json"5 "testing"6 "time"7)89// check verifies what every layout must satisfy: valid shapes inside the10// field, consistent owners/overlaps/neighbours, m by cell count.11func check(t *testing.T, L *Layout) {12 t.Helper()13 G := L.G14 own := L.Owners()15 for _, tl := range L.Tiles {16 if tl.X0 < 0 || tl.Y0 < 0 || tl.X0+tl.W > G || tl.Y0+tl.H > G {17 t.Fatalf("tile %d out of the field", tl.ID)18 }19 if err := ValidShape(tl.Mask(), tl.W, tl.H); err != nil {20 t.Fatalf("tile %d (%dx%d rects %v): %v", tl.ID, tl.W, tl.H, tl.Rects, err)21 }22 if tl.M != MFor(tl.Cells) {23 t.Fatalf("tile %d m=%d want %d", tl.ID, tl.M, MFor(tl.Cells))24 }25 n := 026 for _, m := range tl.Mask() {27 if m {28 n++29 }30 }31 if n != tl.Cells {32 t.Fatalf("tile %d: cells %d, mask has %d", tl.ID, tl.Cells, n)33 }34 }35 // overlaps: symmetric, cell counts match the owner index, neighbours agree36 for _, tl := range L.Tiles {37 seen := map[int]bool{}38 for _, o := range L.Overlaps[tl.ID] {39 if seen[o.With] || o.With == tl.ID {40 t.Fatalf("tile %d: overlap list not a set", tl.ID)41 }42 seen[o.With] = true43 if o.Cells != len(o.Ids) || o.Cells == 0 {44 t.Fatalf("tile %d/%d: cells %d ids %d", tl.ID, o.With, o.Cells, len(o.Ids))45 }46 for _, id := range o.Ids {47 a, b := false, false48 for _, w := range own[id] {49 a = a || w == tl.ID50 b = b || w == o.With51 }52 if !a || !b {53 t.Fatalf("tile %d/%d: cell %d not owned by both", tl.ID, o.With, id)54 }55 }56 back := false57 for _, o2 := range L.Overlaps[o.With] {58 if o2.With == tl.ID && o2.Cells == o.Cells {59 back = true60 }61 }62 if !back {63 t.Fatalf("overlap %d/%d has no mirror", tl.ID, o.With)64 }65 }66 if len(L.Neighbours(tl.ID)) != len(L.Overlaps[tl.ID]) {67 t.Fatalf("tile %d: neighbours vs overlaps", tl.ID)68 }69 }70 // every shared cell is in exactly the overlap lists of its owner pairs71 for id, os := range own {72 for i := 0; i < len(os); i++ {73 for j := i + 1; j < len(os); j++ {74 found := false75 for _, o := range L.Overlaps[os[i]] {76 if o.With == os[j] {77 for _, c := range o.Ids {78 found = found || c == id79 }80 }81 }82 if !found {83 t.Fatalf("cell %d shared by %d and %d but not in their overlap", id, os[i], os[j])84 }85 }86 }87 }88 if L.SeedTile < 0 || L.SeedTile >= len(L.Tiles) {89 t.Fatal("seed tile out of range")90 }91}9293func TestDistinctLines(t *testing.T) {94 want := map[int]int{4: 6, 6: 14, 8: 34, 10: 84, 12: 208, 14: 518, 16: 1296}95 for L, n := range want {96 if got := DistinctLines(L); got != n {97 t.Errorf("D(%d) = %d, want %d", L, got, n)98 }99 }100 // 16 rows of length 6 need more than 14/2 distinct lines101 if ValidShape(Tile{W: 6, H: 16, Rects: [][4]int{{0, 0, 6, 16}}}.Mask(), 6, 16) == nil {102 t.Fatal("6x16 strip accepted")103 }104 // 4 wide by 6 tall: 6 rows of length 4 > 6/2105 if ValidShape(Tile{W: 4, H: 6, Rects: [][4]int{{0, 0, 4, 6}}}.Mask(), 4, 6) == nil {106 t.Fatal("4x6 strip accepted")107 }108 // 16x16: 16 lines of length 16 <= 648109 if err := ValidShape(Tile{W: 16, H: 16, Rects: [][4]int{{0, 0, 16, 16}}}.Mask(), 16, 16); err != nil {110 t.Fatal(err)111 }112 // 6x14: 14 rows of 6 exactly fails (14 > 7); 6x6 passes (6 <= 7)113 if ValidShape(Tile{W: 6, H: 14, Rects: [][4]int{{0, 0, 6, 14}}}.Mask(), 6, 14) == nil {114 t.Fatal("6x14 accepted")115 }116}117118func TestFillShapes(t *testing.T) {119 if len(fillShapes) < 8 {120 t.Fatalf("only %d fill shapes", len(fillShapes))121 }122 for i, sh := range fillShapes {123 if err := ValidShape(sh.Mask(), sh.W, sh.H); err != nil {124 t.Fatal(err)125 }126 if i > 0 && fillShapes[i-1].Cells < sh.Cells {127 t.Fatal("fill shapes not largest first")128 }129 }130 cells := map[int]bool{}131 for _, sh := range fillShapes {132 cells[sh.Cells] = true133 }134 // 8x6 is not valid (8 parallel lines of length 6 > 7), so no 48135 for _, want := range []int{64, 36, 32} {136 if !cells[want] {137 t.Errorf("no fill shape with %d cells", want)138 }139 }140 t.Logf("%d fill shapes, %d..%d cells", len(fillShapes), fillShapes[len(fillShapes)-1].Cells, fillShapes[0].Cells)141}142143func TestShapesAndLines(t *testing.T) {144 sq := Tile{W: 6, H: 6, Rects: [][4]int{{0, 0, 6, 6}}}145 if err := ValidShape(sq.Mask(), 6, 6); err != nil {146 t.Fatal(err)147 }148 if got := len(sq.Lines()); got != 12 {149 t.Fatalf("6x6 has %d lines, want 12", got)150 }151 // L: 16x8 over 8x16152 l := Tile{W: 16, H: 16, Rects: [][4]int{{0, 0, 16, 8}, {0, 0, 8, 16}}}153 if err := ValidShape(l.Mask(), 16, 16); err != nil {154 t.Fatal(err)155 }156 lines := l.Lines()157 // rows: 8 of length 16, 8 of length 8; columns the same158 if len(lines) != 32 {159 t.Fatalf("L has %d lines", len(lines))160 }161 for _, run := range lines {162 if len(run) != 8 && len(run) != 16 {163 t.Fatalf("L line of length %d", len(run))164 }165 }166 // an L with 4-thick arms: 4 parallel lines of length 4 exceed D(4)/2167 if ValidShape(Tile{W: 8, H: 8, Rects: [][4]int{{0, 0, 8, 4}, {0, 0, 4, 8}}}.Mask(), 8, 8) == nil {168 t.Fatal("4-thick L accepted")169 }170 // odd line: 5-wide171 if ValidShape(Tile{W: 5, H: 4, Rects: [][4]int{{0, 0, 5, 4}}}.Mask(), 5, 4) == nil {172 t.Fatal("odd line accepted")173 }174 // disconnected175 if ValidShape(Tile{W: 10, H: 4, Rects: [][4]int{{0, 0, 4, 4}, {6, 0, 4, 4}}}.Mask(), 10, 4) == nil {176 t.Fatal("disconnected shape accepted")177 }178 // short line: a T whose stem is 2 wide179 if ValidShape(Tile{W: 8, H: 8, Rects: [][4]int{{0, 0, 8, 4}, {3, 4, 2, 4}}}.Mask(), 8, 8) == nil {180 t.Fatal("2-wide stem accepted")181 }182}183184func TestGridMatchesPhaseOne(t *testing.T) {185 L, err := Pack(Params{Seed: "a", G: 27, Kind: "grid", N: 14})186 if err != nil {187 t.Fatal(err)188 }189 check(t, L)190 if len(L.Tiles) != 4 || L.Report.Coverage != 1 {191 t.Fatalf("grid 2x2: %d tiles coverage %.2f", len(L.Tiles), L.Report.Coverage)192 }193 // four seams of 14 cells and two diagonal corner touches of one cell194 seams, corners := 0, 0195 for _, os := range L.Overlaps {196 for _, o := range os {197 switch o.Cells {198 case 14:199 seams++200 case 1:201 corners++202 default:203 t.Fatalf("overlap of %d cells in a 2x2 grid", o.Cells)204 }205 }206 }207 if seams != 8 || corners != 4 {208 t.Fatalf("seams %d corners %d (counted from both sides)", seams, corners)209 }210 L15, err := Pack(Params{Seed: "a", G: 196, Kind: "grid", N: 14})211 if err != nil {212 t.Fatal(err)213 }214 check(t, L15)215 if len(L15.Tiles) != 225 {216 t.Fatalf("X=15: %d tiles", len(L15.Tiles))217 }218}219220func replayAccepts(t *testing.T, L *Layout) {221 t.Helper()222 st := newScatterState(L.G, L.Region)223 for k, f := range L.Fixed {224 st.place(-1-k, f)225 }226 st.place(0, L.Tiles[0])227 for i, tl := range L.Tiles[1:] {228 ok, why := st.accepts(tl)229 if !ok {230 t.Fatalf("tile %d fails the placement rule: %s", tl.ID, why)231 }232 st.place(i+1, tl)233 }234}235236// TestScatterChunk packs a region of a field against fixed context tiles237// (chunk mode): every emitted tile lies inside the region, ids start at238// IDBase, overlaps with the fixed tiles are recorded (as All() indexes at239// or past len(Tiles)) and the placement rule holds against them.240func TestScatterChunk(t *testing.T) {241 // context: the tiles of an unrelated scatter at G=100 that intersect242 // the band x in [40, 56), pretending they came from the left chunk243 base, err := Pack(Params{Seed: "ctx", G: 100, Kind: "scatter"})244 if err != nil {245 t.Fatal(err)246 }247 var fixed []Tile248 for _, tl := range base.Tiles {249 if tl.X0+tl.W > 40 && tl.X0 < 56 && tl.X0 >= 0 {250 f := tl251 f.ID = 5000 + tl.ID252 fixed = append(fixed, f)253 }254 }255 if len(fixed) == 0 {256 t.Fatal("no context tiles")257 }258 // context tiles must lie inside the region to be legal anchors; clip259 // the region to the whole field width so they do (a real chunk's260 // fixed tiles straddle its band, which is inside its region)261 L, err := Pack(Params{Seed: "chunk", G: 100, Kind: "scatter", Region: [4]int{40, 0, 60, 100}, Fixed: fixed, IDBase: 300})262 if err != nil {263 t.Fatal(err)264 }265 if len(L.Tiles) < 5 {266 t.Fatalf("only %d tiles in the chunk", len(L.Tiles))267 }268 withFixed := 0269 for i, tl := range L.Tiles {270 if tl.ID != 300+i {271 t.Fatalf("tile %d has id %d", i, tl.ID)272 }273 if tl.X0 < 40 || tl.X0+tl.W > 100 {274 t.Fatalf("tile %d outside the region: x0=%d w=%d", tl.ID, tl.X0, tl.W)275 }276 for _, o := range L.Overlaps[i] {277 if o.With >= len(L.Tiles) {278 withFixed++279 if L.Fixed[o.With-len(L.Tiles)].ID < 5000 {280 t.Fatalf("overlap with a non-fixed index %d", o.With)281 }282 }283 }284 }285 if withFixed == 0 {286 t.Fatal("no overlap with a fixed context tile")287 }288 replayAccepts(t, L)289 t.Logf("chunk: %d tiles, %d overlaps with %d fixed tiles, coverage %.3f", len(L.Tiles), withFixed, len(fixed), L.Report.Coverage)290}291292func TestScatter(t *testing.T) {293 for _, G := range []int{60, 100, 200} {294 start := time.Now()295 L, err := Pack(Params{Seed: "a", G: G, Kind: "scatter"})296 d := time.Since(start)297 if err != nil {298 t.Fatal(err)299 }300 check(t, L)301 replayAccepts(t, L)302 r := L.Report303 if r.Stopped == "coverage" && r.Coverage < 0.72 {304 t.Fatalf("G=%d: stopped at coverage but %.3f", G, r.Coverage)305 }306 if r.Coverage < 0.6 {307 t.Errorf("G=%d: coverage %.3f (stopped: %s)", G, r.Coverage, r.Stopped)308 }309 // the share is over the drops; fill shapes are chosen by fit310 drops := L.Tiles[:r.Tiles-r.Filled]311 share := float64(compoundCount(drops)) / float64(len(drops))312 if share < 0.2 || share > 0.6 {313 t.Errorf("G=%d: compound share %.2f, want near 0.4", G, share)314 }315 rects, other := 0, 0316 for _, tl := range L.Tiles {317 if tl.W != tl.H && len(tl.Rects) == 1 {318 rects++319 }320 if tl.Cells != tl.W*tl.H {321 other++322 }323 }324 if rects == 0 {325 t.Errorf("G=%d: no non-square rectangles", G)326 }327 maxHole, bigHoles := 0, 0328 for _, h := range holesOf(L.Owners(), G, L.Tiles) {329 maxHole = max(maxHole, len(h.cells))330 if len(h.cells) > r.MaxHole {331 bigHoles++332 }333 }334 t.Logf("G=%d: %d holes still over max_hole %d, %d of them inside the convex hull", G, bigHoles, r.MaxHole, L.UnfillableHoles(r.MaxHole))335 t.Logf("G=%d: %d tiles (%d filled) in %s (stopped: %s); coverage %.3f; holes %d (%d cells, mean %.1f, max %d); by cells %v; %d overlaps mean %.1f cells; %d compound, %d non-square rects",336 G, r.Tiles, r.Filled, d.Round(time.Millisecond), r.Stopped, r.Coverage, r.Holes, r.HoleCells, r.MeanHole, maxHole, r.ByCells, r.Overlaps, r.MeanOverlap, r.Compound, rects)337 // measured 0.9-1.1 s at G=200 with the uniqueness bound (more338 // drops are rejected); the bound is loose to keep the test stable339 if G == 200 && d > 5*time.Second { // smoke bound; ~1-2 s idle, more under load340 t.Errorf("G=200 took %s", d)341 }342 }343}344345func TestScatterDeterministic(t *testing.T) {346 a, _ := Pack(Params{Seed: "x", G: 120})347 b, _ := Pack(Params{Seed: "x", G: 120})348 ja, _ := json.Marshal(a)349 jb, _ := json.Marshal(b)350 if string(ja) != string(jb) {351 t.Fatal("same seed, different layout")352 }353 c, _ := Pack(Params{Seed: "y", G: 120})354 jc, _ := json.Marshal(c)355 if string(jc) == string(ja) {356 t.Fatal("different seeds, same layout")357 }358 if a.Kind != "scatter" {359 t.Fatalf("default kind %q", a.Kind)360 }361}362363// TestScatterCoverage85 reports whether a higher coverage target is364// reachable within the rejection bound, and the hole statistics.365func TestScatterCoverage85(t *testing.T) {366 for _, G := range []int{100, 200} {367 for _, cov := range []float64{0.72, 0.85} {368 start := time.Now()369 L, err := Pack(Params{Seed: "a", G: G, Kind: "scatter", Coverage: cov})370 d := time.Since(start)371 if err != nil {372 t.Fatal(err)373 }374 check(t, L)375 replayAccepts(t, L)376 maxHole := 0377 for _, h := range holesOf(L.Owners(), G, L.Tiles) {378 maxHole = max(maxHole, len(h.cells))379 }380 r := L.Report381 t.Logf("G=%d coverage target %.2f: %d tiles (%d filled) in %s, stopped %s, coverage %.3f, holes %d mean %.1f max %d, %d over max_hole inside the hull",382 G, cov, r.Tiles, r.Filled, d.Round(time.Millisecond), r.Stopped, r.Coverage, r.Holes, r.MeanHole, maxHole, L.UnfillableHoles(r.MaxHole))383 }384 }385}386387// TestEveryTilePinnable: every tile of a scatter layout, free-standing or388// as an odd chunk packed against fixed context, shares at least MinLine389// cells with some neighbour (the generator's pin precondition).390func TestEveryTilePinnable(t *testing.T) {391 check := func(name string, L *Layout) {392 t.Helper()393 for i, tile := range L.Tiles {394 ok := false395 for _, o := range L.Overlaps[i] {396 if o.Cells >= MinLine {397 ok = true398 }399 }400 if !ok {401 t.Fatalf("%s: tile %d (%dx%d at %d,%d) has no overlap of %d cells", name, tile.ID, tile.W, tile.H, tile.X0, tile.Y0, MinLine)402 }403 }404 }405 for _, seed := range []string{"a", "b", "c", "d", "e", "f", "g", "h"} {406 L, err := Pack(Params{Seed: seed, G: 60, Kind: "scatter"})407 if err != nil {408 t.Fatal(seed, err)409 }410 check("G=60 "+seed, L)411 // an odd chunk: region inside a bigger field, fixed context = the412 // tiles of a free-standing layout that intersect the region's band413 A, err := Pack(Params{Seed: seed + "-even", G: 148, Kind: "scatter"})414 if err != nil {415 t.Fatal(err)416 }417 region := [4]int{44, 44, 60, 60}418 var fixed []Tile419 for _, ft := range A.Tiles {420 if ft.X0 < region[0]+region[2] && ft.X0+ft.W > region[0] && ft.Y0 < region[1]+region[3] && ft.Y0+ft.H > region[1] {421 fixed = append(fixed, ft)422 }423 }424 B, err := Pack(Params{Seed: seed + "-odd", G: 148, Kind: "scatter", Region: region, Fixed: fixed, IDBase: 100000})425 if err != nil {426 t.Fatal(seed, err)427 }428 check("chunk "+seed, B)429 }430}