Log in

No account? Create an account


leaky life

« previous entry | next entry »
5th Mar 2008 | 21:11

The past light cones of the cells on the unbounded edges of the pattern have a nasty effect. As you go further into the future, even though you only display a small quadrant near the origin, more and more empty space in the past must be examined to work out the state of the cells in the present. This space leak causes the calculation of each generation to get more expensive as the square of the generation number, even though it would ideally be constant.

To fix this, the size of the original universe must be restricted, instead of restricting its size just for display. Divide the display function into two:

  restrict (x,y) = map (take x) . take y
  display = unlines . map (concatMap show)

We also need to change the grow function to deal with the other two edges of the universe.

  bracket a xs = [a] ++ xs ++ [a]
  grow = (bracket deadline) . map (bracket deadcell)

Then in the loop we remove the dimension argument to display and change the main program to:

  main = loop $ restrict (10,10) glider

This is enough to make it possible to compute the 1103 interesting generations of the R pentomino at a few generations per second (text output being rather slow).

| Leave a comment | Share

Comments {0}