Last active
April 25, 2021 02:39
-
-
Save rmmh/91fe79182dfb47859a8ce02e47e91028 to your computer and use it in GitHub Desktop.
worm-polyomino counting
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // How many distinct closed paths visit each cell in an NxN grid exactly once? | |
| package main | |
| import ( | |
| "fmt" | |
| "math/bits" | |
| ) | |
| type walls struct { | |
| vert, horiz uint64 | |
| } | |
| type openentry struct { | |
| open uint64 | |
| boards []*walls | |
| } | |
| var emcount int | |
| var N int | |
| var DEBUG int | |
| func printBoard(open, vert, horiz uint64) { | |
| fmt.Printf("╔") | |
| for i := 0; i < N; i++ { | |
| fmt.Printf("═") | |
| } | |
| fmt.Printf("╗ %x %x %x\n", open, vert, horiz) | |
| for y := 0; y < N; y++ { | |
| fmt.Printf("║") | |
| for x := 0; x < N; x++ { | |
| i := x + y*8 | |
| if open&(1<<i) != 0 { | |
| fmt.Printf(" ") | |
| continue | |
| } | |
| box := 0 | |
| if vert&(1<<i) != 0 { | |
| box |= 1 | |
| } | |
| if y > 0 && vert&(1<<(i-8)) != 0 { | |
| box |= 2 | |
| } | |
| if horiz&(1<<i) != 0 { | |
| box |= 4 | |
| } | |
| if x > 0 && horiz&(1<<(i-1)) != 0 { | |
| box |= 8 | |
| } | |
| fmt.Printf("%c", []rune("•╷╵│╶╭╰7╴╮╯b─def")[box]) | |
| } | |
| fmt.Printf("║\n") | |
| } | |
| fmt.Printf("╚") | |
| for i := 0; i < N; i++ { | |
| fmt.Printf("═") | |
| } | |
| fmt.Printf("╝\n") | |
| } | |
| // swap(1, 8); swap(2, 16); swap(3, 24); ... swap(7, 52) | |
| // swap(10, 17) | |
| func transpose(x uint64) uint64 { | |
| // transpose x, as an 8x8 bitarray | |
| // 1) transpose as a 2x2 array of 4x4 | |
| // 2) transpose as a 4x4 array of 2x2 | |
| // 3) transpose within each 2x2 array | |
| // 01234567 | |
| //8+ 01234567 | |
| //16+ 01234567 | |
| //24+ 01234567 | |
| //32+ 01234567 | |
| //40+ 01234567 | |
| //48+ 01234567 | |
| //54+ 01234567 | |
| // 01 => 02 | |
| // 23 13 | |
| x = x&0xf0f0f0f00f0f0f0f | (x&0xf0f0f0f0)<<28 | (x&0x0f0f0f0f00000000)>>28 | |
| // 0123 => 0426 | |
| // 4567 1537 | |
| // 89AB 8CAE | |
| // CDEF 9DBF | |
| x = x&0xcccc3333cccc3333 | (x&0xcccc0000cccc)<<14 | (x&0x3333000033330000)>>14 | |
| x = x&0xaa55aa55aa55aa55 | (x&0x00aa00aa00aa00aa)<<7 | (x&0x5500550055005500)>>7 | |
| return x | |
| } | |
| func wallLte(a, b walls) bool { | |
| if a.vert != b.vert { | |
| return a.vert <= b.vert | |
| } | |
| return a.horiz <= b.horiz | |
| } | |
| func canonical(vert, horiz uint64) bool { | |
| vertFlipV := bits.ReverseBytes64(vert) >> (64 - 8*(N-1)) | |
| horizFlipV := bits.ReverseBytes64(horiz) >> (64 - 8*(N)) | |
| vertFlipH := bits.ReverseBytes64(bits.Reverse64(vert)) >> (8 - N) | |
| horizFlipH := bits.ReverseBytes64(bits.Reverse64(horiz)) >> (8 - N + 1) | |
| vertRot180 := bits.ReverseBytes64(vertFlipH) >> (64 - 8*(N-1)) | |
| horizRot180 := bits.ReverseBytes64(horizFlipH) >> (64 - 8*(N)) | |
| vertRot90 := transpose(horiz) | |
| horizRot90 := transpose(vert) | |
| vertRot270 := transpose(horizRot180) | |
| horizRot270 := transpose(vertRot180) | |
| vertRot90FlipV := bits.ReverseBytes64(vertRot90) >> (64 - 8*(N-1)) | |
| horizRot90FlipV := bits.ReverseBytes64(horizRot90) >> (64 - 8*(N)) | |
| vertRot90FlipH := bits.ReverseBytes64(bits.Reverse64(vertRot90)) >> (8 - N) | |
| horizRot90FlipH := bits.ReverseBytes64(bits.Reverse64(horizRot90)) >> (8 - N + 1) | |
| if DEBUG > 1 { | |
| fmt.Printf("canonical %b %b flipV: %b %b flipH: %b %b rot90: %b %b\n", vert, horiz, vertFlipV, horizFlipV, vertFlipH, horizFlipH, vertRot90, horizRot90) | |
| printBoard(0, vert, horiz) | |
| printBoard(0, vertFlipV, horizFlipV) | |
| printBoard(0, vertFlipH, horizFlipH) | |
| printBoard(0, vertRot90, horizRot90) | |
| printBoard(0, vertRot180, horizRot180) | |
| printBoard(0, vertRot270, horizRot270) | |
| printBoard(0, vertRot90FlipV, horizRot90FlipV) | |
| printBoard(0, vertRot90FlipH, horizRot90FlipH) | |
| } | |
| return wallLte(walls{vert, horiz}, walls{vertFlipV, horizFlipV}) && | |
| wallLte(walls{vert, horiz}, walls{vertFlipH, horizFlipH}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot180, horizRot180}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot90, horizRot90}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot270, horizRot270}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot90FlipV, horizRot90FlipV}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot90FlipH, horizRot90FlipH}) | |
| } | |
| func impossible(open uint64, pos int) bool { | |
| // is the board impossible to complete since it has an isolated hole or the start/end aren't reachable? | |
| group := uint64(1) << bits.TrailingZeros64(open) | |
| last := uint64(0) | |
| for last != group { | |
| last = group | |
| group = open & (group | | |
| (group&0x7f7f7f7f7f7f7f7f)<<1 | (group&0xfefefefefefefefe)>>1 | | |
| group>>8 | group<<8) | |
| } | |
| groupAdjacent := (group | | |
| (group&0x7f7f7f7f7f7f7f7f)<<1 | (group&0xfefefefefefefefe)>>1 | | |
| group>>8 | group<<8) | |
| return group != open || groupAdjacent&1 == 0 || groupAdjacent&(1<<pos) == 0 | |
| } | |
| func recur(open, vert, horiz uint64, pos, left int) int { | |
| //fmt.Printf("%32b %16b %16b %d\n", open, vert, horiz, bits.OnesCount64(open)) | |
| // printBoard(open, vert, horiz) | |
| if open == 0 { | |
| if pos != 8 { | |
| return 0 | |
| } | |
| emcount++ | |
| if canonical(vert, horiz) { | |
| if DEBUG > 0 { | |
| fmt.Printf("UNIQUE %b %b\n", vert, horiz) //, vertRev, horiz, horizRev) | |
| printBoard(open, vert, horiz) | |
| } | |
| return 1 | |
| } | |
| return 0 | |
| } | |
| if impossible(open, pos) { | |
| // printBoard(open, vert, horiz) | |
| return 0 | |
| } | |
| val := 0 | |
| if pos >= N && open&(1<<(pos-8)) != 0 { | |
| val += recur(open&^(1<<(pos-8)), vert|(1<<(pos-8)), horiz, pos-8, left-1) | |
| } | |
| if open&(1<<(pos+8)) != 0 { | |
| val += recur(open&^(1<<(pos+8)), vert|(1<<(pos)), horiz, pos+8, left-1) | |
| } | |
| if (pos%8) < 7 && open&(1<<(pos+1)) != 0 { | |
| val += recur(open&^(1<<(pos+1)), vert, horiz|(1<<(pos)), pos+1, left-1) | |
| } | |
| if (pos%8) > 0 && open&(1<<(pos-1)) != 0 { | |
| val += recur(open&^(1<<(pos-1)), vert, horiz|(1<<(pos-1)), pos-1, left-1) | |
| } | |
| return val | |
| } | |
| func main() { | |
| DEBUG = 1 | |
| for N = 1; N <= 8; N++ { | |
| emcount = 0 | |
| var open uint64 = (1 << N) - 1 | |
| for i := 1; i < N; i++ { | |
| open |= open << 8 | |
| } | |
| count := recur(open&^3, 1, 1, 1, N*N-2) // start with a corner | |
| fmt.Printf("###N=%d %b has %d distinct solutions (%d total)\n", N, open, count, emcount) | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "fmt" | |
| "math/bits" | |
| "sort" | |
| ) | |
| type walls struct { | |
| vert, horiz uint64 | |
| } | |
| type openentry struct { | |
| open uint64 | |
| boards []*walls | |
| } | |
| var emcount int | |
| var N int | |
| var DEBUG int | |
| func printBoard(open, vert, horiz uint64) { | |
| fmt.Printf("╔") | |
| for i := 0; i < N; i++ { | |
| fmt.Printf("═") | |
| } | |
| fmt.Printf("╗ %x %x %x\n", open, vert, horiz) | |
| for y := 0; y < N; y++ { | |
| fmt.Printf("║") | |
| for x := 0; x < N; x++ { | |
| i := x + y*8 | |
| if open&(1<<i) != 0 { | |
| fmt.Printf(" ") | |
| continue | |
| } | |
| box := 0 | |
| if vert&(1<<i) != 0 { | |
| box |= 1 | |
| } | |
| if y > 0 && vert&(1<<(i-8)) != 0 { | |
| box |= 2 | |
| } | |
| if horiz&(1<<i) != 0 { | |
| box |= 4 | |
| } | |
| if x > 0 && horiz&(1<<(i-1)) != 0 { | |
| box |= 8 | |
| } | |
| fmt.Printf("%c", []rune("•╷╵│╶╭╰7╴╮╯b─def")[box]) | |
| } | |
| fmt.Printf("║\n") | |
| } | |
| fmt.Printf("╚") | |
| for i := 0; i < N; i++ { | |
| fmt.Printf("═") | |
| } | |
| fmt.Printf("╝\n") | |
| } | |
| // swap(1, 8); swap(2, 16); swap(3, 24); ... swap(7, 52) | |
| // swap(10, 17) | |
| func transpose(x uint64) uint64 { | |
| // transpose x, as an 8x8 bitarray | |
| // 1) transpose as a 2x2 array of 4x4 | |
| // 2) transpose as a 4x4 array of 2x2 | |
| // 3) transpose within each 2x2 array | |
| // 01234567 | |
| //8+ 01234567 | |
| //16+ 01234567 | |
| //24+ 01234567 | |
| //32+ 01234567 | |
| //40+ 01234567 | |
| //48+ 01234567 | |
| //54+ 01234567 | |
| // 01 => 02 | |
| // 23 13 | |
| x = x&0xf0f0f0f00f0f0f0f | (x&0xf0f0f0f0)<<28 | (x&0x0f0f0f0f00000000)>>28 | |
| // 0123 => 0426 | |
| // 4567 1537 | |
| // 89AB 8CAE | |
| // CDEF 9DBF | |
| x = x&0xcccc3333cccc3333 | (x&0xcccc0000cccc)<<14 | (x&0x3333000033330000)>>14 | |
| x = x&0xaa55aa55aa55aa55 | (x&0x00aa00aa00aa00aa)<<7 | (x&0x5500550055005500)>>7 | |
| return x | |
| } | |
| func wallLte(a, b walls) bool { | |
| if a.vert != b.vert { | |
| return a.vert <= b.vert | |
| } | |
| return a.horiz <= b.horiz | |
| } | |
| func canonical(vert, horiz uint64) bool { | |
| vertFlipV := bits.ReverseBytes64(vert) >> (64 - 8*(N-1)) | |
| horizFlipV := bits.ReverseBytes64(horiz) >> (64 - 8*(N)) | |
| vertFlipH := bits.ReverseBytes64(bits.Reverse64(vert)) >> (8 - N) | |
| horizFlipH := bits.ReverseBytes64(bits.Reverse64(horiz)) >> (8 - N + 1) | |
| vertRot180 := bits.ReverseBytes64(vertFlipH) >> (64 - 8*(N-1)) | |
| horizRot180 := bits.ReverseBytes64(horizFlipH) >> (64 - 8*(N)) | |
| vertRot90 := transpose(horiz) | |
| horizRot90 := transpose(vert) | |
| vertRot270 := transpose(horizRot180) | |
| horizRot270 := transpose(vertRot180) | |
| vertRot90FlipV := bits.ReverseBytes64(vertRot90) >> (64 - 8*(N-1)) | |
| horizRot90FlipV := bits.ReverseBytes64(horizRot90) >> (64 - 8*(N)) | |
| vertRot90FlipH := bits.ReverseBytes64(bits.Reverse64(vertRot90)) >> (8 - N) | |
| horizRot90FlipH := bits.ReverseBytes64(bits.Reverse64(horizRot90)) >> (8 - N + 1) | |
| if DEBUG > 1 { | |
| fmt.Printf("canonical %b %b flipV: %b %b flipH: %b %b rot90: %b %b\n", vert, horiz, vertFlipV, horizFlipV, vertFlipH, horizFlipH, vertRot90, horizRot90) | |
| printBoard(0, vert, horiz) | |
| printBoard(0, vertFlipV, horizFlipV) | |
| printBoard(0, vertFlipH, horizFlipH) | |
| printBoard(0, vertRot90, horizRot90) | |
| printBoard(0, vertRot180, horizRot180) | |
| printBoard(0, vertRot270, horizRot270) | |
| printBoard(0, vertRot90FlipV, horizRot90FlipV) | |
| printBoard(0, vertRot90FlipH, horizRot90FlipH) | |
| } | |
| return wallLte(walls{vert, horiz}, walls{vertFlipV, horizFlipV}) && | |
| wallLte(walls{vert, horiz}, walls{vertFlipH, horizFlipH}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot180, horizRot180}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot90, horizRot90}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot270, horizRot270}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot90FlipV, horizRot90FlipV}) && | |
| wallLte(walls{vert, horiz}, walls{vertRot90FlipH, horizRot90FlipH}) | |
| } | |
| func impossible(open uint64) bool { | |
| // is the board impossible to complete since it has an isolated hole of the wrong size? | |
| for open != 0 { | |
| group := uint64(1) << bits.TrailingZeros64(open) | |
| last := uint64(0) | |
| for last != group { | |
| last = group | |
| group = open & (group | | |
| (group&0x7f7f7f7f7f7f7f7f)<<1 | (group&0xfefefefefefefefe)>>1 | | |
| group>>8 | group<<8) | |
| } | |
| if bits.OnesCount64(group)%N != 0 { | |
| return true | |
| } | |
| open &^= group | |
| } | |
| return false | |
| } | |
| func recur(open, vert, horiz uint64) int { | |
| // fmt.Printf("%32b %16b %16b %d\n", open, vert, horiz, bits.OnesCount64(open)) | |
| // printBoard(open, vert, horiz) | |
| val := 0 | |
| if open == 0 { | |
| emcount++ | |
| if canonical(vert, horiz) { | |
| if DEBUG > 0 { | |
| fmt.Printf("UNIQUE %b %b\n", vert, horiz) //, vertRev, horiz, horizRev) | |
| printBoard(open, vert, horiz) | |
| } | |
| return 1 | |
| } | |
| return 0 | |
| } | |
| if impossible(open) { | |
| // printBoard(open, vert, horiz) | |
| return 0 | |
| } | |
| target := bits.TrailingZeros64(open) | |
| for _, w := range tiles[target] { | |
| if w.cells&open == w.cells { | |
| val += recur(open&^w.cells, vert|w.vert, horiz|w.horiz) | |
| } | |
| } | |
| return val | |
| } | |
| type tileshape struct{ cells, vert, horiz uint64 } | |
| var tiles = [64][]tileshape{} | |
| func worm(fullopen, open, vert, horiz uint64, pos, left int) { | |
| if left == -1 { | |
| for i := 0; i < 64; i++ { | |
| if fullopen&(1<<i) != 0 { | |
| worm(fullopen, open&^(1<<i), 0, 0, i, N-1) | |
| } | |
| } | |
| } else if left == 0 { | |
| cells := fullopen ^ open | |
| for _, w := range tiles[bits.TrailingZeros64(cells)] { | |
| if cells == w.cells && vert == w.vert && horiz == w.horiz { | |
| return | |
| } | |
| } | |
| for i := 0; i < 64; i++ { | |
| if cells&(1<<i) != 0 { | |
| tiles[i] = append(tiles[i], tileshape{cells, vert, horiz}) | |
| } | |
| } | |
| } else { | |
| if pos >= N && open&(1<<(pos-8)) != 0 { | |
| worm(fullopen, open&^(1<<(pos-8)), vert|(1<<(pos-8)), horiz, pos-8, left-1) | |
| } | |
| if open&(1<<(pos+8)) != 0 { | |
| worm(fullopen, open&^(1<<(pos+8)), vert|(1<<(pos)), horiz, pos+8, left-1) | |
| } | |
| if (pos%8) < 7 && open&(1<<(pos+1)) != 0 { | |
| worm(fullopen, open&^(1<<(pos+1)), vert, horiz|(1<<(pos)), pos+1, left-1) | |
| } | |
| if (pos%8) > 0 && open&(1<<(pos-1)) != 0 { | |
| worm(fullopen, open&^(1<<(pos-1)), vert, horiz|(1<<(pos-1)), pos-1, left-1) | |
| } | |
| } | |
| } | |
| func main() { | |
| DEBUG = 1 | |
| for N = 1; N <= 8; N++ { | |
| tiles = [64][]tileshape{} | |
| emcount = 0 | |
| var open uint64 = (1 << N) - 1 | |
| for i := 1; i < N; i++ { | |
| open |= open << 8 | |
| } | |
| worm(open, open, 0, 0, 0, -1) | |
| count := recur(open, 0, 0) | |
| emstack := []walls{} | |
| sort.Slice(emstack, func(i, j int) bool { | |
| a := emstack[i] | |
| b := emstack[j] | |
| if a.vert != b.vert { | |
| return a.vert < b.vert | |
| } | |
| return a.horiz < b.horiz | |
| }) | |
| fmt.Printf("###N=%d %b has %d distinct solutions (%d total)\n", N, open, count, emcount) | |
| if false { | |
| for _, wall := range emstack { | |
| printBoard(0, wall.vert, wall.horiz) | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment