Smallest Spaceships Supporting Specific Speeds (5s) Project

[Macbi]

Note that at the moment LLS can't rule out sub-periods for ships, so for a speed like (4,2)c/6 you just have to hope you don't get a (2,1)c/3. The SAT solver has some randomness to it, so you can always try running the search again if you don't like the result you got the first time. Or use "-n" to run the search repeatedly (it helps to do this in "-v1" mode, so you don't get swamped by other output).

[AforAmpere]

10c/16:

Code: Select all

x = 3, y = 3, rule = B2aci3cr4in5jr/S1e2en3jq4jqtw5y
obo$2bo$2bo!

(5,2)c/8:

Code: Select all

x = 3, y = 3, rule = B2ace3r4iknrz5ejr/S1e2ekn3a4jtw5a
obo$2bo$2bo!

(4,2)c/8:

Code: Select all

x = 3, y = 3, rule = B2aci3ry4in5ijnr6a/S1e2en3aj4jrtw5ijqy6a7e
obo$2bo$2bo!

(6,4)c/10:

Code: Select all

x = 3, y = 3, rule = B2ac3ery4inty5jr6a/S1e2e3aq4ejqty5jy
obo$2bo$2bo!

6c/14 diagonal:

Code: Select all

x = 3, y = 3, rule = B2aci3r4ijn5jr6e/S1e2cen3kq4jtwz5y
obo$2bo$2bo!

I still haven't gotten the LLS to work, so I did a search of rules with this pattern.

EDIT, 9c/26 diagonal:

Code: Select all

x = 3, y = 3, rule = B2ac3er4intwy5aijkr6ak/S1e2e3jky4-ceinz5ny
obo$2bo$2bo!

[wildmyron]

Wow, great ships everybody.

@Macbi: Fantastic work with your search program. I've been dreaming of such a program but the best I can manage is some random search scripts. What do you think will be the practical limit for small ship periods using LLS?

I haven't tried to get LLS running yet, but here's a few results from my script.

7c/9 orthogonal, 8 cells (I'm guessing this will be beaten pretty soon):

Code: Select all

x = 3, y = 5, rule = B2acn3e4cjky5qy/S2ae3aejr5eqr
2bo$3o2$3o$2bo!

14c/18 orthogonal, 13 cells

Code: Select all

x = 7, y = 7, rule = B2acn3ey4cjy5ry/S2ae3acejr5y
6bo$3bo2bo$3bob2o$o$3bob2o$3bo2bo$6bo!

smaller 10c/14, 7 cells

Code: Select all

x = 6, y = 5, rule = B2aci4aknrz5j/S03r4i5y
5bo$3bobo$o$3bobo$5bo!

[Macbi]

@Macbi: Fantastic work with your search program. I've been dreaming of such a program but the best I can manage is some random search scripts. What do you think will be the practical limit for small ship periods using LLS?

Hard to say. In the oscillator thread I managed to get it up to period 26 with no difficulty, but it will be harder for ships. To some extent it just depends on how easy the problem is. If there happen to be lots of ships of that speed then LLS will find one quite quickly, but if there's only one rule and ship that will work then LLS will take a while to find it.

One thing I noticed is that the search for a population 3 (or whatever) ship was sometimes much faster than the search for ships of any population. At first I had been first trying to find a ship of any population, and then trying successively smaller populations. But in fact it seems faster to impose some population limit from the very beginning.

For orthogonal and diagonal ships LLS can probably be pushed a bit further by imposing symmetry. Of course you don't want to do this until you have to because there might be a smaller asymmetric ship.

When we run out of low-hanging fruit there are a lot of different tweaks I could try to improve speed.

[praosylen]

10-cell 6c/7o:

Code: Select all

x = 3, y = 12, rule = B2-ek3aer4aciyz5inr6-ei7e/S1c3-cky4acekqwz5iry6ack7e
2bo$obo2$2bo2$2bo$2bo2$2bo2$obo$2bo!

EDIT: 17-cell 7c/8o:

Code: Select all

x = 3, y = 17, rule = B2-ik3ejkn4eijt5cknr6-ai7e8/S12n3akqry4ijkqt5-knqr6i
bo$2o$2bo3$b2o$2bo$2bo$o$2bo$2bo$b2o3$2bo$2o$bo!

EDITs 2+: 4-cell 7c/9o:

Code: Select all

x = 2, y = 4, rule = B2ace3cq4-nrty5cinqy6-e/S2-c3eq4qtyz5-acky6-an7e
bo$o$bo$bo!

4-cell (7,1)c/9:

Code: Select all

x = 3, y = 4, rule = B2aci3acq4aijky5-in6aen7e/S1c2a3qy4aiqrtyz5-eqr6k7c8
2bo$2bo2$obo!

3-cell 5c/7o:

Code: Select all

x = 2, y = 4, rule = B2-en3ay4cirw5-ijny6-ae7c8/S1c2ai3ek4cjnr5aknqy6-ck78
o$bo2$bo!

[AforAmpere]

Nice! Have you tried looking for any of the not found p8 ships yet? Like (4,1)c/8, and similar.

EDIT, 8c/10, 7 cells:

Code: Select all

x = 5, y = 7, rule = B2ace3q4a5iny/S2aik3ae4cin5q8
o$4bo$4bo$3bo$4bo$4bo$o!

EDIT 2, (6,2)c/12:

Code: Select all

x = 7, y = 5, rule = B2ack3acq4jr5acj6a/S02n3acijk4ryz5i
bo3bo$obo$5bo2$6bo!

[praosylen]

(4,1)c/8, 3 cells:

Code: Select all

x = 3, y = 4, rule = B2-ei3ae4iknqtwz5ceiky6-an/S02aci3jkn4ikryz5ein6aen78
2bo3$obo!

[Macbi]

(4,3)c/8, 3 cells:

Code: Select all

x = 2, y = 4, rule = B2aci3akn4iyz5cikr6akn7c/S1c2aei3-anqr4ijnqrtw5-ae6e
o$bo2$bo!

[AforAmpere]

Smallest bounding box and pop (2,1)c/3?

Code: Select all

x = 4, y = 5, rule = B2-ek3jy4-ijkn5-cjn6-ck78/S01e2-ai3ijnqy4-ajkn5-aijn6-a78
3bo2$2b2o$bo$o!

Same for (2,1)c/4:

Code: Select all

x = 3, y = 3, rule = B2-ei3kqr4-ajyz5-acr6ain7c8/S2i3-eijn4-kwy5-eny6-e78
obo$2bo$2bo!

EDIT, 4 cell (5,1)c/8:

Code: Select all

x = 2, y = 4, rule = B2ac3nr4kqryz5ckq6-ik7e/S01e2ci3cikny4-qr5jr6ikn7c8
o$bo$bo$bo!

EDIT 2, 3 cell (4,2)c/8:

Code: Select all

x = 3, y = 4, rule = B2-en3cnr4ckntwyz5-ijqy6ae78/S01e3eikn4cjktwyz5nqry6ckn8
obo3$2bo!

[Macbi]

3 cell (5,1)c/8

Code: Select all

x = 2, y = 4, rule = B2aci3ary4acinqwy5-cknr6-cn7/S1c2an3cikn4aekz5-eikn6ekn7e
bo2$bo$o!

Hahaha (Now that we have LLS working on Windows this was my last chance to find the ship that AforAmpere's signature mentioned, but they came in with a 4-cell example just before me.)

[AforAmpere]

Hey, that is better, nice job!

EDIT, 6 cell (5,3)c/8:

Code: Select all

x = 3, y = 5, rule = B2acn3ajky4eiq5-ackn6aek7e8/S12cei3ceiry4cjnrty5-aknr6-ai78
o$bo$2bo$2bo$obo!

Better, 5 cells:

Code: Select all

x = 3, y = 4, rule = B2ace3any4-cekr5-enry6a8/S1e2kn3ainr4-nqtz5eikr6an78
o$bo$b2o$bo!

4 cells:

Code: Select all

x = 3, y = 3, rule = B2aci3-eijn4enqz5ejk6ekn8/S01e2ce3y4ejrtwyz5ajkq6-i7
obo$2bo$2bo!

EDIT, 4 cell 6c/8:

Code: Select all

x = 2, y = 4, rule = B2ace3ey4cjknqyz5-jqry6cin7e/S2akn3acqr4-cikyz5aen6-ck7e8
bo$bo$o$bo!

[Goldtiger997]

Here's a 7-cell (6,1)c/8:

Code: Select all

x = 4, y = 7, rule = B2-ek3ak4acerz5jnq6cek8/S02aen3eknry4-jkqyz5acnr6kn7
3bo2$3bo$bo$2bo$2bo$obo!

I'll see if I can reduce the population. Using LLS is fun!

@AforAmpere, How are you reducing the populations so effectively?

Edit: 6 cells now:

Code: Select all

x = 3, y = 6, rule = B2-ei3ejk4-aetz5ejky7c/S12in3jkry4aijy5jknq6n
bo$2o$2bo2$2bo$o!

[AforAmpere]

Here's a 5-cell one, it might be able to be smaller:

Code: Select all

x = 2, y = 6, rule = B2ace4acqz5-jqr6-e/S2-ce3acejy4inrtyz5-ajqr6-ac8
o2$bo$bo$o$bo!

EDIT, 4 cells:

Code: Select all

x = 2, y = 4, rule = B2-ik3ck4akq5cijkr6-k7e8/S2-cn3cenry4cnqrtyz5acei6ain7e8
bo$o$bo$bo!

4-cell (6,2)c/8:

Code: Select all

x = 2, y = 4, rule = B2-kn3nry4aenrt5eqy6ci7c/S01e2cin3jkr4t5-aiqy6ae7e8
bo$bo$bo$o!

I am using larger bounding boxes with smaller max populations.

9-cell 6c/7, I am reasonably sure this is now optimal:

Code: Select all

x = 2, y = 9, rule = B2ack3eqr4cknqy5jy6cin7e/S02-cn3nr4aejnqr5enry6ek8
bo$bo$o$bo$bo$bo$o$bo$bo!

3-cell (4,2)c/9:

Code: Select all

x = 2, y = 4, rule = B2aci3a4ceiqtw5-eijr6-ac78/S1c2a3-ciq4-ikz5-aenq6a7e
o$bo2$bo!

3-cell (4,3)c/9:

Code: Select all

x = 2, y = 4, rule = B2aci3ay4ciqtyz5-ajnq6-ci78/S1c2a3ceiky4-ktwy5-aey6aei7c8
o$bo2$bo!

3-cell (5,1)c/9:

Code: Select all

x = 3, y = 5, rule = B2-k3er4-jtw5einr6ck8/S2aik3cenry4nqz5aqr6-k7c8
o2$2bo2$2bo!

3-cell (5,2)c/9:

Code: Select all

x = 2, y = 4, rule = B2aci3ackny4-ejkrt5-ckr6aek78/S012ek3in4aejqtz5cinq6-ai7e
bo2$bo$o!

3-cell (5,3)c/9:

Code: Select all

x = 2, y = 4, rule = B2aci3ay4ajktw5akq6aik7c8/S1c2aen3iqry4eiknqrz5eiry6cik7c8
bo2$bo$o!

4-cell (5,4)c/9:

Code: Select all

x = 3, y = 4, rule = B2ac3eq4ntyz5aqr6-en7e8/S12ak3-cnqr4enqrwy5-eiky6-ek
2bo2$b2o$o!

4-cell (6,1)c/9:

Code: Select all

x = 2, y = 4, rule = B2-i3eky4-akqw5aknq6-a78/S2ac3cenry4jknqw5-acij6eik
bo$bo$bo$o!

4-cell (6,2)c/9:

Code: Select all

x = 2, y = 4, rule = B2acn3enry4aci5ceiny6ain7c/S01e2-ae3ackr4-cekwy5enqy6-ik7c8
bo2$2o$bo!

4-cell (6,3)c/9:

Code: Select all

x = 2, y = 4, rule = B2ace3cnq4ajknqyz5ijry6ain7c8/S2ak3eiqy4eqrtw5aknr6ckn
bo$o$bo$bo!

9-cell (7,2)c/9:

Code: Select all

x = 3, y = 6, rule = B2ack3acn4acikntz5cijky6ikn7c/S2aei3ejqr4aeqr5aciq6-in7c
o$b2o$b2o$b2o$bo$bo!

[Goldtiger997]

I've been searching for a (7,1)c/8 for several hours with "-b 14 14", with no success so far. ("-b 13 13" was apparently unsatisfiable.)

In the mean time hear are some other ships. A * next to its cell count means it is optimal.
Edit: Ignore the optimized markings; I now know them to not necessarily be correct.

(4,3)c/10, 3 cells*

Code: Select all

x = 2, y = 4, rule = B2aci3ejy4cjknqwy5-aej6-ac7/S12k3-cknq4cikn5-ajky6-en8
o$bo2$bo!

(5,1)c/10 4 cells*

Code: Select all

x = 2, y = 4, rule = B2aek3aen4-aikqw5eij6-cn7e8/S2aik3cijqr4-acnty5-ijk6ci7c8
o$bo$bo$bo!

(5,2)c/10 4 cells*

Code: Select all

x = 2, y = 4, rule = B2aci3cnr4acejtwy5ikq6aei7c/S02ei3-cnqy4acjkqz5eiknr6-k8
bo2$2o$bo!

(5,3)c/10 4 cells*

Code: Select all

x = 2, y = 4, rule = B2ai3cny4-ejknz5iky6ekn7e/S1c2-ce3-ijy4ciwz5aiqry6aik7e8
bo$bo$bo$o!

(5,4)c/10 3 cells*

Code: Select all

x = 2, y = 4, rule = B2-ek3ak4ctwy5-nqy6-cn7/S1c2ak3acej4acjnrwz5eijky6-k7e
o$bo2$bo!

[Macbi]

A * next to its cell count means it is optimal.

How do you know these ones are optimal?

[Bullet51]

How do you know these ones are optimal?

3 is the least number of cells for a spaceship, since every pattern with less than 3 cells is 180°-rotational symmetric.
But I'm not sure why the 4-cell spaceships are claimed optimal.

So:

(5,1)c/10 4 cells*

Code: Select all

(5,1)c/10

(5,2)c/10 4 cells*

Code: Select all

(5,2)c/10

(5,3)c/10 4 cells*

Code: Select all

(5,3)c/10 

How do you know these ones are optimal?

[Goldtiger997]

How do you know these ones are optimal?

Well I'm probably understanding this wrong, but when I did the equivalent searches with "--force_at_most 3" it returned unsatisfiable. The bounding box I had was large enough (I think) to fit all 3 cell ships in it, so there shouldn't be any 3-cell sp

Code: Select all

aceships for those speeds. Therefore the minimum is >= 4.

Like I said, it's quite likely that I don't understand what I'm talking about...
Edit: I turns out I was right; I didn't know what I was talking about.

Anyway, a 3-cell 7c/10:

Code: Select all

x = 3, y = 5, rule = B2-k3cqry4-acejq5aery6ckn7c/S2-ck3acnry4-aknz5eqy6ce7c8
o2$2bo2$2bo!

(7,1)c/10 4 cells:

Code: Select all

x = 2, y = 4, rule = B2ac3cenqr4-ejnqr5ceqr6-c7e8/S01e2ei3-cky4atw5-ay6-ci78
bo$2o2$bo!

(7,2)c/10 4 cells:

Code: Select all

x = 3, y = 4, rule = B2ac3aekq4acertwz5-aikr6ei7c8/S2-ae3aijy4einqwy5cei678
2bo2$2bo$obo!

(7,3)c/10 4 cells:

Code: Select all

x = 3, y = 3, rule = B2-ik3jr4cknty5acjqr6cen7/S1e2n3ajky4akqt5enqy67e8
obo$2bo$2bo!

[Macbi]

The bounding box I had was large enough (I think) to fit all 3 cell ships in it

I don't think there's a single bounding box that contains all 3 cell ships. A three cell ship could consist of two cells near to each other, and the other one quite far away. The single cell stays where it is (due to S0) while the pair of cells interact in a way that makes a symmetrical pattern grow around them. Eventually the pattern grows to the location of the single cell, which breaks its symmetry, and then it collapses back to the first generation translated by however much.

[77topaz]

I don't think there's a single bounding box that contains all 3 cell ships. A three cell ship could consist of two cells near to each other, and the other one quite far away. The single cell stays where it is (due to S0) while the pair of cells interact in a way that makes a symmetrical pattern grow around them. Eventually the pattern grows to the location of the single cell, which breaks its symmetry, and then it collapses back to the first generation translated by however much.

Yeah, but for a given period the three cells can only be so far removed from each other for them to even be able to interact within the period. Hence, all three-cell ships of a given period, if they exist, must exist within a certain bounding box.

[Macbi]

Yeah, but for a given period the three cells can only be so far removed from each other for them to even be able to interact within the period. Hence, all three-cell ships of a given period, if they exist, must exist within a certain bounding box.

That's true.

By the way, even if someone does calculate the bounding box size needed, it's not enough to run "-b x y" in LLS. The bounding box LLS uses is for the entire evolution of the pattern. Maybe I'll add an option --rigorous_spaceship_check that creates a search pattern covering all ships starting in a given box.

[AforAmpere]

6-cell (7,2)c/9:

Code: Select all

x = 3, y = 7, rule = B2ace3aer4ciqr5acjkn6ck78/S2-ek3ijkr4cjnqwyz56ac78
2bo2$2bo2$obo$2bo$bo!

11-cell (6,1)c/7:

Code: Select all

x = 3, y = 10, rule = B2aci3cjnr4-eiqrw5r6ein78/S12ce3ar4ajqrtwz5ejknq6aen7c8
bo2$2bo$2bo$obo$2bo$bo$2bo$obo$2bo!

EDIT, 5-cell (7,2)c/9:

Code: Select all

x = 3, y = 5, rule = B2ac3ary4inqwy5ein68/S1c2aek3er4aknqwz5ijknr6k8
2bo$bo$o$bo$bo!

4-cell (6,1)c/10:

Code: Select all

x = 2, y = 4, rule = B2ace3kny4eq5ack6-e7e8/S1e2cei3-ky4jqrtwyz5ir6i7c8
bo$bo$bo$o!

4-cell (6,2)c/10:

Code: Select all

x = 2, y = 4, rule = B2aci3ae4jntwz5cjry6-c7e/S01e2ek3aceik4acknrty5aikny6in7e8
bo2$2o$bo!

5-cell 8c/10:

Code: Select all

x = 2, y = 5, rule = B2ac3-ijq4an5ekqry6i8/S01c2-cn3eknqr4aij5aijqy6n
bo$bo$o$bo$bo!

5-cell (8,1)c/10:

Code: Select all

x = 2, y = 6, rule = B2-ik3aejky4akqyz5ci6ckn8/S2-ae3jnqr4iknqry5aik6eik7
bo2$bo2$2o$bo!

(6,1)c/7 down to 10 cells:

Code: Select all

x = 3, y = 9, rule = B2ack3ry4aeitw5i6-ae7e8/S2aik3aceky4aqz5-acj6ikn7
2bo2$2bo$b2o2$obo$bo$2bo$obo!

[AforAmpere]

6-cell (8,2)c/10:

Code: Select all

x = 2, y = 7, rule = B2ace3e4aeirtyz5-cy6eik7c8/S2aci3kr4cejnqyz5-aik6i7e
bo2$2o2$bo$bo$o!

9-cell (6,1)c/7:

Code: Select all

x = 4, y = 9, rule = B2-ei3cr4-ejnqr5eijkr6kn/S2aik3aeky4antwz5-ajkn6aci7c
3bo2$3bo$2b2o2$3bo$2bo$3bo$o2bo!

EDIT, 8 cell (6,1)c/7:

Code: Select all

x = 2, y = 8, rule = B2aci3cejq4ijtyz5-ckny6-a78/S12ai3-cein4rwz5ery6c7e8
bo$bo$bo$bo$o$bo$bo$bo!

EDIT 2, 8 cell 6c/7:

Code: Select all

x = 2, y = 9, rule = B2ac3aenr4ejnt5eir6ce7e8/S1e2n3-ceny4ijrty5acnqr6cin7
bo$bo2$bo$2o$bo2$bo$bo!

EDIT a lot, 7 cell 6c/7:

Code: Select all

x = 2, y = 11, rule = B2ack3-cinr4ciqr5aeq6acn8/S02ein3acijn4ainqty5ciky6k7c8
o$o2$o2$bo2$o2$o$o!

3-cell (4,3)c/11:

Code: Select all

x = 2, y = 4, rule = B2aek3cjnqr4eiknqr5-cenr6cik7/S01e2ckn3acr4ajrtz5ejqr6ai
bo2$o$bo!

4-cell 8c/11:

Code: Select all

x = 2, y = 4, rule = B2-ik3ny4aeijkq5ikny6ekn7c8/S2-cn3aknqy4acetw5acejr6-an7c
bo$bo$o$bo!

5-cell 9c/11:

Code: Select all

x = 2, y = 5, rule = B2ac3ekqr4-krty5acjkq6aen78/S1c2-cn3cy4-ejkqw5cejkn6-ae7c8
bo$bo$o$bo$bo!

3-cell (5,2)c/11:

Code: Select all

x = 3, y = 4, rule = B2-ek3-aijk4ckqwyz5ejy6ekn/S012ck3kny4ijknqz5n6aen
2bo2$o$bo!

Can any of the above be improved?

[AforAmpere]

8c/9!

Code: Select all

x = 3, y = 17, rule = B2acn3jn4eint5inqr6aek8/S12en3ekqry4acikrtw5aenqy6ei7e
bo$2o$2bo$b2o2$obo$2bo$2bo$o$2bo$2bo$obo2$b2o$2bo$2o$bo!

EDIT, 3-cell 5c/5:

Code: Select all

x = 2, y = 3, rule = B2-ik3nr4ceknqtw5-qy678/S2i3cejkr4-aknw5-n678
bo$bo$o!

EDIT 2, 3-cell 7c/7:

Code: Select all

x = 2, y = 3, rule = B2ace3cikn4-anqr5acei6-a78/S2n3-eikr4-a5678
o$bo$bo!

3-cell 9c/9:

Code: Select all

x = 2, y = 3, rule = B2-in3er4ckqrwyz5eijnq6-a8/S2ckn3ejq4eijknqz5-einy6-ei78
bo$bo$o!

3-cell 10c/10:

Code: Select all

x = 2, y = 3, rule = B2-i3y4ijkqrwy5ackny6-c/S2ce3-airy4ajrz5cjkq6cen7
o$bo$bo!

3-cell (5,1)c/10:

Code: Select all

x = 4, y = 2, rule = B2aci3ckn4ijknz5-aciq6-a7c8/S12kn3aekqy4citw5k6ae7e8
bobo$o!

[wildmyron]

@AforAmpere: Very nice, particularly the 8c/9. I had spent a while running a search with that front row, but to no avail.

I think it's time to update the collection. I'll do that tomorrow if you haven't gotten to it before me.

[AforAmpere]

I'll get it now.

EDIT, 4 cell 9c/12:

Code: Select all

x = 2, y = 4, rule = B2aci3cjkn4cikqz5-jny6-ik78/S12e3-cey4ejkyz5ijkqy6aek7c8
bo2$2o$bo!

5 cell 10c/12:

Code: Select all

x = 2, y = 5, rule = B2ac3cek4aeikwy5ackqr6en78/S1c2aek3acer4-eknyz5ky6-ac
bo$bo$o$bo$bo!