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

Tuesday, April 8, 2014

rough notes on finding near misses to cycles in juggler sequence

this is about feeding a number back into a function over and over again, and seeing what kind of patterns we get.

see the entry for the collatz conjecture in the complexity lab manual, it is a similar game

def jug(n) = {int(sqrt(n^3))  if n is odd else  int(sqrt(n))}

int(r) is the greatest integer less than r, i.e. int(4.773)=4

so that jug(2)=2, and jug(2)=1 and jug(1)=1 and we stop there.  that's a fixed point.

jug(3)=int(sqrt(27))=5, and jug(5)=11, etc..

the sequence of numbers we get is called the orbit of the first number under the dynamical system for our function jug(x)

here are the orbits for the first 9 integers
[1]
[2, 1]
[3, 5, 11, 36, 6, 2, 1]
[4, 2, 1]
[5, 11, 36, 6, 2, 1]
[6, 2, 1]
[7, 18, 4, 2, 1]
[8, 2, 1]
[9, 27, 140, 11, 36, 6, 2, 1]
>>>

here is orbit for 37:

 [37, 225, 3375, 196069, 86818724, 9317, 899319, 852846071, 24906114455136, 4990602, 2233, 105519, 34276462, 5854, 76, 8, 2, 1]

it seems that no matter what n we start off with we reach 1 (i think this has been tested up to a million)

no one knows how to prove that this is so.  There are many systems like this and they puzzle us.
wiki on the juggler sequence

the question is: are there numbers for which the orbit reaches a fixed point?  or are there numbers for which the orbit cycles?  for instance, look at the orbit for 3:
[3, 5, 11, 36, 6, 2, 1]
if the square root of 36 had happened to be 5 this orbit would have been:
3, 5, 11, 36, 5, 11, 36, 5...

and 5,11,36 would be a cycle.  no one has found any cycles yet, but lets look for almost cycles like 3, 5, 11, 36, 6... 6 is CLOSE to 5.


so,

i generate an orbit under this dynamical system.  [(x0,0), (x1,1)....(xn,n)]
then i sort this by x, so that xi that are near each other in size are near each other in the sequence

then i create a sequence of the differences between consecutive xi's  and sort that.  here is what i get for 37:

(diff, (xi, i), (xj, j))
(1L, (1L, 17), (2L, 16))
(6L, (2L, 16), (8L, 15))
(9L, (8L, 15), (17, 18))
(20, (17, 18), (37, 0))
(39L, (37, 0), (76L, 14))
(149L, (76L, 14), (225, 1))
(1142L, (2233L, 10), (3375, 2))
(2008L, (225, 1), (2233L, 10))
(2479L, (3375, 2), (5854L, 13))
(3463L, (5854L, 13), (9317, 5))
(90550L, (105519L, 11), (196069, 3))
(96202L, (9317, 5), (105519L, 11))
(703250, (196069, 3), (899319, 6))
(4091283L, (899319, 6), (4990602L, 9))
(29285860L, (4990602L, 9), (34276462L, 12))
(52542262L, (34276462L, 12), (86818724, 4))
(766027347, (86818724, 4), (852846071, 7))
(24905261609065L, (852846071, 7), (24906114455136L, 8))


now if i want to search for orbits with near misses... what do i search for?  obviously the first few entries do not count

the 4th and 5th entries are close to what i'm looking for.  how do i write an algorithm to pick them out?  the diff must be small but the indexes must be far apart.

the 3rd entry has indices 3 apart but i'm not going to count that as a good candidate!

hmm... a programming puzzle!

this post is continued in the comments...

Sunday, April 6, 2014

If I Were Able To Focus I'd Describe This Complexity Lab Manual

The Complexity Lab Manual

What is the complexity lab manual?  It is hard to explain in a few words. It is the science and craft that we've discovered in the last 150 years that begin to bridge the gap between machines and  life, that most people never even get a glimpse of in grade school or college.  it is about discovies and techniques that are so surprisingly different than our thousand years old ways of thought and language.  but the world today is so complex, moving so fast, has become so overpopulated by people who have at their disposal immense powers to transform the earth that it is the duty of everyone to learn these new skills of how to see the world, understand it, and build with it in a sane way.

You will construct machines made of a billion parts all interacting with each other in complicated ways.   you will learn what molecules are and how a trillion of them can make fluid subtle bodies.  you will learn how light, streaming from the hot sun to the cold dark voids of outerspace, sets into motion the weather, makes our hearts beat, our muscles move, our very thoughts themselves to flow.  let's begin.

>>>MELD THESE PARAGRAPHS TOGETHER, ENDING WITH MENTIONING THE POTTER'S CLAY
most people would say that we are not machines, that love is not just a chemical reaction. throughout history most cultures have thought that our very being, our minds, our souls are separate from our bodies of flesh and bone, even that they are immortal and immune from death and decay.  that an eternal supermind and supercraftsman, God, alien to earth, death and decay, outside of the very physical universe,  created bodies out of dumb clay and breathed a little bit of himself into these clay pots to make us alive and and able to feel.


over the past few thousands of years, from the time of the cavemen, the time of the hebrew prophets and the ancient greek philosophers, human culture has built up this notion of an uncrossible divide.  On the one side we put: animated life and human thought and feeling and on the other side mud and machinery.
Most of us would think that there is an unbridgeable gap between the mechanical and the living, between  inanimate rocks chemicals and machines on the one side and  on the other side; living, fluid, subtle, creative, beautifull, beings like trees and animals and people; dancers, artists, writers, you and i who can think and feel.
>>>

complexity lab is about that clay, and what it can do without a supermind creator from the outside.  I know, these are bold thoughts, even heretical thoughts.  but the fact is that we are watching what this clay can do in our microscopes, in our laboratories, in our computers and soon in our nanotechnology factories.  We will learn that life is not made of featureless smooth gobs of stuff like the clay that the potter uses, but that life is made, not from the outside by a potter, but from the inside by a seething swarm of microscopic factories, all interacting with each other a trillion times a second.

But in this modern age most of us do have a vague notion that our bodies have something to do with chemistry, that scientists are saying that we are simply complicated machines or bags of molecules, that our human love and morality are simply chemical reactions.  But what could they mean by this?  How could chemistry or machinery do what you and i can, or even fly like a honeybee who can find flowers, build beehives..?  How can complicated machines be anything like people?  how could complex swarms of molecules, atoms, make life?  Scientists say that 99% of a tree with its finely grained wood, veined leaves, and flowers is made simply of air and water.   just how complicated are these supposed machines, and molecular interactions anyway?

It is the goal of this complexity lab manual to guide you through a series of experiments, projects, diagrams, and stories, to help you get a gut intuition of the kinds of machinery that modern science has discovered and what they are capable of.  To show you that these machines are gazillions of times more subtle, fluid, and creative than cars and robots and computers, and factories.  You will even learn to build some of these machines yourself.  We are learning to build machines that are approaching the suppleness, beauty and creativity of life.

 But our new discoveries of how lifelike machines and chemistry can be is only a hundred and fifty years old,  a mere blink of the eye in the span of human history.  And the schools are not teaching this new view of the world.

In this complexity lab, we will see that our flesh is a swarm of so many more parts than in an automobile or even in a computer.  you will see that their mechanisms of interactions are so much more  fluid and subtle than the machine parts that we are familiar with.

How do the parts of these new machines interact? Most human notions of creativity and government are that a central mind or hierarchy controlling all the parts of the body.  And in the same manner we have tried to build governments on these same models of centralized control.  Even a democracy is based on notions of hierarchical organization.  10,000 people elect one councilperson and 10 counsilpersons work with one mayor, and a million people elect an elector and 100 electors elect one president, and then in daily practice these few people deal with the lives of the many.  This is a clunky system, and not very responsive to the complex times we live in.  In fact, throughout history,  these governments have mostly been ugly and inhumane, and they rarely last more than a few centuries. They exhibit none of the stability and beauty of forests and coral reefs that last for 1000s of years  and are so refreshingly peaceful and beautiful that we flock to them for a break from our clunky ratrace cities. 

the traditional notion of craftsmanship, of building a machine or of creating a work of art, is of a single mind crafting a machine or painting from the outside, or crafting a machine by building a huge factory outside of it which can only touch the parts with a few hands or tools at a time.  We could not imagine how to craft a working kidney with its millions of densly packed, carefully interlocked tubes all in a space of a few inches.

We've yet to figure out how to build a government that can govern a million people in a humane and stable way.  and only recently are we learning how to build a real kidney, or eye.

In the complexity lab we will learn a new form of craftsmanship.  We will learn what happens when large numbers of simple parts interact with each other, instead of being controlled by a central mechanism. We will see that when  those interactions include both stabiliziing and disruptive elements, creativity results.  we will learn that when we build a machine of 10 parts, then 100 parts, then a 1000 parts... that at each stage totally new capabilities appear, they don't just become 10 times faster or smarter, but capabilities that we could never predict appear at each stage. And not just a thousand parts (maybe a car has a thousand parts if we count all the nuts and bolts) We will learn about machines with trillions of parts.

One of the main tasks and most difficult tasks of this complexity lab is to teach you how to think about very large numbers, to feel them in your gut.  you will even learn how to comprehend how big a trillion is!  You will start with understanding 2, then you will understand 3, then you will understand 10 and then 100 and thousand and so on.

In the past, in simpler times, in slower times, in times when there were only hundreds of people scattered across rural landscapes,  when there were only a few scattered cities with more than ten thousand people in them, and only a few cities interacted with each other at a time, there was no need for most of us to think about numbers. numbers weren't important.  But now, that there are six BILLION of us crowding the planet.  (most people don't even know the difference between 10,000 people in a city, 300 million people in the united states, or 6 billion people in the world) when dozens of cities with over 10million people in them span the earth in a tightly interacting global network of commerce and warfare that responds to random events in a split second, when the global economy can calapse in a day, it is our duty to learn to think about numbers.  to think about billions, to think about what happens when networks of billions of people make thousands of decisions every second of the hour, every hour of the day, every day of the year.  we've got to learn how big that number is. and we've got to learn what that number of parts can do.

yes, in the past machines were only made out of a few dozens of clunky metal parts.  but in the past two generations, we've learned to make computers out of nimble switches, switches that communicate with each other.  We've learned to connect thousands of these switches together and have them flipping on and off thousands of times each second.  not the clicking and  clacking of clunky metal parts, the movement is of microscopic bundles of static electricity.  but this was only the start.  An astounding thing happened: every year or so we learned how to weave together ten times as many switches into the same chip the size of a finger nail.  every year or so we learned to make them them make their tiny decisions ten times faster.

we can now connect together billions of switches, all changing each other a billion times a second.  these are the computers we use today.  computers that can animate movies with swarms of 1000s of lifelike people.  programs that can coordinate 100s of activities on our computer desktops.  computer chips in Aibo dogs that can get together and play a passable game of soccer.

And then there is the newest technologies: genetic engineering and nanotechnology.  we ARE learning to build with life and chemistry from the very molecules on up.  It's coming.  It's time that every highschool kid embarking on adulthood in this complicated fast moving world, learns this new worldview.

Old Intro With Links To Labs

Saturday, December 28, 2013

Is It Strange That Langton's Ant Produces Asymetrical Pattern?

So Langton's ant is a two dimensional Turing machine of utter simplicity.

It starts out on an infinite square grid.  Each square starts off white and can be either white or black.   The ant starts on one square facing south and repeats this simple rule:

If on a blank square turn 90degrees clockwise otherwise turn 90degrees counterclockwise, then flip the color of the square from white to black or black to white, then move forward one square.

What it does is quite surprising, taking a long time to create a complex pattern:

http://www.youtube.com/watch?v=1X-gtr4pEBU

It wanders around higgledy piggledy for  9978 steps and then executes a repeating pattern of length 104 which shifts over diagonally each time to produce an endless highway.

We can certainly build a simple mechanical device to do this.  I bet we can even build a protein to do it on a regular face of a crystal, or we can maybe even find a medium sized molecule out there that already does this?

At any rate at first i thought it was odd that this seemingly symmetrical rule produces such an asymmetrical pattern.  But then i realized that the initial conditions are not symmetrical!  They start off all white.

So I decided to try the ant on some different initial conditions.  If i start it on a grid that is alternating black and white stripes or checkerboard pattern of black and white (which i suppose we could think of as more symmetrical initial conditions) the ant surprises me.  It simply executes a boring straight line!  horizontal for horizontal stripes and diagonal for checkerboard.  HUH






The other patterns are for other initial conditions.  if i start the ant with initial random black and white squares of equal probability it wanders aimlessly faster than on all white and hits the wall rather quickly (at this point my program halts).  If I start the ant with a space scattered sparsely with random black squares it tries to do the usual ant thing but keeps getting side tracked!

This is interesting.  So the endless highway is not stable to perturbation.  It seems it will eventually form from any initial state of a small area of randomness but any non white region larger than that small initial area can perturb it.  and of course my stripe, checkerboard and total randomness initial conditions totally negate it.

I think my next step is to watch this ant on toroidal surfaces of various numbers of squares.


Thursday, October 17, 2013

Phase Transition In Asynchronous Conway Life

So here I am messing around with conway's Game Of Life again.





Overview of Game Of Life

This exploration is inspired by the following paper:
"Asynchronism Induces Second Order Phase Transitions in Elementary Cellular Automata" by   Nazim A. Fat├Ęs, Journal of Cellular Automata (2008)

http://hal.inria.fr/inria-00138051


So what is happening here?  Well as we saw in the description of conway life above, what we do is start out with a pattern on a grid.  Then for each cell in the grid we think of what the next generation of that cell will be depending on what its immediate neighbors are.  We do this for the whole grid before replacing all the cells with their next generation computations.  This is called synchronous, since we compute all the cells at once each time.

But real life isn't much like this! In chemistry, or biology, particles interact higgledy piggledy, real cells often react to each other at random times.  So what if we rewrite our Conway Life simulator so that we only recompute a differewnt random bunch cells each time?  This is What Fates did.  In each generation he picked say, 10% of the cells at random and recomputed them.  He got something that looked nothing like conway life.  after all, think out computing a blinker.  If you just compute one of the end cells, without computing the other end and the two side cells, all at once, you won't make it blink, you will just kill the end cell, leaving just two live cells left. this will eventually die.  No blinker.  The patterns in Conway Life depend on every part of the pattern being carefully calculated at once.

So we realize, lets just compute a FEW cells out of synchony and see what happens.  Most of the patterns grow like conway patterns and just some few spots of chaos ensue.  What if we keep executing runs of Conway Life with the percentage of cells that we compute synchronously to be less and less than 100%?  more and more chaos should happen, right?


So: On the right hand side of the images are the usual runs of conway life from a random scattering of half cells on and half off, after a certain number of generations it settles down to the usual low density (about 0.01 live cells) scattering of beeloaves and blinkers and such.  For this particular experiment we actually run it on a torus, that is.. if a glider flies off the right hand side, it reappears on the left, and if it flies off the top, it reappears on the bottom.  the space is actually the surface of a donut!  (you may ask where the hole is...  I'm gonna have to explain that won't i?)
Anyway, as we go towards the left, the % of cells we calculate synchronously drops slowly and more chaos happens.  some curious things though:

Because there is more chaos, and the usual still lives and blinkers can't stabilize, things stay in flux a lot longer than usual and the density of cells that are changing begins to rise as the % asynchronous drops.  At 95% synchronous things usually settle quickl By 90% synchronous things take a long time to settle if at all, and the density begins to rise and things don't look quite conway lifey.  By the time %synchronous drops to about .4 another curious thing happens: the density settles at about .4 to .45 and doesn't rise any higher.  Also the pattern becomes a stable dynamic labyrinth shape you see on the left most pictures.

So we get two kinds of transitions, one from stable mostly motionless sparse conway life to nonstable fluid patterns around 90% synchrony and then by around 40% synchrony we get a stable fluid labyrinth state of density .4.  Fates reports slightly different results but we may be using different algorithms.

Also, Fate reports what he claims is a phase transition rather sharply at around 90%, which is very curious.  Phase transitions are of course wha makes the universe interesting.  A similar thing happens to water as you raise the temperature continuously, you go suddenly from solid ice to fluid water and then suddenly again to expandable steam.

I have more to do on this topic!!!


For those of you who want to see my code, here it is in python.  I use sets of live and neighboring coordinate pairs instead of calculating the whole NxN matrix.  (this optimization is good for sparse conway life but not so much for asynchronous labyrinth pattern!)

grph2 is a silly plotting package i wrote.  you just need something that opens up a canvas and plots points in x,y.
 import grph2
import random as r

def async_conway(N,M,pat,gens,px,alpha,delay):
  """async_conway(pat,lim,px,tx,ty,alpha) --
     run async conway on pat,up to lim gens, tx,ty is torus dims
     alpha is percent of cells to update each gen
     compile averate density =len(live_cells)/tx*ty and
     activity which is numcells to change in a gen/tx*ty"""
  canv=grph2.Grph(tx,ty,px,'conway torus '+str(tx)+'X'+str(ty)+
                            'alpha= '+str(alpha))
  tot=N*M
  live_cells=center(pat,N)
  canv.gens=grph2.k.Label(canv.win)
  canv.gens.pack()
  canv.density=grph2.k.Label(canv.win)
  canv.density.pack()
  canv.activity=grph2.k.Label(canv.win)
  canv.activity.pack()
  adjacent_empties=calc_adjacent_empties(live_cells,tor=True,N,M)
  display(live_cells,canv)
  pop=len(live_cells); active=0
  for n in xrange(gens):
    for m in xrange(delay): pass
    canv.gens.config(text=str(n))
    canv.density.config(text=str(float(pop)/tot))
    canv.activity.config(text=str(float(active)/tot))
    pop,active=async_conway_gen(live_cells, adjacent_empties, canv,
                                tx,ty,alpha,pop,active)


def async_conway_gen(live_cells, adjacent_empties, canv, tx,ty,alpha,
                     pop, active):
  """update the conway world one generation
     alpha is the percent of cells at random to update syncronously
     update pop =len(live), active=numcells chg"""
  die=[]; born=[]; erase=[]
  for cell in live_cells:
    if r.random()      if not conway_calc(live_cells,tor,tx,ty, *cell) & 2:
        #so num nbs is 0,1,4 or more
        die.append(cell); canv.unput(*cell);
        pop-=1; active+=1
  for cell in adjacent_empties:
    if r.random()      c=conway_calc(live_cells, tor,tx,ty,*cell)
      if c==3:
        born.append(cell); canv.put(*cell);
        pop+=1; active+=1
      elif c==0:
        #the cell is no longer adjacent to a live cell
        #take it out of the adjacent_empties set
        erase.append(cell)
        #THIS IS A LITTLE FUNNY ASYNC. WE MIGHT WANT TO UPDATE ***ALL***
        #THE EMPTIES.  THINK IT OUT.
  canv.upd()
  adjacent_empties-=set(erase)
  live_cells.update(born)
  adjacent_empties-=set(born)
  for cell in born:
    adjacent_empties.update(set(nbs(tor,tx,ty, *cell))-live_cells)
  adjacent_empties.update(die)
  live_cells-=set(die)
  return pop,activity



def nbs(tor,tx,ty, x,y):
  """nbs(tor,tx,ty,x,y) --  lazily return one neighbor at a time
     if tor=True then calculate mod tx, ty
     can be extended to cylinder or klein bottl"""
  if tor:
    yield((x-1)%ty,(y-1)%ty); yield(x,(y-1)%ty);
    yield((x+1)%tx,(y-1)%ty)
    yield((x-1)%ty,y); yield((x+1)%tx,y)
    yield((x-1)%ty,(y+1)%ty); yield(x,(y+1)%ty)
    yield((x+1)%tx,(y+1)%ty)
  else: 
    yield(x-1,y-1); yield(x,y-1); yield(x+1,y-1)
    yield(x-1,y); yield(x+1,y)
    yield(x-1,y+1); yield(x,y+1); yield(x+1,y+1)


def conway_calc(live_cells,tor,tx,ty,x,y):
  """add up the number of neighbors of (x,y) that are live
     stop when you get to 4 cause 5,6,7,8 is the same"""
  sm=0
  for nb in nbs(tor,tx,ty, x,y):
    sm+=nb in live_cells
    if sm==4:
      break
  return sm



def calc_adjacent_empties(cells,tor,tx,ty):
  adjacent_empties=set([])
  for cell in cells:
    adjacent_empties.update(set(nbs(tor,tx,ty, *cell))-cells)
  return adjacent_empties

def display(live_cells,canv):
  for cell in live_cells:
    canv.plot(*cell)



def center(pat,N,M=None):
  if M==None: M=N
  cx=N//2; cy=M//2
  xmin, xmax, ymin, ymax=lims(pat)
  xmid=(xmax+xmin)//2
  ymid=(ymax+ymin)//2
  return set([(x-xmid+cx,y-ymid+cy) for x,y in pat])


def lims(pat):
  """return xmin,xmax,ymin,ymax of points in pat"""
  xmax=xmin=pat[0][0]
  ymax=ymin=pat[0][1]
  for x,y in pat[1:]:
    xmax=max(xmax,x); xmin=min(xmin,x)
    ymax=max(ymax,y); ymin=min(ymin,y)
  return xmin, xmax, ymin, ymax


Tuesday, April 23, 2013