import (
    "math/rand"
    "bytes"
    "time"
    "fmt"
    "os"
)

type CellularAutomata struct {
    rule     []byte
    state    []byte
    left     byte
    mid      byte
    right    byte
    rule_idx byte
}

func cal_index(bl, bm, br byte) byte { return 4*bl + 2*bm + br }

func (c *CellularAutomata) Step(grow bool) {

    new_state := make([]byte, len(c.state)+2)
    offset := 0

    for curr := range c.state {
        if curr == 0 {
            if grow {
                c.left = c.state[len(c.state)-1]
            } else {
                c.left = 0
            }
            c.mid = c.state[0]
            c.right = c.state[1]
        } else if curr == len(c.state)-1 {
            c.left = c.state[curr-1]
            c.mid = c.state[curr]
            if grow {
                c.right = c.state[0]
            } else {
                c.right = 0
            }
        } else {
            c.left = c.state[curr-1]
            c.mid = c.state[curr]
            c.right = c.state[curr+1]
        }
        c.rule_idx = cal_index(c.left, c.mid, c.right)
        if grow {
            offset = 1
        }
        new_state[curr+offset] = c.rule[c.rule_idx]
    }

    c.state = new_state
}

func do(ca CellularAutomata, rounds int) time.Duration {

    start := time.Now()
    //fmt.Fprintf(os.Stdout, "%v: begin\n", time.Now())

    for i := 0; i < rounds; i++ {
        //fmt.Fprintf(os.Stdout, "%3d %v\n", i, ca.state)
        ca.Step(false)
    }

    elapsed := time.Since(start)
    fmt.Fprintf(os.Stdout, "..%v rounds..took: %v\n", rounds, elapsed)

    return elapsed
}

func find(ca CellularAutomata, target []byte) (int, time.Duration) {
    start := time.Now()
    round := 0
    for {
        if bytes.Equal(ca.state, target) {
            elapsed := time.Since(start)
            fmt.Fprintf(os.Stdout, "..%v rounds..took: %v\n", round, elapsed)
            return round, elapsed
        }
        if round % 10000000 == 0 {
            elapsed := time.Since(start)
            fmt.Fprintf(os.Stdout, "..%v rounds..took: %v\n", round, elapsed)
            fmt.Fprintf(os.Stdout, "current state: %v\n", ca.state)
        }
        ca.Step(false)
        round++
    }
}

func rand_byte_array(len int) []byte {
    rand.Seed(time.Now().Unix())
    b := make([]byte, len)
    for x := 0; x<len; x+=1 {
        b[x] = byte(rand.Intn(2))
    }
    return b
}

func main() {

    ca := CellularAutomata{}

    // Wolframs Rule 30
    p := []byte{0, 1, 1, 1, 1, 0, 0, 0}
    ca.rule = p

    // Starting state
    q := []byte{1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0}
    ca.state = q

    fmt.Fprintf(os.Stdout, "target: %v\n", rand_byte_array(1000))

    for x := 0; x<30; x+=1 {
        fmt.Fprintf(os.Stdout, "current state: %v\n", ca.state)
        ca.Step(true)
    }

    /*
    m := make(map[byte]time.Duration)
    for x := 0; x<100000; x+=10000 { m[x] = do(ca, x) }
    */

    //x, y := find(ca, q)
    //fmt.Fprintf(os.Stdout, "%v %v\n", x, y)

    //fmt.Fprintf(os.Stdout, "%v\n", m)
}