## slmake

For scripts to aid with computation or simulation in cellular automata.
AlbertArmStain
Posts: 950
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

### Re: slmake

calcyman wrote:
May 30th, 2023, 10:50 am
The old slmake is a greedy algorithm, and the new version that I'm currently writing (pslmake) is a parallelised beam search with heuristic similar to that in the A* search algorithm, where the cost estimate is based on a linear model fitted on diagnostics produced by the old slmake.
Which is still a greedy algorithm, but not as greedy or slow as slmake. It’s still greedy though.
calcyman wrote:
May 30th, 2023, 10:50 am
I don't see how it's related to travelling salesman? The problem is to find a short path from a single block to the desired pattern in the (infinite) directed graph where each node is a constellation and each directed edge corresponds to a glider collision; this is a pathfinding problem. On the other hand, travelling salesman is about finding a minimum-length path/cycle that visits all nodes of a finite graph with weighted edges, which is a very different sort of problem (NP-complete as a function of the size of the graph, whereas pathfinding is polynomial-time in the size of the graph).
I was referring to a construction arm and finding a minimal path for the construction arm. Is there a route optimization for a 90 degree salvo? What about for a 0 degree single channel construction arm?

AlbertArmStain
Posts: 950
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

### Re: slmake

Does pslmake have a feature where you can specify to construct left to right or vise versa?

calcyman
Moderator
Posts: 2881
Joined: June 1st, 2009, 4:32 pm

### Re: slmake

AlbertArmStain wrote:
June 14th, 2023, 6:00 pm
Does pslmake have a feature where you can specify to construct left to right or vise versa?
No, but the natural order is 'back to front' (and because pslmake works backwards, it handles the things at the front to begin with before gradually moving to the back). The left/right ordering is handled by the 'defragmentation' pass which is a postprocessing step, not part of the core algorithm.
What do you do with ill crystallographers? Take them to the mono-clinic!

AlbertArmStain
Posts: 950
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

### Re: slmake

calcyman wrote:
June 14th, 2023, 6:25 pm
AlbertArmStain wrote:
June 14th, 2023, 6:00 pm
Does pslmake have a feature where you can specify to construct left to right or vise versa?
No, but the natural order is 'back to front' (and because pslmake works backwards, it handles the things at the front to begin with before gradually moving to the back). The left/right ordering is handled by the 'defragmentation' pass which is a postprocessing step, not part of the core algorithm.
So that’s why it’s so algorithmically greedy. It could possibly build a section back to front, then move to the next section, unless this is already implemented.

Hippo.69
Posts: 188
Joined: July 14th, 2020, 7:35 pm

### Re: slmake

AlbertArmStain wrote:
June 14th, 2023, 7:04 pm
So that’s why it’s so algorithmically greedy. It could possibly build a section back to front, then move to the next section, unless this is already implemented.
The order of gliders in the salvo can be permuted in many cases (whole blocks). Minimizing the size of salvo would have exponential number of solutions even when considering just these permutations of one salvo. This is why prefering order of targets mostly for example with slowly decresing x+y reduces number of equivalent salvos.

Final defragmentation chooses among the same upto permutation recipe one which is with high probability among cheapest to invoke by an arm.

Next postprocessing is considering the configurtions of nongliders among collisions be the recipe and replacing each glider in salvo by several options of lines and (phases mod small integer) ... to allow the arm choose cheaper variant of recipe.

What I am planning to do is considering final functional pattern as the goal and creating other clusters not interferring with the pattern not to be a problem. So usually some gliders/levels (destroying these clusters) in the recipe could be skipped and still obtain the same functional pattern.

AlbertArmStain
Posts: 950
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

### Re: slmake

Does pslmake have a feature where it will pinpoint the location of the non-spartan objects?

EvinZL
Posts: 758
Joined: November 8th, 2018, 4:15 pm
Location: A tungsten pool travelling towards the sun
Contact:

### Re: slmake

Is pslmake released anywhere?

EvinZL
Posts: 758
Joined: November 8th, 2018, 4:15 pm
Location: A tungsten pool travelling towards the sun
Contact:

### Re: slmake

Doublepost, but here's what seems to be a bug in slmake.

Given this infile.mc:

Code: Select all

``````x = 114, y = 114, rule = LifeHistory
.A\$A.A\$.A.A\$2.A.A\$3.A.A\$4.A.A\$5.A.A\$6.A.A\$7.A.A\$8.A.A\$9.A.A\$10.A.A\$
11.A.A\$12.A.A\$13.A.A\$14.A.A\$15.A.A\$16.A.A\$17.A.A\$18.A.A\$19.A.A\$20.A.A
\$21.A.A\$22.A.A\$23.A.A\$24.A.A\$25.A.A\$26.A.A\$27.A.A\$28.A.A\$29.A.A\$30.A.
A\$31.A\$32.3A.2A3.A\$34.A.A3.A.A\$34.A2.A3.A\$33.2A3.A11.2A\$35.3A12.A.A\$
35.A15.2A3\$52.2A\$44.2A5.A.A\$44.A.A5.A\$45.A\$51.2A\$51.A.A\$46.2A3.A\$46.
2A61\$112.A\$111.A.A\$107.2A.A2.A\$107.2A.A.A\$111.A!
``````
slmake prints:

Code: Select all

``````Instruction set AVX2 detected
Snarkmaker string = 10762 bytes.
Signature: [ 109 ]
Wrong orientation; flipping pattern.
Calling sparsebuild on initial pattern comprising 109 cells
-- data/bespoke/blocker-orient1.rle has period 8.
-- data/bespoke/blocker-orient2.rle has period 8.
-- data/bespoke/blocker-orient3.rle has period 8.
-- data/bespoke/eater2-orient1b.mc has period 1.
-- data/bespoke/eater2-orient1.mc has period 1.
-- data/bespoke/eater2-orient2.mc has period 1.
-- data/bespoke/eater2-orient3.mc has period 1.
-- data/bespoke/figure8-orient1.rle has period 8.
-- data/bespoke/figure8-orient2.rle has period 8.
-- data/bespoke/figure8-orient3.rle has period 8.
-- data/bespoke/mw2g-orient1.mc has period 1.
-- data/bespoke/mw2g-orient2.mc has period 1.
-- data/bespoke/mw2g-orient3b.mc has period 1.
-- data/bespoke/mw2g-orient3c.mc has period 1.
-- data/bespoke/mw2g-orient3.mc has period 1.
-- data/bespoke/mw2g-orient4.mc has period 1.
-- data/bespoke/snarkheart-eater-orient3.rle has period 1.
-- data/bespoke/snarkheart-orient1.rle has period 1.
-- data/bespoke/snarkheart-orient2.rle has period 1.
-- data/bespoke/snarkheart-orient4.rle has period 1.
-- data/bespoke/xs17-easy.rle has period 1.
-- data/bespoke/xs17-eater2.rle has period 1.
-- data/bespoke/xs17-next.rle has period 1.
-- data/bespoke/xs17-third.rle has period 1.
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 3
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 9
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 27
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 81
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 243
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Attempting to construct xs4_33 with 10 gliders (4645 recipes)
Attempting to construct xs4_33 with 11 gliders (4056 recipes)
Attempting to construct xs4_33 with 12 gliders (5092 recipes)
Attempting to construct xs4_33 with 13 gliders (6445 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 729
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Attempting to construct xs4_33 with 10 gliders (4645 recipes)
Attempting to construct xs4_33 with 11 gliders (4056 recipes)
Attempting to construct xs4_33 with 12 gliders (5092 recipes)
Attempting to construct xs4_33 with 13 gliders (6445 recipes)
Attempting to construct xs4_33 with 14 gliders (6549 recipes)
Attempting to construct xs4_33 with 15 gliders (7692 recipes)
Attempting to construct xs4_33 with 16 gliders (8655 recipes)
Attempting to construct xs4_33 with 17 gliders (8928 recipes)
Attempting to construct xs4_33 with 18 gliders (9604 recipes)
Attempting to construct xs4_33 with 19 gliders (10513 recipes)
Reached bailout for strategy 'tree'
Increasing bailout to 2187
Obtained 10 dimers/monomers.
4 objects of < 32 cells.
Attempting to construct xs4_33 with 1 gliders (2 recipes)
Attempting to construct xs4_33 with 2 gliders (3 recipes)
Attempting to construct xs4_33 with 3 gliders (18 recipes)
Attempting to construct xs4_33 with 4 gliders (72 recipes)
Attempting to construct xs4_33 with 5 gliders (382 recipes)
Attempting to construct xs4_33 with 6 gliders (1185 recipes)
Attempting to construct xs4_33 with 7 gliders (2238 recipes)
Reached bailout for strategy 'deep'
Attempting to construct xs4_33 with 8 gliders (2856 recipes)
Attempting to construct xs4_33 with 9 gliders (3648 recipes)
Attempting to construct xs4_33 with 10 gliders (4645 recipes)
Attempting to construct xs4_33 with 11 gliders (4056 recipes)
Attempting to construct xs4_33 with 12 gliders (5092 recipes)
Attempting to construct xs4_33 with 13 gliders (6445 recipes)
Attempting to construct xs4_33 with 14 gliders (6549 recipes)
``````
• At the start, it says "4 objects of < 32 cells" when there are 5.
• It can't construct a block, when it should be very easy to do so.
• Why is it constructing a block first?
I tested it out with only the tub+big sl and it seems to work fine.

calcyman
Moderator
Posts: 2881
Joined: June 1st, 2009, 4:32 pm

### Re: slmake

EvinZL wrote:
July 2nd, 2023, 11:26 am
Doublepost, but here's what seems to be a bug in slmake.

Given this infile.mc:

Code: Select all

``````x = 114, y = 114, rule = LifeHistory
.A\$A.A\$.A.A\$2.A.A\$3.A.A\$4.A.A\$5.A.A\$6.A.A\$7.A.A\$8.A.A\$9.A.A\$10.A.A\$
11.A.A\$12.A.A\$13.A.A\$14.A.A\$15.A.A\$16.A.A\$17.A.A\$18.A.A\$19.A.A\$20.A.A
\$21.A.A\$22.A.A\$23.A.A\$24.A.A\$25.A.A\$26.A.A\$27.A.A\$28.A.A\$29.A.A\$30.A.
A\$31.A\$32.3A.2A3.A\$34.A.A3.A.A\$34.A2.A3.A\$33.2A3.A11.2A\$35.3A12.A.A\$
35.A15.2A3\$52.2A\$44.2A5.A.A\$44.A.A5.A\$45.A\$51.2A\$51.A.A\$46.2A3.A\$46.
2A61\$112.A\$111.A.A\$107.2A.A2.A\$107.2A.A.A\$111.A!
``````
Can you try that but with the input glider shifted SE by, let's say, (5, 5)? It separates gliders from everything else by computing (x & x[8]), so if gliders collide within the first 8 generations, it won't be parsed correctly.
EvinZL wrote:
June 30th, 2023, 1:10 pm
Is pslmake released anywhere?
Not yet: I was abroad this last week and didn't have access to my laptop until today. I need to make some user-friendliness adjustments (such as making everything command-line arguments instead of hardcoded in the source, and including a Python script for downloading pslmake databases).
AlbertArmStain wrote:
June 27th, 2023, 10:27 am
Does pslmake have a feature where it will pinpoint the location of the non-spartan objects?
I don't understand the question; please could you elaborate?
What do you do with ill crystallographers? Take them to the mono-clinic!

dvgrn
Moderator
Posts: 9931
Joined: May 17th, 2009, 11:00 pm