@AlephAlpha

如题，能不能增加一些不考虑的细胞，也就是说，它们能作用于其他细胞，但是对于它们本身能否回到初始状态不关心。感觉实现起来可能应该不会很难（？）

这个可以作为搜索顺序的替代品。

@AlephAlpha

网页版的搜索顺序如果想要自己指定的话是不是仍然可以改 save.json 的 search order 啊？只是没想到好的输入方式，还是说 FromVec 干脆就是命令行版的特有功能？

另外，修改 check_index 是不是可以使 rlifesrc 忽略前面的一些细胞状态是否正确？

basically, increase min cell count when a result is found. （it should need a min cell count option as well)

@AlephAlpha 1. 如果空行的数量超过period就直接出结果
2. 如果当前已经是结果就不要搜了

慢也没事，总比把同一个分支运行很多次好很多。（当然应该做成可选的。）
每搜一行就在散列表中查询它的转子，如果没有就继续搜索并把它的转子记录到散列表中，如果有就回溯。
@AlephAlpha

With the "Random" setting in the option to try on or off cells first, maybe add something to let us choose the probability that the program tries an on or an off cell.

第一，应该有一个选项，对于 gutter-symmetric 的规则（也就是没有 B2i，B4i，B4c，B6i），打开之后，搜到某一行（按行搜时）或某一列（按列搜时）在所有代都为死时停止搜索（因为可以用它自己稳定那一行）。除了震荡子，搜索方向与移动方向相互正交的飞船也可以用这个选项（这样搜 Spider 之类的就很容易）
第二，应该有另一个选项，对于 Choice of state for unknown cells 为 Dead 的搜索，结果的 hash 会被记录在一个表里（不包括离最近的活细胞距离超过2的部分），然后（在搜索过程中）剪掉所有符合表中任意一条记录的分支。不只要用 hash，可能还要用到别的高科技（因为要检测是否“符合表中任意一条记录”）
第三，应该还有一个选项（好吧，这个算是 Feature request），要求第一个 strictly-volatile 或者不对称等等的行/列/行加列出现在前 N 行，如果当前假定的前 N 行/列/行加列都没有 strictly-volatile 或者不对称等等的行/列/行加列，则放弃。

第四，我以前用的那些 save 现在都会提示 Broken saved file.

@yujh-yujh 发现的 Bug:

GitHub connection bad(probably banned in other places, as tested), so I’ll report a bug of rlifesrc here

Rule:B2/S
Width:13
Height:20
Period:6
dx:0
dy:6
Diagonal width:0
Transformation:flip|
Symmetry:C1
Max cell count:0
Search order:automatic 
Choice of state for unknown cells:alive
Skip patterns with subperiod.

@AlephAlpha it makes this result

x = 13, y = 20, rule = B2/S
.............$
.............$
.............$
.............$
.............$
.oo.......oo.$
o..o.....o..o$
.............$
.............$
.oo.......oo.$
o...........o$
...o.....o...$
....o...o....$
..o.......o..$
........o....$
..........o..$
.....o.......$
.o...........$
.............$
.............!

该跳过的没跳过……

目前我设的 "Skip patterns with subperiod" 的条件是：对周期 p 的每一个大于 1 的约数 d，先看 dx/d 和 dy/d 是否为整数；如果都是整数，就看图样在第 p/d 代时是否相当于第 0 代平移 (dx/d, dy/d)。

这样的条件在 Transformation 为 id 时不会有问题，但 Transformation 非平凡时可能会出问题……

关键是要找一个更合适的条件。

等有时间再想怎么修。

就是和golly and lifeviewer 方向不一样，这个已经有段时间了（应该是从头到尾都是错的）

{"config":{"width":6,"height":99,"period":5,"dx":0,"dy":0,"transform":"Id","symmetry":"D2Col","search_order":null,"new_state":"ChooseAlive","max_cell_count":null,"non_empty_front":true,"reduce_max":false,"rule_string":"B2n3/S23-q","diagonal_width":null,"skip_level":"SkipSubperiodSpaceship"},"conflicts":349090,"set_stack":[{"coord":[0,0,0],"state":0,"reason":"Deduce"}, {"coord":[0,0,1],"state":0,"reason":"Deduce"}, {"coord":[0,0,2],"state":0,"reason":"Deduce"}, {"coord":[0,0,3],"state":0,"reason":"Deduce"}, {"coord":[0,0,4],"state":0,"reason":"Deduce"}, {"coord":[1,0,0],"state":0,"reason":"Deduce"}, {"coord":[1,0,1],"state":0,"reason":"Deduce"}, {"coord":[1,0,2],"state":0,"reason":"Deduce"}, {"coord":[1,0,3],"state":0,"reason":"Deduce"}, {"coord":[1,0,4],"state":0,"reason":"Deduce"}, {"coord":[2,0,0],"state":1,"reason":"Deduce"}, {"coord":[2,0,1],"state":0,"reason":"Deduce"}, {"coord":[2,0,2],"state":0,"reason":"Deduce"}, {"coord":[2,0,3],"state":0,"reason":"Deduce"}, {"coord":[2,0,4],"state":0,"reason":"Deduce"}, {"coord":[3,0,0],"state":1,"reason":"Deduce"}, {"coord":[3,0,1],"state":0,"reason":"Deduce"}, {"coord":[3,0,2],"state":0,"reason":"Deduce"}, {"coord":[3,0,3],"state":0,"reason":"Deduce"}, {"coord":[3,0,4],"state":0,"reason":"Deduce"}, {"coord":[4,0,0],"state":0,"reason":"Deduce"}, {"coord":[4,0,1],"state":0,"reason":"Deduce"}, {"coord":[4,0,2],"state":0,"reason":"Deduce"}, {"coord":[4,0,3],"state":0,"reason":"Deduce"}, {"coord":[4,0,4],"state":0,"reason":"Deduce"}, {"coord":[5,0,0],"state":0,"reason":"Deduce"}, {"coord":[5,0,1],"state":0,"reason":"Deduce"}, {"coord":[5,0,2],"state":0,"reason":"Deduce"}, {"coord":[5,0,3],"state":0,"reason":"Deduce"}, {"coord":[5,0,4],"state":0,"reason":"Deduce"}],"check_index":2848}

这个搜索会有奇怪的事情发生。

I have recently did a 3x3 sl search and I had this result:

`Find all results. Won't stop when found one.

x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
oo.$
o.o$
.oo!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
oo.$
o.o$
.o.!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
o..$
ooo$
..o!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
oo.$
.o.$
.oo!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
.oo$
o.o$
oo.!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
.o.$
o.o$
oo.!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
..o$
ooo$
o..!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
.oo$
o.o$
.o.!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
.o.$
o.o$
.oo!
x = 3, y = 3, rule = B34kz5e7c8/S23-a4ityz5k
.o.$
o.o$
.o.!
`

and I've found another rotation of one of the still lives and it's not listed. It's b2o$bo$2o! I think this one is very easy to reproduce, It's just B3/S23-a4z

I clicked "save", then Chrome randomly killed tabs, then killed RLS instead of saving the search like it was supposed to. To reproduce, search with these parameters:
[{"coord":[1,0,0],"state":0},{"coord":[2,0,0],"state":0},{"coord":[3,0,0],"state":0},{"coord":[4,0,0],"state":0},{"coord":[5,0,0],"state":0},{"coord":[6,0,0],"state":0},{"coord":[7,0,0],"state":0},{"coord":[8,0,0],"state":1},{"coord":[6,2,0],"state":0},{"coord":[8,2,0],"state":0},{"coord":[9,2,0],"state":0},{"coord":[2,0,0],"state":0},{"coord":[3,0,1],"state":0},{"coord":[4,0,1],"state":0},{"coord":[5,0,1],"state":0},{"coord":[6,0,1],"state":0},{"coord":[7,0,1],"state":0},{"coord":[8,0,1],"state":0},{"coord":[1,0,1],"state":0},{"coord":[3,0,2],"state":0},{"coord":[4,0,2],"state":0},{"coord":[5,0,2],"state":0},{"coord":[6,0,2],"state":0},{"coord":[7,0,2],"state":0},{"coord":[8,0,2],"state":0},{"coord":[2,0,2],"state":0},{"coord":[3,0,3],"state":0},{"coord":[4,0,3],"state":0},{"coord":[5,0,3],"state":0},{"coord":[6,0,3],"state":0},{"coord":[7,0,3],"state":0},{"coord":[8,0,3],"state":0},{"coord":[2,0,3],"state":0},{"coord":[0,0,0],"state":0},{"coord":[2,0,1],"state":0},{"coord":[1,0,2],"state":0},{"coord":[1,0,3],"state":0}]

B3-ky4jy5cr/S2-in3-aeky4cnrt5a6ekn

17 by 111

D2|

P4

Unknown cells are dead

Reduce max cell count when a result is found

@AlephAlpha

现在网页版的保存进度方式是手动点击按钮下载到本地。

能不能像猫国建设者那样，每隔几十秒钟把存档保存到浏览器缓存里面，这个实现起来会有困难吗。

（其实最好能做一个存档管理器）

@AlephAlpha

今天 rlifesrc（在一些人工的帮助下）在 LeapLife 中找到了一个 p5 的 domino sparker。

x = 16, y = 83, rule = B2n3/S23-q
4b2ob2ob2o$bobo2bo2bo2bobo$o2bo8bo2bo$2o4b4o4b2o3$5bob2obo$5b2o2b2o2$
2o2bo6bo2b2o$o2b4o2b4o2bo$b2o2bo4bo2b2o$3b2o6b2o$3bo8bo$2obob2o2b2obob
2o$2obo8bob2o$3bo2bo2bo2bo$3ob2o4b2ob3o$o4bo4bo4bo$bob2o6b2obo$2obob6o
bob2o$4b2o4b2o$2obo8bob2o$bob2obo2bob2obo$bo2bo2b2o2bo2bo$2b3o6b3o2$6o
4b6o$o14bo$bob3o4b3obo$2obo2b4o2bob2o$6b4o$5b6o$2o2bobo2bobo2b2o$o14bo
$b4o6b4o2$b3ob2o2b2ob3o$obo3b4o3bobo$o3b2o4b2o3bo$b3obo4bob3o2$b3obo4b
ob3o$o3b2o4b2o3bo$obo3b4o3bobo$b3ob2o2b2ob3o2$b4o6b4o$o14bo$2o2bobo2bo
bo2b2o$5b6o$6b4o$2obo2b4o2bob2o$bob3o4b3obo$o14bo$6o4b6o2$2b3o6b3o$bo
2bo2b2o2bo2bo$bob2obo2bob2obo$2obo8bob2o$4b2o4b2o$2obob6obob2o$bob2o6b
2obo$o4bo4bo4bo$3ob2o4b2ob3o$3bo2bo2bo2bo$2obo8bob2o$2obob2o2b2obob2o$
3bo8bo$3b2o6b2o$b2o2bo4bo2b2o$o2b4o2b4o2bo$2o2bo6bo2b2o2$5b2o2b2o$5bob
2obo3$2o4b4o4b2o$o2bo8bo2bo$bobo2bo2bo2bobo$4b2ob2ob2o!

就是记录已知细胞数最大的状态。可以在搜索过程中多一个（可以选择关闭的）框表示目前为止遇到最大的Partial，也可以结束的时候输出。

比如：

{"config":{"width":9,"height":50,"period":3,"dx":0,"dy":0,"transform":"Id","symmetry":"D2Col","search_order":null,"new_state":"Random","max_cell_count":null,"non_empty_front":true,"reduce_max":false,"rule_string":"B2n3/S23-q","diagonal_width":null},"conflicts":3425115,"set_stack":[{"coord":[0,0,0],"state":0,"reason":"Deduce"}, {"coord":[0,0,1],"state":0,"reason":"Deduce"}, {"coord":[0,0,2],"state":0,"reason":"Deduce"}, {"coord":[1,0,0],"state":0,"reason":"Deduce"}, {"coord":[1,0,1],"state":0,"reason":"Deduce"}, {"coord":[1,0,2],"state":0,"reason":"Deduce"}, {"coord":[2,0,0],"state":0,"reason":"Deduce"}, {"coord":[2,0,1],"state":0,"reason":"Deduce"}, {"coord":[2,0,2],"state":0,"reason":"Deduce"}, {"coord":[3,0,0],"state":0,"reason":"Deduce"}, {"coord":[3,0,1],"state":0,"reason":"Deduce"}, {"coord":[3,0,2],"state":0,"reason":"Deduce"}, {"coord":[4,0,0],"state":1,"reason":"Deduce"}, {"coord":[4,0,1],"state":0,"reason":"Deduce"}, {"coord":[4,0,2],"state":0,"reason":"Deduce"}, {"coord":[5,0,0],"state":0,"reason":"Deduce"}, {"coord":[5,0,1],"state":0,"reason":"Deduce"}, {"coord":[5,0,2],"state":0,"reason":"Deduce"}, {"coord":[6,0,0],"state":0,"reason":"Deduce"}, {"coord":[6,0,1],"state":0,"reason":"Deduce"}, {"coord":[6,0,2],"state":0,"reason":"Deduce"}, {"coord":[7,0,0],"state":0,"reason":"Deduce"}, {"coord":[7,0,1],"state":0,"reason":"Deduce"}, {"coord":[7,0,2],"state":0,"reason":"Deduce"}, {"coord":[8,0,0],"state":0,"reason":"Deduce"}, {"coord":[8,0,1],"state":0,"reason":"Deduce"}, {"coord":[8,0,2],"state":0,"reason":"Deduce"}],"check_index":0,"search_index":0}

（还是说Deduce不能这样用？）

另外，如果把以上的new_state改为Alive或Dead，就会提示broken。在什么情况下才会提示broken？

@AlephAlpha 其实我最近想到一个东西，应该不难加，而且能把之前大多数问题都包括进去。

可以在 save.json 里面指定一些逻辑表达式，比如 (![0,0,0]&[0,0,1]&[0,0,2]&[0,0,3])&(!(![0,0,0]&![0,0,1]&![0,0,2]&![0,0,3]))，然后搜的时候如果不满足这些逻辑表达式就回溯。

要不要加一个 skewgutter symmetry?
差不多是这个
x = 13, y = 12, rule = B3-ekqy4j5acy6cn7c/S2-in3aijnr4aw6ci7c8 4bo$3bobo$bo3bo$3b2o$o2bo$bobo$2bobo5b2o$3bo2bo2bo2bo$5bob3obo$6bo$7bo 2bo$8bo!

这样就可以直接导到apgsearch，不用点很多下START。（搜低周期震荡子筛除伪震荡子的时候）

@AlephAlpha

Using latest master:
$ cargo run 10 10 2 --symmetry 'D2\'

Output:
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: SquareWorldError', tui/src/args.rs:316:22 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Symmetries C4, D2/, D4X, and D8 give same error.
Transforms R90, R270, F/, and F\ also give same error.

v0.3.3 works as expected.

我觉得手写有时候有点烦，有时候能不能支持rle吗 @AlephAlpha

I think you should know about that, a lot of people have talked about it(at least the web version)

除了早期从 WLS 抄来的那些改进之外，rlifsrc 引入的改进中最简单又有效的是这两个：前排非空（non-empty front），和对角宽度。其中前排非空的选项已在 4.0 版删除：这个功能还在，只是改成根据对称性、位移、搜索顺序等条件自动开启。

不过和对角宽度比起来，前排非空不是这么直观直观。我也一直害怕有 bug，还是要写点文档总结一下，顺便也为实现 #51 中提到的更多对称性作准备。

前排非空

前排非空的想法很简单：比如说，假如我们要搜 17x5 大小向上飞的 c/3 飞船，搜索顺序是从左到右一列一列地搜，找到了这么一个玩意儿：

注意它在一个周期中的三代，最左边一列都是空的。如果我们把它 ⬅️ 向左移动一列，结果还是满足所有的条件：

于是，我们可以干脆增加一个第一列非空的条件，这样可以有效地缩减搜索空间。

这种情况下我们把第一列叫做前排（front）。如果搜索顺序是一行一行地搜，则把第一行叫做前排；如果搜索顺序是对角方向，则把第一行和第一列都算作前排。

不过，我们还需要定义什么是空——由于 B0 规则的存在，我们不能简单地把死细胞定义为空。这里我们采取的定义是：对于每一代，如果一个细胞的状态和搜索范围之外的细胞一致，则称其为空。也就是说：

• 对于无 B0 的规则，“空”的定义很简单：死细胞即为空。
• 对于有 B0 没有 S8 的 Life-like （含 non-totalistic）的规则，第奇数代死细胞为空，第偶数代活细胞为空。这里把每个周期的最前面一代称为第一代，而非第零代。
• 对于有 B0 没有 S8 的 Generations 规则，若共有 n 种状态，则对于第 i 代，i 模 n 余 1 时死细胞为空，余 2 时活细胞为空，余 3 时刚开始死亡的第一代为空，依此类推。上一条可看作这一条的特例。
• rlifesrc 不支持既有 B0 又有 S8 的规则，此类规则需手动转化为无 B0 的规则再搜。

当我们说一个细胞集合（比如说前排）为空时，指的是集合中每一个细胞都为空。同样到了，说这个集合非空指的是至少有一个细胞非空。

搜索的时候，我们可以用一个变量来记录前排中未知或已知非空的细胞的数量；每次搜到一个在前排的细胞，都根据其状态的变换来更新这个变量；如果变量变成了0，则说明当前的 partial result 不满足前排非空的条件，没必要在它上面浪费时间，可以直接回头。

然后问题来了：什么时候可以要求前排非空？

或者换句话说，怎样的搜索条件有平移不变性，即任何满足此条件的图样在向指定方向平移之后还满足同样的条件？

条件的平移不变性

我们按网页版的 Setting，从上到下一条一条分析：

• 规则：这个当然无关。
• 宽度：
  • ⬆️ 向上平移一格不影响宽度。
  • ⬅️ 向左平移一格会改变图样的左边界，但平移的前提是最左一列为空，因此此条件也不影响结果。
  • ↖️ 向左上（对角方向）平移时的前提是第一行第一列皆空，因此也没有影响。
• 高度：与宽度同理。
• 周期：也无关。
• dx：只是平移的话没有问题。
• dy：也没问题。
• 对角宽度：
  • ⬆️ 向上平移一格时可能会把图样移出对角宽度的范围。这是第一个不满足平移不变性的条件。
  • ⬅️ 同上。
  • ↖️ 向左上平移的话不会有影响。
  • 因此，在设了对角宽度的时候，除非搜索方向是对角方向，否则都不能要求前排非空。
• 变换：
  • Id：恒等变换，完全不变，完全无关。
  • 旋转：平移会导致旋转中心移动，因此不满足平移不变性。
  • 翻转：要翻转轴和平移的方向平行才行，其它情况下不满足平移不变性。
• 对称：
  • C1：没问题。
  • C2/C4：和前面旋转变换的情况一样，不满足平移不变性。
  • D2：要对称轴和平移的方向平行才行，其它情况下不满足平移不变性。
  • D4/D8：不可能两条对称轴都和平移的方向平行，因此不满足平移不变性。
• 最大活细胞数：当然无关。
• 搜索顺序：这不是图样要满足的条件的一部分，但决定了前排的定义。
• 未知细胞的状态选取：这也不是图样要满足的条件的一部分。
• 已知的细胞：已知细胞的坐标是固定的，不满足平移不变性。

后面几个选项也都无关，不一一讨论了。

也就是说，我们需要考虑的只有对角宽度、变换、对称、已知的细胞这几个选项。

半个前排

但有时我们不需要考虑整个前排：比如说，假如我们要搜 45x10 大小向左飞的 c/4 飞船，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿：

注意它一个周期的四个回合中，第一列的上半部分都是空的。如果我们把它上下翻转一下，结果还是满足所有的条件：

因此，我们可以要求一个第一列的上半部分非空，进一步缩减搜索空间。

（写到这里忽然发现这个条件还可以进一步加强：把第一列所有回合的细胞状态写成一个二进制数，然后要求这个二进制数不能小于把它所有数位左右翻转的结果；或者把第一列的上半部分和下半部分写到两个二进制数中，然后比较这两个数就行了。不过 Rust 中整数大小是有限的，用 64 位的整数表示的话就不支持前排超过 64 个细胞的情形；Generations 的规则要把二进制改成 n 进制，能支持的前排细胞数更少，实现上也更复杂一些。）

类似地，如果搜索顺序是一行一行地搜，则只考虑第一行的左半边；如果搜索顺序是对角方向，只考虑第一列。

为了能加上这个条件，我们要要求搜索条件在翻转变换下不变。

如果以图样中心处为原点的话，这里涉及到的三种翻转如下：

• 左右翻转：(x,y) => (-x,y)
• 上下翻转：(x,y) => (x,-y)
• 以对角线为轴翻转：(x,y) => (y,x)

（等等，写到这里我发现我的实现有个严重的 Bug：非各向同性的规则是不能随便翻转的！这有点难办……等改好这个 Bug 再继续写吧。）

（以上 Bug 已修复……希望不要引入新 Bug……）

和之前一样，所有设置从上到下一条一条分析：

• 规则：如果是各向同性的规则就不要紧，但各向异性的规则就要讨论规则的对称性，不然会出前面说的这个 Bug……
• 宽度、高度：
  • ⬆️⬅️ 左右翻转和上下翻转都不影响宽度、高度。
  • ↖️ 能以对角线为轴翻转的前提是宽度等于高度。
• dx、dy
  • ⬆️ 左右翻转会使 dx 变成 -dx，因此 dx 必须为 0；dy 不影响。
  • ⬅️ 上下翻转会使 dy 变成 -dy，因此 dy 必须为 0；dx 不影响。
  • ↖️ 以对角线为轴翻转会让 dx 和 dy 互换，因此 dx 必须等于 dy。
• 对角宽度：
  • ⬆️⬅️ 只有无对角宽度时才能左右翻转和上下翻转。
  • ↖️ 以对角线为轴翻转的话不会有影响。
• 变换：此变换必须和相应的翻转可交换。
  • Id：恒等变换，完全不变，完全无关。
  • 旋转 90°/270°：和所有翻转都不可交换，也就是说先旋转后翻转和先翻转后旋转结果不同。
  • 旋转 180°：这个和所有翻转都交换。
  • 翻转：任一个翻转都和自己可交换。此外左右翻转和上下翻转可交换，以对角线为轴和以反对角线为轴的两个翻转也可交换。别的都不行。
• 对称：这次需要此对称性要求不变的所有变换都和该翻转可交换
  • C1：没问题。
  • C2：和前面旋转 180° 的情形一样，都可以。
  • C4：和前面旋转 90° 的情况一样，都不行。
  • D2：需要 D2 的对称轴和翻转轴平行或垂直才行。
  • D4：需要 D4 的对称轴和翻转轴平行或垂直才行。两个对称轴，一个平行一个垂直。
  • D8：不行。
• 最大活细胞数：当然无关。
• 搜索顺序：这不是图样要满足的条件的一部分，但决定了沿哪条轴翻转。
• 未知细胞的状态选取：这也不是图样要满足的条件的一部分。
• 已知的细胞：已知细胞的坐标是固定的，不满足翻转不变性，除非它就在翻转轴上。

看起来变换、对称和已知细胞的条件比前排非空要宽松。不过我们是在要求前排非空的前提下才能考虑半个前排，所以实际新增的条件只有规则（差点又忘了）、宽度、高度、dx、dy 这些。

前排的第一代

前面说的前排指的是前排的每一代。要求前排非空等价于要求至少有一代的前排非空。于是，对于振荡子（也就是 dx、dy 为 0 的情形），只要规则没有 B0，我们可以干脆前排非空的那一代定为第一代，于是可以要求前排的第一代非空，进一步缩减搜索空间。

但对飞船来说，问题没这么简单。事实上，对于周期为 p 的振荡子，第 p+1 代和第一代是一样的，因此第二代到第 p+1 代也满足原本的条件。但对飞船来说，第 p+1 代相比第一代还会有一个平移，可能会平移出原本的高度和宽度所规定的范围。

不过，搜索飞船的一种常见情况是：每个周期仅平移一格，而且平移的方向正好是向着前排。

比如说，假如我们要搜 21x13 大小向左飞的 c/4 飞船，对称性是 D2-，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿（这次把每一代都画出来了，从左到右）：

这飞船前排的第一代是空的。于是，它的第五代只是把第一代向前平移一格，并不会移出规定的范围。也就是说，它的第二到第五代也满足原本的条件：

因此，这种情况下也可以要求前排的第一代非空。

也就是说，如果要要求前排的第一代非空，在前排非空的条件的基础上，我们还需要：

• ⬆️ 一行一行搜时，要 dx = 0, 0 <= dy <= 1，而且规则不能有 B0。
• ⬅️ 一列一列搜时，要 dy = 0, 0 <= dx <= 1，而且规则不能有 B0。
• ↖️ 对角方向搜时，要 dx = dy, 0 <= dx <= 1，而且规则不能有 B0。

（写到这里忽然发现，没必要完全禁掉 B0 的规则，其实可以改成要求前排的前两代非空；对于 Generations 的规则，若有 n 种状态，则可以改为前排的前 n 代非空。这里需要的改动很小，已改。）

没那么前的前排

上一节的讨论只适合飞船每个周期向前平移一格的情形。如果平移不止一格呢？

此时，我们不能再要求前排的第一代非空。事实上，此时前排的第一代必须是空的，因为这些细胞的前一代的整个邻域都已经在搜索范围之外。

不过，我们可以把“前排”往后挪一挪。

比如说，假如我们要搜 12x15 大小向左飞的 2c/5 飞船，对称性是 D2-，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿（这次把每一代都画出来了，从左到右）：

它第一代前两列都是空的。第六代只是把第一代向前移动两格，不会移出规定的范围。于是，和之前一样，我们可以考虑它的第二到第六代：

于是，我们可以干脆把前排的定义从第一列移到第二列，继续要求新的“前排”的第一代非空。

一般地，如果飞船每个周期向前平移 d 格（平移的方向必须向着前排），我们就可以把前排的定义修改为第 d-1 行/列/行加列。

但我们还要说明新的要求比原本要求的前排（所有代）非空要强，不然直接用原本的要求不就行了吗？

这也不难。一个细胞非空的必要条件是它前一代的邻域中至少有一个细胞非空。若飞船周期为 p，新的前排是第 d-1 列，那么新前排的前一代对应于第 p 代往前刚离开搜索范围的那一列，其邻域的三列只有一列在搜索范围之内，也就是第 p 代的第一列。因此，只要要求新的前排第一代非空，旧的前排就一定也非空。

于是，我们可以把上一节的条件改进为：

• ⬆️ 一行一行搜时，要 dx = 0, dy >= 0，而且规则不能有 B0，此时。
• ⬅️ 一列一列搜时，要 dy = 0, dx >= 0，而且规则不能有 B0。
• ↖️ 对角方向搜时，要 dx = dy, dx >= 0，而且规则不能有 B0。

此时“前排”的定义为：

• ⬆️ 若 dy = 0，则前排还是第一行，否则改为第 dy-1 行。
• ⬅️ 若 dx = 0，则前排还是第一列，否则改为第 dx-1 列。
• ↖️ 若 dx = 0，则前排还是第一行加第一列，否则改为第 dy-1 行加第 dx-1 列。

目前 rlifesrc 采用的前排非空的条件就是这么多。

自定义对称性

前面说了这么多，一方面是为了总结和查 bug，另一方面是为实现 #51 中提到的自定义对称性做准备。

其实说“自定义对称性”有点不准确，因为这也包含了一些不属于对称性的条件。

我们想要支持哪些条件呢？先试着列举一下。

• 给定一个细胞，指定其状态。这个其实已经通过“已知的细胞”实现了。
• 给定一个细胞，要求其状态和另一个指定的细胞一致/不一致。
• 给定一个区域，要求区域内的所有细胞都处于某个指定的状态。
• 给定一个区域，要求其状态和该区域通过某种变换得到的另一个区域一致/不一致。

区域怎么定义，允许哪些变换，都是需要讨论的。

自定义对称性最好还能写成一种方便读取的格式，比如说 JSON。

（未完待续）

I lost a randomized search to a logout from my school, who loves logging off people if they lose connection for 5 minutes or so. How do I get that search back when I don't know the seed?
Let us seed the PRNG.

@AlephAlpha RT。