photonsrc, a zfind-like program for finding higher-period photons

[LaundryPizza03]

I've developed an experimental zfind-like search program for photons with arbitrary period, since to the best of my knowledge, no other programs can currently do this.

The basic idea in the search is that when a cell in a photon is updated, each row moves forward 1 cell, so in effect each row depends only on the previous two rows. In other words, the problem is equivalent to a rule on the following neighborhood:

Code: Select all

x = 3, y = 3, rule = B/S012345678History
3B$3B$BAB!

A corollary of this result is that each row eventually repeats with a period that is a multiple of the row in front of it. By exploring the de Bruijn diagram of a particular row and isolating cycles with length dividing a target period, we can search a tree of photon frontends and find a spaceship.

Improvement to-do's:

• Improve detection of duplicate/redundant results.
• Improve the tree search algorithm (currently standard DFS)
• Possibly add support for B0 rules that allow lightspeed spaceships

photonsrc_v0.1.zip

(17.35 KiB) Downloaded 116 times

Usage:

Code: Select all

python photonsrc.py [-h] -r RULE [-p PERIOD] -w WIDTH [-s SYMMETRY] [--subperiod SUBPERIOD]

The output somewhat resembles that of qfind.

Code: Select all

python photonsrc.py -r B2/S0 -w 7 -s u -p 4 --subperiod true   
Rule: B2/S0
Period: 4
Width: 13
Symmetry: odd

x = 13, y = 2, rule = B2/S0
b2o7b2o$o2bo5bo2bo!


x = 11, y = 2, rule = B2/S0
b2o5b2o$o2bo3bo2bo!


x = 11, y = 4, rule = B2/S0
2b2o3b2o2$bo7bo$o2bo3bo2bo!


x = 11, y = 3, rule = B2/S0
2b2o3b2o$bo7bo$o9bo!

Search complete.

[LaundryPizza03]

I fixed a bug that caused some cycles to be dropped, so ships such as the p2 in B2/S025 should no longer be skipped. I also changed the search order of the first row. It's a little slower now, though.

Code: Select all

x = 20, y = 13, rule = B2/S025
6b2o4b2o$5bobob2obobo$2b2obo8bob2o$bobobobob2obobobobo$3bo12bo$3bo3b2o
2b2o3bo$3b3o3b2o3b3o$7bo4bo$bo6b4o6bo$obo2bo8bo2bobo3$obo14bobo!

Interestingly, the runtime of this algorithm is, in theory, independent of the period.

[LaundryPizza03]

I decided to swap out the DFS for a gfind-like algorithm, as well as implementing a hash table to accelerate the computation of row evolution. It could be sped up a bit more with an extra hash table, but it's pretty decent as is. I even found a new spaceship in the rule B2/S024.

[LaundryPizza03]

Changes for v1.1: The hash table is now automatically compressed after computing every node. It was taking up far too much space; for example, when running p2 at width 10 on even symmetry in B2/S025, it took up over 201 MB at the end of the first BFS round. Also, terminating the program no longer produces an error message.

[LaundryPizza03]

I'm trying to improve the runtime of photonsrc and need to figure out a more efficient way of enumerating the available cycles from a row. Anyone have any suggestions?

I did drastically improve the duplicate detection, however.