1package rippleeffect23import "fmt"45type Cell struct {6 X int `json:"x"`7 Y int `json:"y"`8}910type Cage struct {11 ID int `json:"id"`12 Size int `json:"size"`13 Cells []Cell `json:"cells"`14}1516type boundaryMask uint81718const (19 boundaryTop boundaryMask = 1 << iota20 boundaryRight21 boundaryBottom22 boundaryLeft23)2425func (m boundaryMask) has(flag boundaryMask) bool {26 return m&flag != 027}2829type geometry struct {30 width int31 height int32 cages []Cage33 cageGrid [][]int34 cageCells [][]point35 cageSizes []int36 boundaries [][]boundaryMask37}3839func buildGeometry(width, height int, cages []Cage) (*geometry, error) {40 if width <= 0 || height <= 0 {41 return nil, fmt.Errorf("invalid ripple effect size %dx%d", width, height)42 }43 if len(cages) == 0 {44 return nil, fmt.Errorf("ripple effect requires at least one cage")45 }4647 cageGrid := make([][]int, height)48 for y := range height {49 cageGrid[y] = make([]int, width)50 for x := range width {51 cageGrid[y][x] = -152 }53 }5455 idSeen := make(map[int]struct{}, len(cages))56 cageCells := make([][]point, len(cages))57 cageSizes := make([]int, len(cages))58 for cageIdx, cage := range cages {59 if _, exists := idSeen[cage.ID]; exists {60 return nil, fmt.Errorf("duplicate cage id %d", cage.ID)61 }62 idSeen[cage.ID] = struct{}{}6364 size := cage.Size65 if size == 0 {66 size = len(cage.Cells)67 cages[cageIdx].Size = size68 }69 if size != len(cage.Cells) {70 return nil, fmt.Errorf("cage %d size %d does not match %d cells", cage.ID, cage.Size, len(cage.Cells))71 }72 if size <= 0 || size > 9 {73 return nil, fmt.Errorf("cage %d has invalid size %d", cage.ID, size)74 }7576 cells := make([]point, 0, len(cage.Cells))77 for _, cell := range cage.Cells {78 if cell.X < 0 || cell.X >= width || cell.Y < 0 || cell.Y >= height {79 return nil, fmt.Errorf("cage %d has out-of-bounds cell (%d,%d)", cage.ID, cell.X, cell.Y)80 }81 if cageGrid[cell.Y][cell.X] >= 0 {82 return nil, fmt.Errorf("cell (%d,%d) belongs to multiple cages", cell.X, cell.Y)83 }84 cageGrid[cell.Y][cell.X] = cageIdx85 cells = append(cells, point{x: cell.X, y: cell.Y})86 }87 if !cellsConnected(cells) {88 return nil, fmt.Errorf("cage %d is not connected", cage.ID)89 }9091 cageCells[cageIdx] = cells92 cageSizes[cageIdx] = size93 }9495 for y := range height {96 for x := range width {97 if cageGrid[y][x] < 0 {98 return nil, fmt.Errorf("cell (%d,%d) is not assigned to any cage", x, y)99 }100 }101 }102103 return &geometry{104 width: width,105 height: height,106 cages: cages,107 cageGrid: cageGrid,108 cageCells: cageCells,109 cageSizes: cageSizes,110 boundaries: buildBoundaryMasks(cageGrid),111 }, nil112}113114func cellsConnected(cells []point) bool {115 if len(cells) <= 1 {116 return true117 }118119 cellSet := make(map[point]struct{}, len(cells))120 for _, cell := range cells {121 cellSet[cell] = struct{}{}122 }123124 queue := []point{cells[0]}125 visited := map[point]struct{}{cells[0]: {}}126 for len(queue) > 0 {127 curr := queue[0]128 queue = queue[1:]129 for _, next := range orthogonalNeighbors(curr, 1<<30, 1<<30) {130 if _, ok := cellSet[next]; !ok {131 continue132 }133 if _, ok := visited[next]; ok {134 continue135 }136 visited[next] = struct{}{}137 queue = append(queue, next)138 }139 }140141 return len(visited) == len(cells)142}143144func buildBoundaryMasks(cageGrid [][]int) [][]boundaryMask {145 height := len(cageGrid)146 width := len(cageGrid[0])147 masks := make([][]boundaryMask, height)148 for y := range height {149 masks[y] = make([]boundaryMask, width)150 for x := range width {151 cage := cageGrid[y][x]152 if y == 0 || cageGrid[y-1][x] != cage {153 masks[y][x] |= boundaryTop154 }155 if x == width-1 || cageGrid[y][x+1] != cage {156 masks[y][x] |= boundaryRight157 }158 if y == height-1 || cageGrid[y+1][x] != cage {159 masks[y][x] |= boundaryBottom160 }161 if x == 0 || cageGrid[y][x-1] != cage {162 masks[y][x] |= boundaryLeft163 }164 }165 }166 return masks167}168169func orthogonalNeighbors(p point, width, height int) []point {170 neighbors := make([]point, 0, 4)171 if p.x > 0 {172 neighbors = append(neighbors, point{x: p.x - 1, y: p.y})173 }174 if p.x+1 < width {175 neighbors = append(neighbors, point{x: p.x + 1, y: p.y})176 }177 if p.y > 0 {178 neighbors = append(neighbors, point{x: p.x, y: p.y - 1})179 }180 if p.y+1 < height {181 neighbors = append(neighbors, point{x: p.x, y: p.y + 1})182 }183 return neighbors184}