Adapting gfind

For scripts to aid with computation or simulation in cellular automata.
wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Adapting gfind

Post by wildmyron » August 9th, 2019, 12:54 am

I think it's clear what needs to be done with gfind to support nt rules - just that nobody other than Paul Tooke has decided to put in the effort to do so (and publish the result of that effort).
LaundryPizza03 wrote:Should I use the version in the OP in the meantime?
Considering how long we've all been waiting for someone else to do this, I'd say yes. :P
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: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Adapting gfind

Post by LaundryPizza03 » August 10th, 2019, 3:23 am

wildmyron wrote:I think it's clear what needs to be done with gfind to support nt rules - just that nobody other than Paul Tooke has decided to put in the effort to do so (and publish the result of that effort).
LaundryPizza03 wrote:Should I use the version in the OP in the meantime?
Considering how long we've all been waiting for someone else to do this, I'd say yes. :P
Which version of Hensel notation does it use?

EDIT: Also, how do I compile it?

Code: Select all

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

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

Re: Adapting gfind

Post by wildmyron » August 13th, 2019, 8:33 am

Sorry, I think I wasn't entirely clear. Paul Tooke hasn't published the work he did on adapting gfind for non-totalistic rules (at least not that I'm aware of and definitely not here).
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: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Adapting gfind

Post by LaundryPizza03 » August 13th, 2019, 8:46 pm

wildmyron wrote:Sorry, I think I wasn't entirely clear. Paul Tooke hasn't published the work he did on adapting gfind for non-totalistic rules (at least not that I'm aware of and definitely not here).
I mean the script in the OP, gfind-pt.c.

Code: Select all

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

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

Re: Adapting gfind

Post by wildmyron » August 13th, 2019, 10:30 pm

LaundryPizza03 wrote:
wildmyron wrote:Sorry, I think I wasn't entirely clear. Paul Tooke hasn't published the work he did on adapting gfind for non-totalistic rules (at least not that I'm aware of and definitely not here).
I mean the script in the OP, gfind-pt.c.
Sorry, I misunderstood. To compile gfind-pt.c under Cygwin or "Linux on WSL" you should comment out the defines for PATCH01 and PATCH02 and use something like the following command to compile:

Code: Select all

gcc -O3 -funroll-loops -march=native -o gfind-pt gfind-pt.c
Also, looking over the thread it seems I've misremembered. Paul Tooke did of couse publish his kludged Just Friends version of gfind, it was a more generalized NT version of gfind which hasn't been published.
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: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Adapting gfind

Post by LaundryPizza03 » August 14th, 2019, 1:04 am

wildmyron wrote:
LaundryPizza03 wrote:
wildmyron wrote:Sorry, I think I wasn't entirely clear. Paul Tooke hasn't published the work he did on adapting gfind for non-totalistic rules (at least not that I'm aware of and definitely not here).
I mean the script in the OP, gfind-pt.c.
Sorry, I misunderstood. To compile gfind-pt.c under Cygwin or "Linux on WSL" you should comment out the defines for PATCH01 and PATCH02 and use something like the following command to compile:

Code: Select all

gcc -O3 -funroll-loops -march=native -o gfind-pt gfind-pt.c
Also, looking over the thread it seems I've misremembered. Paul Tooke did of couse publish his kludged Just Friends version of gfind, it was a more generalized NT version of gfind which hasn't been published.
I still can't compile it. What do -funroll and -loops do?

Code: Select all

gfind-pt.c:482:12: warning: format string is not a string literal
      (potentially insecure) [-Wformat-security]
    printf(timeStr);
           ^~~~~~~
gfind-pt.c:482:12: note: treat the string as an argument to avoid this
    printf(timeStr);
           ^
           "%s", 
gfind-pt.c:491:35: warning: implicitly declaring library function 'memset' with
      type 'void *(void *, int, unsigned long)'
      [-Wimplicit-function-declaration]
void resetHash() { if (hash != 0) memset(hash,0,4*HASHSIZE); }
                                  ^
gfind-pt.c:491:35: note: include the header <string.h> or explicitly provide a
      declaration for 'memset'
gfind-pt.c:610:31: warning: '&&' within '||' [-Wlogical-op-parentheses]
                if (x >= qTail || !EMPTY(x) && PARENT(x) >= y) y = x;
                               ~~ ~~~~~~~~~~^~~~~~~~~~~~~~~~~
gfind-pt.c:610:31: note: place parentheses around the '&&' expression to silence
      this warning
                if (x >= qTail || !EMPTY(x) && PARENT(x) >= y) y = x;
                                            ^
                                  (                          )
gfind-pt.c:629:54: warning: format specifies type 'int' but the argument has
      type 'node' (aka 'unsigned long') [-Wformat]
                printf("Exceeded %d node limit, search aborted\n", QSIZE);
                                 ~~                                ^~~~~
                                 %lu
gfind-pt.c:364:15: note: expanded from macro 'QSIZE'
#define QSIZE ((node) (1<<qBits))
              ^~~~~~~~~~~~~~~~~~~
gfind-pt.c:810:15: warning: using the result of an assignment as a condition
      without parentheses [-Wparentheses]
        if (fp=fopen(dumpFile,"r"))
            ~~^~~~~~~~~~~~~~~~~~~~
gfind-pt.c:810:15: note: place parentheses around the assignment to silence this
      warning
        if (fp=fopen(dumpFile,"r"))
              ^
            (                     )
gfind-pt.c:810:15: note: use '==' to turn this assignment into an equality
      comparison
        if (fp=fopen(dumpFile,"r"))
              ^
              ==
gfind-pt.c:824:23: warning: format specifies type 'unsigned int' but the
      argument has type 'unsigned long' [-Wformat]
    fprintf(fp,"%u\n",FILEVERSION);
                ~~    ^~~~~~~~~~~
                %lu
gfind-pt.c:791:21: note: expanded from macro 'FILEVERSION'
#define FILEVERSION ((unsigned long) 2000102901)
                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
gfind-pt.c:836:23: warning: format specifies type 'unsigned int' but the
      argument has type 'unsigned long' [-Wformat]
    fprintf(fp,"%u\n",qHead-qStart);
                ~~    ^~~~~~~~~~~~
                %lu
gfind-pt.c:837:23: warning: format specifies type 'unsigned int' but the
      argument has type 'unsigned long' [-Wformat]
    fprintf(fp,"%u\n",qEnd-qStart);
                ~~    ^~~~~~~~~~~
                %lu
gfind-pt.c:858:16: warning: format specifies type 'int' but the argument has
      type 'long' [-Wformat]
                printf("%d", n);
                        ~~   ^
                        %ld
gfind-pt.c:862:29: warning: format specifies type 'int' but the argument has
      type 'long' [-Wformat]
        if (n >= 100) printf("%d", n/10);
                              ~~   ^~~~
                              %ld
gfind-pt.c:863:23: warning: format specifies type 'int' but the argument has
      type 'long' [-Wformat]
        else printf("%d.%d", n/10, n%10);
                     ~~      ^~~~
                     %ld
gfind-pt.c:863:29: warning: format specifies type 'int' but the argument has
      type 'long' [-Wformat]
        else printf("%d.%d", n/10, n%10);
                        ~~         ^~~~
                        %ld
gfind-pt.c:1220:30: warning: operator '<<' has lower precedence than '+'; '+'
      will be evaluated first [-Wshift-op-parentheses]
                                srows[i] = r << MAXWIDTH + 1;
                                             ~~ ~~~~~~~~~^~~
gfind-pt.c:1220:30: note: place parentheses around the '+' expression to silence
      this warning
                                srows[i] = r << MAXWIDTH + 1;
                                                ~~~~~~~~~^~~
13 warnings generated.
Undefined symbols for architecture x86_64:
  "_enqueue", referenced from:
      _doCompactPart2 in gfind-pt-00bdf1.o
      _findPaths in gfind-pt-00bdf1.o
      _search in gfind-pt-00bdf1.o
  "_isVisited", referenced from:
      _findPaths in gfind-pt-00bdf1.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

Code: Select all

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

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

Re: Adapting gfind

Post by wildmyron » August 14th, 2019, 3:43 am

Oh, for clang you need to change function definitions with "inline" to "static inline". Eg:

change

Code: Select all

inline long hashFunction(node b, row r) {
to

Code: Select all

static inline long hashFunction(node b, row r) {
and the same for all the other function definitions with inline. Ref: http://conwaylife.com/forums/viewtopic. ... 612#p29612 and https://github.com/conwaylife/gfind/com ... b58fe57b67 for example of this change applied to the original gfind.c

"-funroll-loops" is an optimization flag. I'm not sure that it helps with gfind performance so you can safely omit it from the compile command.
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: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Adapting gfind

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

So how do I run a non-totalistic rule?

EDIT1: And how do I process the dump files?

EDIT2: I've figured out how to dump files.

Code: Select all

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

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

Re: Adapting gfind

Post by wildmyron » August 16th, 2019, 12:23 pm

LaundryPizza03 wrote:So how do I run a non-totalistic rule?
You can't run searches in non-totalistic rules with gfind-pt.c without modification, i.e. combining the "latest gfind hack" EricG with the patches to gfind in gfind-pt.c

I'm confused why you are asking this question, but I guess I haven't been clear.
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: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Adapting gfind

Post by LaundryPizza03 » March 25th, 2020, 1:44 am

I notice that gfind-pt does not support rules with B0.

Code: Select all

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

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

Re: Adapting gfind

Post by LaundryPizza03 » August 3rd, 2020, 6:36 am

Note: For those interested in modding gfind for NT rules, the latest version of gfind (v4.9, August 2011) is available here. As Paul Tooke's hack of 4.6 doesn't support B0 rules and lacks the bugfixes made in 4.9, I'd recommend starting with v4.9.

Code: Select all

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

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

Re: Adapting gfind

Post by LaundryPizza03 » April 28th, 2021, 10:26 am

In macOS Big Sur I can't compile gfind-pt because of the following error from code in PATCH07:

Code: Select all

gfind-pt.c:491:35: error: implicitly declaring library function 'memset' with
      type 'void *(void *, int, unsigned long)'
      [-Werror,-Wimplicit-function-declaration]
void resetHash() { if (hash != 0) memset(hash,0,4*HASHSIZE); }

Code: Select all

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

User avatar
ihatecorderships
Posts: 309
Joined: April 11th, 2021, 12:54 pm
Location: Falls Church, VA

Re: Adapting gfind

Post by ihatecorderships » May 21st, 2021, 2:54 pm

What does the level parameter mean?

Also, are there any other parameters I can enter except the speed and the level?

Edit: How can I search oblique or diagonal spaceships, or with different symmetries?
Basically, could someone give me a summary of all the parameters?
-- Kalan Warusa
Don't drink and drive, think and derive.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Adapting gfind

Post by Sokwe » May 21st, 2021, 8:14 pm

ihatecorderships wrote:
May 21st, 2021, 2:54 pm
What does the level parameter mean?

Also, are there any other parameters I can enter except the speed and the level?

Edit: How can I search oblique or diagonal spaceships, or with different symmetries?
Basically, could someone give me a summary of all the parameters?
Run gfind with 'c' as the only parameter to get a summary of all the parameters.
-Matthias Merzenich

User avatar
ihatecorderships
Posts: 309
Joined: April 11th, 2021, 12:54 pm
Location: Falls Church, VA

Re: Adapting gfind

Post by ihatecorderships » May 21st, 2021, 8:21 pm

Hmm, using c as the only parameter doesn't seem to work.
-- Kalan Warusa
Don't drink and drive, think and derive.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Adapting gfind

Post by Sokwe » May 21st, 2021, 9:09 pm

ihatecorderships wrote:
May 21st, 2021, 8:21 pm
Hmm, using c as the only parameter doesn't seem to work.
If that doesn't work, then I don't see how gfind could be working at all. What does the output look like? Here's what I get when I run gfind-pt with 'c' as the only parameter:

Code: Select all

gfind 4.6, D. Eppstein, 10 February 2001
Rule: c
usage: gfind rule/options
  e.g. gfind B3/S23/D4/O2 finds c/4 diagonal gliders
  and c/2 orthogonal spaceships in Conway's life.

available options:
  /dNN searches for diagonal gliders with periods in NN
  /oNN searches for orthogonal gliders with periods in NN
  /nNN searches for gliders that move steps in NN every period

  /xNN disallows patterns with live NN-neighbor cells
  /zNN disallows patterns with dead NN-neighbor cells

  /lNN limits the search to graphs of 2^NN vertices, i.e.
       to widths for which period*width*2 <= NN (default 50)

  /fNN stop after NN gliders found (best in combination with /h0)
  /hNN sets the hash table size to 2^NN (default 21)
       Use /h0 to disable duplicate elimination.
  /qNN sets the BFS queue size to 2^NN (default 23)
  /iNN groups 2^NN queue entries to an index node (default 4)
  /*NN performs depth first iterated deepening when 2^NN leaves in queue
  /-NN reduces width when iterated deepening level reaches NN
  /eNN set minimum deepening increment to NN (default=period)
  /r   reverses search order of pattern rows

  /a   searches for asymmetric patterns
  /g   searches for glide-reflect patterns only
  /u   searches for odd bilaterally symmetric patterns
  /v   searches for even bilaterally symmetric patterns
  /w   searches for symmetric or skew-symmetric patterns with gutters
  /k   searchs for knights move patterns

  /p   dumps program state to file after each deepening
  /j   dumps program state at start of search
"gfind command file" reloads the state from the specified file
and performs the command. Available commands:
  s    resumes search from the loaded state
  h    searches only the head (first half) of the BFS queue
  t    searches only the tail (second half) of the BFS queue
  p    previews partial results
-Matthias Merzenich

User avatar
ihatecorderships
Posts: 309
Joined: April 11th, 2021, 12:54 pm
Location: Falls Church, VA

Re: Adapting gfind

Post by ihatecorderships » May 21st, 2021, 9:47 pm

I think it's because I'm using the precompiled windows version, and that just closes, but thanks for the list of parameters.
-- Kalan Warusa
Don't drink and drive, think and derive.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Adapting gfind

Post by Sokwe » May 21st, 2021, 10:33 pm

ihatecorderships wrote:
May 21st, 2021, 9:47 pm
I think it's because I'm using the precompiled windows version, and that just closes, but thanks for the list of parameters.
A precompiled version shouldn't work fundamentally differently than a version you compile yourself. gfind is a command line tool, so it should be run from the Windows command line interpreter.
-Matthias Merzenich

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

Re: Adapting gfind

Post by LaundryPizza03 » June 7th, 2021, 10:50 am

LaundryPizza03 wrote:
April 28th, 2021, 10:26 am
In macOS Big Sur I can't compile gfind-pt because of the following error from code in PATCH07:

Code: Select all

gfind-pt.c:491:35: error: implicitly declaring library function 'memset' with
      type 'void *(void *, int, unsigned long)'
      [-Werror,-Wimplicit-function-declaration]
void resetHash() { if (hash != 0) memset(hash,0,4*HASHSIZE); }
I still haven't received a response about how to resolve this issue.

Code: Select all

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

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Adapting gfind

Post by Sokwe » June 7th, 2021, 5:45 pm

LaundryPizza03 wrote:
June 7th, 2021, 10:50 am
LaundryPizza03 wrote:
April 28th, 2021, 10:26 am
In macOS Big Sur I can't compile gfind-pt because of the following error from code in PATCH07:

Code: Select all

gfind-pt.c:491:35: error: implicitly declaring library function 'memset' with
      type 'void *(void *, int, unsigned long)'
      [-Werror,-Wimplicit-function-declaration]
void resetHash() { if (hash != 0) memset(hash,0,4*HASHSIZE); }
I still haven't received a response about how to resolve this issue.
Add the following line at around line 248:

Code: Select all

#include <string.h>
However, the part of the code referenced in the error has nothing to do with PATCH07, so I don't know why you mentioned it.

Also, I recommend disabling PATCH04 by commenting out line 149. This allows searches above logical-width 14 (up to 28).
-Matthias Merzenich

User avatar
May13
Posts: 787
Joined: March 11th, 2021, 8:33 am

Re: Adapting gfind

Post by May13 » December 19th, 2021, 5:50 am

gfind and gfind-pt both seems to be buggy.
1. B0 (gfind v4.9 bug, impossible to run gfind-pt)
gfind returned weird pattern instead of spaceship:

Code: Select all

gfind 4.9, D. Eppstein, 20 August 2011
Rule: B013456/S23456o4uv/n3/l88
Searching for speed 3c/4, width 21, bilateral symmetry.

x = 21, y = 9, rule = B013456/S23456
21o$21o$21o$o3b13o3bo$21o$o3b13o3bo$21o$21o$21o!

Search complete.
2. Bug with symmetric searches (gfind-pt, doesn't appears in gfind v4.9)
./gfind-pt B3/S245/o5v/n2/l80/f1 returns 2c/5 spaceship but
./gfind-pt B3/S245/o5uv/n2/l80/f1 doesn't.
3. Bug in B2 rulespace (both gfind v4.9 and gfind-pt)
This spaceship doesn't appears:

Code: Select all

x = 10, y = 23, rule = B24567/S
3bo2bo2$3bo2b2o2$7b2o2$7bo2$5b4o2$7b3o$4bo$7bo$7obo2$4b3o2$5bo2$6bo2$b
4o!
So c/2o's was unknown in 32 rules (B2456/S2:B245678/S678) for more than 20 years of the gfind's existence!
4. Getting stuck (gfind v4.9, doesn't appears in gfind-pt)
For example, gfind v4.9 got stuck while searching for this photon:

Code: Select all

x = 32, y = 25, rule = B25678/S0245
12b2o4b2o$11bobob2obobo$10bobo6bobo$12b8o$13b2o2b2o$13bob2obo$10b2ob2o
2b2ob2o$5b2o2bobo2bo2bo2bobo2b2o$4bobobob12obobobo$3bobo2bo14bo2bobo$
2bob2ob3o12b3ob2obo$4bo3bo14bo3bo$4b2o20b2o$2b3o22b3o$bob2o22b2obo$obo
bob2o16b2obobobo$2b2o2bobo14bobo2b2o$3b5obo2b2o4b2o2bob5o$9bobobob2obo
bobo$4b3ob3ob2o4b2ob3ob3o$6bo2b2o3b4o3b2o2bo$5b4obo2b2o2b2o2bob4o$4bo
4bo2bo6bo2bo4bo$8b6o4b6o$7bo6bo2bo6bo!
These bugs are known, I just combined them into one post.
Therefore, someone who wants to create a new modification of gfind should pay attention to these bugs.
The latest version of hex-gliders.db have 668 gliders from OT hexagonal rules. Let's find more!
My CA (13 rules)
My scripts: new-glider.py v0.2 (new version), nbsearch2a.py, collector.py v0.3

Post Reply