Q&A for ptbsearch

[chris_c]

@Chris
1)I made a pull request to your repo. Enhanced ptblist.pl and added some catalysts. (Part of them may be unnecessary) For others, it can be viewed on http://www.github.com/Scorbie/ptbsearch

Yeah, the catalyst files look nice. I didn't get chance to understand what the ptblist.pl stuff was about but I will try soon.

2)survive crashes on one of the inputs I used, but I'm not sure what the problem is. To make things harder, it works when compiled with -g. (Both -g and -O3 -g works)
This

The input file is here:
https://drive.google.com/file/d/0B057ay ... sp=sharing
and survive crashes on

Code: Select all

survive a < g6211

Looks like it is because of buffer overflow. The line corresponding to the pattern below is 2083 characters long which overflows the 'nextpat' buffer by 83 bytes:

Code: Select all

x = 68, y = 49, rule = B3/S23
33bo$33b3o$36bo28b2o$35b2o28bobo$66b2o$62b2o$61bobo$61bo$59bobo$59b2o$
32b2o21b2o$32b2o3b2o16bobo$37bobo16b2o$37bo$29b2o10bo$29b2o$40bo2bo2$
42bo2bo$38b3o$38bo5bo2bo$39bo2bo$46bo2bo$41bo2bo$48bo2bo$43bo2bo$50bo
2bo$45bo2bo$52bo2bo$47bo2bo$54bo2bo$49bo2bo$56bo2bo$51bo2bo$58bo2bo$
53bo2bo$60bo$55bo2bo2$57bo6$3bo$b3o$o$2o!

[Scorbie]

Looks like it is because of buffer overflow. The line corresponding to the pattern below is 2083 characters long which overflows the 'nextpat' buffer by 83 bytes:

Huh. That was really fast. Thank you really much! Maybe that means that we should make 'nextpat' buffer a little larger?

Yeah, the catalyst files look nice. I didn't get chance to understand what the ptblist.pl stuff was about but I will try soon.

Maybe I'll just explain it here to save your time.
ptblist.pl reads the pattern list file (which is often ptb2 output) line by line. Then it runs ptb2 (with only one catalyst) with each of the patterns.
ptblist.pl determines the params to run ptb2 from user input and the ptb2 output file. Specifically, these:

• The user invokes ptblist.pl with ptblist.pl input_file catalyst_file max_gen and the catalyst_file and max_gen is used directly in ptb2.
• Each line of ptb2 output has this format: pattern min_gen_of_interaction and this min_gen_of_interaction is used in ptb2.

The inefficient part I spotted is that even if existing catalysts are damaged, ptblist doesn't know that, so ptblist happily adds catalysts anyway until max_gen specified by the user.

I found a small workaround for this phenomenon. If you do survive [every character used in input] < ptb2_output (| uniq.pl, optional) >new_ptb2_output then survive doesn't filter anything, but it generates additional information. which is: (peeks at readme file)

Code: Select all

<input line> <max #generations fixed part is "damaged" and then restored> \
               <#generations during last "damaged" period> \
               <last generation fixed part was intact> \
               <#cells - fixed part> \
               <final pattern - fixed part>

where the "input line" is the following because it is redirected from ptb2 output file:

Code: Select all

<pattern> <generation of first interaction>

so we can see that we don't have to add catalysts after <last generation fixed part was intact> which is $flds[4] in the script.
So I modified the script so that it compares $flds[4] $ARGV[2] and takes the less of the two, and then runs ptb2 till that generation.

[Scorbie]

What do you think? Are some of them too big?

I don't know. In fact it's hard to say if this kind of thing will make searches faster or not. I profiled the code and the first thing to say is that 98% of the time is spent inside the placeNewPerturbor function.

What this function does is run the current pattern up to MAX_GEN and returns an array of triples (x, y, t) that says "when the perturbor is displaced by (x, y) the interaction begins at time t".

There seem to be two phases to this function. The first phase is just a dumb convolution between the catalyst and the existing pattern. By finding the first time that the catalyst gets within 2 cells of the existing pattern you get a lower bound on the interaction time. The second phase is a more detailed test of interaction and gets rid of things like a glider flying past the edge of a block without any interaction.

Profiling seems to suggest that both phases take around 50% of the time.

Doing a polymerisation should help with the convolution phase because I guess the time taken in this step should be roughly proportional to the size of the perimeter of the catalyst (but that is a completely untested hypothesis).

But in the interaction phase, ptbsearch generates the entire catalyst and everything within 2 cells and checks if there is any interaction. It seems like this would lead to quite a bit of unnecessary work in the case of big polymerised catalysts.

I'm not saying I know the answer for definite, but I reckon you should keep things simple until you are sure there is a benefit.

I am thinking of ways to improve this bottleneck. I haven't learned programming in depth, so I'm asking for advice whether or not this has a possibility of making the program faster. What I've thought is this:

1) Cache the whole pattern (without catalysts) from gen 0 to MAX_GEN. For every cell that was on, make a list of generations at which the cell was on.
2) For every catalyst, For every position (that a catalyst may interact with the pattern) see when the surrounding cells get on.
3) Paste the cached pattern in that generation and run a couple of generations. Discard the catalyst at that position if the * cells get damaged.
4) If the catalyst had no effect, get the next gen where the surrounding cells get on and continue (2).

Or... is this precisely how placeNewPerturbor works? This takes 99% of the time? Seriously?

EDIT: if that's the case we could specify "cells that should not be on" near the catalyst and discard that if that is the first cell in the neighborhood to be on.

[Scorbie]

Okay, I made a test suite(Whoops, a misnomer, I guess.) for testing new catalyst components. Unfortunately the scripts are in bash, so if someone wants to use it in windows the one should convert them to a batch file. (And I used 'time' to measure execution time and 'wc' to count the lines in a file, so one should probably find a windows alternative to that, too.)

Prerequisites:

• Place the testsuite folder in the ptbsearch directory. (ptbsearchdir/testsuite)
• Compile the modified ptb2 source (if you are using Windows.)
• Run genrandom.py. It simply generates random soups in Paul Callahan's format (which is used in gencols and ptb2) (You can invoke it either with or without arguments. Look at genrandom.py for instructions.)

cmp.sh
Purpose

• Verify if alternate forms of catalysts does make a program faster.

To Use

• Put the two forms of the catalysts in cat1, cat2.
• Run cmp.sh

Result

• On the console, it will output the time taken in ptb2.
• It will also generate two files, namely cmp_cat1u.life and cmp_cat2u.life. This will show you the perturbations of each form that the other missed.

cat.sh
Purpose

• Find out how often the catalyst does its work.

To Use

• Put the catalysts you want to verify in 'cats' folder.
• Add the catalyst activities you want to screen in 'control' file. (e.g. if you don't want snakelike reactions in the catalysis of a table, add the snake catalyst in the 'control' file)
• Run cat.sh

Result

• On the console, it will output the number of unique reactions of each catalyst. (Reactions not found in catalysts in 'control' file)
• It will generate a bunch of files, all starting with 'uniq_'. These are the actual reactions.

Limitations:
The test suite is based on the programs and scripts in ptbsearch, and thus has the limitations of ptbsearch. Specifically,

• cmp.sh may report two same reactions as different.
• cat.sh may report solutions that should have been filtered by 'control' catalysts.

These are becuase finding out the catalyses in catalyst B and not in catalyst A (done by uniq.pl and survive) currently has false positives. Specifically, it reports false positives if the reactions are the same but the catalyst gets destroyed later. For instance, it will report MikeP's honeyfarm catalyst used merely as a boat if the catalyst gets destroyed later. Another limitation is:

• Both cmp.sh and cat.sh will report no solutions of rock catalysts even though there are unique catalyses.

This is another limitation of ptbsearch, as it discards all reactions with only rock catalysts. Therefore, for example, cat.sh will return 0 results on hook_with_tail, long_hook_with_tail, and eater_hook_with_tail, even though they are pretty versatile as catalysts.

EDIT: Rock catalyst issue is pretty much fixed in testsuite and here's the updated version that uses a burning-hot-new version of ptbsearch

EDIT: Uploaded to Github, Address is https://github.com/Scorbie/ptbtest

[chris_c]

What I've thought is this:

1) Cache the whole pattern (without catalysts) from gen 0 to MAX_GEN. For every cell that was on, make a list of generations at which the cell was on.
2) For every catalyst, For every position (that a catalyst may interact with the pattern) see when the surrounding cells get on.
3) Paste the cached pattern in that generation and run a couple of generations. Discard the catalyst at that position if the * cells get damaged.
4) If the catalyst had no effect, get the next gen where the surrounding cells get on and continue (2).

Or... is this precisely how placeNewPerturbor works?

Yeah that's roughly how placeNewPerturbor works. The main difference is that in step 3 it only runs the pattern for one generation and checks that at least one of the cells on the boundary of the perturbor is different to how it would have been if the perturbor was absent.

This takes 99% of the time? Seriously?

Yeah, pretty sure that function was taking 98% of the time when I last checked.

If that's the case we could specify "cells that should not be on" near the catalyst and discard that if that is the first cell in the neighborhood to be on.

I have thought about doing something like this in the past but I'm not sure it would make things faster. The point is that if 98% of the time is taken by placeNewPerturbor then to make the program significantly faster we either need to speed this function up or make sure that is called a fewer number of times.

Making the placeNewPerturbor function more "clever" surely won't speed it up, but will it mean that it gets called less often? I am sceptical. The reason is that placeNewPerturbor is called once on every call to perturbEnum (the main recursive function in the whole of ptbsearch). But the call to survives inside perturbEnum ensures that we only recurse on perturbors that survive for a decent number of generations on their own.

In summary, the current implementation of placeNewPerturbors is "dumb" and returns all possible perturbor placements no matter how hopeless. Then the call to survives is used to filter out perturbor placements that are obviously bad.

Now if you make placeNewPerturbor more clever so that it throws out more of the hopeless perturbor placements earlier what exactly are you gaining? Not very much I imagine since those extra calls to survive that the "dumb" method uses are already taking <2% of the time.

Okay, I made a test suite...

Looks very interesting but I don't have time to look at the moment. You are the boss when it comes to catalyst selection so I will trust whatever research you come up with.

This is another limitation of ptbsearch, as it discards all reactions with only rock catalysts.

We have a definite reason to fix that issue now. If this branch works for you then I will push it into my main branch soon.

[Scorbie]

If that's the case we could specify "cells that should not be on" near the catalyst and discard that if that is the first cell in the neighborhood to be on.

I have thought about doing something like this in the past but I'm not sure it would make things faster. The point is that if 98% of the time is taken by placeNewPerturbor then to make the program significantly faster we either need to speed this function up or make sure that is called a fewer number of times.

...

In summary, the current implementation of placeNewPerturbors is "dumb" and returns all possible perturbor placements no matter how hopeless. Then the call to survives is used to filter out perturbor placements that are obviously bad.

Now if you make placeNewPerturbor more clever so that it throws out more of the hopeless perturbor placements earlier what exactly are you gaining? Not very much I imagine since those extra calls to survive that the "dumb" method uses are already taking <2% of the time.

Thanks for the explanation. That makes sense. I get that we need to make placeNewPerturbor faster for a speed boost. (Guess that's not easy.)

Okay, I made a test suite...

Looks very interesting but I don't have time to look at the moment. You are the boss when it comes to catalyst selection so I will trust whatever research you come up with.

Thanks. I'll post whatever results that come up to the Patterns thread. I thought it would be interesting to just look at the results. (Pretty surprised to know that MikeP's catalyst occurs pretty often.)

This is another limitation of ptbsearch, as it discards all reactions with only rock catalysts.

We have a definite reason to fix that issue now. If this branch works for you then I will push it into my main branch soon.

Thanks a lot! Will check it out tomorrow.

[Scorbie]

@chris
1) Okay, the rock version was working great with some testing! I haven't tested much, though...
2) And I think this pull request is has both good and bad points:
https://github.com/ceebo/ptbsearch/comm ... 7c825e949a
Bad: It outputs a bunch of useless "Working with perturber (1 to nperturbs)" when running ptblist.pl.
Still it's good to see the messages in ptb2. I guess the ideal stderr printing options would be different for everybody.
3) Merely converting tabs to eight spaces really makes the code much prettier.

Back to the rock fork, unfortunately I couldn't apply the rock fork to the test suite... You could see why on this post.
In short, ptbsearch's duplicate filtering algorithm is rather crude, and fails to remove unwanted results like these:

Code: Select all

x = 14, y = 25, rule = B3/S23
b2ob2obo$o4b4o$7o$2o4b2o$b2o2b3obo$o4b2o$6bobo$b2o2b2o$3o3b4o$bo2bo2b
3o5$12bo$11bobo$11bobo$8bo3bo$8b4o2$8b4o$8bo3bo$11bobo$11bobo$12bo!

(The beehive-with-tail-thing can be replaced by an eater.)

I'll try to modify the code myself. If you are interested in the details, read on.
Okay, I think I got a good fix: wrap these two lines... like this:

Code: Select all

if(restored == 0{
        prodcells = cells.ncells - matchcells.ncells;
        copyLifeList(&cells, &outcells);
}

I think this is how it works:

According to the readme file: survive outputs the following:

Code: Select all

<input line> <max #generations fixed part is "damaged"[1] and then restored> \
               <#generations during last "damaged" period> \
               <last generation fixed part was intact> \
               <#cells - fixed part> \
               <final pattern - fixed part>

And uniq.pl uses the last param as an id to filter out duplicates. That last param simply means "The whole pattern just before the catalyst is demolished - catalyst cells".[2]
Well that does filter out exact duplicates like a block and a transparent block, but it cannot filter out other trivial stator variants like the beehive-with-tail-thing above. All these trivial variants have different sizes and shapes, and thus are demolished in different generations.

Therefore I suggest to change the survive program so that it outputs perhaps, the same (whole pattern - catalyst) except at the generation when the last catalysis is over. I would like to hear what you think regarding this.

[1]Note the wording: "damaged" is not the catalyst being totally wrecked, but rather temporarily damaged and then being restored.
[2]For people who would like to know precisely, the last three params mean:
<last generation ... > simply means just before the catalyst is wrecked.
<#cells - fixed part> is simply the population in that generation.
<final pattern - fixed part> is simply the pattern[/size]

[chris_c]

@chris
1) Okay, the rock version was working great with some testing! I haven't tested much, though...
2) And I think this pull request is has both good and bad points:
https://github.com/ceebo/ptbsearch/comm ... 7c825e949a
Bad: It outputs a bunch of useless "Working with perturber (1 to nperturbs)" when running ptblist.pl.
Still it's good to see the messages in ptb2. I guess the ideal stderr printing options would be different for everybody.
3) Merely converting tabs to eight spaces really makes the code much prettier.

1. Cool. 2. I am willing to revert the commit. It's up to you. 3. Probably a good idea.

Back to the rock fork, unfortunately I couldn't apply the rock fork to the test suite...

Okay, I think I got a good fix: wrap these two lines... like this:

Code: Select all

if(restored == 0{
        prodcells = cells.ncells - matchcells.ncells;
        copyLifeList(&cells, &outcells);
}

Yes, that does look like it should be a pretty good fix. Note that you take the "snapshot" when the catalyst is restored so catalysts that restore at different speeds will give different results even if the active part of the reaction is the same. It might be better to take the snapshot a fixed amount of time after the beginning of the interaction (maybe start + 10?). I can code it that way if you think it would be better.

[Scorbie]

I am willing to revert the commit.

Well, I guess it won't be too hard to see the progress anyway as the updated ptblist.pl prints the current progress... It's a minor thing anyway, so I guess no need for the extra work.
EDIT: By the way, is it possible to revert 'sandwiched' commits like these easily or do you have to make that change manually?

It might be better to take the snapshot a fixed amount of time after the beginning of the interaction (maybe start + 10?). I can code it that way if you think it would be better.

That's a really good idea! If it just takes a snapshot when the catalyst is recovered, it will count every glider eater as a seperate pattern.There may be reactions that don't last for 10 gens, so how about setting the condition to something like this? You should probably add the restored==0 condition as a base case anyway (for short-lived catalysts).

Code: Select all

 if (restored==0 or generation == start +10)

[chris_c]

By the way, is it possible to revert 'sandwiched' commits like these easily or do you have to make that change manually?

git revert HEAD~n creates a new commit that negates the changes in the commit n steps ago.

If it just takes a snapshot when the catalyst is recovered, it will count every glider eater as a seperate pattern.There may be reactions that don't last for 10 gens, so how about setting the condition to something like this?

This is the implementation I had in mind. The idea is to remember the time when the last interaction began and only allow taking the snapshots for a fixed amount of time afterwards. As a base case I still always capture at the first moment the catalysts are restored.

The advantage of this method is (or should be, it's completely untested) that in the following pattern

Code: Select all

x = 53, y = 16, rule = B3/S23
10bo39bo$10bobo37bobo$10b3o37b3o$12bo39bo6$2b2o36bob2o$3bo34b3ob2o$3o
34bo$o37b3ob2o$40bobo$40bobo$41bo!

both reactions begin at generation 46 so the final snapshot should be taken in both patterns at gen 56 and they will be treated as equal. If you only captured the first restoration then the Eater1 would be captured 3 generations before the Eater2 and so they would look like different reactions.

BUT basing it on the time of the first interaction is not as foolproof as I thought it was. There is the equivalence below that was spotted by Extrementhusiast:

Code: Select all

x = 71, y = 21, rule = B3/S23
64b2o$65bo$65bob2obo$64b2obob2o2$64b3o$64bo2bo$66b2o$12b2o$12b2o2$63bo
$62bobo$63b2o5$b3o51b3o$2bo53bo$3o51b3o!

The reactions are equivalent but begin and end at different times. For this reaction the best way to test uniqueness is the old method of capturing the last moment before the catalysts are destroyed.

So now you have three different implementations of survive. The questions are which way is most useful for your current project and which way is most useful in general?

[Scorbie]

his is the implementation I had in mind. The idea is to remember the time when the last interaction began and only allow taking the snapshots for a fixed amount of time afterwards. As a base case I still always capture at the first moment the catalysts are restored.

A cursory look seems pretty good. If that has no bugs then it would be really good.

BUT basing it on the time of the first interaction is not as foolproof as I thought it was. There is the equivalence below that was spotted by Extrementhusiast:

Code: Select all

x = 71, y = 21, rule = B3/S23
64b2o$65bo$65bob2obo$64b2obob2o2$64b3o$64bo2bo$66b2o$12b2o$12b2o2$63bo
$62bobo$63b2o5$b3o51b3o$2bo53bo$3o51b3o!

The reactions are equivalent but begin and end at different times. For this reaction the best way to test uniqueness is the old method of capturing the last moment before the catalysts are destroyed.

I think the old program could not see them as identical in general. As you said, the two reactions begin and end at different times. But even the old version cannot differentiate these two reactions in general, because the catalysts are wrecked in different generations. The right reaction is wrecked in around gen 358 and the left one is wrecked in around gen 391. By the way, they aren't going to be compared directly, because they have different number of catalysts. But I do see your point. Two identical catalysis can have different starting and ending generations. One solution to that would be capturing at gen 10n. e.g if one reaction occured at gen 58~64 and other at 61~67, check both reactions at gen 70. This still has its own limitations. I think filtering out all identical solutions are pretty tricky, and the only way that comes into mind is to cache all generations (actually, after the last catalysis would suffice) to every solution, and filtering out using that thing. But I think...(continued)

So now you have three different implementations of survive. The questions are which way is most useful for your current project and which way is most useful in general?

Your last implementation, if it works as expected is the best among not changing the source code too much. Remember that the original survive could not filter out trivial stator variants? That seems to be pretty ineffective. Also, the second implementation does its work great in just censusing patterns, but it may have problems in eliminating various reactions such as eliminating glider eaters, eliminating trivial BTS/eater2/whatever catalysis that can be replaced by a block, etc. The last one, however, seems to handle all those problems quite nicely, so I guess your last solution is the way to go, if it works as expected

[chris_c]

But even the old version cannot differentiate these two reactions in general, because the catalysts are wrecked in different generations. The right reaction is wrecked in around gen 358 and the left one is wrecked in around gen 391.

Oh, sorry. I didn't run it long enough and just assumed both reactions would last until the end

Your last implementation, if it works as expected is the best among not changing the source code too much. Remember that the original survive could not filter out trivial stator variants? That seems to be pretty ineffective.

Good. I'll let things settle for a few days and push something to the main branch if there are no other issues. I suppose I was overestimating the number of times that a reaction survives until generation 500. If this number is quite small then I guess that the original implementation is not going to give better results very often.

[Scorbie]

Good. I'll let things settle for a few days and push something to the main branch if there are no other issues. I suppose I was overestimating the number of times that a reaction survives until generation 500. If this number is quite small then I guess that the original implementation is not going to give better results very often.

To be honest, I'm not sure how often the reaction survives till gen 500. But it was pretty annoying to see all those results, and what I am sure is that it is going to increase quite a bit, as you allowed the 'tail rock' catalysis to ptbsearch, and quite a lot of catalysts have a tailish thing thus allows that.

Hmm... Could you reckon why ptbsearch wasn't able to filter out the left reaction (where the right one could be used as a filter) All tail-based rock catalyses are filtered, but not this boat bit. Strange.

Code: Select all

x = 60, y = 20, rule = B3/S23
11b2o2bo2bo$11bo3b4o$12b3o41bo$16b3o37b3o$12b4o3bo39bo$12bo2bo2b2o38b
2o5$3ob2ob2o31b3ob2ob2o$3ob3o33b3ob3o$3ob2o2bo31b3ob2o2bo$b3o2b4o31b3o
2b4o$3o3bobo31b3o3bobo$8obo30b8obo$ob2obob3o30bob2obob3o$bo3b3obo31bo
3b3obo$b2o2bobo33b2o2bobo$o2b3obobo30bo2b3obobo!

[chris_c]

Hmm... Could you reckon why ptbsearch wasn't able to filter out the left reaction (where the right one could be used as a filter) All tail-based rock catalyses are filtered, but not this boat bit. Strange.

Code: Select all

x = 60, y = 20, rule = B3/S23
11b2o2bo2bo$11bo3b4o$12b3o41bo$16b3o37b3o$12b4o3bo39bo$12bo2bo2b2o38b
2o5$3ob2ob2o31b3ob2ob2o$3ob3o33b3ob3o$3ob2o2bo31b3ob2o2bo$b3o2b4o31b3o
2b4o$3o3bobo31b3o3bobo$8obo30b8obo$ob2obob3o30bob2obob3o$bo3b3obo31bo
3b3obo$b2o2bobo33b2o2bobo$o2b3obobo30bo2b3obobo!

Hmm... that did seem strange for a while. But look carefully at generations 81 and 82!

Probably there is a simple fix but I can't think at the moment.

[Scorbie]

Probably there is a simple fix but I can't think at the moment

I think this is negligible enough to just ignore for now. Speaking of eaters, I think it would be really interesting if catalysis of a glider doesn't count as such, but that would be pretty hard, won't it?
EDIT: Thought for a bit and changed my mind. I think this suggests that we should not take snapshot at restored == 0 as a base case. I would not like to count, for example, the interactions at gen 81-82 of the eater_table catalyst as a seperate catalysis.

Also, I said before that I was not sure how often there are duplicates of different starting and ending generations but the same final pattern. Well, we could use both the old filter and the new filter!
The second to the last of the output of survive is merely the population of the final pattern, so we could get rid of that and add "pattern after last catalysis" instead.
And here's the working version of uniq.py (edited uniq.pl and couldn't get it to work. I'm illiterate in perl.)

Code: Select all

#!/usr/bin/env python
import fileinput
interfilter = set()
outfilter = set()
for line in fileinput.input():
    pat, startgen, maxrecovtime, wrecktime, lastsurvgen,\
        interpat, outpat = line.split()
    if interpat not in interfilter and outpat not in outfilter:
        print line,
    if interpat not in interfilter:
        interfilter.add(interpat)
    if outpat not in outfilter:
        outfilter.add(outpat)

[Scorbie]

After some inspection I see a slight problem. The program would not capture catalyses that take more than 10 gens.
So, with this and my change of mind in the previous post, yet another suggestion would be capturing right after the catalysts are restored. Do you see any problems here?

Code: Select all

#include <stdio.h>
#include <limits.h>
#include "gen.h"
#include <malloc.h>

main(int argc, char *argv[]) {

  static LifeList cells;
  static LifeList matchcells;
  static LifeList boundarycells;
  static LifeList intercells;
  static LifeList outcells;
  int i,j,n=0;
  int gens=500;
  int x,y;
  int match;
  int pos;
  int count[240];
  int least= 0;
  int fail;
  int damaged;
  int restored;
  int firstgen;
  int maxgen;
  int restorefilter=10;
  char interpat[100000];
  char outpat[100000];


  History hist;
  int period, repetitions;
  Cell lifetrail[5000];
  static char nextpat[10000];
  int ncls;

  initLifeList(&cells);
  initLifeList(&matchcells);
  initLifeList(&boundarycells);
  initLifeList(&intercells);
  initLifeList(&outcells);

  if (argc>2) {
      sscanf(argv[2], "%d", &restorefilter);
  }

  while(gets(nextpat)) {

    for (i=0; i<240; i++) { count[i] = i; }

    getpat(nextpat, &cells);
    copyLifeList(&cells, &matchcells);

    if (argc>1) {
      for (i=0; argv[1][i]; i++) {
        matchcells.ncells =
          removeIfEquals(matchcells.cellList, matchcells.ncells, argv[1][i]);
      }
    }

    copyLifeList(&matchcells, &boundarycells);
    spread(&boundarycells, 1);

    fail=0;
    damaged=0;
    restored=0;
    firstgen=0;
    maxgen=0;
    for (i=0; i<gens; i++) {
      generate(&cells);

      //      printf("%d %d %d %d\n", i, fail, damaged, restored);

      count[i%240] = cells.ncells;

      if (cells.ncells == 0) break;

      match = 1;
      for (j=0; j<180; j++) {
        if (count[j] != count[j+60]) {
          match = 0;
          break;
        }
      }

      if (match) break;

      if ( matchLifeList(&cells, &matchcells, 0) < matchcells.ncells
           || matchLifeList(&cells, &boundarycells, 0) != matchcells.ncells) {
        fail++;
        restored=0;
        if (firstgen == 0){firstgen = i; maxgen = i+restorefilter+10;}
      } else {
        copyLifeList(&cells, &outcells);
        restored++;
        if (restored>restorefilter) {
          if (restored == restorefilter+1 || i <= maxgen)
            copyLifeList(&cells, &intercells);
          if (fail>damaged) damaged=fail;
          fail = 0;
          firstgen = 0;
        }
      }

      if (fail>150) break;

    }

    if (damaged) {
      fflush(stdout);
      removeLifeList(&intercells, &matchcells, 0);
      removeLifeList(&outcells, &matchcells, 0);
      makeString(intercells.cellList, intercells.ncells, interpat);
      makeString(outcells.cellList, outcells.ncells, outpat);

      printf("%s %d %d %d %s %s\n", nextpat, damaged, fail, i-fail, interpat, outpat);
    }

  }
}

[chris_c]

After some inspection I see a slight problem. The program would not capture catalyses that take more than 10 gens.

Hmm... not sure I agree. The first restoration is always output even if the generation is greater than maxgen.

So, with this and my change of mind in the previous post, yet another suggestion would be capturing right after the catalysts are restored. Do you see any problems here?

No problems there. In fact I was thinking something similar. If you don't want very short restorations to be output like you mentioned in your previous post, then this is the better place to take the capture in all circumstances. How about this?

Regarding outputting two different captures: I would rather not think about it until we know everything else works properly.

[Scorbie]

Whoa, I independently edited my file and it's the same as yours! Yep, I'll test with that.
Oh, by the way, my version above saves two captures.

After some inspection I see a slight problem. The program would not capture catalyses that take more than 10 gens.

Hmm... not sure I agree. The first restoration is always output even if the generation is greater than maxgen.

EDIT: You're right. I must have thought wrong.

By the way I was thinking about ways to deal with two identical catalysts with different starting and ending generations. How about taking snapshots at 30n gens? (One would have to use a different snapshot if the reactions or wrecking occur near gen 30n)

[Scorbie]

Okay, did a brief test, worked great, and the only difference was that yours and mine gave similar results, except that these were in yours but not in mine:

Code: Select all

x = 199, y = 38, rule = B3/S23
193b2o$193b2o3$58bob2o132b2o$56b3obo56b2o74bo2bo$55bo5bo55bo75bobo$56b
o5bo51b2obo50b2ob2obobo14bobobobo$57bob3o52bo2bob2o46bo2b3o2bo14bobobo
bobo$56b2obo56bobobo46bo3b2obo16bo2bo2bo$115b2o50bo2bo2bobo16b2ob2o$4b
2o3b2obo100bo2bo50b4o2b3o17bobo$3b5obob2o40b2ob2obobo51b2o53bobob4o17b
obo$4b2ob4obo39bo2b3o2bo109b2o2b3o17bo$4bo3bo2bo40bo3b2obo62b2ob2obobo
36b4ob5o$4bobobobo41bo2bo2bobo60bo2b3o2bo37bo3bobobo$3b2ob2o2b3o39b4o
2b3o60bo3b2obo38b4o2b3o$3bo2b2o2bobo40bobob4o60bo2bo2bobo$4bob3o3bo42b
2o2b3o59b4o2b3o$4b2o2bobo41b4ob5o60bobob4o$52bo3bobobo63b2o2b3o$52b4o
2b3o60b4ob5o$121bo3bobobo$121b4o2b3o7$4b2o$3bobo$b3obobo$o4b2obo$ob2o
4bo$bobob3o$3bobo$3b2o!

Hopefully the catalysts all live long and prosper. I found a reaction that caused to delete two of them in my search:

Code: Select all

x = 99, y = 19, rule = B3/S23
2o44b2o$bo44bo47bob2o$bobo39b2obo45b3obo$2b2o39bo2bob2o41bo5bo$45bobob
o42bo5bo$44b2o47bob3o$42bo2bo46b2obo$42b2o$7b2ob2obobo$6bo2b3o2bo36b2o
b2obobo29b2ob2obobo$6bo3b2obo36bo2b3o2bo29bo2b3o2bo$6bo2bo2bobo35bo3b
2obo30bo3b2obo$6b4o2b3o35bo2bo2bobo29bo2bo2bobo$7bobob4o35b4o2b3o29b4o
2b3o$9b2o2b3o35bobob4o30bobob4o$6b4ob5o37b2o2b3o31b2o2b3o$6bo3bobobo
35b4ob5o28b4ob5o$6b4o2b3o35bo3bobobo29bo3bobobo$50b4o2b3o29b4o2b3o!

So no abnormalities so far.

[chris_c]

How about taking snapshots at 30n gens? (One would have to use a different snapshot if the reactions or wrecking occur near gen 30n)

Nah... if I was going to put in that amount of work I would want to make a proper solution. Here is a python/pseudo-code sketch of something more ideal:

Code: Select all

MAX_TIME = 100

reactions_db = [set() for i in range(MAX_TIME)]


def add_active_reactions(pattern):
    
    t0 = last_restoration_time(pattern)
    t1 = destruction_time(pattern)

    pattern = evolve(pattern, t0)

    for t in range(t0, t1):
        
        active_reaction = remove(pattern, catalysts)
        reactions_db[t].add(hash(active_reaction))

        pattern = evolve(pattern, 1)


def is_uniq(pattern):
    
    damaged = False
    seen_so_far = True
    
    for t in range(MAX_TIME):

        status = get_status(pattern)

        if status == OK:

            if damaged:
                damaged = False
                active_reaction = remove(pattern, catalysts)
                seen_so_far = hash(active_reaction) in reactions_db[t]

        elif status == DAMAGED:

            damaged = True

        elif status == DESTROYED:
            break

    return not seen_so_far

The idea is to keep a database of all the active reactions seen after the last successful catalysis in a pattern. The add_active_reactions function probably requires two passes through the pattern. One to determine times t0 and t1 and the other to extract the active reaction. In the is_uniq function you would probably want to set "seen_so_far" a few generations after the first restoration instead of straight away.

Probably this can be implemented in Python/Golly. You would need to parse the output from ptb2 and forget about the current survive and uniq programs. I don't plan on doing this though.

[Scorbie]

Nice approach.

In the is_uniq function you would probably want to set "seen_so_far" a few generations after the first restoration instead of straight away.

Umm... Why? Isn't it good it the reaction is seen_so_far just after the first restoration?

Probably this can be implemented in Python/Golly. You would need to parse the output from ptb2 and forget about the current survive and uniq programs. I don't plan on doing this though.

Yep, I guess in some distant future when ptbsearch is integrated with Golly this would be much easier to do

[chris_c]

Umm... Why? Isn't it good it the reaction is seen_so_far just after the first restoration?

There could be a dying spark in the active region when the catalyst is first restored. e.g. Eater1 eating a glider.

[Kazyan]

Sorry to bug you two, but survive.c is not compiling on my (Ubuntu) machine. I've ran the makefile and ptb2 is working, but no "survive.o" or "survive" file is created. "gcc ./survive.c" results in this:

Code: Select all

./survive.c: In function ‘main’:
./survive.c:35:3: warning: ‘gets’ is deprecated (declared at /usr/include/stdio.h:638) [-Wdeprecated-declarations]
   while(gets(nextpat)) {
   ^
/tmp/ccJoLdco.o: In function `main':
survive.c:(.text+0x373): warning: the `gets' function is dangerous and should not be used.
survive.c:(.text+0x4c): undefined reference to `initLifeList'
survive.c:(.text+0x56): undefined reference to `initLifeList'
survive.c:(.text+0x60): undefined reference to `initLifeList'
survive.c:(.text+0xa8): undefined reference to `getpat'
survive.c:(.text+0xb7): undefined reference to `copyLifeList'
survive.c:(.text+0x107): undefined reference to `removeIfEquals'
survive.c:(.text+0x16b): undefined reference to `generate'
survive.c:(.text+0x233): undefined reference to `matchLifeList'
survive.c:(.text+0x275): undefined reference to `copyLifeList'
survive.c:(.text+0x300): undefined reference to `removeLifeList'
survive.c:(.text+0x31e): undefined reference to `makeString'
collect2: error: ld returned 1 exit status

...and "g++ ./survive.c" does this:

Code: Select all

./survive.c: In function ‘int main(int, char**)’:
./survive.c:35:9: warning: ‘char* gets(char*)’ is deprecated (declared at /usr/include/stdio.h:638) [-Wdeprecated-declarations]
   while(gets(nextpat)) {
         ^
./survive.c:35:21: warning: ‘char* gets(char*)’ is deprecated (declared at /usr/include/stdio.h:638) [-Wdeprecated-declarations]
   while(gets(nextpat)) {
                     ^
./survive.c:45:69: error: ‘removeIfEquals’ was not declared in this scope
    removeIfEquals(matchcells.cellList, matchcells.ncells, argv[1][i]); 
                                                                     ^

gcc is up-to-date on my machine.

[chris_c]

Sorry to bug you two, but survive.c is not compiling on my (Ubuntu) machine. I've ran the makefile and ptb2 is working, but no "survive.o" or "survive" file is created. "gcc ./survive.c" results in this

No problem! Yeah, my Makefile knowledge is close to zero. It looks like I should add the line "all: ptb2 survive" before the "ptb2: ..." line. Either that or you will need to type "make survive" to (hopefully) get survive to compile.

[Kazyan]

No problem! Yeah, my Makefile knowledge is close to zero. It looks like I should add the line "all: ptb2 survive" before the "ptb2: ..." line. Either that or you will need to type "make survive" to (hopefully) get survive to compile.

"make survive" did the trick. I checked what happens if you add "all: ptb2 survive" to the Makefile, and it does compile both programs. Thanks!