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;
Without specifying custom model data, some default will be used on execution and finds the Glider:
Code: Select all
glpsol -m loopsrch.mod
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;
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;
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;
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;
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;
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;
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$