wwei47 wrote: June 14th, 2021, 9:21 am
Edit 2: It can also decompose the triple and quad pseudo still lives. For A5e, we must sometimes branch, since A5e implies two possible different decompositions. This is only necessary if the A5e has three different colors after override (A5e is handled last):
I think that a graph algorithm operating on a graph of A5e inductions could help. It's A4n5e that makes it so much harder than it would be otherwise due to the multiple decomposition thing. It's not practical to list all decompositions, because there could be around 2^n different decompositions, and that would explode quickly. The algorithm assigns each island a different color, and forces interacting islands (Except for A5e inductions) to have the same color. Wicks can be detected by seeing if the same color occurs at (50,0), (0,100), or (50,100) offsets anywhere on the board. The wicks are then all deleted, and everything that doesn't involve purely an A5e induction is lifted off the board and transferred to another board. Then it's time to deal with what's left: Stuff involving purely A5e inductions. I haven't figured out exactly what to do for this part yet.
A4n5e, making everything so difficult. A4n is involved in allowing decomposition in the first place.
EDIT: Lifting off non-A5e stuff is a bit harder than it first seems due to A4c and A4y interactions:
Code: Select all
x = 100, y = 21, rule = B3/S23Super:T100,50
58.2I.2I$57.I.I.I$53.2G.I.I2.I$53.2G.2I3.I.I$22.G.2G36.2I$22.2G.G27.2M
.2E6.2I$50.2M2.M.E.E5.I$21.C.2E25.M.2M3.2E7.I$19.3C.E.E22.2M15.2I$18.
C5.2E22.M6.4E8.2I$19.C6.2E.E19.M5.E3.E7.I.I$18.2C6.E.2E18.2M8.2E8.2I$
2A8.2A8.2C8.2E8.2A8.2M8.2E8.2I8.2A8.2A$A2.2A5.A2.2A5.C2.2A5.E2.2A5.A2.
2A5.M2.2A5.E2.2A5.I2.2A5.A2.2A5.A2.2A$.A.2A6.A.2A6.C.2A6.E.2A6.A.2A6.
M.2A6.E.2A6.I.2A6.A.2A6.A.2A$2A8.2A8.2C8.2E8.2A8.2M8.2E8.2I8.2A8.2A$.
A.2A6.A.2C6.C.2E6.E.2A6.A.2M6.M.2E6.E.2I6.I.2A6.A.2A6.A.2A$A2.A.A4.A2.
C.C4.C2.E.E4.E2.A.A4.A2.M.M4.M2.E.E4.E2.I.I4.I2.A.A4.A2.A.A4.A2.A.A$2A
2.A.A3.2A2.C.C3.2C2.E.E3.2E2.A.A3.2A2.M.M3.2M2.E.E3.2E2.I.I3.2I2.A.A3.
2A2.A.A3.2A2.A.A$5.A2.2A5.C2.2C5.E2.2E5.A2.2A5.M2.2M5.E2.2E5.I2.2I5.A
2.2A5.A2.2A5.A2.2A$6.2A.A6.2C.C6.2E.E6.2A.A6.2M.M6.2E.E6.2I.I6.2A.A6.
2A.A6.2A.A!
But those can probably be handled the same way that they're handled in the "override" phase.
Edit 2: This is a better A4y interaction example:
Code: Select all
x = 5, y = 11, rule = B3/S23Super:T100,50
3.2I$3.I$4.I$3.2I$2G$2G.2C$3.2C$2E$E$.E$2E!
Edit 3: No, the graph algorithm idea won't work the way that I thought...
Code: Select all
x = 12, y = 12, rule = B3/S23Super:T100,50
6.2G.2I$6.2G.2I2$5.A.3A.A$5.2A.A.2A$3.2A$2E2.A$2E.A$3.2A$2C.A$2C2.A$3.
2A!
Edit 4: I'm able to separate objects that apgsearch sticks together, but I haven't finished the A5e portion of the code yet.

- Screenshot 2021-06-15 4.04.51 PM.png (9.62 KiB) Viewed 3794 times
Edit 5: I did a DFS to exhaustively list decompositions. At the same time, I don't think I would want to use this as an stdin-I simply think it's not fast enough and that the algorithm could break. I want to rewrite this with the algorithm mniemiec suggested-something I call bispectral decomposition.
Edit 6: I feel silly now.
Edit 7: Very silly indeed.
Edit 8: Why am I doing this lol
Edit 9: I plan to make around 45 more edits after this.
Edit 10: Bispectral decomposition works like this:
Edit 11: First, I make an p+1-generation stack of all of a pattern's generations.
Edit 12: Now, for my own trick that fixes what could be a fatal flaw in my color decomposition algorithm.
Edit 13: I start at the LAST generation, not the first.
Edit 14: You see, a spark like in the color decomposition example with 2 Kok's Galaxies dies off.
Edit 15: If I were to trace forwards, the spark would not be identified as being part of a Kok's Galaxy. It dies off without interacting.
Edit 16: If I trace backwards, the spark is born from 3 neighbors. So I can label that as part of the Kok's Galaxy.
Edit 17: Of course, I still have to label the cells with any of A4knqt5r6i as 2-interacting, and with A4cy5e as 3-interacting.
Edit 18: In other words, a 2-interacting cell means that if one side gets marked during bispectral decomposition, then the other side automatically gets marked as well.
Edit 19: For 3-interacting, the rules are different. For A4cy, if three cells get marked, then the fourth one gets marked too.
Edit 20: For A5e, if the two isolated corner cells get marked, then the three adjacent ones get marked too.
Edit 21: The bispectral part comes from how we mark the cells.
Edit 22: We mark the first cell with (0,0), and other cells relative to it.
Edit 23: This is essentially two different spectra, one in the x direction, one in the y direction. This method also has built-in wick detection and unwrapping.
Edit 24: It works like this. If we need to set a cell with a different coordinate than it already was, then we have a wick on our hands. No board quadrupling needed.
Edit 25: Because we don't wrap the coordinates on the torus edge, the coordinates correspond to locations on an infinite grid.
Edit 26: Once we run out of cells we can mark, we see if there's any A5e that needs branching on. If there is, then we branch into a DFS search until we get everything.
Edit 27: After that, we've truly gotten everything that's part of the same object. If it's a wick, we delete it. If it's not a wick, we still delete it, but we also transfer it to another grid and unwrap it. It might be worth using an error state for wicks.
Edit 28: Do this until the last generation is empty.
Edit 29: Only 25 edits to go!
Edit 30: What else can I write about...?
Edit 31: I remember investigating a weird rule involving 3xn oscillators that were 1xn every other generation.
Edit 32: Sadly, apgsearch didn't work on it because I can't compile it for B0 non-totalistic

Edit 33: There were also a bunch of other interesting 1D alternating rules.
Edit 34: But this one was especially promising.
Edit 35: I wonder if 9c/10 will require a distributed search or something.
Edit 36: 18 edits left, I'm 2/3rds of the way there!
Edit 37: It's strange how even I can find an 8c/9. If I remember correctly, the frontend was nonstandard too.
Edit 38: I wonder what (m,n)c/m speeds are possible with 2 alternating rules.
Edit 39: So far, the known examples are (4,1)c/4, (6,2)c/6, and (8,2)c/8.
Edit 40: What makes (2,1)c/2 impossible, but higher-period ships like (4,2)c/4 possible?
Edit 41: What makes some catalysts so much easier to find than others?
Edit 42: 12 edits left!
Edit 43: I'm also curious about 3 alternating rules, since that's the next simplest case. (3,1)c/3, (3,2)c/3, and a few other speeds live here.
Edit 44: Where can stripey ships exist? They make high-period ships easier to find, since they tend to tame explosions a bunch.
Edit 45: 9 more edits to go -> 5/6ths of the way there
Edit 46: I like dr.
Edit 47: Stripes also seem to tame plain old B2a as well.
Edit 48: 6 more edits->8/9ths of the way there
Edit 49: There are 32768 3-alternating rules.
Edit 50: We can make these assumptions:
Code: Select all
1 a1 a2 a3 a4
0 b1 !b1 b3 b4
0 c1 !c1 c3 c4
Code: Select all
1 a1 a2 a3 a4
1 b1 b2 b3 b4
0 c1 !c1 c3 c4
Edit 51: 3 edits->17/18ths of the way there
Edit 52: 2 edits->26/27ths of the way there
Edit 53: 1 edit->53/54ths of the way there
Edit 54: 54

- 54.png (87.43 KiB) Viewed 3716 times