ConwayLife.com

I've been wanting to write a program in C/C++ since it's the way to go for searching for potential patterns of interest, but no particular idea has peaked my interests yet. To remedy that, I'm starting a topic where people can post ideas for potential search programs so me or others here could go for it. Not only that, but ideas on how to optimize certain aspects of searching (i.e. Codeholics suggestion to store coordinates of live cells on a recent topic by simsim) are welcome as well.

I do have a question of my own:
What language is more efficient to write with, C or C++? I know the syntax between the two is very similar, but if there's a difference between the two that's significant enough to take notice of, I'll write in C, otherwise, I'll just go with C++.

EDIT: This topic is also the place to talk about the creation of search programs for things that don't already have search programs dedicated to them, so those kind of ideas are welcome as well.

flipper77 wrote:What language is more efficient to write with, C or C++?

With C++ it's easy to lose a lot of performance on some minor thing. Like using namespace std; will reduce your performance by 200%.

If you use classes, virtual functions could slow you down significantly as well.

But if you take simple C code, and compile it with C++, the code will run at the same speed. If you're using C++ just make sure you know the implications on performance of each line of code. Especially if you're using std functions - which by themselves are great, but beware how do you use them.

By the way with C you can also lose performance if you pass everything as void*. So it's less about the language and more about the specific usage and implementation, and making sure you know the implications of what you're doing on performance.

----

By the way, why do you want to write a search program? you could for example add interface to existing program. Or rewrite existing program in more simple and readable way. You can also make something like LifeAPI based on some existing search program, that would be very simple to tweak and use. Finally you can also help expand the LifeAPI, by say implementing some of the existing search utilities using it.

flipper77 wrote:I've been wanting to write a program in C/C++ since it's the way to go for searching for potential patterns of interest, but no particular idea has peaked my interests yet. To remedy that, I'm starting a topic where people can post ideas for potential search programs so me or others here could go for it.

Most of my ideas along these lines are a little bit vague and more than half crazy (or I would have implemented them already, I suppose.) Here's an assortment of items from my recent wish lists.

• Hit all constellations of small ash still lifes inside an MxN bounding box with a glider in all possible ways, and return any cases where the same constellation recurs.
• Same as above, but return all cases where the output is nothing but gliders and/or spaceships. Build a searchable catalog of glider splitters and turners, to allow easy re-timing and lane adjustments for gliders to build synchronized salvos or, say, a "seed" constellation that builds a dart when you hit it with a single glider.
• Same as above, but return all vanish reactions. Collect them into a searchable spark catalog for glider constructions. Sparks that are on the very edge of the reaction envelope are the most useful, especially if the envelope has just gotten a few cells wider at that point. That seems like a metric that could be figured out using the new LifeAPI project, with a little cleverness.
• Some kind of lifesrc/WLS/JLS-like backtracking search for predecessors of objects, that gives higher priority to solutions with a higher proportion of stable structures (especially toward the center of the object?) One can imagine (though it's pretty definitely just wishful thinking) feeding in a weekender, and having the search gradually find a larger and larger stable core object or constellation, and work the edge sparks back in time to a big pile of incoming gliders.
• Same as above, but prioritizing predecessors with "non-space-dust" fingerprints. Maybe make a catalog of all 5x5 subpatterns in old-universe random soups? Anyway, see if there's a way to statistically distinguish Life universes that have been running for a long time, from random soups that are just a few ticks from the Big Bang -- and use that information to pick predecessors that are more likely to be constructible themselves.
  
  -----------------------------------------
• I've been wondering recently if it's possible to run an exhaustive search to find the c/7 loafer spaceship -- or rather, the loafer and every spaceship up to the same size. The loafer fits in a snub-pointed triangle of 53 cells, so the absolute dumb-as-a-stone brute force method would be to enumerate all 9,007,199,254,740,992 different combinations of 53 ON and OFF cells, run each for 1024 ticks (or maybe just 100) and check that the original pattern never recurs with an offset.
  
  9 quadrillion is... um... still a little high even for distributed computing. But it should be possible to cut that down tremendously, maybe by including only objects with M < number of bits < N, discarding anything with a bounding box small enough that it has already been tested, etc. I've been playing around a little bit with a couple of the high-performance computing clusters at the University here this semester, and it seems as if it might be possible to close the rest of the gap just by running on a few thousand cores at once -- it's a fairly easy computation to split up into separate pieces, and we won't have a large number of results coming back.
  
  So it would be interesting to see what the largest bounding box is that can be exhaustively tested for spaceships (and maybe high-period oscillators while we're at it). Looks like it's higher than 6x6, maybe 7x7, but 10x10 is far out of reach unless someone manages to apply a lot of sneaky tricks to reduce the number of cases.

dvgrn wrote:Some kind of lifesrc/WLS/JLS-like backtracking search for predecessors of objects, that gives higher priority to solutions with a higher proportion of stable structures (especially toward the center of the object?) One can imagine (though it's pretty definitely just wishful thinking) feeding in a weekender, and having the search gradually find a larger and larger stable core object or constellation, and work the edge sparks back in time to a big pile of incoming gliders.

I actually wanted to write something like this inside golly using lifesrc and python. The point would be to get all parent from lifesrc, and then filter the parents by some priority (say go 5 generations back and find all parents that contain glider, or SL). Then search for parent on those object alone (removing the gliders and SL).

One can start by doing just the first stage - take the thousands parent from lifesrc output, and filter them. Say find all those who contain glider or SL already.

Anyway with my LifeAPI I would rather do some brute force searching and filter the stable objects myself. The iterator there is fast enough to brute-force search up to 30 unknown cells in reasonable time, which is quite a lot. The advantage of brute force is that it's not limited in number of generations - one can search 15 generation forward easily with brute force approach, while lifesrc will waste a lot of time in this ranges (will get "unknown" state too much).

Well, I ALWAYS code in C++, there seems some reason to use C++ here, for example:
* template for working in any rule
* default parameter for recursive functions
* (probably) lambda function
...
Nonetheless, C++ is very hard to use, but using C requires some tricky techniques, so if you are going to use C++, go on anyway.

I recently encountered an algorithm called A* (Yeah, now I see it's very well-known.)
This made me wonder if it can be applied to BFS searches like *find.

As you all know, *find is a BFS search, with pruning rows.
Well we may apply A* by setting the heuristic for each row as the expected number of rows for the final pattern. i.e.

let:
m = avg number of branches for each row
b = number of branches of the current row
e = expected number of rows additionally needed to complete the search
r = length of row
p = period
And we assume (crudely) that the branches are pretty random. Then, approximately,
"All possible rows are visited after e rows." or,
2^rp = b * m^(e-1)
rp * log2 = (e-1) logm + logb
e = (rp * log2 - logb) / logm
And add this to the number or rows needed to get to the current state to get the heuristic.

Here's a (I think reasonable) idea for searching oscs with rotor size < mxn:
Search for patterns with an unstable mxn region and a stable outside region surrounding it. Edit for clarity: This pattern might become stable or oscillate with rotor inside the variable region when generated forever. If the outside region changes, the pattern should be discarded.
I think "1 surrounding layer + each cell's stable neighbor count" is more than enough for representing the configuration for the outside stable region.
Here are some ways to search for them:
1) Brute force for all mxn inside patterns, checking if there's a surrounding stable pattern that's stable forever.
2) For all outside stable patterns (or 1 layer + stable neighbor count) find an inside mxn pattern that lets it stable forever. Organize results.
3) Search from cell to cell, like lifesrc/gfind/JLS/whatever.
4) Search by using dr with appropriate params. Definitely possible, but I'm not sure how efficient this would be, compared to simple dr search and compared to other search methods here.

Wondering if distinct perturbations can be represented as a git branch, and two independent changes can be merged. Is this idea useful?