bgneal@43: """Chapter 6, exercise 3 in Allen Downey's Think Complexity book.
bgneal@43: 
bgneal@43: This exercise asks you to experiment with Rule 110 and see how many spaceships you can find.
bgneal@43: 
bgneal@43: 1. Modify your program from the previous exercises so it starts with an initial
bgneal@43:    condition that yields the stable background pattern.
bgneal@43: 
bgneal@43: 2. Modify the initial condition by adding different patterns in the center of
bgneal@43:    the row and see which ones yield spaceships. You might want to enumerate all
bgneal@43:    possible patterns of n bits, for some reasonable value of n. For each
bgneal@43:    spaceship, can you find the period and rate of translation? What is the
bgneal@43:    biggest spaceship you can find?
bgneal@43: 
bgneal@43: """
bgneal@43: import os.path
bgneal@43: import cPickle
bgneal@43: 
bgneal@43: from CircularCA import CircularCA
bgneal@43: from CADrawer import PyplotDrawer
bgneal@43: 
bgneal@43: FILENAME = 'rule110.pkl'
bgneal@43: RULE = 110
bgneal@43: 
bgneal@43: def find_ic(show=False):
bgneal@43:     """This function sets up a rule 110 CA with a random initial condition and
bgneal@43:     runs it for 600 time steps. The last row is the initial condition (IC) we
bgneal@43:     are interested in for producing future CA to investigate rule 110 and
bgneal@43:     spaceships.
bgneal@43: 
bgneal@43:     We use 600 steps because of figure 6.6 in Think Complexity.
bgneal@43: 
bgneal@43:     The CA is run through 600 steps and then the last row is pickled in a file
bgneal@43:     for future use.
bgneal@43: 
bgneal@43:     """
bgneal@43:     ca = CircularCA(RULE, 600, 600)
bgneal@43:     ca.start_random()
bgneal@43:     ca.loop(599)
bgneal@43: 
bgneal@43:     if show:
bgneal@43:         drawer = PyplotDrawer()
bgneal@43:         drawer.draw(ca)
bgneal@43:         drawer.show()
bgneal@43: 
bgneal@43:     # get the last row of the CA and pickle it to a file so we can use it in the
bgneal@43:     # future:
bgneal@43: 
bgneal@43:     last_row = ca.array[599, :]
bgneal@43:     with open(FILENAME, 'wb') as fp:
bgneal@43:         cPickle.dump(last_row, fp, protocol=2)
bgneal@43: 
bgneal@43:     print "last row pickled in {}".format(FILENAME)
bgneal@43: 
bgneal@43: 
bgneal@43: def rule110(script, n):
bgneal@43:     """Open the IC pickle file and initialize a CA with it.
bgneal@43:     Modify the 32 center columns with the bit pattern given by n, which should
bgneal@43:     be a hexidecimal number.
bgneal@43:     Then step the CA and display it.
bgneal@43: 
bgneal@43:     """
bgneal@43:     print 'loading {}...'.format(FILENAME)
bgneal@43:     with open(FILENAME, 'rb') as fp:
bgneal@43:         ic = cPickle.load(fp)
bgneal@43: 
bgneal@43:     print 'creating CA...'
bgneal@43:     ca = CircularCA(RULE, 600, 600)
bgneal@43:     ca.start_row(ic)
bgneal@43: 
bgneal@43:     n = int(n, 16)
bgneal@43:     print 'modifying center of row with {:x}'.format(n)
bgneal@43:     a = ca.array
bgneal@43:     mask = 1 << 31
bgneal@43:     j = 600 / 2 - 16 + 1    # +1 because of the ghost column on the left
bgneal@43:     for i in xrange(32):
bgneal@43:         a[0, j] = 1 if n & mask else 0
bgneal@43:         j += 1
bgneal@43:         mask >>= 1
bgneal@43: 
bgneal@43:     print 'stepping CA...'
bgneal@43:     ca.loop(599)
bgneal@43: 
bgneal@43:     drawer = PyplotDrawer()
bgneal@43:     drawer.draw(ca)
bgneal@43:     drawer.show()
bgneal@43: 
bgneal@43: 
bgneal@43: if __name__ == '__main__':
bgneal@43:     import sys
bgneal@43: 
bgneal@43:     if not os.path.exists(FILENAME):
bgneal@43:         find_ic()
bgneal@43: 
bgneal@43:     rule110(*sys.argv)