Glider/osc. search tool - in a non-programming language

For scripts to aid with computation or simulation in cellular automata.
Post Reply
Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Glider/osc. search tool - in a non-programming language

Post by Naszvadi » March 17th, 2018, 5:32 pm

It is ready, somewhat trolling, but works! Slow, and remain to be unoptimized. In pure GMPL, execute it with GLPK! Prints out the first feasible pattern according to the specified parameters, then quits.

Save this as a textfile with name "loopsrch.mod":

Code: Select all

/* Oscillator, still life and spaceship search utility in Conway's Game of Life */

/* Written and converted to GNU MathProg by NASZVADI, Peter, 2017-2018
   <vuk@cs.elte.hu> */

param generations, integer, >= 1;
/* generations of a ship */

param phoenix, integer, >= 0 <= 1, default 0;
/* 0 or 1, depending on whether the pattern must be a phoenix */

param movex, integer, >= 0;
param movey, integer, >= 0;
/* movement, both zeroes means hunting for an oscillator, not a ship */

param height, integer, >= 1;
param width, integer, >= 1;
/* height and width of the pattern */

param maxpop, integer, default width * height;
param minpop, integer, default 1;
/* maximal and minimal population, positive minpop is enforced
   in order to exclude blank pattern */

set GENS := 0..generations;
/* set of generations */

set GENSD1 := 1..generations;
/* eliminating the starting gen from the above list */

set ROWS := -1..(height + (2 * generations));
/* set of rows of the predecessor */

set COLUMNS := -1..(width + (2 * generations));
/* set of columns of the predecessor */


set CELLS := setof{(i,j,k) in ROWS cross COLUMNS cross GENS:
    i >= (generations - k) and i <= (height + generations + k - 1) and
    j >= (generations - k) and j <= (width + generations + k - 1)}(i,j,k);

set ZEROCELLS := (ROWS cross COLUMNS cross GENS) diff CELLS;
/* complementer sets of CELLS */

set MOORE := {(0, 1, 2), (0, -1, 2), (1, 0, 2), (-1, 0, 2), (1, 1, 2),
    (-1, 1, 2), (1, -1, 2), (-1, -1, 2), (0, 0, 1)};
/* Moore-neighbourhood relative coordinates */

param changegens{(i,j,k) in CELLS}, default 0;
param fixgens{(i,j,k) in CELLS}, default 0;
/* two lists of ("row", "column", "generation", <0|1>) elements, where
   the last tuple with "1" has enforcement on the denoted cell compared
   with its 0th generation state */

var x{ROWS, COLUMNS, GENS}, binary;
/* generations' states */

var dpos{ROWS, COLUMNS, GENSD1}, >= 0;
/* positive part of the distances from 6 (derived magic number for CGoL) */

var dneg{ROWS, COLUMNS, GENSD1}, >= 0;
/* negative part of the distances from 6 */

var dposup{ROWS, COLUMNS, GENSD1}, binary;
/* positive part's upper bound enforcement */

var dnegup{ROWS, COLUMNS, GENSD1}, binary;
/* negative part's upper bound enforcement */

/******************************************************************************************/

s.t. maincons{(i, j, k) in CELLS: k > 0}:
    sum{(a, b, h) in MOORE} (h * x[i + a, j + b, k]) = 6 + dpos[i,j,k] - dneg[i,j,k];
/* linearized */

s.t. complcons{(i, j, k) in ZEROCELLS}: x[i,j,k] = 0;

s.t. posbound{(i, j, k) in CELLS: k > 0}: dpos[i,j,k] <= 11 * dposup[i,j,k];
/* constraining positive part of distance */

s.t. negbound{(i, j, k) in CELLS: k > 0}: dneg[i,j,k] <= 6 * dnegup[i,j,k];
/* constraining negative part of distance */

s.t. mutex{(i, j, k) in CELLS: k > 0}: dposup[i,j,k] + dnegup[i,j,k] = 1;
/* Ensuring that (at most/)exactly one is positive among the pos./neg. parts */

s.t. alive{(i, j, k) in CELLS: k > 0}: dpos[i,j,k] + dneg[i,j,k] <= 18 - 17 * x[i,j,k-1];
/* <= 1 */

s.t. dead{(i, j, k) in CELLS: k > 0}: dpos[i,j,k] + dneg[i,j,k] >= 2 - 2 * x[i,j,k-1];
/* >= 2 */

s.t. movement{(i, j) in ROWS cross COLUMNS: i >= movex - 1 and j >= movey - 1}: x[i,j,generations] = x[i-movex,j-movey,0];
s.t. dummy: sum{(i, j) in ROWS cross COLUMNS} x[i, j, 0] >= minpop;
s.t. popbound: sum{(i, j) in ROWS cross COLUMNS} x[i, j, 0] <= maxpop;

s.t. isphoenix{(i, j, k) in ROWS cross COLUMNS cross GENSD1}: x[i,j,k]+x[i,j,k-1] <= 2-phoenix;

s.t. changeforce{(i, j, k) in CELLS: changegens[i,j,k] > 0}: x[i,j,0]+x[i,j,k] = 1;
s.t. fixforce{(i, j, k) in CELLS: fixgens[i,j,k] > 0}: x[i,j,0] = x[i,j,k];

/* This is a feasibility problem, so no objective is needed */

solve;

/******************************************************************************************/

printf "\n#Life 1.05\n";
for{i in ROWS}{
    for{j in COLUMNS: j >= generations}{
        printf "%s", if x[i, j, 0] > 0 then "*" else if sum{j2 in COLUMNS: j2 >= j}x[i, j2, 0] > 0 or j == generations then "." else "";
    }
    printf "\n";
}
printf "\n";

/******************************************************************************************/

data;

/* Richard K. Guy's glider will appear with these parameters */
param generations := 4;
param movex := 1;
param movey := 1;
param height := 3;
param width := 3;

end;
Install glpk with "brew" on OSX, or with typing "sudo apt-get install glpk-utils" on ubuntu/debian linux system console. Obtain more information about using and installing GLPK on other systems at http://www.gnu.org/software/glpk

Without specifying custom model data, some default will be used on execution and finds the Glider:

Code: Select all

glpsol -m loopsrch.mod
Some example model data files:
blinker.dat - execute with "glpsol -m loopsrch.mod --data blinker.dat"

Code: Select all

data;

param generations := 2;
param maxpop := 5;
param movex := 0;
param movey := 0;
param height := 5;
param width := 5;

end;
lwss.dat:

Code: Select all

data;

/* glpsol -m loopsrch.mod --cuts --data lwss.dat */

param generations := 4;
param movex := 2;
param movey := 0;
param height := 5;
param width := 4;

end;
toad.dat:

Code: Select all

data;

param generations := 2;
param minpop := 4;
param movex := 0;
param movey := 0;
param height := 2;
param width := 4;
param changegens[2,2,1] := 1;

end;
boat.dat:

Code: Select all

data;
/* the only still life with population 5 */
param generations := 1;
param minpop := 5;
param maxpop := 5;
param movex := 0;
param movey := 0;
param height := 7;
param width := 7;

end;
Cheating is allowed - giving hints in models are possible, like finding Phoenix 1:

Code: Select all

data;

/* glpsol -m loopsrch.mod --last --data phoenix.dat */

param generations := 2;
param movex := 0;
param movey := 0;
param height := 8;
param width := 8;
param phoenix := 1;
param changegens :=     2 5 1 1,2 6 1 1,
                3 4 1 1,3 5 1 1,3 6 1 1,3 7 1 1,
        4 3 1 1,                                4 8 1 1,
5 2 1 1,5 3 1 1,                                5 8 1 1,5 9 1 1,
6 2 1 1,6 3 1 1,                                6 8 1 1,6 9 1 1,
        7 3 1 1,                                7 8 1 1,
                8 4 1 1,8 5 1 1,8 6 1 1,8 7 1 1,
                        9 5 1 1,9 6 1 1;

end;
Badly scaled model, it seems to be unusable for periods higher than 3 or 4 even when patterns are looked up in small rectangles. Use at your own risk and NOT on others' CPU time, especially do not search Loafer with it!

This custom model also triggers a bug in GLPK 4.57 came with Ubuntu 16.04 - this looks for Mold (p4):

Code: Select all

data;
/* execute this to trigger bug: glpsol -m loopsrch.mod --cuts --last --data moldp4.dat */
param generations := 4;
param movex := 0;
param movey := 0;
param minpop := 12;
param maxpop := 12;
param height := 6;
param width := 6;
param phoenix := 0;
param fixgens :=
     4 4 1 1,4 4 2 1,4 4 3 1,
     4 5 1 1,4 5 2 1,4 5 3 1,
     4 6 1 1,4 6 2 1,4 6 3 1,
     4 7 1 1,4 7 2 1,4 7 3 1,
     4 8 1 1,4 8 2 1,4 8 3 1,
     4 9 1 1,4 9 2 1,4 9 3 1,
     5 4 1 1,5 4 2 1,5 4 3 1,
     5 5 1 1,5 5 2 1,5 5 3 1,
     5 6 1 1,5 6 2 1,5 6 3 1,
     5 7 1 1,5 7 2 1,5 7 3 1,
     5 8 1 1,5 8 2 1,5 8 3 1,
     5 9 1 1,5 9 2 1,5 9 3 1,
     6 6 1 1,6 6 2 1,6 6 3 1,
     6 7 1 1,6 7 2 1,6 7 3 1,
     6 8 1 1,6 8 2 1,6 8 3 1,
     6 9 1 1,6 9 2 1,6 9 3 1,
     7 7 1 1,7 7 2 1,7 7 3 1,
     7 8 1 1,7 8 2 1,7 8 3 1,
     7 9 1 1,7 9 2 1,7 9 3 1,
     8 8 1 1,8 8 2 1,8 8 3 1,
     8 9 1 1,8 9 2 1,8 9 3 1,
     9 4 1 1,9 4 2 1,9 4 3 1,
     9 8 1 1,9 8 2 1,9 8 3 1,
     9 9 1 1,9 9 2 1,9 9 3 1;

end;
Yes, I have further plans like release models for other rules. It uses the same linear mapping as this: ../forums/viewtopic.php?f=9&t=2563. Of course both codes can be altered to look up patterns in some other rules like Seeds, 34Life, Live Free or Die etc.

With extending the code an objective function, can search patterns with extrema like minimal/maximal population in a given bounding box etc.

An example run - at the end it prints the pattern in a Golly-compatible format:

Code: Select all

user@errorlevel:0:~/Work/20180316/glpk$ glpsol -m loopsrch.mod 
GLPSOL: GLPK LP/MIP Solver, v4.57
Parameter(s) specified in the command line:
 -m loopsrch.mod
Reading model section from loopsrch.mod...
Reading data section from loopsrch.mod...
128 lines were read
Generating maincons...
Generating complcons...
Generating posbound...
Generating negbound...
Generating mutex...
Generating alive...
Generating dead...
Generating movement...
Generating dummy...
Generating popbound...
Generating isphoenix...
Generating changeforce...
Generating fixforce...
Model has been successfully generated
GLPK Integer Optimizer, v4.57
3038 rows, 1949 columns, 8886 non-zeros
1397 integer variables, all of which are binary
Preprocessing...
93 constraint coefficient(s) were reduced
526 rows, 416 columns, 1618 non-zeros
236 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.600e+01  ratio =  1.600e+01
GM: min|aij| =  5.000e-01  max|aij| =  2.000e+00  ratio =  4.000e+00
EQ: min|aij| =  2.500e-01  max|aij| =  1.000e+00  ratio =  4.000e+00
2N: min|aij| =  2.500e-01  max|aij| =  1.500e+00  ratio =  6.000e+00
Constructing initial basis...
Size of triangular part is 526
Solving LP relaxation...
GLPK Simplex Optimizer, v4.57
526 rows, 416 columns, 1618 non-zeros
      0: obj =   0.000000000e+00 inf =   2.000e+00 (1)
      2: obj =   0.000000000e+00 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+     2: mip =     not found yet >=              -inf        (1; 0)
+  3956: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (151; 246)
+  3956: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 683)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   1.0 secs
Memory used: 5.1 Mb (5386269 bytes)

#Life 1.05
**
*.*
*

Model has been successfully processed
user@errorlevel:0:~/Work/20180316/glpk$ 
[EDIT #1 2018.03.18] FIXED two printing bugs. Sometimes removed necessary empty lines before.

Post Reply