bgneal@42: """Chapter 6, exercise 2 in Allen Downey's Think Complexity book.
bgneal@42: 
bgneal@42: 4. Implement a Rule 30 CA on a ring with a few hundred cells, run it for as many
bgneal@42:    time steps as you can in a reasonable amount of time, and output the center
bgneal@42:    column as a sequence of bits. Test it using DieHarder.
bgneal@42: 
bgneal@42: We'll take a slightly different tact. We will create a program that will
bgneal@42: continually output the center column as a bit stream. Once we reach the end of
bgneal@42: the time steps, we'll copy the last row to row 0 and start again. This way we
bgneal@42: can feed the data into dieharder over a pipe without it exhausting our stream.
bgneal@42: 
bgneal@42: """
bgneal@42: import sys
bgneal@42: 
bgneal@42: from CircularCA import CircularCA
bgneal@42: 
bgneal@42: 
bgneal@42: def main(script, bytes_wanted):
bgneal@42: 
bgneal@42:     bytes_wanted = int(bytes_wanted)
bgneal@42: 
bgneal@42:     # Create a circular CA that is 257 columns; it is odd so that we have a true
bgneal@42:     # "center" column. Our CA will have 8192 steps. This will give us 8192
bgneal@42:     # / 8 == 1024 bytes of pseudo-random (we hope) data using rule 30. Once
bgneal@42:     # we've reached the end of the time steps, we'll copy the last row to the
bgneal@42:     # first and start over.
bgneal@42: 
bgneal@42:     rows = 8193
bgneal@42:     cols = 257
bgneal@42:     mid = cols // 2
bgneal@42:     ca = CircularCA(30, rows, cols)
bgneal@42:     ca.start_single()
bgneal@42: 
bgneal@42:     iters = 0
bgneal@42:     bytes_produced = 0
bgneal@42:     while True:
bgneal@42:         ca.loop(rows - 1)
bgneal@42: 
bgneal@42:         iters += 1
bgneal@42:         if iters == 1:
bgneal@42:             # don't use the first iteration as the first few rows will have 0's
bgneal@42:             # until it fills up
bgneal@42:             ca.wrap()
bgneal@42:             continue
bgneal@42: 
bgneal@42:         a = ca.get_array(mid, mid + 1)
bgneal@42: 
bgneal@42:         # output the bit stream a byte at a time
bgneal@42:         x = 0
bgneal@42:         i = 0
bgneal@42:         for n, item in enumerate(a):
bgneal@42:             # don't use the first bit because it is a repeat from the previous
bgneal@42:             # iteration
bgneal@42:             if n == 0:
bgneal@42:                 continue
bgneal@42: 
bgneal@42:             x <<= 1
bgneal@42:             x |= item[0]
bgneal@42:             i += 1
bgneal@42:             if i == 8:
bgneal@42:                 sys.stdout.write(chr(x))
bgneal@42:                 x = 0
bgneal@42:                 i = 0
bgneal@42:                 bytes_produced += 1
bgneal@42:                 if bytes_produced >= bytes_wanted:
bgneal@42:                     return  # we're done
bgneal@42: 
bgneal@42:         # now start the CA over:
bgneal@42:         ca.wrap()
bgneal@42: 
bgneal@42: 
bgneal@42: if __name__ == '__main__':
bgneal@42:     main(*sys.argv)