Thursday, July 10, 2014

I've Learned To Make Movies Of My Cellular Automata!

We met langton's ant some time ago, here is a movie I made of it.  Takes 7minutes.  Not sure how to speed up the movie yet.

video

here is my code:

#this is a generator function for yielding an NxN cellspace for langton's ant
#for gens number of generations
#grp2 and display are my own imaging library, it's a bit dopey, it doesn't take part in the
#creation of the movie file
 def langton(gens,N,px, delay, fill=lambda x,y : None ):
    """langton(gens,N,px,delay,fill) --
         do langton's ant in an NxN field
         withh pix size px and delay between steps
         fill is an optional function of cellspace and
         N which can fill cellspace with an initial
         pattern"""
    canv=grph2.Grph(N,N,px,'langton')
    #make a label box for gen 
    canv.gens=grph2.k.Label(canv.win)
    canv.gens.pack()
    dirs=((0,-1), (1,0), (0,1), (-1,0))
    gen,antx,anty,ant_dir=0,N//2, N//2, 0
    cellspace=[[0]*N for i in range(N)]
    fill(cellspace,N)
    display(cellspace, canv, N)
    canv.upd()
    for ii in xrange(gens):
        if cellspace[antx][anty]:
            cellspace[antx][anty]=0
            canv.unplot(antx,anty)
            ant_dir=(ant_dir-1)%4
        else:
            cellspace[antx][anty]=1
            canv.plot(antx,anty)
            ant_dir=(ant_dir+1)%4
      antx+=dirs[ant_dir][0]
      anty+=dirs[ant_dir][1]
      #put gen in label
      canv.gens.config(text=str(gen))
      canv.upd()
      gen+=1
      for i in xrange(delay): pass
      yield cellspace




#this creates a python imaging library image from a list of coordinates that
#should be painted as black squares of pxXpx number of pixels each

import Image

def ctimgf(coords,px,N,M,bkgr=(255,255,255),
                            pts=(0,0,0)):
  """ctigf(coords, fname, px, N, M, bkgr=(255,255,255),
                                    pts=(0,0,0) --
       return  an (N*px) X (M*px) image file for the coords"""
  im=Image.new('RGB',(N*px,M*px),bkgr)
  pix=im.load()
  for x,y in coords:
     for i in xrange(px):
        for j in xrange(px):
           pix[x*px+i,y*px+j]=pts
  return im


this calls my langtons ant program for gens number of generations and produces an image file for each generation

def langfmov(gens,sz,px,delay):
    """langfmov(gens,sz,px,delay,dur) -- display langton ant
         for gens gens and write a file for each gen in format
         lang00001.jpg etc.. """
   #create indesx i and cellspace cs for each generation of langton's ant
    for i, cs in enumerate(langton(gens,sz,px,delay)):
        #create a list of coordiates for each 'on' cell in the ant's pattern 
        lp=[(x,y) for x,yl in enumerate(cs)  #x is the row coordinate and yl is the row
                           for y,val in enumerate(yl) if val==1]  #y is the collumn coordinate
        #save an image file of those on and off coordinates
        ctimgf(lp,px,sz+1,sz+1).save("lang%05d.jpg" % i)



#my god that code is terse!  i let python get me carried away!  and i got x,y revered i think

#i call it:
langfmov(11000, 65, 4, 0)

#only took my computer a minute to produce 11,000 5kb jpgs

#the final command to make the movie i give in  linux:
avconv -f image2 -i lang%05d.jpg lang10000.avi

#('m not sure what the -f image2 command does!)
#only takes about 19seconds to create a 10mb movie!!!

Thursday, July 3, 2014

More Pretty Math Patterns: Spiral Fibonaci Strings

You may have heard of the Fibonacci numbers:
f0=0, f1=1 and fn=f(n-1) + f(n-2), so that the numbers are:

0,1,1,2,3,5,8....   (you add the last two numbers to get the next.  the next one will be 13)

There are tons of fun facts about these critters.

Today I saw something similar - Fibonacci strings:
f0='0', f1='1' and fn = f(n-1) concatenated with f(n-2), so the strings are:

'0', '1', '10', '101', '10110', '10110101',  ,...

(you tack the second to last string at the end of the last string to get the next.  the next one is '1011010110110'.   This can be extended as long as we like.

When i saw this I immediately decided I wanted to plot it in a spiral, don't ask me why...

So the spiral would start from a '1' at the center, then a '0' to the right and then up and counterclockwise:
011
110
01...

here is a plot for the Fibonacci string large enough to fill an 11x11 plot (I filled in the ones and zeros in the center where it starts)
That's weird... doesn't seem to be any pattern.  I didn't really expect one either!  lets try a bigger plot with more of the string:











Well, that's curious, more:

Seems to be two kinds of regions..
Now we see some kind of pattern
It's a metaspiral on the spiral, very weird.  Does it continue?

Apparently it does.  I have no clue why this happens, it will bear some careful observation and thinking!  The length of the Fibonacci string grows exponentially, the length of one trip around the spiral grows...

1
8=1+1+1+1+4
3+3+3+3+4=16
5+5+5+5+4=24

so it grows by 8 each time.  That's linear.  I don't see why they match up in such a curious fashion!

UPDATE:
i drew some lines and did some counting:

here is a smaller region:

Look at the metaspirals bands on the right.  focus on the ones made up of mostly horizontal rows of dots.  I will find out how far apart they are.  notice in some places the horizontal row of dots is only two long.  i will count how many spiral lines between these.

there are 18.  this is consistent in the bigger pic too.

now each spiral grows by 8 squares as it comes around.  so the first spiral of any metaspiral band is 8*18 squares longer than the first spiral of the previous band.  8*18=144 which is the 12th fibonacci number.

THIS is a CLUE.  though i'm still clueless about what is going on!

For those of you curious about my computer code, here it is in python:

 

#first create the Fibonacci string:
fs=['0','1']
while len(fs[-1]) < 1000000:
   fs.append(fs[-1]+fs[-2])
fs=fs[-1]  #choose the last string produced

#now create an image of the spiral with this string:
def make_fib_sp(N, px, fname, fibstr):
   """make_fib_sp(N, px, fname, fibstr) -- create an image file fname
       (give it an extension like .jpg or .png...)
       of a pattern of pixels based on starting from the
       center of the image and working one pixel around in a
       spiral based on the mapping with the fibonacci string fibstr:
       f0='0',f1='1', fn+1=fn concat fn-1
       look at a fibonacci string long enough to fill an NxN square
       and around the spiral draw black if 1 and white if 0
       uses Image library and spriral
       px is the number of pixels in the image to make each square"""
   from PIL import Image  #python image library
   bkgr=(255,255,255); pts=(0,0,0)  #background is white, pts are black
   img=Image.new('RGB',(N*px,N*px),bkgr) #create an Image object
   pix=img.load()  # this is for fast construction of image
   idx=0
   ctr=N//2
   #I iterate over the coordinates given by my spiral generator
   for x,y in mf.spiral(ctr, ctr, lambda x,y,xs,ys:
                                                          abs(x-xs)>=ctr-1):
      #because spiral stops sloppily...
      if x<0 or="" x="">=N or y<0 or="" y="">=N:
         break
      if fibstr[idx]=='1': #draw a black pixel
         xp=x*px; yp=y*px
         for i in xrange(px):  #fill the square in as px X px pixels
            for j in xrange(px):
               pix[xp+i,yp+j]=pts
      idx+=1
   img.save(fname) 


def spiral(x,y,exit_fun):
   """spiral(x,y, exit_fun) -
       lazily return coordinates in a spiral path starting
       from (x,y) then to (x+1,y), (x+1,y-1) etc...
       counterclockwise until exit_fun(x,y,xs,ys) is true
       xs,ys are the initial center coords
       NOTE tests exit function only ONCE around the
       spiral so exit_fun should use < or > rather than ==
       as an exact value in each round might be missed.
       since the spiral goes around with smaller and bigger
       values, it's best to use some version of
       abs(x-xs) for exit_fun getting it to stop where you
       want is subtle"""
   incs=2
   xs,ys=x,y
   if not exit_fun(x,y,xs,ys):
      yield x,y
   while not exit_fun(x,y,xs,ys):
      x+=1; yield x,y
      for i in range(incs-1):
         y-=1; yield x,y
      for i in range(incs):
         x-=1; yield x,y
      for i in range(incs):
         y+=1; yield x,y
      for i in range(incs):
         x+=1; yield x,y
      incs+=2