Python Questions

[dvgrn]

I probably should have used zip() in my previous posting -- map() is more general-purpose, letting you apply a function to each element, which is pretty much overkill here. Instead try

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

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.

Sets also come with efficient union and intersection methods, which came up a few posts back. But they're unordered collections, and I'm uneducated-guessing that they might need a little more memory overhead, and so it might take a little more time to convert from a Golly cell list to a set of coordinates. Even a simple list of coordinates has the operators you need -- "in" and "remove".

The detail that hasn't been addressed is how to get from a list of coordinates --

[[0,0], [0,1], [1,0], [1,2], [2,1]] or [(0,0), (0,1), (1,0), (1,2), (2,1)]

-- back to a simple Golly-compatible cell list. Golly doesn't accept nested lists like the above. So when you're all done membership-checking and adding and removing, you have to flatten the list again.

Extending the previous example:

Code: Select all

import golly as g
import itertools

g.setrule("Life")

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

x,y = 18,11

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

if (x,y) in coords:
  coords.remove((x,y))

flatcells = list(itertools.chain.from_iterable(coords))

g.new("Result with cell removed")
g.putcells(flatcells)

There are shorter and even more mysterious versions that will work fine here, and don't require importing anything:

flatcells = sum(coords,[])
# this is significantly slower for long coord lists,
# and it only works if coords are [x,y] lists, not (x,y) tuples

or

flatcells = reduce(list.__add__, (list(c) for c in coords))
# {converts from tuple to list if needed}

or (rumored to be among the fastest methods):

flatcells = []
map(flatcells.extend, coords)

That's lots more options than you need, of course. But you'll see most of these functions eventually in other contexts. It's nice to have an example of zip(), sum(), map(), extend(), reduce() and so on, doing something familiar and understandable.

[The Turtle]

I thought about using these functions. They might be helpful.

Code: Select all

# Puts the x-coordinates and y-coordinates in "pattern" in two-element lists inside a new list
def zip_pattern(pattern):
	return [[pattern[i], pattern[i + 1]] for i in range(0, len(pattern), 2)]


# Takes two-element lists inside a list and puts the x-coordinates and y-coordinates in the same list
def unzip_pattern(pattern):
	return [i for j in range(len(pattern)) for i in pattern[j]]

Are they too slow? They use for loops. (unzip_pattern() uses a double for loop) Or does it not matter (is the speed insignificant)?

I was also wondering how golly.evolve() works. Does it store the pattern as a two-dimensional array, or something else? And how does it apply the b3/s23 rule (and others) to the pattern?

Thanks,
The Turtle

[dvgrn]

I thought about using these functions... Are they too slow? They use for loops. (unzip_pattern() uses a double for loop) Or does it not matter (is the speed insignificant)?

Unless you're doing some very intensive pattern-processing, you're very unlikely to notice the speed difference between your for-loop methods and any of the other options I posted. If you do get to where some list-processing operation seems to be taking a very long time, then you'll be in a good situation to do some simple time trials and pick the fastest option.

I was also wondering how golly.evolve() works. Does it store the pattern as a two-dimensional array, or something else? And how does it apply the b3/s23 rule (and others) to the pattern?

I've been hoping someone else would answer that one, since I'm not really clear on all the details. It won't be a full-sized two-dimensional array, for sure -- that's a sure-fire way to eat up memory and slow performance to a crawl, for any but the smallest bounding boxes.

QuickLife tracks just the active areas, as I recall, where there are ON cells that aren't in a P1 or P2 holding pattern... and HashLife represents everything as a tile, but the big tiles with no ON cells in them are a really easy fast easy lookup, of course.

Patterns are translated back and forth between Golly's internal representation and Python cell lists in a fairly straightforward way, no tricky shortcuts. This is why g.evolve(0) always returns a freshly sorted copy of cell list, with any overlaps taken care of. Golly does (what is usually) quite a bit of extra unnecessary work for evolve(0), creating a new universe and copying cells into it, then back out again. If the cell list is already sorted, then it would be a lot quicker to just return the original list...!

Golly's source code can be browsed online, so you might just start with line 1092 of wxpython.cpp, and look things up from there if you want to research any farther:

Code: Select all

static PyObject* py_evolve(PyObject* self, PyObject* args)
{
    if (PythonScriptAborted()) return NULL;
    wxUnusedVar(self);
    int ngens = 0;
    PyObject* inlist;
    
    if (!PyArg_ParseTuple(args, (char*)"O!i", &PyList_Type, &inlist, &ngens)) return NULL;
    
    // create a temporary universe of same type as current universe
    lifealgo* tempalgo = CreateNewUniverse(currlayer->algtype, allowcheck);
    const char* err = tempalgo->setrule(currlayer->algo->getrule());
    if (err) tempalgo->setrule(tempalgo->DefaultRule());
    
    // copy cell list into temporary universe
    bool multistate = (PyList_Size(inlist) & 1) == 1;
    int ints_per_cell = multistate ? 3 : 2;
    int num_cells = PyList_Size(inlist) / ints_per_cell;
    for (int n = 0; n < num_cells; n++) {
        int item = ints_per_cell * n;
        long x = PyInt_AsLong( PyList_GetItem(inlist, item) );
        long y = PyInt_AsLong( PyList_GetItem(inlist, item + 1) );
        // check if x,y is outside bounded grid
        const char* err = GSF_checkpos(tempalgo, x, y);
        if (err) { delete tempalgo; PYTHON_ERROR(err); }
        if (multistate) {
            long state = PyInt_AsLong( PyList_GetItem(inlist, item + 2) );
            if (tempalgo->setcell(x, y, state) < 0) {
                tempalgo->endofpattern();
                delete tempalgo;
                PYTHON_ERROR("evolve error: state value is out of range.");
            }
        } else {
            tempalgo->setcell(x, y, 1);
        }
        if ((n % 4096) == 0 && PythonScriptAborted()) {
            tempalgo->endofpattern();
            delete tempalgo;
            return NULL;
        }
    }
    tempalgo->endofpattern();
    
    // advance pattern by ngens
    mainptr->generating = true;
    if (tempalgo->gridwd > 0 || tempalgo->gridht > 0) {
        // a bounded grid must use an increment of 1 so we can call
        // CreateBorderCells and DeleteBorderCells around each step()
        tempalgo->setIncrement(1);
        while (ngens > 0) {
            if (PythonScriptAborted()) {
                mainptr->generating = false;
                delete tempalgo;
                return NULL;
            }
            if (!mainptr->CreateBorderCells(tempalgo)) break;
            tempalgo->step();
            if (!mainptr->DeleteBorderCells(tempalgo)) break;
            ngens--;
        }
    } else {
        tempalgo->setIncrement(ngens);
        tempalgo->step();
    }
    mainptr->generating = false;
    
    // convert new pattern into a new cell list
    PyObject* outlist = PyList_New(0);
    bool done = ExtractCellList(outlist, tempalgo);
    delete tempalgo;
    if (!done) {
        Py_DECREF(outlist);
        return NULL;
    }
    
    return outlist;
}

[The Turtle]

Patterns are translated back and forth between Golly's internal representation and Python cell lists in a fairly straightforward way, no tricky shortcuts. This is why g.evolve(0) always returns a freshly sorted copy of cell list, with any overlaps taken care of. Golly does (what is usually) quite a bit of extra unnecessary work for evolve(0), creating a new universe and copying cells into it, then back out again. If the cell list is already sorted, then it would be a lot quicker to just return the original list...!

Has anyone written a function to sort a pattern? If not, I'd be happy to make one! (except it takes a lot of time to put the function in code; I'm not a fast programmer, and I don't want to "reinvent the wheel".)

EDIT:
Just something I've been wondering about:
Why does "import golly" in a python interpreter or program raise an error?

Thanks,
The Turtle

[dvgrn]

Has anyone written a function to sort a pattern? If not, I'd be happy to make one! (except it takes a lot of time to put the function in code; I'm not a fast programmer, and I don't want to "reinvent the wheel".)

sortedclist = g.evolve(clist,0)

should work just fine for most purposes. If you have an algorithm that can reliably improve on the efficiency of g.evolve(), you could post it on the Scripts board. Otherwise there's probably no need to worry about it.

Just something I've been wondering about:
Why does "import golly" in a python interpreter or program raise an error?

Python doesn't have the necessary pointers to know where to look for Golly function definitions. And of course those functions can only work while Golly is running, anyway. I'm not sure what would be required to run a Golly script from IDLE or the Python command line. No doubt Golly's source code can give you some hints, but it might take some serious digging.

[The Turtle]

How can I loop through a list two at a time (with using dvgrn's trick posted previously)?
(The code is [[clist,clist[i+1]] for i in range(0,len(clist),2)])

EDIT:
For example, something like this: (it doesn't work though)

for i, j in pattern:
print i, j

so that
>> [0, 1, 2, 3, 4, 5]
prints
i = 0, j = 1
i = 2, j = 3
i = 4, j = 5

sortedclist = g.evolve(clist,0)

should work just fine for most purposes. If you have an algorithm that can reliably improve on the efficiency of g.evolve(), you could post it on the Scripts board. Otherwise there's probably no need to worry about it.

Is this the Scripts board, or this?

[dvgrn]

How can I loop through a list two at a time (with using dvgrn's trick posted previously)?
(The code is [[clist,clist[i+1]] for i in range(0,len(clist),2)])

I usually just do

Code: Select all

for i in range(0, len(clist), 2):
  print clist[i], clist[i+1]

but there are lots of other options. For example, you could use the code you quoted above:

Code: Select all

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

# or

for item in [[clist[i],clist[i+1]] for i in range(0,len(clist),2)]:
  print item

Is this the Scripts board, or this?

Contributions under the second link (the "Golly Scripts" thread) would be fine. You could start a new thread if necessary (the first link is what I was calling the "Scripts board') but there's usually no need to do that for small one-off contributions.

[The Turtle]

I'll post this here because the script is unfinished.
I was able to write this code to sort single values, but not Golly coordinate lists.
Here it is:

Code: Select all

def insertion_sort(unordered_list):
	ordered_list = []
	
	for i in unordered_list:
		low, high = 0, len(ordered_list)
		index = 0
		
		while True:
			if high - low <= 1:
				ordered_list.insert(high, i)
				break
			
			if ordered_list[index] < i:
				low = index
			
			if ordered_list[index] == i:
				break
			
			if ordered_list[index] > i:
				high = index
			
			index = (low + high) // 2
	
	return ordered_list

I'm sure someone could modify the code to accept Golly coordinate lists, but I don't know how.

Thanks for everyone's help,
The Turtle

[dvgrn]

I'll post this here because the script is unfinished.
I was able to write this code to sort single values, but not Golly coordinate lists.

Yes, this is probably a good place for unfinished scripts like this. An insertion sort is good Python practice, but it's certainly not going to be fast enough to compete with Golly's g.evolve().

Even if you want to stick with non-Golly Python and produce your own sorted lists for some reason, it would be much more efficient to use Python's built-in sort() or sorted() functions. Writing a lot of code to do a simple sort is definitely a re-invention of a square stone wheel, when nice round steel-belted radials are readily available.

(If you get through and understand everything in that linked article, you'll know a lot more about Python than I do. To use sort() or sorted(), you'll need to convert the original flat Golly list to a coordinate list. If the default sort order isn't what you want, use the "key" parameter as the article describes to set your own sort order.)

[The Turtle]

I'll post this here because the script is unfinished.
I was able to write this code to sort single values, but not Golly coordinate lists.

An insertion sort is good Python practice, but it's certainly not going to be fast enough to compete with Golly's g.evolve().

Why?

[dvgrn]

An insertion sort is good Python practice, but it's certainly not going to be fast enough to compete with Golly's g.evolve().

Why?

Python is a high-level interpreted language, where Golly's C++ code is compiled into an executable. So if they're doing pretty much the same amount of number-crunching, a C++ version of a task will be 10 to 100 times faster than the same task running in Python.

On top of that, an insertion sort is a slow algorithm. It has the great virtue of simplicity, but it's not nearly as fast as a lot of other options. Notice the insertion sort's red "n squared" ratings in the comparative list -- compared to all the O(n log(n)) options, that's just plain not very efficient.

And again, the same task can be accomplished in just a couple of lines of code by calling Python's sort() or sorted() functions. That gets you an n log(n) algorithm (Timsort) with no drawbacks that I can think of. Or it can be done with a one-line kludge by calling g.evolve().

Generally in cases like this it's better to do actual time tests: feed a few thousand good-sized random samples to both algoithms, and use Python's time module to measure which one is faster in practice. I'd be very surprised, but I could certainly be wrong about the relative speed of g.evolve() vs. your insertion-sort code.

[The Turtle]

An insertion sort is good Python practice, but it's certainly not going to be fast enough to compete with Golly's g.evolve().

Why?

Python is a high-level interpreted language, where Golly's C++ code is compiled into an executable. So if they're doing pretty much the same amount of number-crunching, a C++ version of a task will be 10 to 100 times faster than the same task running in Python.

On top of that, an insertion sort is a slow algorithm. It has the great virtue of simplicity, but it's not nearly as fast as a lot of other options. Notice the insertion sort's red "n squared" ratings in the comparative list -- compared to all the O(n log(n)) options, that's just plain not very efficient.

And again, the same task can be accomplished in just a couple of lines of code by calling Python's sort() or sorted() functions. That gets you an n log(n) algorithm (Timsort) with no drawbacks that I can think of. Or it can be done with a one-line kludge by calling g.evolve().

Generally in cases like this it's better to do actual time tests: feed a few thousand good-sized random samples to both algoithms, and use Python's time module to measure which one is faster in practice. I'd be very surprised, but I could certainly be wrong about the relative speed of g.evolve() vs. your insertion-sort code.

According to my tests, my insertion sort is a lot faster for sorting 10 elements, faster for 100 elements, a tiny bit faster for 1000 elements, and way slower for 10000 elements. But again, my insertion sort sorts values one at a time, while Golly has to crunch numbers two at a time; it's like comparing apples and oranges.

Oh, and here's the code I used:

Code: Select all

from random import randint
from timeit import timeit
from golly import evolve, note

tests = 50
elements_to_sort = 10000

def insertion_sort():
	ordered_list = []
	
	unordered_list = [randint(0, 9) for i in range(elements_to_sort)]
	
	for i in unordered_list:
		low, high = -1, len(ordered_list)
		index = 0
		
		while True:
			if high - low <= 1:
				ordered_list.insert(high, i)
				break
			
			if ordered_list[index] < i:
				low = index
			
			if ordered_list[index] == i:
				break
			
			if ordered_list[index] > i:
				high = index
			
			index = (low + high) // 2
	
	return ordered_list


def golly_sort():
	evolve([randint(0, 9) for i in range(2 * elements_to_sort)], 0)


note('insertion sort: ' + str(timeit(insertion_sort, number = tests)) + ' seconds per %d tests for %d elements to sort' % (tests, elements_to_sort))

note('golly sort: ' + str(timeit(golly_sort, number = tests)) + ' seconds per %d tests for %d elements to sort' % (tests, elements_to_sort))

Any suggestions? And why is the insertion sort faster over small lists but slower over large lists? I'm sure there's some explanation, but I'm not that mathematically inclined to figure it out.

Thanks,
The Turtle

[calcyman]

That gets you an n log(n) algorithm (Timsort) with no drawbacks that I can think of.

Well, the worst-case performance for each of the algorithms are:

• Bubble sort: O(n^2)
• Quicksort, Merge sort: O(n log n)
• Timsort: SEGMENTATION FAULT

http://www.envisage-project.eu/proving- ... to-fix-it/

[Kiran]

the worst-case performance for each of the algorithms

Quicksort

O(n log n)

Actually the worst case in O(t^2).

[wildmyron]

I have a modified soup search script which causes Golly to consume an ever increasing amount of RAM and eventually hang because a variable is growing in size with every iteration - for no good reason that I can see. Here is a sample script which exhibits the same behaviour:

Code: Select all

import golly as g

fixedsoup = g.parse('2bo$b2o$2o$b2o4$b2o$2o$b2o$2bo!', -20, -5)
fixedsoup += g.parse('o$2o$b2o$2o4$2o$b2o$2o$o!', 17, -5)
fixedsoup += g.parse('2bo6bo$b3o4b3o$2obo4bob2o!', -6, -19)
fixedsoup += g.parse('2obo4bob2o$b3o4b3o$2bo6bo!', -6, 17)
g.note('Create fixed soup')

def soup(p):
    thesoup = fixedsoup
    g.note('Length of fixed soup is: ' + str(len(fixedsoup)))
    
    g.select([0, 0, 16, 16])
    g.randfill(p)
    patt = g.getcells([0, 0, 16, 16])
    patt += g.transform(patt, 0, 0, 1, 0, 0, -1)
    patt += g.transform(patt, -1, 0, -1, 0, 0, 1)
    thesoup += patt
    
    return thesoup

for ii in xrange(10):
    rect = g.getrect()
    if(len(rect)):
        g.select(rect)
        g.clear(0)
    
    g.putcells(soup(50))
    g.show('Soup # ' + str(ii) + ' created')
    g.update()
    g.run(1000)

Am I just missing something obvious or is there a bug somewhere?

Golly version: golly-2.7-win64 downloaded from sourceforge.net
Python version: 2.7.8 (default, Jun 30 2014, 16:08:48) [MSC v.1500 64 bit (AMD64)]
Windows 7 Enterprise (64bit) with SP1

[dvgrn]

I have a modified soup search script which causes Golly to consume an ever increasing amount of RAM and eventually hang because a variable is growing in size with every iteration - for no good reason that I can see. Here is a sample script which exhibits the same behaviour...
Am I just missing something obvious or is there a bug somewhere?

This is normal Python behavior (oddly enough).

The problem would go away if you replaced

thesoup = fixedsoup

with

thesoup = fixedsoup[:]

or, if you want something maybe a little less mysterious,

thesoup = list(fixedsoup)

-- i.e., make a copy of the fixedsoup list in thesoup, instead of just pointing thesoup to the exact same list in the same place in memory (so that changes to thesoup are actually changes to fixedsoup).

Just one of those things that trips everybody up until they find out that Python does that with lists. The link has a longer explanation if you need it.

[wildmyron]

I have a modified soup search script which causes Golly to consume an ever increasing amount of RAM and eventually hang because a variable is growing in size with every iteration - for no good reason that I can see. Here is a sample script which exhibits the same behaviour...
Am I just missing something obvious or is there a bug somewhere?

This is normal Python behavior (oddly enough).

The problem would go away if you replaced

thesoup = fixedsoup

with

thesoup = fixedsoup[:]

or, if you want something maybe a little less mysterious,

thesoup = list(fixedsoup)

-- i.e., make a copy of the fixedsoup list in thesoup, instead of just pointing thesoup to the exact same list in the same place in memory (so that changes to thesoup are actually changes to fixedsoup).

Just one of those things that trips everybody up until they find out that Python does that with lists. The link has a longer explanation if you need it.

Thank you for the explanation. That's particularly frustrating as I read that message as well as your response and I was looking at that line thinking the exact thing you said - that I should be making a copy of the list. However, I assumed I'd get an error and didn't think I'd be modifying a global variable without declaring it global in the function. Hopefully I'll remember for next time.

[praosylen]

How do you access .rule files in Golly's Rules folder?

[drc]

How do you access .rule files in Golly's Rules folder?

Enter their titles in Golly's "set rule dialog" and/or open them in notepad

[praosylen]

How do you access .rule files in Golly's Rules folder?

Enter their titles in Golly's "set rule dialog" and/or open them in notepad

I mean in Python.

[Scorbie]

How do you access .rule files in Golly's Rules folder?

From Golly Help > Python Scripting > getdir:

Code: Select all

getdir(dirname) 
Return the path of the specified directory: 
"app" — the directory containing the Golly application. 
"data" — the user-specific data directory: 
On Linux:
~/.golly/
On Mac OS X:
~/Library/Application Support/Golly/
On Windows:
C:\Documents and Settings\username\Application Data\Golly\
"temp" — the directory Golly uses to store various temporary files. All these files are deleted when Golly quits. 
"rules" — the user-specific rules directory set in Preferences > Control. 
"patterns" — the directory displayed by File > Show Patterns. 
"scripts" — the directory displayed by File > Show Scripts. 
"download" — the directory Golly uses to store downloaded files. 
In each case a full path is returned, terminated by the appropriate path separator for the current platform. 
Example: golly.open(golly.getdir("app") + "Patterns/Life/Breeders/breeder.lif") 

So os.path.join(golly.getdir("rules"), rule_file_name) would do the trick.
The "Python Scripting" page is THE man page for golly scripting, so I suggest you look there if you are not sure how to implement something.

[praosylen]

How do you access .rule files in Golly's Rules folder?

From Golly Help > Python Scripting > getdir:

Code: Select all

getdir(dirname) 
Return the path of the specified directory: 
"app" — the directory containing the Golly application. 
"data" — the user-specific data directory: 
On Linux:
~/.golly/
On Mac OS X:
~/Library/Application Support/Golly/
On Windows:
C:\Documents and Settings\username\Application Data\Golly\
"temp" — the directory Golly uses to store various temporary files. All these files are deleted when Golly quits. 
"rules" — the user-specific rules directory set in Preferences > Control. 
"patterns" — the directory displayed by File > Show Patterns. 
"scripts" — the directory displayed by File > Show Scripts. 
"download" — the directory Golly uses to store downloaded files. 
In each case a full path is returned, terminated by the appropriate path separator for the current platform. 
Example: golly.open(golly.getdir("app") + "Patterns/Life/Breeders/breeder.lif") 

So os.path.join(golly.getdir("rules"), rule_file_name) would do the trick.
The "Python Scripting" page is THE man page for golly scripting, so I suggest you look there if you are not sure how to implement something.

Thank you! That was exactly what I needed to know!

[HartmutHolzwart]

I want to run some sequence of 17c/45 pies against debris and see whether this sequence remains undamaged after (say) 270 gens.

How would I do that using glife and the builtin Golly hash function? The thing is that is OK when the pies leave some debris behind them, but they themselves shouldn't be damaged.

A little like gencols, but more specialzed to my specific needs.

My brain seems to work in emergency mode only today... I could not find any example scripts so far.

Thanks in advance for any hints,
Hartmut

[dvgrn]

I want to run some sequence of 17c/45 pies against debris and see whether this sequence remains undamaged after (say) 270 gens.

How would I do that using glife and the builtin Golly hash function? The thing is that is OK when the pies leave some debris behind them, but they themselves shouldn't be damaged.

Offhand I don't see how you'd apply golly.hash() to that problem. That would be more appropriate if you have, say, a list of half a million different debris constellations, and you want to find out quickly whether a new constellation matches any of them.

The hash of a 17c/45 pi plus debris is going to be unavoidably different from the hash of a plain 17c/45 pi. So never mind golly.hash(), I think. Let's see if I can restate the problem in a way that points to a workable solution.

For each round of tests you're going to have a column of blinkers, on which is running a series of pi heptominos, at some spacing or other. Call that pi-heptomino pattern "P".

[Might there be multiple columns? Then include as many blinkers as needed to get a clean rectangular bounding box, I guess, and add enough extra blinkers above the pi climbers that the rectangle will still match exactly after 270-or-whatever ticks -- blinkers and all.]

You're running Pattern P for 270 ticks, and then you want to match the evolved pattern against P at an offset of 270*17/45=102 cells north of its original location. If all of the cells in P are present in golly.evolve(P,270) at a (0,-102) offset, even after interacting with whatever debris you place nearby, then at least you've got something worth looking at.

One simple way to check for the presence of P is to save the population -- oldpop = int(golly.getpop()) -- then use golly.putcells(P,0,-102,1,0,0,1,"xor") -- then check the new population and see if it's {population of P} less than oldpop. Any population bigger than that is a definite failure: one or more cells are missing from the translated P. EDIT: Or, maybe a tiny bit faster, just plain golly.putcells(P,0,-102) and then check to make sure that the population hasn't increased... same thing really.

The above bits of code use straight Golly cell lists, no glife module needed. There's a different but equivalent syntax that you can use if you import the glife module -- basically just P.put(0,-102), when you've defined P as a glife pattern object. But offhand I don't see how that gains you anything -- might be simpler to stick with Golly's standard functions, which are easier to look up in the Help file...!

[HartmutHolzwart]

Dave,

the XOR is an alternative way to reach the same goal. I didn't want to hash the whole pattern, but only the relevant part of it. And then compare the hash of the relevant part to the original pie sequence. I was lead to the hash function as it states that the hash is pretty unique and independent from the actual location.

BUT, essentially I would need the same steps to identify the relevant part of the pattern as in the XOR method.

BTW., as every year end, I'm taking up the idea of making another 17c/45 caterpillar. The lead I follow is to create the second blinker trail of the caterpillar front end not with two gliders provided by the helix, but with only one glider and a series of helper pies that massage one source glider into a blinker at a suitable position either 28, 30 or 32 cells apart from the first. So far no luck, but a few near misses.

If this could be managed, then we could go with less glider multiplier *WSS in the front end, which in turn would reduce the length of the caterpillar. That combined with other savings through cheaper *WSS build methods might really lead to a significantly smaller size.

Thanks,
Hartmut