Python Questions

gmc_nxtman · Post by **gmc_nxtman** » July 5th, 2015, 11:19 am

HashLife is designed to recognize repetition in patterns' structure and history, and take advantage of it.

QuickLife, I'm not really sure about. It seems to have something to do with the size of the universe, due to the fact that running a universe with a blinker and a glider 8,000 cells away is sufficiently laggier than doing it closer, regardless of how small the population is.

Freywa · Post by **Freywa** » July 5th, 2015, 11:42 am

The Turtle wrote:Also, how exactly does QuickLife and HashLife work? Why are they extremely fast? Is it the programming language or something else?

Ah, that brings me to the topic of hashing/memoisation where sub-patterns get stored for later recall without needing further computation of their evolutions.

QuickLife is a standard, run-of-the-mill totalistic CA algorithm with a few trivial optimisations. As mentioned in the documentation of Golly, this is better for very chaotic schemes like Noah's ark. Hashlife is a very different breed, a program invemted by Gosper in the 1980s for pushing the limits of contemporary computers; it works by splitting whatever is getting evolved into a quadtree – each node has four children – and exploiting regularity within that tree (assumed as present) to avoid doing things twice.

The Turtle · Post by **The Turtle** » July 5th, 2015, 12:14 pm

Freywa wrote: QuickLife is a standard, run-of-the-mill totalistic CA algorithm with a few trivial optimisations. As mentioned in the documentation of Golly, this is better for very chaotic schemes like Noah's ark. Hashlife is a very different breed, a program invemted by Gosper in the 1980s for pushing the limits of contemporary computers; it works by splitting whatever is getting evolved into a quadtree – each node has four children – and exploiting regularity within that tree (assumed as present) to avoid doing things twice.

I'm confused.
What is a quadtree? What is &ndash?
And exactly?

gmc_nxtman · Post by **gmc_nxtman** » July 5th, 2015, 6:00 pm

Question: How exactly does one get a python script to write files to your computer?

I'm working on a very advanced glider search program, and requires an external input file and preferably external output files.

Maybe it doesn't have to have an external input file, but a better way of inputting search parameters than just adjusting the code.

Post by **dvgrn** » July 6th, 2015, 11:07 am

The Turtle wrote:I'm confused. What is a quadtree?

Start with the Wikipedia artice on Hashlife. There's a link there to Tom Rokicki's article in Dr. Dobb's Journal, which shows a quadtree representation of a small sample pattern.

The Turtle wrote:What is &ndash?

Not supposed to be part of the answer to your question. An en dash is one of those snazzy punctuation characters, longer than a hyphen but shorter than an em dash, that silly programs like Microsoft Word like to automatically insert along with their StupidQuote(tm) characters, so that your text is magically full of weird junk when you copy and paste it into a nice simple text editor or browser window. Just pretend that "&ndash" is "--" and it will all make sense.

Freywa · Post by **Freywa** » July 6th, 2015, 1:23 pm

I apologise for trying to use the HTML character entity for the en dash. On a desktop I can chord Ctrl/Shift/u, 2013 and get that character correct, but I was on a smartphone when typing my previous response and couldn't insert the en through the input keyboards.

Post by **dvgrn** » July 6th, 2015, 2:10 pm

gmc_nxtman wrote:Question: How exactly does one get a python script to write files to your computer?

I'm working on a very advanced glider search program, and requires an external input file and preferably external output files.

Maybe it doesn't have to have an external input file, but a better way of inputting search parameters than just adjusting the code.[/quote]
Here again, sample code can be very useful. Check out goto.py, for example:

Code: Select all

def savegen(filename, gen):
    try:
        f = open(filename, 'w')
        f.write(gen)
        f.close()
    except:
        g.warn("Unable to save given gen in file:\n" + filename)

# --------------------------------------------------------------------

GotoINIFileName = g.getdir("data") + "goto.ini"
previousgen = ""
try:
    f = open(GotoINIFileName, 'r')
    previousgen = f.readline()
    f.close()
    if not validint(previousgen):
        previousgen = ""
except:
    # should only happen 1st time (GotoINIFileName doesn't exist)
    pass

There's also a sample use of g.getstring(), which shows you how to set up a script to re-run with the same settings by default (saved to an INI file in Golly's "data" directory) but allow you to change those defaults if you want to, instead of just hitting [Enter] to accept them.

gmc_nxtman · Post by **gmc_nxtman** » July 6th, 2015, 5:51 pm

Well now I'm not so sure it's possible to implement as a golly script, because the idea in mind is sort of "smart learning program" which attempts to find a predecessor to a pattern by randomly filling a selection, (according to parameters/filters) running it for one generation, looking how many cells it gets wrong from the input, and tries to correct them. Also the program would download files from catagolue containing every natural SL/ OSC and apply them to the filters.

Parameters include:
• Max number of cells allowed for the program to get wrong
• Max radius around the incorrect cell to try and change
• Regional filters (prevent a configuration of cells from occuring in the predecessor)
• Direct filters (prevent the entire predecessor from being the configuration)
• When to halt the program and stop searching (after n ticks stepped back)

Anyways it's a fairly ambitious project, and I'm not sure whether it's possible to write in python, or whether it's even a good algorithm for finding predecessors anyways.

Post by **dvgrn** » July 7th, 2015, 6:03 pm

gmc_nxtman wrote:Well now I'm not so sure it's possible to implement as a golly script, because the idea in mind is sort of "smart learning program" which attempts to find a predecessor to a pattern by randomly filling a selection, (according to parameters/filters) running it for one generation, looking how many cells it gets wrong from the input, and tries to correct them.

If you're familiar with Python, a Golly script might be a good start. Get a proposed algorithm working and see if it can successfully do simple searches. Then maybe think about rewriting in something faster like C++, but only if the concept seems to be working well and you just need more speed.

gmc_nxtman wrote:Parameters include:
...
• Max radius around the incorrect cell to try and change

If you're looking at 1-tick predecessors, and a cell is coming out wrong, to correct the problem you absolutely have to change at least one of the cell's immediate neighbors. Anything farther away than that won't matter.

Depending on how big the initial pattern is, it might not be too big a search to make a list of all possible predecessors. The tough part is automatically cutting down that list to just a few likely cases. An exhaustive search quickly explodes into an impossibly large task, just half a dozen ticks back or so. This is the problem that lifesrc/WLS/JLS backtracking searches tend to run into. I think it does make sense to work backward one tick at a time, and come up with some kind of scoring system for predecessors.

Here's the beginning of a short conversation from the last time this subject came up. Or anyway there's some discussion there of lifesrc exhaustive predecessor searches, as opposed to rated/weighted backtracking searches.

gmc_nxtman wrote:Anyways it's a fairly ambitious project, and I'm not sure whether it's possible to write in python, or whether it's even a good algorithm for finding predecessors anyways.

The only way to find out for sure is to write the program and try it. Any steps toward solving the backtracking problem would be very interesting!

The Turtle · Post by **The Turtle** » July 8th, 2015, 10:31 am

How do I make my own modules where the module file is in a different folder?
Where are all the default Python modules stored? Can I put my module there?
Thanks!

The Turtle · Post by **The Turtle** » July 10th, 2015, 6:27 pm

Code: Select all

import golly

max_generations = 256
pattern = golly.getcells(golly.getrect())
new_pattern = golly.evolve(pattern, max_generations)

text = "In %d generations, this pattern " % max_generations
if new_pattern != golly.evolve(new_pattern, 1):
	text += "does not turn"
else:
	text += "turns "
text += "into a still life."
golly.show(text)

# something that deletes all cells in the Life universe

golly.putcells(new_pattern)

I wrote a program to detect whether a given pattern turns into still lifes in a given number of generations.
I need to put something where the commented code is. What should I put?
Any suggestions?

Post by **Andrew** » July 11th, 2015, 2:19 am

The Turtle wrote:I need to put something where the commented code is. What should I put?

The simplest and fastest command would just be golly.new(""), but you wouldn't be able to undo to the original pattern. Here's a safer way to clear all live cells (without changing the current selection, if any):

Code: Select all

oldsel = golly.getselrect()
golly.select(golly.getrect())
golly.clear(0)
golly.select(oldsel)

Post by **Andrew** » July 11th, 2015, 2:37 am

The Turtle wrote:How do I make my own modules where the module file is in a different folder?

Python searches for imported modules using the list of directories specified in sys.path. You can see that list by running these commands in Golly via File > Run Clipboard:

Code: Select all

import golly as g
import sys
g.note(str(sys.path))

If you look at the result you'll see the first directory is the empty string which means "look in the current directory" (ie. the same directory as the the .py file given to Golly). Notice also that the last directory is the Python folder supplied with Golly -- that's how the glife module is found if your script contains "import glife".

So, the easiest way to create your own module is to create a folder called, say, mymodule and create a file inside that folder called __init__.py. The code in that file will be executed when your .py scripts do "import mymodule". If you store all your .py files in the same location as the mymodule folder then Python should have no problem finding it. If for some reason you want to store the mymodule folder somewhere else then your scripts will need to start with code like this:

Code: Select all

import sys
sys.path.append("/path/to/mymodule")
import mymodule

The Turtle · Post by **The Turtle** » July 14th, 2015, 2:59 pm

Is there a function that returns the different cells in two cell lists?
If not, how can I write one? The method I am thinking of is to take the first element of the first list and test whether or not it is in the second cell list, take the second element and compare, etc. Is there a faster way?

How can I get the width and height of a pattern relative to the origin?

Thanks,
The Turtle

Post by **dvgrn** » July 14th, 2015, 4:36 pm

The Turtle wrote:Is there a function that returns the different cells in two cell lists?

I believe the simplest trick is

Code: Select all

g.evolve(g.join(cell_list1, cell_list2),0)

You can't just use g.join() by itself, because that command happily leaves the duplicate cells in there. The duplicates would disappear when you did a g.putcells() operation, but if you're not careful they can cause lots of trouble before then.

The Turtle wrote:If not, how can I write one? The method I am thinking of is to take the first element of the first list and test whether or not it is in the second cell list, take the second element and compare, etc. Is there a faster way?

That will work, of course. There are simpler ways, and there are faster ways, but the faster ways may not be simple, and vice versa.

Let's say you have a length-M list and a length-N list. I'm assuming that the cell lists aren't multi-state, so a given (X,Y) is either there or it's not.

If the two cell lists are in a predictable order -- e.g., in row order, left to right, as Golly tends to return cell lists from getrect(), evolve(), etc. -- then you can get through the two lists a lot more quickly. It just takes a single coordinated pass through the two lists, which takes time on the order of (M+N) instead of (M*N). Basically just step forward in each list until you've passed the current element in the other list, then switch to the other list and do the same thing. You'll end up with a new combined ordered list and can easily catch any duplicates.

Python can also do this kind of work for you. E.g., make the cell lists into two sets, each containing the coordinate pairs from each list. Take the union of the two sets, then flatten the result back into a cell list. That's probably going to be fairly time-efficient, though not necessarily very memory-efficient. No idea how it compares with the way Golly does it.

The Turtle wrote:How can I get the width and height of a pattern relative to the origin?

Not quite sure what "relative to the origin" means here, but for any cell_list,

min(cell_list[0::2]), min(cell_list[1::2]) is the upper left corner of the bounding box, and

max(cell_list[0::2]), max(cell_list[1::2]) is the lower right corner, in absolute coordinates.

Subtract (and add 1) to get the width and height. Again you could have Golly do the work using g.putcells() into a temporary new layer, followed by g.getrect().

The Turtle · Post by **The Turtle** » July 14th, 2015, 6:05 pm

dvgrn wrote:
The Turtle wrote:How can I get the width and height of a pattern relative to the origin?
Not quite sure what "relative to the origin" means here, but for any cell_list,

min(cell_list[0::2]), min(cell_list[1::2]) is the upper left corner of the bounding box, and

max(cell_list[0::2]), max(cell_list[1::2]) is the lower right corner, in absolute coordinates.

Subtract (and add 1) to get the width and height. Again you could have Golly do the work using g.putcells() into a temporary new layer, followed by g.getrect().

That should help me.
How does that syntax work? I've never seen it before.

Post by **dvgrn** » July 15th, 2015, 11:28 am

The Turtle wrote:How does that syntax work? I've never seen it before.

With minor apologies, here's a link that explains too much but contains lots of details that you might find useful eventually -- examples of slice assignment, named slices, negative step sizes, and so on.

I also went through the basics of slice syntax in code comments toward the top of this thread.

The Turtle · Post by **The Turtle** » July 15th, 2015, 5:34 pm

dvgrn wrote: I also went through the basics of slice syntax in code comments toward the top of this thread.

Whoops. I missed that.

The Turtle · Post by **The Turtle** » July 15th, 2015, 8:38 pm

dvgrn wrote: Let's say you have a length-M list and a length-N list. I'm assuming that the cell lists aren't multi-state, so a given (X,Y) is either there or it's not.

If the two cell lists are in a predictable order -- e.g., in row order, left to right, as Golly tends to return cell lists from getrect(), evolve(), etc. -- then you can get through the two lists a lot more quickly. It just takes a single coordinated pass through the two lists, which takes time on the order of (M+N) instead of (M*N). Basically just step forward in each list until you've passed the current element in the other list, then switch to the other list and do the same thing. You'll end up with a new combined ordered list and can easily catch any duplicates.

Like this?

Code: Select all

# XORs cells in two cell lists
def different_cells(pattern1, pattern2):
	result = []
	pattern1_index = 0
	pattern2_index = 0
	
	# The cell lists must have an even number of elements
	assert len(pattern1) % 2 == 0
	assert len(pattern2) % 2 == 0
	
	# Loop through the two lists
	# The cell list must be in order, sorted by x value, then by y value
	
	# Compare the first two elements of each list
	# If the elements are different, add the element to the list "result"
	# Advance the index for the list with the lesser value
	# Compare the second value of the list with the lesser value with the first value of the list with the greater value
	# Repeat until a list has no more elements to check
	# If so, return "result" plus the rest of the other list
	
	# The cells are represented in sets of two; that is, [0, 0, 0, 1] represents the cells (0, 0) and (0, 1)
	# This means the index is advanced by two every time
	
	while True:
		# If there are no more elements to check in "pattern1"
		if pattern1_index >= len(pattern1):
			result += pattern2[pattern2_index:]
			return result
		
		# If there are no more elements to check in "pattern2"
		if pattern2_index >= len(pattern2):
			result += pattern1[pattern1_index:]
			return result
		
		# If "pattern1"'s index's x value is less than "pattern2"'s index's x value
		if pattern1[pattern1_index] < pattern2[pattern2_index]:
			result += [pattern1[pattern1_index], pattern1[pattern1_index + 1]]
			pattern1_index += 2
			continue
		
		# If "pattern1"'s index's x value is equal to "pattern2"'s index's x value
		if pattern1[pattern1_index] == pattern2[pattern2_index]:
			# If "pattern1"'s index's y value is less than "pattern2"'s index's y value
			if pattern1[pattern1_index + 1] < pattern2[pattern2_index + 1]:
				result += [pattern1[pattern1_index], pattern1[pattern1_index + 1]]
				pattern1_index += 2
				continue
				
			# If "pattern1"'s index's y value is equal to "pattern2"'s index's y value
			if pattern1[pattern1_index + 1] == pattern2[pattern2_index + 1]:
				pattern1_index += 2
				pattern2_index += 2
				continue
			
			# If "pattern1"'s index's x value is greater than "pattern2"'s index's x value
			if pattern1[pattern1_index + 1] > pattern2[pattern2_index + 1]:
				result += [pattern2[pattern2_index], pattern2[pattern2_index + 1]]
				pattern2_index += 2
				continue
		
		# If "pattern1"'s index's x value is greater than "pattern2"'s index's x value
		if pattern1[pattern1_index] > pattern2[pattern2_index]:
			result += [pattern2[pattern2_index], pattern2[pattern2_index + 1]]
			pattern2_index += 2
			continue

The Turtle · Post by **The Turtle** » July 16th, 2015, 8:15 pm

I noticed that my function in my previous post had an error. I was pondering it until now.
The bug is Golly returns cell lists as x first, then y, but sorts them y first, and then x. Why does Golly do this?

EDIT:
Here is the (hopefully) bug-free code:

Code: Select all

# XORs cells in two cell lists
def different_cells(pattern1, pattern2):
   result = []
   pattern1_index = 0
   pattern2_index = 0
   
   # Loop through the two lists
   # The cell list must be in order, sorted by x value, then by y value
   
   # Compare the first two elements of each list
   # If the elements are different, add the element to the list "result"
   # Advance the index for the list with the lesser value
   # Compare the second value of the list with the lesser value with the first value of the list with the greater value
   # Repeat until a list has no more elements to check
   # If so, return "result" plus the rest of the other list
   
   # The cells are represented in sets of two; that is, [0, 0, 0, 1] represents the cells (0, 0) and (0, 1)
   # This means the index is advanced by two every time
   
   while True:
      # If there are no more elements to check in "pattern1"
      if pattern1_index >= len(pattern1):
         result += pattern2[pattern2_index:]
         return result
      
      # If there are no more elements to check in "pattern2"
      if pattern2_index >= len(pattern2):
         result += pattern1[pattern1_index:]
         return result
      
      # If "pattern1"'s index's x value is less than "pattern2"'s index's x value
      if pattern1[pattern1_index + 1] < pattern2[pattern2_index + 1]:
         result += [pattern1[pattern1_index], pattern1[pattern1_index + 1]]
         pattern1_index += 2
         continue
      
      # If "pattern1"'s index's x value is equal to "pattern2"'s index's x value
      if pattern1[pattern1_index + 1] == pattern2[pattern2_index + 1]:
         # If "pattern1"'s index's y value is less than "pattern2"'s index's y value
         if pattern1[pattern1_index] < pattern2[pattern2_index]:
            result += [pattern1[pattern1_index], pattern1[pattern1_index + 1]]
            pattern1_index += 2
            continue
            
         # If "pattern1"'s index's y value is equal to "pattern2"'s index's y value
         if pattern1[pattern1_index] == pattern2[pattern2_index]:
            pattern1_index += 2
            pattern2_index += 2
            continue
         
         # If "pattern1"'s index's x value is greater than "pattern2"'s index's x value
         if pattern1[pattern1_index] > pattern2[pattern2_index]:
            result += [pattern2[pattern2_index], pattern2[pattern2_index]]
            pattern2_index += 2
            continue
      
      # If "pattern1"'s index's x value is greater than "pattern2"'s index's x value
      if pattern1[pattern1_index + 1] > pattern2[pattern2_index + 1]:
         result += [pattern2[pattern2_index], pattern2[pattern2_index + 1]]
         pattern2_index += 2
         continue

The Turtle · Post by **The Turtle** » July 21st, 2015, 7:24 pm

What is the best way to determine whether a given cell is in a cell list, without putting the pattern on the screen and using golly.getcell()?
I have the feeling the answer is simple...

Post by **dvgrn** » July 21st, 2015, 10:45 pm

The Turtle wrote:What is the best way to determine whether a given cell is in a cell list, without putting the pattern on the screen and using golly.getcell()?
I have the feeling the answer is simple...

Not that simple, just because a Golly cell list isn't a list of coordinate pairs, it's just a long list of numbers.

You can iterate through the list and compare each (even index, odd index) to your target X and Y, of course. But it sounds as if you're looking for something simpler.

Here's a trick I've been using quite a lot lately. If you convert the cell list to a list of coordinate pairs, Python can do the presence/absence test for you very simply, with just "if [x,y] in {coordlist}":

Code: Select all

import golly as g

clist = g.parse("12b3o$2bo5b2o2bo$b2o6b2o2bo$obo5bo$bo3$10b3o$12bo$11bo$18b3o$18bo$19bo!")

x,y = 18,11

coords = [[clist[i],clist[i+1]] for i in range(0,len(clist),2)]

if [x,y] in coords:
  g.note("Yes, [" + str(x)+","+str(y)+"] is one of the points in clist.")

Of course, there are a jillion other ways to do the same thing. Some people might prefer using slices and map():

Code: Select all

import golly as g

clist = g.parse("12b3o$2bo5b2o2bo$b2o6b2o2bo$obo5bo$bo3$10b3o$12bo$11bo$18b3o$18bo$19bo!")

x,y = 18,11

coords = map(None,clist[0::2],clist[1::2])

g.note(str(coords))

if (x,y) in coords: # coordinates are tuples now, not lists
  g.note("Yes, (" + str(x)+","+str(y)+") is one of the points in clist.")

These only work for cell lists from two-state rules, of course. Otherwise you need to change the "2"s to "3"s, and maybe test for a matching cell state if you want to do that.

The Turtle · Post by **The Turtle** » July 22nd, 2015, 4:23 pm

dvgrn wrote:
The Turtle wrote:What is the best way to determine whether a given cell is in a cell list, without putting the pattern on the screen and using golly.getcell()?
I have the feeling the answer is simple...
Not that simple, just because a Golly cell list isn't a list of coordinate pairs, it's just a long list of numbers.

You can iterate through the list and compare each (even index, odd index) to your target X and Y, of course. But it sounds as if you're looking for something simpler.

Here's a trick I've been using quite a lot lately. If you convert the cell list to a list of coordinate pairs, Python can do the presence/absence test for you very simply, with just "if [x,y] in {coordlist}":
Code: Select all
import golly as g

clist = g.parse("12b3o$2bo5b2o2bo$b2o6b2o2bo$obo5bo$bo3$10b3o$12bo$11bo$18b3o$18bo$19bo!")

x,y = 18,11

coords = [[clist[i],clist[i+1]] for i in range(0,len(clist),2)]

if [x,y] in coords:
  g.note("Yes, [" + str(x)+","+str(y)+"] is one of the points in clist.")
Of course, there are a jillion other ways to do the same thing. Some people might prefer using slices and map():
Code: Select all
import golly as g

clist = g.parse("12b3o$2bo5b2o2bo$b2o6b2o2bo$obo5bo$bo3$10b3o$12bo$11bo$18b3o$18bo$19bo!")

x,y = 18,11

coords = map(None,clist[0::2],clist[1::2])

g.note(str(coords))

if (x,y) in coords: # coordinates are tuples now, not lists
  g.note("Yes, (" + str(x)+","+str(y)+") is one of the points in clist.")
These only work for cell lists from two-state rules, of course. Otherwise you need to change the "2"s to "3"s, and maybe test for a matching cell state if you want to do that.

How about deleting a cell or adding a cell without golly.setcell()?
My best way for adding a cell is the append the cell x-coordinate and y-coordinate, then use golly.evolve(), and I don't have the method for deleting a cell (yet).
You have a way of making your answers sound so simple...

Post by **calcyman** » July 22nd, 2015, 5:16 pm

I would suggest using Python's built-in set container (of 2-tuples) instead of a list, since it has precisely the insertion, querying and deletion operations you require. Search for the emboldened words if you haven't encountered these data structures yet.

The Turtle · Post by **The Turtle** » July 22nd, 2015, 7:45 pm

calcyman wrote:I would suggest using Python's built-in set container (of 2-tuples) instead of a list, since it has precisely the insertion, querying and deletion operations you require. Search for the emboldened words if you haven't encountered these data structures yet.

I read the documentation on sets.
Apparently sets are unordered. How do I order the set back into the default ordering returned by the golly module?

ConwayLife.com

Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions

Re: Python Questions