Adapting gfind

For scripts to aid with computation or simulation in cellular automata.
Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Adapting gfind

Post by Paul Tooke » July 8th, 2012, 9:13 am

Some time back, I started a topic Adapting Gencols in which I described some modifications that I had made to Paul Callahan's gencols program and invited similar contributions. Sadly, to date no-one has taken up this invitation :( , but discussion in the topic "A new GoL searching program" and a bout of optimism have lead me to try the same thing for David Eppstein's gfind.

I would be interested to hear of any modifications that people have made. Contributions could involve code snippets or simply descriptions of how to modify it for a particular purpose. I'd be particularly interested if anyone has modified gfind to accept its command line parameters in a less contorted and more standardised format. It should be fairly straightforward to do and I've always intended to do this but somehow never got around to it.

Describing several years worth of modifications is a bit to much to handle in one forum posting, and it also involves a good deal more effort than I'm prepared to put in, so the first thing I'll do is to lob some code over the fence for the benefit of the impatient and then gradually add descriptions of the individual patches in future postings.

Below are two attachments, gfind-pt.c and gfind-v46.c. One is my heavily modified (about 1000 lines of C code have been added) version of gfind. *PLEASE* don't just download this file, compile and run it. It is there for looking at, not running. The other file is the original version 4.6 source upon which the modified file is based. I've included it so that anyone using diff style tools can see what changes have been made.

Caveat emptor! Again, please don't just compile and run the modified code. I offer no support for it and no guarantees about its performance or general fitness for purpose. It contains Intel-, Windows-, and Microsoft -specific code that may cause it to compile incorrectly or not at all. It also may not run correctly. For all I know, if you run it on your system it may format your hard disk whilst making rude noises through your computer speakers and sending abusive emails to everyone in your contacts list.

The best way to use the modified file is to load it into your favourite text editor and do a case-insensitive search for "patch". There is a fairly lengthy set of introductory comments near the start of the file which describes a set of patches, tagged PATCH01, PATCH02 etc. These tags appear later on in the code where the modifications occur. There are also some later modifications that unfortunately weren't numbered this way. They will have comments nearby with the word "patch" in them, but probably little in the may of explanation about what has been done or why.

Of course an even better way to use the file, for those who are interested at all, is to simply ignore it and wait for me to post explanations of the individual changes. This route will require a bit of patience!
Attachments
gfind.v46.c
David Eppstein's gfind version 4.6, unmodified
(61.42 KiB) Downloaded 878 times
gfind-pt.c
gfind v4.6 as modified by Paul Tooke
(88.16 KiB) Downloaded 928 times

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 8th, 2012, 11:46 am

Adapting gfind Part 1 - Parameterizing the Minimum Deepening Increment.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In this posting I will describe a way to modify gfind to add an additional parameter to specify what I call the minimum deepening amount. This is the delta (<-- insert lower case Greek character here) in Section 5 of David Eppstein's Searching for Spaceships article. As David points out, gfind sets this equal to the spaceship period, but that any small value should do. As it happens, at higher periods using the period for this value can lead to what I see as suboptimal behaviour. [EDIT: clarified that last sentence]

Firstly, a little explanation of the background to this.

The basic MO behind gfind is to search a tree of spaceship rows, where each path down the tree extends a single spaceship by one row in one phase, with the ordering of successive rows cleverly interleaved so that those at particular distances back up the tree satisfy a recurrence relationship through the CA rule. The tree starts with an empty root node which suffices to represent an infinite number of empty rows in front of the ship. The search has found a spaceship when it has added sufficient empty rows to represent the empty space behind it. The recurrence relationship between rows enable new tree nodes to be added by finding only those rows which are consistent with those already added.

The main search is breadth first. This quickly fills up available memory, so David added a process called compaction which removes nodes from the tree which cannot be extended any further and shrinks the array holding the tree to free up the space used by these nodes. This process on its own can enable the search to progress further, but diminishing returns mean that in harder searches it will eventually fail to reclaim enough memory for the search to continue. David therefore augmented the search with "Iterated Deepening". This occurs before each compaction round and consists of a fixed level depth-first search of each node in the tree yet to be visited. This is a kind of lookahead. It tries to extend the current node by up to N rows, for some N. If this succeeds at some point then the current node is, as far as can be determined at this point, a viable path to a spaceship and is left alone. If, on the other hand, the search completes without reaching this depth then no such path is possible and so the node is removed from the tree. The power of gfind comes in no small amount from the remarkable effectiveness of this deepening process.

The N referred to above is the "deepening amount" and is recalculated at each deepening round to give a value that extends the combined depths of the breadth-first and depth-first searches by at least some minimum fixed value. This is the "minimum deepening amount" referred to earlier. In essence it is the number of extra levels that we are expecting the breadth-first search to have added to the tree since the last deepening. If it has fallen short then the deepening amount is increased to compensate, similarly if it has exceeded expectations then the deepening amount is reduced accordingly. Increasing the deepening amount leads to an exponential increase in the amount of time taken by the deepening round. Ideally it should be enough to be effective whilst being as quick as possible. The default value for the initial deepening amount and the minimum deepening amount are set equal to the spaceship period. This is OK for lower periods, but at greater widths or higher periods it can lead to the deepening amount rising alarmingly, with the time taken taken by each deepening round quickly escalating from minutes to days. With a lower increment, the deepening is less aggressive, but also of course less effective. Carefully balancing this amount and the queue size can speed up high period searches.

That was the "why", now here is the "how". I'll describe how to modify gfind version 4.9 to add a command-line parameter specifying the minimum deepening amount. This is referred to as "PATCH09" in the modified file I posted earlier. Note that if you want to use the line numbers that I supply here then you'll find it easier if you apply the changes in reverse order. It just makes more sense (and is easier for me!) if I describe them sequentially from the start of the file.

Firstly, gfind holds all of its parameters in an array. We will need to extend this in order to hold the new parameter, locate the following code (at line 167)

Code: Select all

#define P_PUFFER 16
#define P_TRACING 17
#define NUM_PARAMS 18
Change it to:

Code: Select all

#define P_PUFFER 16
#define P_TRACING 17
/* MINDEEP PATCH - define a parameter for the deepening increment */
#define P_MINDEEP 18
#define NUM_PARAMS 19
Now add a little macro that will return this value, or default to the spaceship period if the parameter wasn't supplied.
Locate the following code (at line 215)

Code: Select all

#define findLimit params[P_FINDLIMIT]
#define searchLimit params[P_SEARCHLIMIT]
change it to

Code: Select all

#define findLimit params[P_FINDLIMIT]
#define searchLimit params[P_SEARCHLIMIT]
/* MINDEEP PATCH - deepening increment, default to period */
#define MINDEEP  ((params[P_MINDEEP]>0) ? params[P_MINDEEP] : period)
Having defined the parameter we'll now use it. Locate the following code within deepen() (at line 1647)

Code: Select all

	i = currentDepth();
	if (i >= lastdeep) deepeningAmount = period;
	else deepeningAmount = lastdeep + period - i;	/* go at least one period deeper */
Change it to

Code: Select all

    /* MINDEEP PATCH - change 'period' to MINDEEP, user specifiable */
	i = currentDepth();
	if (i >= lastdeep) deepeningAmount = MINDEEP;
	else deepeningAmount = lastdeep + MINDEEP - i;	/* go at least MINDEEP deeper */
Of course having added the parameter we need to let the user know about it when they type gfind c.
Locate this code in usage() at line 1886

Code: Select all

	printf("  /-NN reduces width when iterated deepening level reaches NN\n");
	printf("  /r   reverses search order of pattern rows\n");
Change it to:

Code: Select all

	printf("  /-NN reduces width when iterated deepening level reaches NN\n");
	/* MINDEEP PATCH - Set minimum deepening increment */
	printf("  /eNN set minimum deepening increment to NN (default=period)\n");
	printf("  /r   reverses search order of pattern rows\n");
Of course all of this is pointless unless we explain to gfind how to get this parameter from the command line. Locate the following code in parserule() at line 1931

Code: Select all

			case '*': param = P_DEPTHLIMIT; params[P_DEPTHLIMIT] = 0; break;

			case 'g': case 'G': params[P_MODES] |= M_GLIDE; param = -1; break;
Change it to:

Code: Select all

			case '*': param = P_DEPTHLIMIT; params[P_DEPTHLIMIT] = 0; break;
			/* MINDEEP PATCH - minimum deepening increment */
			case 'e': case 'E': param = P_MINDEEP; break;

			case 'g': case 'G': params[P_MODES] |= M_GLIDE; param = -1; break;
Compile the modified code and you can specify a minimum deepening amount of NN by adding "eNN" to the command line. Try experimenting. A value of 1 and sometimes 2 is often too ineffective, but values of 2, 3 or 4 can speed up p6+ searches. It also helps if you can vary this parameter as the search progresses but the margins of this post are far too narrow to contain a description of how to do that!

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 11th, 2012, 8:42 am

In the topic entitled A new GoL searching program" EricG enquired about a modified version of gfind that I used to search for spaceships in David Bell's Just Friends rule and speculated about searching in other non-totalistic 2-state rules. It is possible to search in these rules, but I only did so by implementing a gruesome kludge. A cleaner modification that supports these in a generalized manner is possible, but involves a fair bit of work to implement.

I had started to write what started to rapidly turn into a lengthy treatise on the kludge that I performed and how I thought it ought to have been done in a cleaner fashion. I soon realised that I was probably going into too much detail, so here is a brief summary of the salient points which will hopefully be of some use.

Basicallly, the only places where gfind really uses the rule in anger are within the functions set4x() and terminal(). The former builds the tables which are used for finding successors to previously discovered rows, the latter checks whether the most recently added rows are sufficient to terminate a spaceship. I kludged them so that irrespective of what was entered at the command line, set4x() always built a rule table for the Just Friends rule and terminal always checked for terminations compatible with that rule. The remainder of the program was satisfied so long as I searched in B2/S12 (which is close enough) and stripped the "rule = " part out of the RLE output.

A more general approach which handles different non-totalistic (as well as totalistic!) rules without ghastly kludges is possible but non-trivial.

The first problem is how to get the rule into and out of gfind. The former isn't helped by the command line format that David Eppstein implemented to get around the fact that the MAC he was using to develop gfind didn't have a proper command line as such. If we can get around this (and I have recently thought of a clean backwards-compatible way of doing so) then getting the rule out again is fairly easy: we just need to modify or replace the printRule() function.

Implementing the set4x() function in a clean way is fairly trivial. The code in file "rules.c" in the .zip file I posted in the Adapting Gencols topic builds a rule table in exactly the right format for set4x(). Adapting the terminal() function is a bit harder but not insurmountable. The core of this function checks whether, for a period P search, we have found at least P (in some cases more) empty rows. If it hasn't then the test fails. It then checks whether the previous P non-empty rows would, if adjacent to two empty rows, cause births in the immediately adjacent empty row. If any of them do then the test fails, otherwise it succeeds. The latter tests are performed by bit parallel operations selected according to the specific CA rule. To extend this to non-totalistic rules these tests need to be generalised.

The remaining work involves replacing all of the tests that are done to the "rule" variable, the tests for B0, and deciding what to do about the "badRuleBits" variable.

The "rule" variable is an integer bitmask used to keep record of the birth and survival rules. It is tested at various places in gfind where it needs to decide whether the CA rule has certain properties. This is necessary when, for example, deciding what symmetry modes are appropriate for the rule. It is also tested in the reachable() and terminal() functions when special action needs to be taken based on the CA rule. Since it isn't possible to encapsulate even a restricted set of non-totalistic rules within a 32-bit integer, some other mechanism needs to be found for performing these tests. In each case it is necessary to understand precisely what is being tested for and why, in order for the test to be generalised.

I mention the tests for B0 separately because they appear in the code in the form "if (params[P_BIRTHS] & 1)" which is actually the same as "if (rule&(1<<9))" or even "if (rule&01000)". Otherwise, my comments above about the "rule" variable apply.

The "badruleBits" variable is a bitmask in the same format as the rule variable. It is set from the /x and /z parameters and specify rules which must never be used. This facilitates searches for spaceships which work in a range of rules. For example, a search with rule specified as s23x4b3z5 would find spaceships that work in all of S23/B3, S234/B3, S23/B35 and S234/B35. In this case, badruleBits would hold S4/B5 and the rule table generated by set4x() would mark as illegal the situations in which a live cell has 4 neighbours or dead cell 5.

I must confess to being in two minds about how to handle badruleBits. Does it really make sense to consider a range of non-totalistic rules? Should it just be supported for totalistic rules? Does anyone even use /x and/or /z?

Answers to the latter question, and indeed any feedback at all would be welcome. The deathly silence that has greeted my earlier postings to this topic isn't particularly encouraging. Even a "your code sucks Paul"-type comment would give me some indication as to whether or not I'm wasting my time here.

EricG
Posts: 199
Joined: August 19th, 2011, 5:41 pm
Location: Chicago-area, USA

Re: Adapting gfind

Post by EricG » July 11th, 2012, 10:37 am

Paul,

If you had sent your posts above to me personally, as old fashioned paper mail, they would be on the short list of non-living things I would grab if my house was burning down.

Thank you very much for going to so much work! About the lack of feedback: Maybe I'm wrong, but I think this forum promotes an ethos which says "don't post for chit-chat - post when you have something substantial to contribute" -- that's the only reason I didn't say thank you immediately. Maybe other readers feel similarly. But, really, thank you very much! Your posts so far have been very substantial, and I was looking forward to fully digesting them by diving into them once they were complete. For now, I confess I've really only skimmed them - I was heeding your advice to be patient ("for those who are interested at all, is to simply ignore it and wait for me to post explanations of the individual changes. This route will require a bit of patience!")

Regarding your first post: I think that was a great introduction to gfind, where people can learn a lot even if they don't want to modify it.

Regarding the non-totalistic rules: I'm naively surprised that terminal() works for B2/S12 in a B2-a/S12 JustFriends search - is it that it just works some of the time, and sometimes gfind outputs ships which actually fail in B2-a/S12?

My overall feedback regarding your questions about the non-totalistic modifications take the line "this is hard enough, lets be lazy regarding the luxury features". So, as for the badRuleBits variable, for my purposes I'd just forget about it. I'm happy to search in one rule at a time. I also see getting the rule back out as a luxury feature -- if the program called it "that weird rule you're interested in", I'd be happy. And finally, I'm not all that unhappy if I have to manually enter a rule table each time I want to search in a new non-totalistic rule, although parsing notations like Alan Hensel's is easy enough (I'm about to post a script which does this for Golly.) The key question for me is how the rules are specified in set4x(). Maybe it is obvious, I really haven't tried to answer this question for myself yet. If you would be willing to post your kludged JustFriends version, I bet I could learn from example.

Anyway, I'm obviously not up to speed yet, but I'm looking forward to working on this. Thanks again.

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 11th, 2012, 12:47 pm

EricG wrote:
Thank you very much for going to so much work!
Thanks for that. :D It's nice to have encouragement.

and:
I'm naively surprised that terminal() works for B2/S12 in a B2-a/S12 JustFriends search
It doesn't even try to! As I said in the third paragraph of my earlier post, the changes I made to set4x() and terminal() mean that these functions assume the Just Friends rule *regardless of the rule actually specified*. I could have searched in B3/S23 and they would have ignored this and worked just the same. The reason for specifying B2/S12 was to satisfy the rest of the unkludged part of the program, particularly the part which looks for compatible symmetry modes.

I didn't want to post my kludged version for a number of reasons, not least because it is complicated by the inclusion of some of my other (unrelated) changes and also several Just Friends-specific addons, such as searches for wickstretchers, wall-walkers and the like. I've therefore taken the set4x() and terminal() kludges and applied them to an otherwise unmodified copy of gfind version 4.9, resulting in the file gfjf.c attached below for your perusal. In general, I would expect the table building shown here in set4x() to be done externally by "non-totalistic rule aware" code. Similiarly I would expect such code to do the prep work for tests in terminal() - just as makeUnterm() does for mirror-symmetric diagonal mode in the unmodified gfind.

Note that this kludged version, like my original, only really works properly in orthogonal searches and asymmetric diagonal searches (It finds the glider). I was only interested in orthogonal searches, so I didn't include the relevant tests for diagonal symmetry modes in terminal(). Most of them are probably easy to add back in. The original diagGlide test ought to work, but the other tests need closer examination. Note that in other rules it is possible to be stymied by the 'nanny' tests in one of searchWidth() or smallOffset(). This is part of the work that I mentioned of generalizing the checks on "rule". Fortunately for me, B2/S12 is sufficient to pass the appropriate tests. This, apart from the fact that gfind requires a rule before it will do anything at all is the only reason that I specified B2/S12.
Attachments
gfjf.c
A version of gfind v4.9 kludged to search the Just Friends rule. For illustrative purposes only.
(64.07 KiB) Downloaded 1069 times

User avatar
velcrorex
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: Adapting gfind

Post by velcrorex » July 11th, 2012, 4:33 pm

Paul,
Thanks so much for uploading your modified gfind as well as the detailed explanations. I've been using your version ever since you uploaded it. I particularly like the save/load/preview, the ability to search for 2c/4 glide reflect (and others), date/time stamps, and the ability to change that deepening parameter.

I have never used the /x or /z parameters.

I have a possibly useful edit to gfind to share. Add the following line to the beginning of the enqueue function (around line 637 in your version)

Code: Select all

	if(b==0&&r!=0) r=INITROW;
where INITROW is an integer. The binary representation of this integers specifies the first row of the pattern to search. I'm not entirely sure how this works or if there's a better way to implement this, but it seems to work as I've described.
-Josh Ball.

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 12th, 2012, 7:31 am

Velcrorex:

Your code replaces the first row generated from the root node with INITROW - but doesn't replace all of them (and generally there are going to be a lot). It will therefore have many siblings. Indeed it will be the first of the 'level 1' nodes to be searched, but it won't be the only one and of course you have thrown away the row that you have replaced.

If it is your intention to *only* search for spaceships that begin with INITROW, then locate the following code in search() at line 2281 in my modified version:

Code: Select all

enqueue(0,0);
and replace it with:

Code: Select all

enqueue(0,0);
enqueue(dequeue(),INITROW);
The first line adds an empty row as the root node and it's own parent. Having PARENT(0)=0 means that this node effectively represents the infinite number of empty rows lying ahead of the spaceship. We also of course need at least one node in the search queue for the search to get started. The second line removes the root node from the search queue, adding INITROW as it's only offspring. The search will therefore begin with our node containing INITROW being the only one in the queue.
Of course, if you have multiple rows to add you could follow this code with:

Code: Select all

enqueue(dequeue(),INITROW2);
enqueue(dequeue(),INITROW3);
...and so on. If you are looking to extend an existing spaceship fragment you will need at least 2*period such rows, firstly so that reachable() has enough to chew on without scanning back to the root node, and secondly so that you can recognize which phase a result is in (success() picks the shortest when producing output.) But be careful when doing this: you will need to work out the correct order in which to add the rows. Perhaps I'll get around to explaining how to do this but (a) it is well beyond gfind 101 and (b) leaving you to work it out for yourself will perhaps be suitable punishment for you doing precisely what I asked you to not do. :)

Incidentally, If you are interested in following this up, you might want to ponder the code immediately following line 2281 in my modified version: the "if (dumpandexit)" code invoked by the /j switch. Why did I add that? Again, a partial explanation: it gave me a copy of the initial search state which I could edit to perform the queue initialization described above without having to edit and recompile gfind.

EricG
Posts: 199
Joined: August 19th, 2011, 5:41 pm
Location: Chicago-area, USA

Re: Adapting gfind

Post by EricG » July 12th, 2012, 9:35 pm

Paul, I'm posting just to give you feedback as soon as I had some. Since the following comment is going to be pretty lacking in real substance, I'll follow it up with something that will be useful to people (in the very near future / as time permits...)

A few minutes ago, I got the JustFriends modified version working in a different rule! Woo hoo!!! Thank You!

I wanted to search for ships in some of the old MCell Weighted Life rules (I've recently ported all of them to ruletrees, forthcoming) and at least in one case, SimpleInverseFire, which is B2eicv4568/s156ak78 in Alan Hensel's notation, it worked!!!! I'm really delighted.

I'm bewildered - thus far at least - by how terminal() works. But I understand how set4x() works, and when I set up a rule table for SimpleInverseFire, it started spitting out complex spaceships of different speeds. Thank you for the explanation, and thank you for the simplified JustFriends modification code. So far, I've left terminal() alone, although the next step is to blindly take out your patches, and put the original back in, just to see what happens, what breaks, etc. Any more comments you want to make about how terminal() works will certainly be appreciated, of course.

Edit: Sure enough, as I search deeper, the program outputs both diagonal and orthogonal ships which fall apart from the rear. Fortunately, some don't.

Edit2: Putting the original terminal() code back in and then varying the totalistic rule at the prompt seems to yield good results. I'll need to be more systematic about it to say anything more specific. But it is quite motivating to be getting working spaceships.

Thanks again, and I'll share all of my non-totalistic work as soon as I have time to write it up.)

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 13th, 2012, 10:01 am

EricG wrote:
I'm bewildered - thus far at least - by how terminal() works.
It is a bit cryptic in parts. The ostensible objective of terminal() of course is to check whether sufficient empty rows have been added to have found the trailing edge of a spaceship. Once the search has found 2*period empty rows then subsequent rows will be looking for rows satisfying the CA rule relationship:
(empty-row, empty-row, new-row) -> empty-row
Another empty row clearly satisfies this requirement, and can be repeated indefinitely. In theory then. the body of terminal() could look like like this:

Code: Select all

	for (p = 0; p < 2*period; p++) {	/* last and 2nd last row in each phase must be zero */
		if (ROW(n) != 0) return 0;
		n = PARENT(n);
	}
In practice, gfind can't do this! Adding a sequence of 2*Period empty rows to the search tree effectively adds a new root node. It's children will actually be restarting the search all over again. Terminal() is therefore designed to look ahead, it first checks that Period empty rows (Period+Offset in reverse search) have been added. It then checks whether this can be extended to 2*Period empty rows. This is satisfied for the most part if the following CA relationship is true:
(2nd-last-row, last-row = empty-row, empty-row) -> empty-row
Hence the comment "2nd last row mustn't cause births" (meaning births in the last row). For cells far enough away from the centre of a symmetric space ship, three consecutive cells r0,r1,r2 must fail to satisfy:

Code: Select all

r2 r1 r0
0  0  0    -> 1
0  0  0

This is tested with bitwise parallel operations on row, row>>1 & row>>2. The exact operations are determined by the CA rule according which bit-triples cause births. I can see this being generalised to non-totalistic rules by previously determining from the rule table which of the 8 possibilities of r0, r1 &r2 cause births. These would result in a bit mask to be used by terminal() to select from 8 bitwise tests.

Near the centre of symmetric spaceships, things are slightly more complicated than this, particularly for diagonal symmetry modes. Here is the code that terminal() uses for orthogonally mirror symmetric modes with additional explanatory comments:

Code: Select all

      else if (diagonal == 0 && (mode == odd || mode == even)) {
         if ((rule & (1 << (2 + 9))) == 0) {// if the rule doesn't includes B2
                                            // (then it must include B3!)
            if ((r & 03) == 03) return 0;   // centre looks like ??***?? or ??****??
                                            //  - causes birth
         } else if (mode == odd) {          // rule has B2, odd symmetric
            if ((r & 03) == 02) return 0;   // centre looks like ??*.*?? - causes birth
         } else                             // rule has B2, even symmetric
                                            // (all other cases already handled)
            if ((r & 03) == 01) return 0;   // centre looks like ??.**.?? - causes birth
      }
Hopefully the comments give sufficient clues to aid in decyphering the other tests. Probably the most cryptic, but also the best to study is the check for the centre of diagonally symmetric spaceships. I believe that this serves as a good model for how to handle the central region for all symmetry modes in non-totalistic rules. This test uses a table called oddMirrorUnterm[] previously generated by makeUnterm(). It uses the lowest 4 bits of the row, which I'll call r0 (the LSB), r1, r2, and r3. It is checking a trailing edge which looks like this:

Code: Select all

r0 r1 r2 r3
r1 0  0  0
r2 0  0  0
r3 0  0  0
The central region doesn't cause births if the following apply:

Code: Select all

r0 r1 r2                       r1 r2 r3
r1 0  0     -> 0     and       0  0  0   -> 0
r2 0  0                        0  0  0
In totalistic rules, the first fails if the rule has Bn with n=r0+2r1+2r2 and the second fails if it has Bn with n=r0+r1+r2. This is precisely what makeUnterm() checks. A version of this procedure extended to support non-totalistic rules could easily do the same thing from a rule table.

I hope this helps and that I haven't caused further bewilderment!

Alegend
Posts: 31
Joined: October 5th, 2009, 3:20 pm

Re: Adapting gfind

Post by Alegend » July 18th, 2012, 8:17 pm

Hmm... The MINDEEP patch for me seems to slow it down a bit. Especially at high levels. b3s23/n1/o7/a/e4/lNN was how I did it.

EricG
Posts: 199
Joined: August 19th, 2011, 5:41 pm
Location: Chicago-area, USA

Re: Adapting gfind

Post by EricG » July 20th, 2012, 4:27 am

This note is primarily meant to give Paul feedback -- I really do intend to write up the following so that everyone can easily join in, if they don't already know how.

I've had very little time to work on the terminal() code, but I can report some progress anyway -- tonight I was able to find ships in various 2 state weighted life rules, not just the isotropic ones which can be expressed in Alan Hensel's notation.

Of particular interest, hexagonal rules can be searched! It helps to use gfind's "/a" flag, which tells gfind to search only for asymmetric spaceships. Shallow searches (up to /l100) of Paul Callahan's B2o/S2m34 weighted rule, and MCell's HexInverseFire only turned up the same small glider identified by Callahan, but this shows that weighted hexagonal rules can be searched successfully, even without addressing the terminal() issue.

As for totalistic hexagonal rules, it is hard to know where to start, but B25/S356H seemed somewhat lifelike, so I tried searching it, and sure enough, it worked! This search: b25/s356/a/l80 turned up this c/5 spaceship:

x = 7, y = 10, rule = B25/S356H
2bo$bo$3b2o$2bobobo$o4b2o$bob2o$2bo$4bo$2bo$4bo!

S5 and S6 are optional - the ship also works in B25/S35H and B25/S3H.
B6 can also be added (B256/S3H, etc).

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 20th, 2012, 7:14 am

Alegend wrote:
The MINDEEP patch for me seems to slow it down a bit
What width were you searching at? Lowering the deepening increment can slow things down because it makes the deepening round less efficient, which means that there are more of them. Therefore, although the duration of each individual deepening round is decreased, the overall amount of time is increased. This is particularly true at narrower widths where the deepening rounds are only taking a few minutes anyway. At greater widths where the deepening rounds are taking days at a time, reducing the deepening amount can make quite a difference at the start of the search when the tree is at its "bushiest".

I typically used lower deepening increments at the start of a search to get over the initial 'hump' at the beginning and then made use of the save/restore state facility in the modified version that I posted to progressively increase the deepening amount.

The problem with testing this kind of modification of course is that the kind of searches that it is likely to be most useful for are so lengthy that repeating them with different search parameters can tie up a computer for months.

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 20th, 2012, 7:56 am

EricG wrote:
hexagonal rules can be searched!
:o I'm astounded! As you're probably aware, gfind works by using five previously discovered rows a,b,c,d,e to find two new rows x & y (of which, only y is used) such that, according to the CA rule:
cdy -> e & abx -> y
(It also uses additional rows to provide a bit of lookahead, but that isn't relevant here.) At the bit level, set4x()
uses the rule table to establish which of the following hold:

Code: Select all

c2 c1 c0         a2 a1 a0
d2 d1 d0 -> e1   b2 b1 b0 -> y1
y2 y1 y0         x2 x1 x0
It then creates tables, used by reachable(), which are indexed by a2a1a0b2b1b0c2c1c0d2d1d0e1 and hold a bit mask for which values of (x0,y0,x1,y1) it is possible to extend x & y by adding specific values of x2,y2.

In hex rules of course, the rule table will effectively ignore two diagonally opposite corners, so one of (x0 & y0) or (x2 & y2) can take any value without affecting the evolution of the central cell. Did you get lucky or did you see this coming? I can only think that your rule table was oriented so that it was x0 and y0 that were being ignored. In the 'flipped' version where x2 and y2 were in the 'don't care' corner, set4x() would find that every combination of x2 and y2 was valid. As a result I would have expected you to have been quickly inundated with a pile of useless results.

Thanks for the feedback. It's nice to see that you're making progress. I've made a little myself too. The actual program output attached below might interest you.
Attachments
sif.txt
(7.28 KiB) Downloaded 835 times

Alegend
Posts: 31
Joined: October 5th, 2009, 3:20 pm

Re: Adapting gfind

Post by Alegend » July 20th, 2012, 5:39 pm

BTW, Paul, I was searching a bit higher than level 100. Anyways, on Stack Exchange's Math site, I had an epiphany. Somebody told me how de Bruijn graphs worked, and I came up with a theory as to how they might be searched. You look for Hamiltonian paths through the graph, until you come upon one that seems to fit the spaceship you're looking for, then translate it into a de Bruijn sequence, and then a Life pattern. What do you guys think?

EricG
Posts: 199
Joined: August 19th, 2011, 5:41 pm
Location: Chicago-area, USA

Re: Adapting gfind

Post by EricG » July 21st, 2012, 7:10 am

Hi Paul!

Yes, I find that SimpleInverseFire output very interesting, particularly the diagonal ship! What is even more interesting to me is that you seem to found ships I didn't, but I seem to have found ships that you didn't as well. Even the shallowest of my searches (by not specifying an "L" parameter) revealed different ships.

Here's my collection so far:
x = 224, y = 22, rule = SimpleInverseFire
148bo21bo11bo$147b3o19b3o4bo4b3o$118bo29bo21bo4b3o4bo17bobo$30bo3bo82b
3o28bo21bo5bo5bo17b3o$29bo2bo2bo82bo27b5o17b5o3bo3b5o14bo3bo$29b7o50bo
9bo20bobo28bo21bo3b5o3bo17bobo17bobo$32bo51bo3bo5bo3bo17bo3bo55bo23bob
o17bobo$30b5o50bo2bo5bo2bo19bobo81bo17bo3bo$31b3o12b5o17b2o15bob2o5b2o
bo122bobo$bobo7bobo18bo13bo3bo16bo17bo3bo3bo3bo20bo$4o7b4o17bo15bo19b
4o12bo2b3obob3o2bo19bo$2bobo5bobo18b3o12b5o17b2o2bo43b5o$b2ob2o3b2ob2o
18bo34b3o18bobobobo23bo$b3o3bo3b3o18bo15bo15b3obo18bobobobobo20b5o$o2b
9o2bo17bo14bobo17b2ob2o15bo7bo22bo$2bobobobobobo16bo2bo2bo10bo3bo12b5o
3bo46bo$3bo2bobo2bo18bobobo10b2o3b2o10bo4b4o$2bo9bo15b3obob3o9bo3bo14b
obo$3bob5obo17bo2bo2bo11bobo16bo$4bo5bo18bobobobo12bo$4bobobobo16bob2o
3b2obo$7bo20bobo3bobo!

My guess is that you're well on your way to working out the various terminal() conditions, but you're not finished, hence the discrepancy. But if that's not the case, maybe it would be helpful for you to see what I've been doing (or really, what I haven't been doing, since I've been doing the least effort version, using David Epstein's original terminal() code.)

Attached is a SimpleInverseFire version of your patched gfind code. Search for the string "EDG Patch" to see what I did (or undid). Also included below are two python scripts which build the rule tables needed for gfind.

I'm going to stop writing to Paul directly for a moment, and address anyone else reading this thread. If you'd like to search for spaceships in Weighted Life rules or in Hensel notation non-totalistic rules, here's what you can do (for now, until Paul comes out with a much improved version!):

1) Download SimpleInverseFire-v2.c and the two included scripts. Run either of the gfind-related scripts, and look for their output in Golly's rule table (set in Golly's preferences). For searching hexagonal totalistic rules, use the For-gifind-from-WeightedLife.py, and set all the weights to "1" except NE and SW, which should be set to zero.

2) Open SimpleInverseFire-v2.c, and search for the string "EDG Patch" until you find the long list of RuleTab entries. Delete these entries, and replace them with the output from one of the gfind-related scripts.

3) Rename and recompile the new version of SimpleinverseFire-v2.c. When the proram asks for a rule, type in any totalistic rule (eg B3/S23).

Back to Paul:

The For-gfind-from-HenselNotation.pyscript will probably make you want to cover your eyes in horror, as it is an ugly way to do what you did in GenCols! Both scripts create lots of duplicate entries, but the C compiler really doesn't mind the smidgen of extra work. Obviously, this sort of code should be in the C program, not in a separate python script.

As for whether searching for hexagonal rules successfully was lucky or not, I suspect the following two sentences will answer that question: I think it worked because I didn't let set4x() do its thing, and instead built ruletables using the scripts below. Once the ruletable is thrown together by one of the scripts, there is no problem, since gfind's rule table is just like weighted life and doesn't insist on isotropy. (So, in other words, I got lucky, right?) Seriously, lucky or not, it does work -- I've found one of Carter Bays' hexagonal spaceships as well. And I've also found spaceships in non-isotropic rules like MCell's Mosquito2, which is weighted like this:

-1 -1 5
5 . C .5
5 -1 -1

But I'd rather have an isotropic version that works very well, and it look like you're well on the way to creating one!

Here are the two gfind scripts:

Code: Select all

# For-gfind-from-WeightedLife.py
#  by Eric Goldstein, July 20, 2012.

# The comments and most of the code are from Weightedlife->Ruletree(1.0).py

import golly


# Default values
RS = []
RB = []
ME_weight = 0
NW_weight = 1 
NN_weight = 1    
NE_weight = 1
WW_weight = 1     
EE_weight = 1
SW_weight = 1         
SS_weight = 1
SE_weight = 1

CR = chr(13)
LF = chr(10)

# The lookup table below for Life32"s non-totalistic notation uses the eight neighbor values:
#   N,NE,E,SE,S,SW,W,NW

notationdict = {  
                 "1e" : [1,0,0,0,0,0,0,0],  #   N 
                 "1c" : [0,1,0,0,0,0,0,0],  #   NE
                 "2a" : [1,1,0,0,0,0,0,0],  #   N,  NE
                 "2e" : [1,0,1,0,0,0,0,0],  #   N,  E 
                 "2k" : [1,0,0,1,0,0,0,0],  #   N,  SE
                 "2i" : [1,0,0,0,1,0,0,0],  #   N,  S 
                 "2c" : [0,1,0,1,0,0,0,0],  #   NE, SE
                 "2v" : [0,1,0,0,0,1,0,0],  #   NE, SW
                 "3a" : [1,1,1,0,0,0,0,0],  #   N,  NE, E
                 "3v" : [1,1,0,1,0,0,0,0],  #   N,  NE, SE 
                 "3y" : [1,1,0,0,1,0,0,0],  #   N,  NE, S      (3r in non-swapped notation)
                 "3q" : [1,1,0,0,0,1,0,0],  #   N,  NE, SW
                 "3j" : [1,1,0,0,0,0,1,0],  #   N,  NE, W
                 "3i" : [1,1,0,0,0,0,0,1],  #   N,  NE, NW
                 "3e" : [1,0,1,0,1,0,0,0],  #   N,  E,  S
                 "3k" : [1,0,1,0,0,1,0,0],  #   N,  E,  SW
                 "3r" : [1,0,0,1,0,1,0,0],  #   N,  SE, SW     (3y in non-swapped notation)
                 "3c" : [0,1,0,1,0,1,0,0],  #   NE, SE, SW 
                 "4a" : [1,1,1,1,0,0,0,0],  #   N,  NE, E,  SE
                 "4y" : [1,1,1,0,1,0,0,0],  #   N,  NE, E,  S  (4r in non-swapped notation)
                 "4q" : [1,1,1,0,0,1,0,0],  #   N,  NE, E,  SW
                 "4i" : [1,1,0,1,1,0,0,0],  #   N,  NE, SE, S
                 "4r" : [1,1,0,1,0,1,0,0],  #   N,  NE, SE, SW (4y in non-swapped notation)
                 "4k" : [1,1,0,1,0,0,1,0],  #   N,  NE, SE, W
                 "4v" : [1,1,0,1,0,0,0,1],  #   N,  NE, SE, NW 
                 "4z" : [1,1,0,0,1,1,0,0],  #   N,  NE, S,  SW
                 "4j" : [1,1,0,0,1,0,1,0],  #   N,  NE, S,  W
                 "4t" : [1,1,0,0,1,0,0,1],  #   N,  NE, S,  NW
                 "4w" : [1,1,0,0,0,1,1,0],  #   N,  NE, SW, W
                 "4e" : [1,0,1,0,1,0,1,0],  #   N,  E,  S,  W
                 "4c" : [0,1,0,1,0,1,0,1],  #   NE, SE, SW, NW
                 "5a" : [0,0,0,1,1,1,1,1],  #   SE, S,  SW, W,  NW
                 "5v" : [0,0,1,0,1,1,1,1],  #   E,  S,  SW, W,  NW
                 "5y" : [0,0,1,1,0,1,1,1],  #   E,  SE, SW, W,  NW (5r in non-swapped notation)
                 "5q" : [0,0,1,1,1,0,1,1],  #   E,  SE, S,  W,  NW
                 "5j" : [0,0,1,1,1,1,0,1],  #   E,  SE, S,  SW, NW 
                 "5i" : [0,0,1,1,1,1,1,0],  #   E,  SE, S,  SW, W 
                 "5e" : [0,1,0,1,0,1,1,1],  #   NE, SE, SW, W,  NW, 
                 "5k" : [0,1,0,1,1,0,1,1],  #   NE, SE, S,  W,  NW
                 "5r" : [0,1,1,0,1,0,1,1],  #   NE, E,  S,  W, NW  (5y in non-swapped notation)
                 "5c" : [1,0,1,0,1,0,1,1],  #   N,  E,  S,  W,  NW
                 "6a" : [0,0,1,1,1,1,1,1],  #   E,  SE, S,  SW, W,  NW
                 "6e" : [0,1,0,1,1,1,1,1],  #   NE, SE, S,  SW, W,  NW
                 "6k" : [0,1,1,0,1,1,1,1],  #   NE, E,  S,  SW, W,  NW
                 "6i" : [0,1,1,1,0,1,1,1],  #   NE, E,  SE, SW, W,  NW
                 "6c" : [1,0,1,0,1,1,1,1],  #   N,  E,  S,  SW, W,  NW
                 "6v" : [1,0,1,1,1,0,1,1],  #   N,  E,  SE, S,  W,  NW
                 "7e" : [0,1,1,1,1,1,1,1],  #   NE, E,  SE, S,  SW, W,  NW 
                 "7c" : [1,0,1,1,1,1,1,1]   #   N,  E,  SE, S,  SW, W,  NW
                }

#  Here's a graphical depiction of the notation.
dummyvariable = '''
x = 147, y = 97, rule = B/S012345678
21b3o6b5o5bo3bo6b3o6b5o5bo3bo5bo3bo6b3o10bo5b4o6b5o5bobobo5b5o$20bo3bo
5bo9bo2bo6bo3bo7bo7bo3bo5bo3bo5bo3bo9bo5bo3bo7bo7bobobo9bo$20bo9bo9bob
o7bo3bo7bo7bo3bo5bo3bo5bo3bo9bo5bo3bo7bo7bobobo8bo$20bo9b3o7b2o8b5o7bo
7bo3bo6bobo6bo3bo9bo5b4o8bo7bobobo7bo$20bo9bo9bobo7bo3bo7bo7bo3bo7bo7b
obobo5bo3bo5bo3bo7bo7bobobo6bo$20bo3bo5bo9bo2bo6bo3bo7bo8bobo8bo7bo2bo
6bo3bo5bo3bo7bo7bobobo5bo$21b3o6b5o5bo3bo5bo3bo5b5o7bo9bo8b2obo6b3o6bo
3bo7bo8bobo6b5o4$b3o6b7o$o3bo5bo5bo$o2b2o5bo5bo$obobo5bo2bo2bo$2o2bo5b
o5bo$o3bo5bo5bo$b3o6b7o4$b2o17b7o3b7o$obo17bo5bo3bo5bo$2bo17bobo3bo3bo
2bo2bo$2bo17bo2bo2bo3bo2bo2bo$2bo17bo5bo3bo5bo$2bo17bo5bo3bo5bo$5o15b
7o3b7o4$b3o16b7o3b7o3b7o3b7o3b7o3b7o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo
5bo3bo5bo$4bo15bobobobo3bo2bo2bo3bobo3bo3bobo3bo3bo2bo2bo3bo3bobo$3bo
16bo2bo2bo3bob2o2bo3bo2bo2bo3bob2o2bo3bo2bo2bo3bo2bo2bo$2bo17bo5bo3bo
5bo3bo2bo2bo3bo5bo3bo2bo2bo3bobo3bo$bo18bo5bo3bo5bo3bo5bo3bo5bo3bo5bo
3bo5bo$5o15b7o3b7o3b7o3b7o3b7o3b7o4$b3o16b7o3b7o3b7o3b7o3b7o3b7o3b7o3b
7o3b7o3b7o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo
3bo5bo$4bo15bobobobo3bo2bo2bo3bobo3bo3bob2o2bo3bo3bobo3bobobobo3bo2b2o
bo3bo3bobo3bo3bobo3bobobobo$2b2o16bo2bo2bo3bob2o2bo3bo2b2obo3bob2o2bo
3bo2b2obo3bob2o2bo3bo2bo2bo3bo2bo2bo3bo2b2obo3bo2bo2bo$4bo15bobo3bo3bo
2bo2bo3bo2bo2bo3bo5bo3bo3bobo3bo5bo3bo2bo2bo3bob2o2bo3bo2bo2bo3bo2bo2b
o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$b
3o16b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o4$2b2o16b7o3b7o3b7o3b7o3b7o
3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o$bobo16bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3b
o5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$o2bo16bobobobo3bo2bo2bo
3bo2b2obo3bob3obo3bob2o2bo3bobobobo3bob2o2bo3bob2o2bo3bo3bobo3bobobobo
3bob3obo3bobo3bo3bob2o2bo$5o15bo2bo2bo3bob3obo3bob2o2bo3bob2o2bo3bo2bo
2bo3bob2o2bo3bob2o2bo3bob2o2bo3bob3obo3bo2bo2bo3bo2bo2bo3bob2o2bo3bo2b
o2bo$3bo16bobobobo3bo2bo2bo3bo3bobo3bo5bo3bob2o2bo3bobo3bo3bo2bo2bo3bo
3bobo3bo2bo2bo3bob2o2bo3bo2bo2bo3bo2b2obo3bo2b2obo$3bo16bo5bo3bo5bo3bo
5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$3bo16b
7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o4$5o15b7o3b7o3b7o3b
7o3b7o3b7o3b7o3b7o3b7o3b7o$o19bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5b
o3bo5bo3bo5bo3bo5bo$4o16bo2bo2bo3bobobobo3bo2b2obo3bo3bobo3bob2o2bo3bo
bo3bo3bobobobo3bob2o2bo3bob2o2bo3bobobobo$4bo15bob3obo3bo2b2obo3bob2o
2bo3bo2b2obo3bob2o2bo3bob3obo3bob3obo3bob2o2bo3bob2o2bo3bob3obo$4bo15b
o2b2obo3bobobobo3bobobobo3bob3obo3bob2o2bo3bob2o2bo3bobo3bo3bo2b2obo3b
obobobo3bo2bo2bo$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo
3bo5bo3bo5bo$b3o16b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o4$b3o16b7o3b
7o3b7o3b7o3b7o3b7o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$o19bo2bo
2bo3bobobobo3bo2b2obo3bo2b2obo3bobobobo3bob2o2bo$4o16bob3obo3bo2b2obo
3bob3obo3bo2b2obo3bob3obo3bob3obo$o3bo15bob3obo3bob3obo3bobobobo3bob3o
bo3bobobobo3bo2b2obo$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$b3o16b
7o3b7o3b7o3b7o3b7o3b7o4$5o15b7o3b7o$4bo15bo5bo3bo5bo$3bo16bo2b2obo3bob
3obo$3bo16bob3obo3bo2b2obo$2bo17bob3obo3bob3obo$2bo17bo5bo3bo5bo$2bo
17b7o3b7o4$b3o6b7o$o3bo5bo5bo$o3bo5bob3obo$b3o6bob3obo$o3bo5bob3obo$o
3bo5bo5bo$b3o6b7o!
'''


   

WeightedRulestring = golly.getstring('''   

This script converts Weighted Life rules to a rule table usable by 
David Epstein's gfind program, as modified by Paul Tooke.

Newly created rule tables will be placed in Golly's Rules directory (set in Golly"s preferences).   
You can delete them once you've moved them into Paul Tooke's modified gfind program.
                                                          
Enter a Weighted Life rule here:
''', "NW5,NN1,NE5,WW1,ME0, EE1,SW5,SS1,SE5,HI0,RS1,RS5,RB2,RB10") 

WeightedRulestring = WeightedRulestring.replace("ame = ", "ame=")
WeightedRulestring = WeightedRulestring.replace(" ", ",")
WeightedRulestring = WeightedRulestring.replace(CR, ",")
WeightedRulestring = WeightedRulestring.replace(LF, ",")
 
for x in WeightedRulestring.split(","):
   if x.startswith("Name=") or x.startswith("name="):
      name = x.split("ame=")[1]
   else:
      x = x.upper()
      if x.startswith("NW"):
         NW_weight = int(x.split("NW")[1])
      elif x.startswith("NN"):
         NN_weight = int(x.split("NN")[1])
      elif x.startswith("NE"):
         NE_weight = int(x.split("NE")[1])
      elif x.startswith("WW"):
         WW_weight = int(x.split("WW")[1])
      elif x.startswith("EE"):
         EE_weight = int(x.split("EE")[1])
      elif x.startswith("SW"):
         SW_weight = int(x.split("SW")[1])
      elif x.startswith("SS"):
         SS_weight = int(x.split("SS")[1])
      elif x.startswith("SE"):
         SE_weight = int(x.split("SE")[1])
      elif x.startswith("ME"):
         ME_weight = int(x.split("ME")[1])
      elif x.startswith("RS"):
         RS.append(int(x.split("RS")[1]))
      elif x.startswith("RB"):
         RB.append(int(x.split("RB")[1]))
      elif x.startswith("HI"):
         n_states = (int(x.split("HI")[1]))

f = open(golly.getdir("rules")+"gfind-table"+"  temp"+".txt", "w")   # using temp for the rule name, for now.   Put code from weightedlife-ruletree in, once that finalizes.


def convertorder_aux (x2, x3, x6, x9, x8, x7, x4, x1):
    return [x1, x2, x3, x4, 0, x6, x7, x8, x9]    # by inserting zero, it can not handle ME values.   To do: take ME_weight as a parameter.

def isotropy (x1, x2, x3, x4, x5, x6, x7, x8, x9):
   return [[x1, x2, x3, x4, x5, x6, x7, x8, x9],
             [x3, x2, x1, x6, x5, x4, x9, x8, x7],
             [x7, x8, x9, x4, x5, x6, x1, x2, x3],
             [x1, x4, x7, x2, x5, x8, x3, x6, x9],
             [x9, x6, x3, x8, x5, x2, x7, x4, x1],
             [x7, x4, x1, x8, x5, x2, x9, x6, x3],
             [x9, x8, x7, x6, x5, x4, x3, x2, x1],
             [x3, x6, x9, x2, x5, x8, x1, x4, x7]
            ]


def handleall(B_or_S_flag, RB_or_RS_list):
  for i in notationdict:
      converted = convertorder_aux(notationdict[i][0],notationdict[i][1],notationdict[i][2],notationdict[i][3],notationdict[i][4],notationdict[i][5],notationdict[i][6],notationdict[i][7])
      for config in isotropy(converted[0],converted[1],converted[2],converted[3], converted[4], converted[5], converted[6], converted[7], converted[8]):
       for rulevalue in RB_or_RS_list:
         if rulevalue == NW_weight*config[0]+NN_weight*config[1]+NE_weight*config[2]+WW_weight*config[3]+EE_weight*config[5]+SW_weight*config[6]+SS_weight*config[7]+SE_weight*config[8]:

           
           f.write( "ruleTab[")

           if config[0] == 1:
               f.write("mNW + ")
   
           if config[1] == 1:
               f.write( "mNN + ")
  

           if config[2] == 1:
               f.write("mNE +  ")
 


           if config[3] == 1:
               f.write("mWW + ")
   
           if  config[5] == 1:
               f.write("mEE +   ")
  


           if  config[6] == 1:
               f.write("mSW + ")
   

           if  config[7] == 1:
               f.write("mSS +  ")
  

           if  config[8] == 1:
               f.write("mSE + ")
          
           f.write(B_or_S_flag + "] = 1;" +"\n")

handleall("0",RB)
handleall("mME",RS)

f.flush()
f.close()
golly.show("Created gfind-table"+ "  temp"+".txt in "+golly.getdir("rules"))


            
             
           

Code: Select all

# For-gfind-from-HenselNotation.py
# by Eric Goldstein, July 20, 2012.

#  All of the comments (and most of the code) is from HenselNotation->Ruletable.py

# This script builds a ruleTable for Life32's non-totalistic notation. 
# The notation was originally adapted from Alan Hensel"s work on that subject.

dialog_box_message =  '''This script will allow you to enter the non-totalistic rule notation 
used by Johan Bontes' Life32 program, based on work by Alan Hensel.
Please look in the script file to see how the notation works.

The goal is to create a series of rule table entries for David Epstein's gfind proram, as modified by Paul Tooke.  
Newly created rules will be placed in Golly's Rules directory (set in Golly"s preferences).  
You can delete them once you've moved them into Paul Tooke's modified gfind program.
 
Enter a rule here:
   '''

# Minor note:
# Unfortunately, Alan Hensel's notation for r and y are swapped in Life32.   
# Life32's rule dialog box shows the correct arrangements, but they are swapped in the implementation.
# What should work as 3r, 4r, and 5r, actually work as 3y, 4y, and 5y, and vice versa.
# This script swaps the definition of r and y just like Life32 does, so that patterns intended to be run
# on Life32 will run the same way in Golly.  

 
# Golly"s ruleTable format use the following notation:  
#  C,N,NE,E,SE,S,SW,W,NW,C' 
# where C is the current state, and C' is the new state, and
# where the eight neighbors in the Moore neighborhood are as shown below.

#     NW  N  NE 
#     W   C  E  
#     SW  S  SE 

# The lookup table below for Life32"s non-totalistic notation uses the eight neighbor values:
#   N,NE,E,SE,S,SW,W,NW



notationdict = {  
                 "1e" : [1,0,0,0,0,0,0,0],  #   N 
                 "1c" : [0,1,0,0,0,0,0,0],  #   NE
                 "2a" : [1,1,0,0,0,0,0,0],  #   N,  NE
                 "2e" : [1,0,1,0,0,0,0,0],  #   N,  E 
                 "2k" : [1,0,0,1,0,0,0,0],  #   N,  SE
                 "2i" : [1,0,0,0,1,0,0,0],  #   N,  S 
                 "2c" : [0,1,0,1,0,0,0,0],  #   NE, SE
                 "2v" : [0,1,0,0,0,1,0,0],  #   NE, SW
                 "3a" : [1,1,1,0,0,0,0,0],  #   N,  NE, E
                 "3v" : [1,1,0,1,0,0,0,0],  #   N,  NE, SE 
                 "3y" : [1,1,0,0,1,0,0,0],  #   N,  NE, S      (3r in non-swapped notation)
                 "3q" : [1,1,0,0,0,1,0,0],  #   N,  NE, SW
                 "3j" : [1,1,0,0,0,0,1,0],  #   N,  NE, W
                 "3i" : [1,1,0,0,0,0,0,1],  #   N,  NE, NW
                 "3e" : [1,0,1,0,1,0,0,0],  #   N,  E,  S
                 "3k" : [1,0,1,0,0,1,0,0],  #   N,  E,  SW
                 "3r" : [1,0,0,1,0,1,0,0],  #   N,  SE, SW     (3y in non-swapped notation)
                 "3c" : [0,1,0,1,0,1,0,0],  #   NE, SE, SW 
                 "4a" : [1,1,1,1,0,0,0,0],  #   N,  NE, E,  SE
                 "4y" : [1,1,1,0,1,0,0,0],  #   N,  NE, E,  S  (4r in non-swapped notation)
                 "4q" : [1,1,1,0,0,1,0,0],  #   N,  NE, E,  SW
                 "4i" : [1,1,0,1,1,0,0,0],  #   N,  NE, SE, S
                 "4r" : [1,1,0,1,0,1,0,0],  #   N,  NE, SE, SW (4y in non-swapped notation)
                 "4k" : [1,1,0,1,0,0,1,0],  #   N,  NE, SE, W
                 "4v" : [1,1,0,1,0,0,0,1],  #   N,  NE, SE, NW 
                 "4z" : [1,1,0,0,1,1,0,0],  #   N,  NE, S,  SW
                 "4j" : [1,1,0,0,1,0,1,0],  #   N,  NE, S,  W
                 "4t" : [1,1,0,0,1,0,0,1],  #   N,  NE, S,  NW
                 "4w" : [1,1,0,0,0,1,1,0],  #   N,  NE, SW, W
                 "4e" : [1,0,1,0,1,0,1,0],  #   N,  E,  S,  W
                 "4c" : [0,1,0,1,0,1,0,1],  #   NE, SE, SW, NW
                 "5a" : [0,0,0,1,1,1,1,1],  #   SE, S,  SW, W,  NW
                 "5v" : [0,0,1,0,1,1,1,1],  #   E,  S,  SW, W,  NW
                 "5y" : [0,0,1,1,0,1,1,1],  #   E,  SE, SW, W,  NW (5r in non-swapped notation)
                 "5q" : [0,0,1,1,1,0,1,1],  #   E,  SE, S,  W,  NW
                 "5j" : [0,0,1,1,1,1,0,1],  #   E,  SE, S,  SW, NW 
                 "5i" : [0,0,1,1,1,1,1,0],  #   E,  SE, S,  SW, W 
                 "5e" : [0,1,0,1,0,1,1,1],  #   NE, SE, SW, W,  NW, 
                 "5k" : [0,1,0,1,1,0,1,1],  #   NE, SE, S,  W,  NW
                 "5r" : [0,1,1,0,1,0,1,1],  #   NE, E,  S,  W, NW  (5y in non-swapped notation)
                 "5c" : [1,0,1,0,1,0,1,1],  #   N,  E,  S,  W,  NW
                 "6a" : [0,0,1,1,1,1,1,1],  #   E,  SE, S,  SW, W,  NW
                 "6e" : [0,1,0,1,1,1,1,1],  #   NE, SE, S,  SW, W,  NW
                 "6k" : [0,1,1,0,1,1,1,1],  #   NE, E,  S,  SW, W,  NW
                 "6i" : [0,1,1,1,0,1,1,1],  #   NE, E,  SE, SW, W,  NW
                 "6c" : [1,0,1,0,1,1,1,1],  #   N,  E,  S,  SW, W,  NW
                 "6v" : [1,0,1,1,1,0,1,1],  #   N,  E,  SE, S,  W,  NW
                 "7e" : [0,1,1,1,1,1,1,1],  #   NE, E,  SE, S,  SW, W,  NW 
                 "7c" : [1,0,1,1,1,1,1,1]   #   N,  E,  SE, S,  SW, W,  NW
                }

#  Here's a graphical depiction of the notation.
dummyvariable = '''
x = 147, y = 97, rule = B/S012345678
21b3o6b5o5bo3bo6b3o6b5o5bo3bo5bo3bo6b3o10bo5b4o6b5o5bobobo5b5o$20bo3bo
5bo9bo2bo6bo3bo7bo7bo3bo5bo3bo5bo3bo9bo5bo3bo7bo7bobobo9bo$20bo9bo9bob
o7bo3bo7bo7bo3bo5bo3bo5bo3bo9bo5bo3bo7bo7bobobo8bo$20bo9b3o7b2o8b5o7bo
7bo3bo6bobo6bo3bo9bo5b4o8bo7bobobo7bo$20bo9bo9bobo7bo3bo7bo7bo3bo7bo7b
obobo5bo3bo5bo3bo7bo7bobobo6bo$20bo3bo5bo9bo2bo6bo3bo7bo8bobo8bo7bo2bo
6bo3bo5bo3bo7bo7bobobo5bo$21b3o6b5o5bo3bo5bo3bo5b5o7bo9bo8b2obo6b3o6bo
3bo7bo8bobo6b5o4$b3o6b7o$o3bo5bo5bo$o2b2o5bo5bo$obobo5bo2bo2bo$2o2bo5b
o5bo$o3bo5bo5bo$b3o6b7o4$b2o17b7o3b7o$obo17bo5bo3bo5bo$2bo17bobo3bo3bo
2bo2bo$2bo17bo2bo2bo3bo2bo2bo$2bo17bo5bo3bo5bo$2bo17bo5bo3bo5bo$5o15b
7o3b7o4$b3o16b7o3b7o3b7o3b7o3b7o3b7o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo
5bo3bo5bo$4bo15bobobobo3bo2bo2bo3bobo3bo3bobo3bo3bo2bo2bo3bo3bobo$3bo
16bo2bo2bo3bob2o2bo3bo2bo2bo3bob2o2bo3bo2bo2bo3bo2bo2bo$2bo17bo5bo3bo
5bo3bo2bo2bo3bo5bo3bo2bo2bo3bobo3bo$bo18bo5bo3bo5bo3bo5bo3bo5bo3bo5bo
3bo5bo$5o15b7o3b7o3b7o3b7o3b7o3b7o4$b3o16b7o3b7o3b7o3b7o3b7o3b7o3b7o3b
7o3b7o3b7o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo
3bo5bo$4bo15bobobobo3bo2bo2bo3bobo3bo3bob2o2bo3bo3bobo3bobobobo3bo2b2o
bo3bo3bobo3bo3bobo3bobobobo$2b2o16bo2bo2bo3bob2o2bo3bo2b2obo3bob2o2bo
3bo2b2obo3bob2o2bo3bo2bo2bo3bo2bo2bo3bo2b2obo3bo2bo2bo$4bo15bobo3bo3bo
2bo2bo3bo2bo2bo3bo5bo3bo3bobo3bo5bo3bo2bo2bo3bob2o2bo3bo2bo2bo3bo2bo2b
o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$b
3o16b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o4$2b2o16b7o3b7o3b7o3b7o3b7o
3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o$bobo16bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3b
o5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$o2bo16bobobobo3bo2bo2bo
3bo2b2obo3bob3obo3bob2o2bo3bobobobo3bob2o2bo3bob2o2bo3bo3bobo3bobobobo
3bob3obo3bobo3bo3bob2o2bo$5o15bo2bo2bo3bob3obo3bob2o2bo3bob2o2bo3bo2bo
2bo3bob2o2bo3bob2o2bo3bob2o2bo3bob3obo3bo2bo2bo3bo2bo2bo3bob2o2bo3bo2b
o2bo$3bo16bobobobo3bo2bo2bo3bo3bobo3bo5bo3bob2o2bo3bobo3bo3bo2bo2bo3bo
3bobo3bo2bo2bo3bob2o2bo3bo2bo2bo3bo2b2obo3bo2b2obo$3bo16bo5bo3bo5bo3bo
5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$3bo16b
7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o4$5o15b7o3b7o3b7o3b
7o3b7o3b7o3b7o3b7o3b7o3b7o$o19bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5b
o3bo5bo3bo5bo3bo5bo$4o16bo2bo2bo3bobobobo3bo2b2obo3bo3bobo3bob2o2bo3bo
bo3bo3bobobobo3bob2o2bo3bob2o2bo3bobobobo$4bo15bob3obo3bo2b2obo3bob2o
2bo3bo2b2obo3bob2o2bo3bob3obo3bob3obo3bob2o2bo3bob2o2bo3bob3obo$4bo15b
o2b2obo3bobobobo3bobobobo3bob3obo3bob2o2bo3bob2o2bo3bobo3bo3bo2b2obo3b
obobobo3bo2bo2bo$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo
3bo5bo3bo5bo$b3o16b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o3b7o4$b3o16b7o3b
7o3b7o3b7o3b7o3b7o$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$o19bo2bo
2bo3bobobobo3bo2b2obo3bo2b2obo3bobobobo3bob2o2bo$4o16bob3obo3bo2b2obo
3bob3obo3bo2b2obo3bob3obo3bob3obo$o3bo15bob3obo3bob3obo3bobobobo3bob3o
bo3bobobobo3bo2b2obo$o3bo15bo5bo3bo5bo3bo5bo3bo5bo3bo5bo3bo5bo$b3o16b
7o3b7o3b7o3b7o3b7o3b7o4$5o15b7o3b7o$4bo15bo5bo3bo5bo$3bo16bo2b2obo3bob
3obo$3bo16bob3obo3bo2b2obo$2bo17bob3obo3bob3obo$2bo17bo5bo3bo5bo$2bo
17b7o3b7o4$b3o6b7o$o3bo5bo5bo$o3bo5bob3obo$b3o6bob3obo$o3bo5bob3obo$o
3bo5bo5bo$b3o6b7o!
'''



         # This is the isotropy function's order:  NW,NN,NE,WW,ME,EE,SW,SS,SE
         # This is the notationdict's order:     N,NE,E,SE,S,SW,W,NW

#  So, a conversion function is necessary to use notationdict.  
#   the conversion function takes a notationdict entry like "1,1,1,0,0,0,0,0" and 
#   returns "0 1 1 0 0 1 0 0 0"
# and then isotropy can be run on that result.

def convertorder (totalistic_num, notation_letter):
    n = notationdict[totalistic_num+notation_letter]
    return convertorderaux(n[0], n[1], n[2], n[3], n[4], n[5], n[6], n[7])

def convertorderaux (x2, x3, x6, x9, x8, x7, x4, x1):
    return [x1, x2, x3, x4, 0, x6, x7, x8, x9]

def isotropy (x1, x2, x3, x4, x5, x6, x7, x8, x9):
   return [[x1, x2, x3, x4, x5, x6, x7, x8, x9],
             [x3, x2, x1, x6, x5, x4, x9, x8, x7],
             [x7, x8, x9, x4, x5, x6, x1, x2, x3],
             [x1, x4, x7, x2, x5, x8, x3, x6, x9],
             [x9, x6, x3, x8, x5, x2, x7, x4, x1],
             [x7, x4, x1, x8, x5, x2, x9, x6, x3],
             [x9, x8, x7, x6, x5, x4, x3, x2, x1],
             [x3, x6, x9, x2, x5, x8, x1, x4, x7]
            ]

def create_isotropy_rows (input_isotropy_list, bs):
  result = ""

  for row in input_isotropy_list:
    result = result + "ruleTab["
    if row[0] == 1:
       result = result + "mNW + "
   
    if row[1] == 1:
       result = result + "mNN + "
  

    if row[2] == 1:
       result = result + "mNE +  "
 


    if row[3] == 1:
       result = result + "mWW + "
   
    if  row[5] == 1:
       result = result + "mEE +   "
  


    if  row[6] == 1:
       result = result + "mSW + "
   

    if  row[7] == 1:
       result = result + "mSS +  "
  

    if  row[8] == 1:
       result = result + "mSE + "
    result = result + bs + "] = 1;" +"\n"
  return result



# The following function takes a rule element like B2a or B2-a and creates the appropriate ruleTable row.
# Parameters:
# bs is a string with one of two values "0," to indicate birth, and "1," to indicates survival.
# totalistic_num is one character string "0" ... "8"
# notation_letter is a one character string indicating Hensel's notation "a", 
# inverse_list is a list of notation letters for inverse notation 

def create_table_row(bs,totalistic_num, notation_letter, inverse_list):
   result = ""
   if totalistic_num == "0":
      if bs == "0":
          result = "Sorry - not ready for B0 rules yet..."
      else:
          result = "ruleTab[mME] = 1;"+"\n" 
   elif totalistic_num == "8":
     result = "ruleTab[mNW+mNN+mNE+mWW+mME+mEE+mSW+mSS+mSE+mME] = 1;" + "\n"        
   elif notation_letter != "none":
      myinput = convertorder(totalistic_num, notation_letter)
      result =  create_isotropy_rows(isotropy(myinput[0],myinput[1],myinput[2],myinput[3],myinput[4],myinput[5],myinput[6],myinput[7],myinput[8]), bs)


   elif inverse_list != []:
      for i in notationdict: 
         if not (i[1] in inverse_list) and i.startswith(totalistic_num):
             myinput = convertorder(totalistic_num, i.replace(totalistic_num, ""))
             result = result+ create_isotropy_rows(isotropy(myinput[0],myinput[1],myinput[2],myinput[3],myinput[4],myinput[5],myinput[6],myinput[7],myinput[8]), bs)   
   else: 
      for i in notationdict:
         if i.startswith(totalistic_num):
             myinput = convertorder(totalistic_num, i.replace(totalistic_num, ""))
             result = result + create_isotropy_rows(isotropy(myinput[0],myinput[1],myinput[2],myinput[3],myinput[4],myinput[5],myinput[6],myinput[7],myinput[8]), bs)   
   return result



import golly

CR = chr(13)
LF = chr(10)




rulestring = golly.getstring(dialog_box_message, "B2a/S12") 


# The following code cleans up the rulestring
# so that it makes a valid and somewhat readable file name - eg "B2-a_S12.table"

rulestring = rulestring.replace(" ", "")
rulestring = rulestring.lower()
rulestring = rulestring.replace("b", "B")
rulestring = rulestring.replace("s", "S")

# The variable named rulestring will be parsed.  
# The variable named rule_name will be the name of the new file.
# Valid rules contain a slash character but filenames can not include slashes.

rule_name = rulestring.replace("/", "_")  

# To do:  Allow the user to specify their own name for a rule.

#  The following code cleans up the rule string to 
#  make life easier for the parser.

if rulestring.startswith("B") or rulestring.startswith("S"):
    rulestring = rulestring.replace("/", "")
else:
    rulestring = rulestring.replace("/", "B")

rulestring = rulestring + "\n"  

# Lets make a new file

f = open(golly.getdir("rules")+"gfind-table"+rule_name+".txt", "w")

# Now create the header for the rule table


# Now that the header for the rule table has been created, 
# parse the rulestring, and add rows to the ruleTable as we go.

# Lets say rule strings contain "rule elements", such as B2i, or B2-a, which are composed of: 
# 1) a birth or survival flag 
# 2) a "totalistic context" consisting of an integer between zero and 8
# 3) a "notation_letter".   
# 4) a flag for "positive" or "inverse" notation

bs = "mME"                        # Use "mME" for survival or "BIRTH" for birth
totalistic_context = "none"      # "none" will be replaced with "0" through
                                 # "8" by the parser.
last_totalistic_context = "none" # Lets the parser remember the previous  
                                 # integer it encountered.
notation_letter = "none"         # "none","a", "e", "i", etc.
positive_or_inverse = "positive" 
inverse_list = []

for x in rulestring:
  if x == "S" or x == "B" or x.isdigit() or x == "\n":
     last_totalistic_context = totalistic_context   
     totalistic_context = x                         
     if last_totalistic_context != "none"  and notation_letter == "none":
         f.write(create_table_row(bs, last_totalistic_context, "none",[]))             
     if last_totalistic_context != "none" and  positive_or_inverse == "inverse":
         f.write(create_table_row(bs, last_totalistic_context, "none", inverse_list))  
     # Now lets get ready to move on to the next character.
     notation_letter = "none"
     inverse_list = []
     positive_or_inverse = "positive"
     if x == "S" or x == "B":
         totalistic_context = "none"
     if x == "S":
         bs = "mME"
     if x == "B": 
         bs = "0"
  elif x == "-":
    positive_or_inverse = "inverse"
  elif x in ["c", "a", "e", "k", "i", "v", "j", "y", "q", "r", "w", "t", "z"] and totalistic_context != "none":
     if positive_or_inverse == "positive":
        notation_letter = x
        f.write(create_table_row(bs, totalistic_context, notation_letter, []))    
     else:
        notation_letter = x
        inverse_list.append(x) 
 

f.flush()
f.close()
golly.show("Created gfind-table"+rule_name+".txt in "+golly.getdir("rules"))




Attachments
SimpleInverseFire-v2.c
(81.55 KiB) Downloaded 867 times

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 21st, 2012, 11:58 am

Alegend wrote:
You look for Hamiltonian paths through the graph
Yes! You are obviously on the road to Damascus (not an attractive destination under present-day circumstances) but I would describe the algorithm differently. (Or perhaps I misunderstood your description.)

gfind isn't looking for a Hamiltonian circuit! Far from it, the aim of the outer de Bruijn graph search is to visit the fewest nodes possible in order to find the shortest circuit(s) which in turn represent the shortest spaceships. If you haven't already read David Eppstein's Searching for Spaceships article, I would strongly suggest that you do so. Even if you have read it before, now that you understand what de Bruijn graphs are, you are better prepared to understand how the algorithms used in gfind work.

As for your c/7 searches, I tried experimenting the other day with the "l98a" search which takes about 12 minutes on my laptop. Unfortunately the variability in the search times, even when using identical parameters, was high enough to mask the effect of trying different search parameters. The general tendency though was that practically anything that I did which has speeded up searches in the past had the opposite effect. My conclusion was this width was far too small to give useful results. I am glad to hear therefore that you were searching "a bit higher" than l100, a lot higher I hope! When I did the l112 (width 8 ) search in 2000 it took just over a day to complete. With a modern computer, l140 (width 10) and even higher should be achievable.

Alegend
Posts: 31
Joined: October 5th, 2009, 3:20 pm

Re: Adapting gfind

Post by Alegend » July 21st, 2012, 1:50 pm

Ah okay. I believe I was trying to do a l126 search, but then again, my 2007 computer is old. Plus, I can't upgrade it. I estimate that it'll be around 45 minutes on my end. Perhaps I should just work on algorithms and code for the time being. XD

Paul Tooke
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Adapting gfind

Post by Paul Tooke » July 22nd, 2012, 2:01 pm

Mostly to EricG:

You *have* been busy! It's nice to see those scripts. I had produced a simple adaption of Tim Hutton's C++ program to convert Alan Hensel's extended rule notation into a Golly rule table, but I suspect most folks would feel more comfortable with a Python script.

I am still surprised that hexagonal neighbourhoods work. I repeated your test with B25/S356H and found the same c/5 spaceship. Then I did What You Mustn't Ever Do with hexagonal rules and created a 'flipped' table with the NW and SE weights 0. I was gobsmacked when the program performed exactly the same as before (in terms of deepening levels and amounts etc.,) and then output the same spaceship flipped about the vertical axis! I'm not sure what is going on here, but my philosophy has always been that anything that gets useful results out of a search program is No Bad Thing.

As for the discrepancy between our Simple Inverse Fire results: do you remember what I told everybody not to do with my bodged code? You are running a much mangled version of gfind version 4.6 whereas my WIP is based on (an otherwise unadulterated copy of) version 4.9. Furthermore, you must have done runs with SEARCHLIMIT set to at least 66 to find that asymmetric width 11 c/3. The default value is 50 and my search was with /l60 which would have found asymmetric c/3 spaceships of width 10 but not width 11 - the maximum width is SEARCHLIMIT/(2*period).

That exploding diagonal spaceship was, as you suspected, down to the fact that I was still finishing off the terminal() code. I just repeated that exact search and got the same results *minus* the false result.

My WIP isn't ready for the public gaze yet - next I have to consider how to handle the code which decides which speeds and symmetry modes to search. This is much more complicated in non-totalistic rules!

Thanks for the continued feedback on your progress, it is really helpful.

jmgomez
Posts: 43
Joined: October 6th, 2015, 1:42 am

Re: Adapting gfind

Post by jmgomez » March 13th, 2017, 6:42 pm

Hi Eric,

I`m trying to run you program For-gfind-from-HenselNotation.py but this import a golly file, could you tell me please from where I can get the golly file?

Thank you
-Josè Manuel Gómez Soto

User avatar
BlinkerSpawn
Posts: 1992
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Adapting gfind

Post by BlinkerSpawn » March 13th, 2017, 7:51 pm

If you're talking about where it says "import golly as g" then as long as golly can find your Python install then you should be ok.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Adapting gfind

Post by dvgrn » March 13th, 2017, 9:06 pm

BlinkerSpawn wrote:If you're talking about where it says "import golly as g" then as long as golly can find your Python install then you should be ok.
In case this isn't quite clear: a Python script with the header line "import golly..." can only be run from inside Golly, via File > Run Script. If you try to run it via IDLE or the command line, you'll get mysterious errors.

jmgomez
Posts: 43
Joined: October 6th, 2015, 1:42 am

Re: Adapting gfind

Post by jmgomez » March 14th, 2017, 7:59 pm

Thanks,

That was exactly what happened, I was running the script from IDLE.
Running from Golly work ok!

Best the best
-jm

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Adapting gfind

Post by testitemqlstudop » March 10th, 2019, 10:23 am

Sorry for bumping this ancient thread, but I have a problem with ntgfind.

When I run the Hensel-to-Ruletable converter with the rule B2c3aei4ajnr5acn/S2-ci3-ck4in5jkq6c7c (x3vi), I get this:

Code: Select all

ruleTab[mNE +  mSE + 0] = 1;
ruleTab[mNW + mSW + 0] = 1;
ruleTab[mNE +  mSE + 0] = 1;
ruleTab[mSW + mSE + 0] = 1;
ruleTab[mNW + mNE +  0] = 1;
ruleTab[mSW + mSE + 0] = 1;
ruleTab[mNW + mSW + 0] = 1;
ruleTab[mNW + mNE +  0] = 1;
ruleTab[mNN + mNE +  mEE +   0] = 1;
ruleTab[mNW + mNN + mWW + 0] = 1;
ruleTab[mEE +   mSS +  mSE + 0] = 1;
ruleTab[mWW + mSW + mSS +  0] = 1;
ruleTab[mNN + mNE +  mEE +   0] = 1;
ruleTab[mEE +   mSS +  mSE + 0] = 1;
ruleTab[mWW + mSW + mSS +  0] = 1;
ruleTab[mNW + mNN + mWW + 0] = 1;
ruleTab[mNN + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mSS +  0] = 1;
ruleTab[mNN + mEE +   mSS +  0] = 1;
ruleTab[mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mEE +   0] = 1;
ruleTab[mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mSS +  0] = 1;
ruleTab[mNN + mWW + mEE +   0] = 1;
ruleTab[mNW + mNN + mNE +  0] = 1;
ruleTab[mNW + mNN + mNE +  0] = 1;
ruleTab[mSW + mSS +  mSE + 0] = 1;
ruleTab[mNW + mWW + mSW + 0] = 1;
ruleTab[mNE +  mEE +   mSE + 0] = 1;
ruleTab[mNE +  mEE +   mSE + 0] = 1;
ruleTab[mSW + mSS +  mSE + 0] = 1;
ruleTab[mNW + mWW + mSW + 0] = 1;
ruleTab[mNN + mNE +  mEE +   mSE + 0] = 1;
ruleTab[mNW + mNN + mWW + mSW + 0] = 1;
ruleTab[mNE +  mEE +   mSS +  mSE + 0] = 1;
ruleTab[mWW + mSW + mSS +  mSE + 0] = 1;
ruleTab[mNW + mNN + mNE +  mEE +   0] = 1;
ruleTab[mEE +   mSW + mSS +  mSE + 0] = 1;
ruleTab[mNW + mWW + mSW + mSS +  0] = 1;
ruleTab[mNW + mNN + mNE +  mWW + 0] = 1;
ruleTab[mNN + mNE +  mWW + mSS +  0] = 1;
ruleTab[mNW + mNN + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mSS +  mSE + 0] = 1;
ruleTab[mNN + mWW + mEE +   mSW + 0] = 1;
ruleTab[mNE +  mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mEE +   mSE + 0] = 1;
ruleTab[mNN + mEE +   mSW + mSS +  0] = 1;
ruleTab[mNW + mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mNE +  mSW + mSE + 0] = 1;
ruleTab[mNW + mNN + mSW + mSE + 0] = 1;
ruleTab[mNW + mNE +  mSS +  mSE + 0] = 1;
ruleTab[mNE +  mWW + mSW + mSE + 0] = 1;
ruleTab[mNW + mNE +  mEE +   mSW + 0] = 1;
ruleTab[mNW + mEE +   mSW + mSE + 0] = 1;
ruleTab[mNW + mNE +  mSW + mSS +  0] = 1;
ruleTab[mNW + mNE +  mWW + mSE + 0] = 1;
ruleTab[mNW + mWW + mSW + mSS +  mSE + 0] = 1;
ruleTab[mNE +  mEE +   mSW + mSS +  mSE + 0] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mSW + 0] = 1;
ruleTab[mNW + mNN + mNE +  mEE +   mSE + 0] = 1;
ruleTab[mNW + mWW + mSW + mSS +  mSE + 0] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mSW + 0] = 1;
ruleTab[mNW + mNN + mNE +  mEE +   mSE + 0] = 1;
ruleTab[mNE +  mEE +   mSW + mSS +  mSE + 0] = 1;
ruleTab[mNW + mNN + mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mNE +  mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mEE +   mSW + mSS +  0] = 1;
ruleTab[mNW + mNN + mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mEE +   mSS +  mSE + 0] = 1;
ruleTab[mNN + mNE +  mWW + mEE +   mSS +  0] = 1;
ruleTab[mNN + mWW + mEE +   mSS +  mSE + 0] = 1;
ruleTab[mNN + mWW + mEE +   mSW + mSS +  0] = 1;
ruleTab[mNE +  mSW + mME] = 1;
ruleTab[mNW + mSE + mME] = 1;
ruleTab[mNW + mSE + mME] = 1;
ruleTab[mNE +  mSW + mME] = 1;
ruleTab[mNE +  mSW + mME] = 1;
ruleTab[mNW + mSE + mME] = 1;
ruleTab[mNE +  mSW + mME] = 1;
ruleTab[mNW + mSE + mME] = 1;
ruleTab[mNN + mEE +   mME] = 1;
ruleTab[mNN + mWW + mME] = 1;
ruleTab[mEE +   mSS +  mME] = 1;
ruleTab[mWW + mSS +  mME] = 1;
ruleTab[mNN + mEE +   mME] = 1;
ruleTab[mEE +   mSS +  mME] = 1;
ruleTab[mWW + mSS +  mME] = 1;
ruleTab[mNN + mWW + mME] = 1;
ruleTab[mNN + mNE +  mME] = 1;
ruleTab[mNW + mNN + mME] = 1;
ruleTab[mSS +  mSE + mME] = 1;
ruleTab[mWW + mSW + mME] = 1;
ruleTab[mNE +  mEE +   mME] = 1;
ruleTab[mEE +   mSE + mME] = 1;
ruleTab[mSW + mSS +  mME] = 1;
ruleTab[mNW + mWW + mME] = 1;
ruleTab[mNN + mSE + mME] = 1;
ruleTab[mNN + mSW + mME] = 1;
ruleTab[mNE +  mSS +  mME] = 1;
ruleTab[mWW + mSE + mME] = 1;
ruleTab[mNW + mEE +   mME] = 1;
ruleTab[mEE +   mSW + mME] = 1;
ruleTab[mNW + mSS +  mME] = 1;
ruleTab[mNE +  mWW + mME] = 1;
ruleTab[mNN + mNE +  mSS +  mME] = 1;
ruleTab[mNW + mNN + mSS +  mME] = 1;
ruleTab[mNN + mSS +  mSE + mME] = 1;
ruleTab[mWW + mEE +   mSW + mME] = 1;
ruleTab[mNE +  mWW + mEE +   mME] = 1;
ruleTab[mWW + mEE +   mSE + mME] = 1;
ruleTab[mNN + mSW + mSS +  mME] = 1;
ruleTab[mNW + mWW + mEE +   mME] = 1;
ruleTab[mNN + mSW + mSE + mME] = 1;
ruleTab[mNN + mSW + mSE + mME] = 1;
ruleTab[mNW + mNE +  mSS +  mME] = 1;
ruleTab[mNE +  mWW + mSE + mME] = 1;
ruleTab[mNW + mEE +   mSW + mME] = 1;
ruleTab[mNW + mEE +   mSW + mME] = 1;
ruleTab[mNW + mNE +  mSS +  mME] = 1;
ruleTab[mNE +  mWW + mSE + mME] = 1;
ruleTab[mNN + mNE +  mSW + mME] = 1;
ruleTab[mNW + mNN + mSE + mME] = 1;
ruleTab[mNW + mSS +  mSE + mME] = 1;
ruleTab[mNE +  mWW + mSW + mME] = 1;
ruleTab[mNE +  mEE +   mSW + mME] = 1;
ruleTab[mNW + mEE +   mSE + mME] = 1;
ruleTab[mNE +  mSW + mSS +  mME] = 1;
ruleTab[mNW + mWW + mSE + mME] = 1;
ruleTab[mNN + mNE +  mSE + mME] = 1;
ruleTab[mNW + mNN + mSW + mME] = 1;
ruleTab[mNE +  mSS +  mSE + mME] = 1;
ruleTab[mWW + mSW + mSE + mME] = 1;
ruleTab[mNW + mNE +  mEE +   mME] = 1;
ruleTab[mEE +   mSW + mSE + mME] = 1;
ruleTab[mNW + mSW + mSS +  mME] = 1;
ruleTab[mNW + mNE +  mWW + mME] = 1;
ruleTab[mNN + mNE +  mWW + mME] = 1;
ruleTab[mNW + mNN + mEE +   mME] = 1;
ruleTab[mWW + mSS +  mSE + mME] = 1;
ruleTab[mNN + mWW + mSW + mME] = 1;
ruleTab[mNE +  mEE +   mSS +  mME] = 1;
ruleTab[mNN + mEE +   mSE + mME] = 1;
ruleTab[mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNW + mWW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mNE +  mME] = 1;
ruleTab[mNW + mNN + mNE +  mME] = 1;
ruleTab[mSW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mWW + mSW + mME] = 1;
ruleTab[mNE +  mEE +   mSE + mME] = 1;
ruleTab[mNE +  mEE +   mSE + mME] = 1;
ruleTab[mSW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mWW + mSW + mME] = 1;
ruleTab[mNN + mNE +  mEE +   mME] = 1;
ruleTab[mNW + mNN + mWW + mME] = 1;
ruleTab[mEE +   mSS +  mSE + mME] = 1;
ruleTab[mWW + mSW + mSS +  mME] = 1;
ruleTab[mNN + mNE +  mEE +   mME] = 1;
ruleTab[mEE +   mSS +  mSE + mME] = 1;
ruleTab[mWW + mSW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mWW + mME] = 1;
ruleTab[mNN + mEE +   mSS +  mME] = 1;
ruleTab[mNN + mWW + mSS +  mME] = 1;
ruleTab[mNN + mEE +   mSS +  mME] = 1;
ruleTab[mWW + mEE +   mSS +  mME] = 1;
ruleTab[mNN + mWW + mEE +   mME] = 1;
ruleTab[mWW + mEE +   mSS +  mME] = 1;
ruleTab[mNN + mWW + mSS +  mME] = 1;
ruleTab[mNN + mWW + mEE +   mME] = 1;
ruleTab[mNN + mNE +  mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mSW + mSS +  mME] = 1;
ruleTab[mNN + mNE +  mSS +  mSE + mME] = 1;
ruleTab[mWW + mEE +   mSW + mSE + mME] = 1;
ruleTab[mNW + mNE +  mWW + mEE +   mME] = 1;
ruleTab[mWW + mEE +   mSW + mSE + mME] = 1;
ruleTab[mNW + mNN + mSW + mSS +  mME] = 1;
ruleTab[mNW + mNE +  mWW + mEE +   mME] = 1;
ruleTab[mNW + mEE +   mSW + mSS +  mSE + mME] = 1;
ruleTab[mNE +  mWW + mSW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mNE +  mEE +   mSW + mME] = 1;
ruleTab[mNW + mNE +  mEE +   mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mWW + mSW + mSE + mME] = 1;
ruleTab[mNW + mNE +  mWW + mSW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mSE + mME] = 1;
ruleTab[mNN + mNE +  mEE +   mSW + mSE + mME] = 1;
ruleTab[mNW + mNE +  mWW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mNE +  mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNN + mNE +  mWW + mSW + mSE + mME] = 1;
ruleTab[mNW + mNN + mEE +   mSW + mSE + mME] = 1;
ruleTab[mNW + mNE +  mWW + mSS +  mSE + mME] = 1;
ruleTab[mNN + mNE +  mWW + mSW + mSE + mME] = 1;
ruleTab[mNW + mNN + mEE +   mSW + mSE + mME] = 1;
ruleTab[mNW + mNE +  mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNW + mWW + mEE +   mSS +  mSE + mME] = 1;
ruleTab[mNE +  mWW + mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNN + mNE +  mWW + mEE +   mSW + mME] = 1;
ruleTab[mNW + mNN + mEE +   mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mWW + mSS +  mSE + mME] = 1;
ruleTab[mNN + mNE +  mWW + mSW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mWW + mEE +   mSE + mME] = 1;
ruleTab[mNN + mNE +  mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mWW + mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNN + mNE +  mWW + mEE +   mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mWW + mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mEE +   mSS +  mME] = 1;
ruleTab[mNN + mWW + mEE +   mSW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mEE +   mSS +  mME] = 1;
ruleTab[mNN + mNE +  mWW + mEE +   mSS +  mSE + mME] = 1;
ruleTab[mNN + mWW + mEE +   mSW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mWW + mEE +   mSW + mSS +  mSE + mME] = 1;
ruleTab[mNN + mNE +  mWW + mEE +   mSW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mEE +   mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mWW + mEE +   mSW + mSS +  mSE + mME] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mEE +   mSW + mSS +  mME] = 1;
ruleTab[mNW + mNN + mNE +  mWW + mEE +   mSS +  mSE + mME] = 1;
ruleTab[mNN + mNE +  mWW + mEE +   mSW + mSS +  mSE + mME] = 1;
However, when I run "./ntgfind B3/S23/O2/U" to rediscover this rule's period-2 spaceship as a test, I get this:

Code: Select all

gfind 4.9, D. Eppstein, 20 August 2011
Just Friends kludge by Paul Tooke
Rule: B3/S23/O2/U
Constructing c/2 edge filters... found 10507/65536 patterns
Searching for speed c/2, width 23, bilateral symmetry.

x = 5, y = 4, rule = B3/S23
obobo$2ob2o$5o$2bo!

Searching for speed 2c/4, width 11, bilateral symmetry.
Searching for speed 3c/6, width 7, bilateral symmetry.
Search complete.
The result, "obobo$2ob2o$5o$2bo!", isn't even close:

Code: Select all

x = 5, y = 4, rule = B2c3aei4ajnr5acn/S2-ci3-ck4in5jkq6c7c
obobo$2ob2o$5o$2bo!
How do I fix this?

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Adapting gfind

Post by wildmyron » March 10th, 2019, 10:53 am

This thread hasn't been updated with recent info in a long time...

EricG's script uses a previous version of Hensel notation. To use that script (without modification) you need to modify the rulestring by swapping 'r' and 'y' wherever they appear and replace 'n' with 'v'. Additionally, there's a bug in the script with S8 - the ruletab line for S8 includes two copies of mMe. If you do use it with such a rule you need to either modify the script first or edit the appropriate line in the ruletable.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Adapting gfind

Post by LaundryPizza03 » August 6th, 2019, 4:16 am

I think the next step is adding direct support of non-totalistic rules to ntgfind by merging the rule-generation table into the main program, preferably with the updated Hensel notation used by Golly.

I can't post the fixed For-gfind-from-HenselNotation.py script because I don't have the necessary copyright permissions, but I can describe how the changes may be carried out:
  1. Find the notationdict and change all instances of r to y, and vice versa. (This will be indicated in the comments.) Also change instances of v to n, e.g. 2v -> 2n.
  2. Go to the very bottom of the program and remove the second instance of mME underneath "elif totalistic_num == "8":".
  3. Update the comments and associated trinkets accordingly.
The main component of the ntgfind program will require some new code for parsing Hensel notation, and maybe even MAP codes, and storing the ruletable as a non-hardcoded variable.

My main motivation for writing this post is that the latest gfind hack is too cumbersome to be practical for exploring very large numbers of rules, as I and most other people likely do at OCA, and because ntzfind is extremely memory-intensive and doesn't support dumping anymore. Someone somewhere (possibly in this thread or the 5s thread) also mentioned an idea of a script that combines with ntgfind or a similar program to search large rulespaces for a spaceship of a particular speed, 9c/10 orthogonal in particular, though such programs are rather unreliable at relativistic speeds. Should I use the version in the OP in the meantime?

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

Post Reply