1package netwalk23import (4 "fmt"5 "math/bits"6)78type directionMask uint8910const (11 north directionMask = 1 << iota12 east13 south14 west15)1617const allDirections = north | east | south | west1819type cellKind uint82021const (22 emptyCell cellKind = iota23 nodeCell24 serverCell25)2627type point struct {28 X int29 Y int30}3132type tile struct {33 BaseMask directionMask34 Rotation uint835 InitialRotation uint836 Locked bool37 Kind cellKind38}3940type Puzzle struct {41 Size int42 Root point43 Tiles [][]tile44}4546type boardState struct {47 nonEmpty int48 connected int49 dangling int50 locked int51 solved bool52 allMatched bool53 connectedToRoot [][]bool54 tileHasDangling [][]bool55 rotatedMasks [][]directionMask56}5758type directionSpec struct {59 dx int60 dy int61 bit directionMask62 opp directionMask63}6465var directions = []directionSpec{66 {dx: 0, dy: -1, bit: north, opp: south},67 {dx: 1, dy: 0, bit: east, opp: west},68 {dx: 0, dy: 1, bit: south, opp: north},69 {dx: -1, dy: 0, bit: west, opp: east},70}7172func newPuzzle(size int) Puzzle {73 tiles := make([][]tile, size)74 for y := range size {75 tiles[y] = make([]tile, size)76 }77 return Puzzle{Size: size, Tiles: tiles}78}7980func (p Puzzle) inBounds(x, y int) bool {81 return x >= 0 && x < p.Size && y >= 0 && y < p.Size82}8384func (p Puzzle) activeAt(x, y int) bool {85 return p.inBounds(x, y) && p.Tiles[y][x].Kind != emptyCell86}8788func (p Puzzle) firstActive() point {89 if p.activeAt(p.Root.X, p.Root.Y) {90 return p.Root91 }92 for y := range p.Size {93 for x := range p.Size {94 if p.activeAt(x, y) {95 return point{X: x, Y: y}96 }97 }98 }99 return point{}100}101102func isActive(t tile) bool {103 return t.Kind != emptyCell104}105106func rotateMask(mask directionMask, rotation uint8) directionMask {107 shift := rotation % 4108 if shift == 0 {109 return mask110 }111 value := uint8(mask & allDirections)112 return directionMask(((value << shift) | (value >> (4 - shift))) & uint8(allDirections))113}114115func degree(mask directionMask) int {116 return bits.OnesCount8(uint8(mask))117}118119func uniqueRotations(mask directionMask) []uint8 {120 seen := make(map[directionMask]struct{}, 4)121 rotations := make([]uint8, 0, 4)122 for rot := uint8(0); rot < 4; rot++ {123 rotated := rotateMask(mask, rot)124 if _, ok := seen[rotated]; ok {125 continue126 }127 seen[rotated] = struct{}{}128 rotations = append(rotations, rot)129 }130 return rotations131}132133func maskGlyph(mask directionMask) string {134 switch mask {135 case 0:136 return " "137 case north:138 return "╵"139 case east:140 return "╶"141 case south:142 return "╷"143 case west:144 return "╴"145 case north | south:146 return "│"147 case east | west:148 return "─"149 case north | east:150 return "└"151 case east | south:152 return "┌"153 case south | west:154 return "┐"155 case west | north:156 return "┘"157 case north | east | south:158 return "├"159 case east | south | west:160 return "┬"161 case south | west | north:162 return "┤"163 case west | north | east:164 return "┴"165 case north | east | south | west:166 return "┼"167 default:168 return "?"169 }170}171172func encodeMaskRows(tiles [][]tile) string {173 return encodeRows(len(tiles), func(x, y int) byte {174 return nibbleHex(uint8(tiles[y][x].BaseMask))175 })176}177178func encodeRotationRows(tiles [][]tile, initial bool) string {179 return encodeRows(len(tiles), func(x, y int) byte {180 value := tiles[y][x].Rotation181 if initial {182 value = tiles[y][x].InitialRotation183 }184 return byte('0' + value%4)185 })186}187188func encodeKindRows(tiles [][]tile) string {189 return encodeRows(len(tiles), func(x, y int) byte {190 switch tiles[y][x].Kind {191 case serverCell:192 return 'S'193 case nodeCell:194 return '#'195 default:196 return '.'197 }198 })199}200201func encodeLockRows(tiles [][]tile) string {202 return encodeRows(len(tiles), func(x, y int) byte {203 if tiles[y][x].Locked {204 return '#'205 }206 return '.'207 })208}209210func decodePuzzle(size int, masks, rotations, initial, kinds, locks string) (Puzzle, error) {211 if size <= 0 {212 return Puzzle{}, fmt.Errorf("invalid netwalk size %d", size)213 }214 maskRows, err := decodeRows(size, masks)215 if err != nil {216 return Puzzle{}, fmt.Errorf("decode masks: %w", err)217 }218 rotationRows, err := decodeRows(size, rotations)219 if err != nil {220 return Puzzle{}, fmt.Errorf("decode rotations: %w", err)221 }222 initialRows, err := decodeRows(size, initial)223 if err != nil {224 return Puzzle{}, fmt.Errorf("decode initial rotations: %w", err)225 }226 kindRows, err := decodeRows(size, kinds)227 if err != nil {228 return Puzzle{}, fmt.Errorf("decode kinds: %w", err)229 }230 lockRows, err := decodeRows(size, locks)231 if err != nil {232 return Puzzle{}, fmt.Errorf("decode locks: %w", err)233 }234235 puzzle := newPuzzle(size)236 rootCount := 0237 for y := range size {238 for x := range size {239 maskValue, ok := parseNibble(maskRows[y][x])240 if !ok {241 return Puzzle{}, fmt.Errorf("invalid mask value %q at (%d,%d)", maskRows[y][x], x, y)242 }243 rotationValue := rotationRows[y][x]244 initialValue := initialRows[y][x]245 if rotationValue < '0' || rotationValue > '3' || initialValue < '0' || initialValue > '3' {246 return Puzzle{}, fmt.Errorf("invalid rotation at (%d,%d)", x, y)247 }248249 t := tile{250 BaseMask: directionMask(maskValue),251 Rotation: uint8(rotationValue - '0'),252 InitialRotation: uint8(initialValue - '0'),253 }254255 switch kindRows[y][x] {256 case 'S':257 t.Kind = serverCell258 puzzle.Root = point{X: x, Y: y}259 rootCount++260 case '#':261 t.Kind = nodeCell262 case '.':263 t.Kind = emptyCell264 default:265 return Puzzle{}, fmt.Errorf("invalid cell kind %q at (%d,%d)", kindRows[y][x], x, y)266 }267268 if t.Kind == emptyCell && t.BaseMask != 0 {269 return Puzzle{}, fmt.Errorf("empty tile at (%d,%d) has mask", x, y)270 }271 if t.Kind != emptyCell && t.BaseMask == 0 {272 return Puzzle{}, fmt.Errorf("active tile at (%d,%d) has empty mask", x, y)273 }274 if lockRows[y][x] == '#' {275 t.Locked = true276 }277 puzzle.Tiles[y][x] = t278 }279 }280281 if rootCount != 1 {282 return Puzzle{}, fmt.Errorf("expected exactly one root, got %d", rootCount)283 }284285 return puzzle, nil286}287288func encodeRows(size int, valueAt func(x, y int) byte) string {289 buf := make([]byte, 0, size*size+max(size-1, 0))290 for y := range size {291 for x := range size {292 buf = append(buf, valueAt(x, y))293 }294 if y < size-1 {295 buf = append(buf, '\n')296 }297 }298 return string(buf)299}300301func decodeRows(size int, raw string) ([][]byte, error) {302 rows := make([][]byte, size)303 currentRow := 0304 currentCol := 0305 rows[currentRow] = make([]byte, size)306307 for i := 0; i < len(raw); i++ {308 ch := raw[i]309 if ch == '\r' {310 continue311 }312 if ch == '\n' {313 if currentCol != size {314 return nil, fmt.Errorf("row %d has width %d, want %d", currentRow, currentCol, size)315 }316 currentRow++317 if currentRow >= size {318 return nil, fmt.Errorf("too many rows")319 }320 rows[currentRow] = make([]byte, size)321 currentCol = 0322 continue323 }324 if currentCol >= size {325 return nil, fmt.Errorf("row %d exceeds width %d", currentRow, size)326 }327 rows[currentRow][currentCol] = ch328 currentCol++329 }330331 if currentRow != size-1 || currentCol != size {332 return nil, fmt.Errorf("incomplete grid")333 }334335 return rows, nil336}337338func nibbleHex(value uint8) byte {339 if value < 10 {340 return '0' + value341 }342 return 'a' + (value - 10)343}344345func parseNibble(value byte) (uint8, bool) {346 switch {347 case value >= '0' && value <= '9':348 return value - '0', true349 case value >= 'a' && value <= 'f':350 return 10 + value - 'a', true351 case value >= 'A' && value <= 'F':352 return 10 + value - 'A', true353 default:354 return 0, false355 }356}357358func analyzePuzzle(p Puzzle) boardState {359 state := boardState{360 connectedToRoot: make([][]bool, p.Size),361 tileHasDangling: make([][]bool, p.Size),362 rotatedMasks: make([][]directionMask, p.Size),363 }364 for y := range p.Size {365 state.connectedToRoot[y] = make([]bool, p.Size)366 state.tileHasDangling[y] = make([]bool, p.Size)367 state.rotatedMasks[y] = make([]directionMask, p.Size)368 for x := range p.Size {369 t := p.Tiles[y][x]370 if !isActive(t) {371 continue372 }373 state.nonEmpty++374 if t.Locked {375 state.locked++376 }377 state.rotatedMasks[y][x] = rotateMask(t.BaseMask, t.Rotation)378 }379 }380381 allMatched := true382 halfEdges := 0383 for y := range p.Size {384 for x := range p.Size {385 t := p.Tiles[y][x]386 if !isActive(t) {387 continue388 }389 mask := state.rotatedMasks[y][x]390 for _, dir := range directions {391 if mask&dir.bit == 0 {392 continue393 }394 halfEdges++395 nx := x + dir.dx396 ny := y + dir.dy397 if !p.activeAt(nx, ny) {398 state.tileHasDangling[y][x] = true399 state.dangling++400 allMatched = false401 continue402 }403 neighborMask := state.rotatedMasks[ny][nx]404 if neighborMask&dir.opp == 0 {405 state.tileHasDangling[y][x] = true406 state.dangling++407 allMatched = false408 }409 }410 }411 }412413 state.allMatched = allMatched414 if !p.activeAt(p.Root.X, p.Root.Y) {415 return state416 }417418 queue := []point{p.Root}419 state.connectedToRoot[p.Root.Y][p.Root.X] = true420 for len(queue) > 0 {421 cur := queue[0]422 queue = queue[1:]423 state.connected++424 mask := state.rotatedMasks[cur.Y][cur.X]425 for _, dir := range directions {426 if mask&dir.bit == 0 {427 continue428 }429 nx := cur.X + dir.dx430 ny := cur.Y + dir.dy431 if !p.activeAt(nx, ny) || state.connectedToRoot[ny][nx] {432 continue433 }434 neighborMask := state.rotatedMasks[ny][nx]435 if neighborMask&dir.opp == 0 {436 continue437 }438 state.connectedToRoot[ny][nx] = true439 queue = append(queue, point{X: nx, Y: ny})440 }441 }442443 matchedEdges := halfEdges / 2444 state.solved = state.nonEmpty > 0 &&445 allMatched &&446 state.connected == state.nonEmpty &&447 matchedEdges == state.nonEmpty-1448449 return state450}