86 lines
1.8 KiB
Go
86 lines
1.8 KiB
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
func nextInCycle(c []int, index int) int {
|
|
return c[index % len(c)]
|
|
}
|
|
|
|
func kolakoski(c []int, slen int) []int {
|
|
s := make([]int, slen)
|
|
i, k := 0, 0
|
|
for {
|
|
s[i] = nextInCycle(c, k)
|
|
if s[k] > 1 {
|
|
for j := 1; j < s[k]; j++ {
|
|
i++
|
|
if i == slen {
|
|
return s
|
|
}
|
|
s[i] = s[i - 1]
|
|
}
|
|
}
|
|
i++
|
|
if i == slen {
|
|
return s
|
|
}
|
|
k++
|
|
}
|
|
}
|
|
|
|
func possibleKolakoski(s []int) bool {
|
|
slen := len(s)
|
|
rle := make([]int, 0, slen)
|
|
prev := s[0]
|
|
count := 1
|
|
for i := 1; i < slen; i++ {
|
|
if s[i] == prev {
|
|
count++
|
|
} else {
|
|
rle = append(rle, count)
|
|
count = 1
|
|
prev = s[i]
|
|
}
|
|
}
|
|
// no point adding final 'count' to rle as we're not going to compare it anyway
|
|
for i := 0; i < len(rle); i++ {
|
|
if rle[i] != s[i] {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
func printInts(ia []int, suffix string) {
|
|
fmt.Print("[")
|
|
alen := len(ia)
|
|
for i := 0; i < alen; i++ {
|
|
fmt.Print(ia[i])
|
|
if i < alen - 1 {
|
|
fmt.Print(", ")
|
|
}
|
|
}
|
|
fmt.Printf("]%s\n", suffix)
|
|
}
|
|
|
|
func main() {
|
|
ias := make([][]int, 4)
|
|
ias[0] = []int{1, 2}
|
|
ias[1] = []int{2, 1}
|
|
ias[2] = []int{1, 3, 1, 2}
|
|
ias[3] = []int{1, 3, 2, 1}
|
|
slens := []int{20, 20, 30, 30}
|
|
for i, ia := range ias {
|
|
slen := slens[i]
|
|
kol := kolakoski(ia, slen)
|
|
fmt.Printf("First %d members of the sequence generated by ", slen)
|
|
printInts(ia, ":")
|
|
printInts(kol, "")
|
|
p := possibleKolakoski(kol)
|
|
poss := "Yes"
|
|
if !p {
|
|
poss = "No"
|
|
}
|
|
fmt.Println("Possible Kolakoski sequence?", poss, "\n")
|
|
}
|
|
}
|