1package hashiwokakero23import (4 "math/rand/v2"5 "testing"6)78func testBridgeLayoutByMode(t *testing.T, mode HashiMode) Puzzle {9 t.Helper()1011 for attempt := range 64 {12 rng := rand.New(rand.NewPCG(uint64(mode.Width*100+attempt+1), uint64(mode.Height*1000+attempt+1)))13 islandCount := mode.MinIslands + rng.IntN(mode.MaxIslands-mode.MinIslands+1)14 islands := placeIslandsSeeded(mode.Width, mode.Height, islandCount, rng)15 if islands == nil {16 continue17 }1819 p := Puzzle{20 Width: mode.Width,21 Height: mode.Height,22 Islands: islands,23 }2425 if !buildSpanningTreeSeeded(&p, rng) {26 continue27 }28 addExtraBridgesSeeded(&p, rng)29 return p30 }3132 t.Fatalf("failed to build bridge layout for %s", mode.Title())33 return Puzzle{}34}3536func bridgeAxisSpan(p *Puzzle, b Bridge) (x1, y1, x2, y2 int, horizontal, ok bool) {37 a := p.FindIslandByID(b.Island1)38 c := p.FindIslandByID(b.Island2)39 if a == nil || c == nil {40 return 0, 0, 0, 0, false, false41 }4243 if a.Y == c.Y {44 return a.X, a.Y, c.X, c.Y, true, true45 }46 if a.X == c.X {47 return a.X, a.Y, c.X, c.Y, false, true48 }49 return 0, 0, 0, 0, false, false50}5152func rangeContainsInterior(v, bound1, bound2 int) bool {53 min, max := bound1, bound254 if min > max {55 min, max = max, min56 }57 return v > min && v < max58}5960func bridgesCross(p *Puzzle, a, b Bridge) bool {61 if a.Island1 == b.Island1 || a.Island1 == b.Island2 || a.Island2 == b.Island1 || a.Island2 == b.Island2 {62 return false63 }6465 ax1, ay1, ax2, ay2, aHorizontal, aok := bridgeAxisSpan(p, a)66 bx1, by1, bx2, by2, bHorizontal, bok := bridgeAxisSpan(p, b)67 if !aok || !bok || aHorizontal == bHorizontal {68 return false69 }7071 hx1, hy, hx2 := ax1, ay1, ax272 vx, vy1, vy2 := bx1, by1, by273 if !aHorizontal {74 hx1, hy, hx2 = bx1, by1, bx275 vx, vy1, vy2 = ax1, ay1, ay276 }7778 return rangeContainsInterior(vx, hx1, hx2) && rangeContainsInterior(hy, vy1, vy2)79}8081func assertNoBridgeCrossings(t *testing.T, p *Puzzle) {82 t.Helper()8384 for i := 0; i < len(p.Bridges); i++ {85 for j := i + 1; j < len(p.Bridges); j++ {86 if bridgesCross(p, p.Bridges[i], p.Bridges[j]) {87 t.Fatalf("bridge %d crosses bridge %d", i, j)88 }89 }90 }91}9293func TestGeneratePuzzleRequiredCountsByBoardSize(t *testing.T) {94 for modeIndex, mode := range benchmarkHashiModesByBoardSize() {95 t.Run(mode.Title(), func(t *testing.T) {96 puzzle, err := GeneratePuzzleSeeded(mode, rand.New(rand.NewPCG(uint64(modeIndex+900), uint64(modeIndex+901))))97 if err != nil {98 t.Fatalf("GeneratePuzzleSeeded failed: %v", err)99 }100 if puzzle.Width != mode.Width || puzzle.Height != mode.Height {101 t.Fatalf("dimensions = %dx%d, want %dx%d", puzzle.Width, puzzle.Height, mode.Width, mode.Height)102 }103 if len(puzzle.Bridges) != 0 {104 t.Fatalf("expected cleared bridges, got %d", len(puzzle.Bridges))105 }106 for _, island := range puzzle.Islands {107 if island.Required < 1 || island.Required > 8 {108 t.Fatalf("island %d required=%d out of range", island.ID, island.Required)109 }110 }111 })112 }113}114115func TestBridgeLayoutConstraintInvariantsByBoardSize(t *testing.T) {116 for _, mode := range benchmarkHashiModesByBoardSize() {117 t.Run(mode.Title(), func(t *testing.T) {118 p := testBridgeLayoutByMode(t, mode)119120 if !p.IsConnected() {121 t.Fatal("expected connected bridge layout")122 }123124 seen := make(map[[2]int]bool, len(p.Bridges))125 for _, b := range p.Bridges {126 if b.Count < 1 || b.Count > 2 {127 t.Fatalf("bridge count out of range: %d", b.Count)128 }129 key := [2]int{b.Island1, b.Island2}130 if seen[key] {131 t.Fatalf("duplicate bridge pair: %v", key)132 }133 seen[key] = true134135 i1 := p.FindIslandByID(b.Island1)136 i2 := p.FindIslandByID(b.Island2)137 if i1 == nil || i2 == nil {138 t.Fatalf("bridge references unknown island: %+v", b)139 }140 if !isDirectlyConnectable(&p, *i1, *i2) {141 t.Fatalf("bridge between non-directly-connectable islands: %+v", b)142 }143 }144145 assertNoBridgeCrossings(t, &p)146147 for _, island := range p.Islands {148 count := p.BridgeCount(island.ID)149 if count < 1 || count > 8 {150 t.Fatalf("island %d bridge count=%d out of range", island.ID, count)151 }152 }153 })154 }155}