JSeeker

For scripts to aid with computation or simulation in cellular automata.
Post Reply
wwei23

JSeeker

Post by wwei23 » October 5th, 2020, 6:28 pm

A simple search program written in Node.js. You don't need to compile anything, you just need to install Node.js.

Code: Select all

var parameters=require("./in.json");
var period=parameters.period;
var dx=parameters.dx;
var dy=parameters.dy;
var search=parameters.search;
var column=[];
var longestpartial;
var B=parameters.B;
var S=parameters.S;
var cells=search.slice();
for(var i=0;i<search[0].length;i++){
    column.push(0);
}
for(var i=0;i<2*period;i++){
    cells.push(column.slice());
    cells=[column.slice()].concat(cells);
}
for(var i=0;i<cells.length;i++){
    for(var j=0;j<2*period;j++){
        cells[i]=[0].concat(cells[i]);
    }
}
var trim=function(grid){
    var trimmed=[];
    for(var i=0;i<grid.length-4*period;i++){
        trimmed.push([]);
    }
    for(var i=2*period;i<grid.length-2*period;i++){
        for(var j=2*period;j<grid[0].length;j++){
            trimmed[i-2*period][j-2*period]=grid[i][j];
        }
    }
    return trimmed;
};
var plaintext=function(grid){
    var text=""
    for(var j=0;j<grid[0].length;j++){
        for(var i=0;i<grid.length;i++){
            if(grid[i][j]===1){
                text+="O";
            }else{
                text+=".";
            }
        }
        text+="\n";
    }
    return text;
};
var transition=function(x1,x2,x3,x4,x5,x6,x7,x8,x9){
    var n=x1+x2+x3+x4+x6+x7+x8+x9;
    if((x5&&S.indexOf(n)>-1)||(!x5&&B.indexOf(n)>-1)){
        return true;
    }
    return false;
};
var crop=function(grid,x,y){
    var cropped=[];
    for(var i=0;i<2*period+1;i++){
        cropped.push([]);
    }
    for(var i=0;i<(2*period+1);i++){
        for(var j=0;j<(2*period+1);j++){
            cropped[i][j]=grid[x+i-period][y+j-period];
        }
    }
    return cropped;
};
var step3=function(grid){
    var x1;
    var x2;
    var x3;
    var x4;
    var x5;
    var x6;
    var x7;
    var x8;
    var x9;
    var stepped=grid.slice();
    while(stepped.length>3){
        var stepped2=[];
        for(var i=0;i<stepped.length-2;i++){
            stepped2.push([]);
        }
        for(var i=1;i<stepped.length-1;i++){
            for(var j=1;j<stepped.length-1;j++){
                x1=stepped[i-1][j-1];
                x2=stepped[i-1][j];
                x3=stepped[i-1][j+1];
                x4=stepped[i][j-1];
                x5=stepped[i][j];
                x6=stepped[i][j+1];
                x7=stepped[i+1][j-1];
                x8=stepped[i+1][j];
                x9=stepped[i+1][j+1];
                stepped2[i-1][j-1]=transition(x1,x2,x3,x4,x5,x6,x7,x8,x9);
            }
        }
        stepped=stepped2.slice();
    }
    x1=stepped[0][0];
    x2=stepped[0][1];
    x3=stepped[0][2];
    x4=stepped[1][0];
    x5=stepped[1][1];
    x6=stepped[1][2];
    x7=stepped[2][0];
    x8=stepped[2][1];
    x9=stepped[2][2];
    return transition(x1,x2,x3,x4,x5,x6,x7,x8,x9);
};
var check_cell=function(grid,x,y){
    var section=crop(grid,x,y);
    return (step3(section)*1)===section[period+dx][period+dy];
};
var check_completion=function(){
    var alive=0;
    for(var i=0;i<cells.length;i++){
        for(var j=cells[0].length-2;j>=cells[0].length-2-2*period;j--){
            alive+=Math.abs(cells[i][j]);
        }
    }
    if(alive===0){
        return true;
    }else{
        return false;
    }
};
var guess_cell=function(z){
    var x=2*period;
    var y=2*period;
    while(cells[x][y]>=0){
        if(x===cells.length-1-2*period){
            x=2*period;
            y+=1;
            if(y>=cells[0].length){
                longestpartial=trim(cells);
                for(var i=0;i<cells.length;i++){
                    if(i<2*period||i>=cells.length-2*period){
                        cells[i].push(0);
                    }else{
                        cells[i].push(-1);
                    }
                }
            }
        }else{
            x+=1;
        }
    }
    if(x===2*period){
        x=cells.length-1-2*period;
        y-=1;
    }else{
        x-=1;
    }
    if(y<2*period){
         throw("No completion found, longest partial:\n"+JSON.stringify(longestpartial)+"\n"+plaintext(longestpartial)+"(Iterations: "+z+")");
    }
    if(x===cells.length-1-2*period){
        var valid=true;
        for(var i=-period;i<=period;i++){
            valid=valid&&check_cell(cells,x+i,y-period);
        }
        if(!valid){
            if(cells[x][y]===0){
                cells[x][y]=1;
            }else{
                while(cells[x][y]===1){
                    cells[x][y]=-1;
                    if(x===2*period){
                        x=cells.length-1-2*period;
                        y-=1;
                        if(y<2*period){
                            throw("No completion found, longest partial:\n"+JSON.stringify(longestpartial)+"\n"+plaintext(longestpartial)+"(Iterations: "+z+")");
                        }
                    }else{//Backtracking
                        x-=1;
                    }
                }
                cells[x][y]=1;//When we reach a 0, make it a 1
            }
        }else{
            if(x===cells.length-1-2*period){
                x=2*period;
                y+=1;
            }else{
                x+=1;
            }
            cells[x][y]=0;
        }
    }else{
        if(!check_cell(cells,x-period,y-period)){
            if(cells[x][y]===0){
                cells[x][y]=1;
            }else{
                while(cells[x][y]===1){
                    cells[x][y]=-1;
                    if(x===2*period){
                        x=cells.length-1-2*period;
                        y-=1;
                         if(y<2*period){
                             throw("No completion found, longest partial:\n"+JSON.stringify(longestpartial)+"\n"+plaintext(longestpartial)+"(Iterations: "+z+")");
                        }
                    }else{//Backtracking
                        x-=1;
                    }
                }
                cells[x][y]=1;//When we reach a 0, make it a 1
            }
        }else{
            if(x===cells.length-1-2*period){
              x=2*period;
                y+=1;
            }else{
                x+=1;
            }
            cells[x][y]=0;
        }
    }
};
console.log("Input pattern:");
console.log(trim(cells));
console.log(plaintext(trim(cells)));
var i=0;
while(!check_completion()){
    i+=1;
    guess_cell(i);
    if(i%1048576===0){
        console.log(i+" iterations:");
        console.log(trim(cells));
        console.log(plaintext(trim(cells)));
    }
}
if(i===1){
    console.log("Completed in 1 iteration");
}else{
    console.log("Completed in "+i+" iterations")
}
console.log("Result:");
console.log(trim(cells));
console.log(plaintext(trim(cells)));
Here's how to use it.
After you install Node.js, you need to create a file called in.json in the same directory as JSeeker.js. in.json is a JSON file specifying the period, displacement, the rule, and the pattern you're trying to complete, in the form of an array of cells. Here are 3 examples. First of all, let's specify this as our in.json:

Code: Select all

{"period":3,"dx":1,"dy":0,"search":[[0],[0],[0],[0],[1]],"B":[3],"S":[2,3]}
Now run JSeeker:

Code: Select all

C:\Users\wwei23\Documents>node ./JSeeker.js
Let the search run, and when it finishes, the result should look like this.

Code: Select all

C:\Users\wwei23\Documents>node ./JSeeker.js
Input pattern:
[ [ 0 ], [ 0 ], [ 0 ], [ 0 ], [ 1 ] ]
....O

Completed in 425946 iterations
Result:
[ [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ] ]
....O
..OO.
..OO.
....O
..O..
.OOO.
.O...
OO...
..O..
.O.O.
.O.O.
.O...
...O.
.OO..
.OO..
...O.
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
Congratulations, you've found 25P3H1V0.1!

Code: Select all

x = 5, y = 16, rule = B3/S23
4bo$2b2o$2b2o$4bo$2bo$b3o$bo$2o$2bo$bobo$bobo$bo$3bo$b2o$b2o$3bo!
For our next example, we're going to find the LWSS. But this time, there's a twist. This should be your in.json for this example:

Code: Select all

{"period":4,"dx":0,"dy":2,"search":[[0],[1],[1],[1]],"B":[3],"S":[2,3]}
After letting JSeeker run, this should be your result:

Code: Select all

C:\Users\wwei23\Documents>node ./JSeeker.js
Input pattern:
[ [ 0 ], [ 1 ], [ 1 ], [ 1 ] ]
.OOO

Completed in 1079 iterations
Result:
[ [ 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
  [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ] ]
.OOO
O..O
...O
...O
O.O.
....
....
....
....
....
....
....
....
....
....
Now, what's so special about this? Well, if you look at the input pattern, you'll see that it has a width of 4. However, the LWSS has a width of 5, not 4. If you try to find the LWSS with gfind or JLS at width 4, you won't get anything. So why did JSeeker find the LWSS? It's pretty simple. The LWSS has a phase that's only four cells wide (all four phases, actually, but you only need one), and JSeeker doesn't care about the width of the other phases. It only stores one phase when searching, so that's the only phase whose width matters to it.

Code: Select all

x = 4, y = 5, rule = B3/S23
b3o$o2bo$3bo$3bo$obo!
JSeeker is also able to find oscillators, as well as search in alien rules. Let's try to find a P3 oscillator in one of my favorite rules. Use this as your in.json, and run JSeeker:

Code: Select all

{"period":3,"dx":0,"dy":0,"search":[[1,1,1],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0]],"B":[3],"S":[2]}
This one takes quite a bit longer to run, but it still completes successfully:

Code: Select all

C:\Users\wwei23\Documents>node ./JSeeker.js
Input pattern:
[ [ 1, 1, 1 ],
  [ 0, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 0 ] ]
O......
O......
O......

1048576 iterations:
[ [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, -1, -1 ],
  [ 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, -1, -1 ],
  [ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, -1, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, -1, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, -1, -1 ],
  [ 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, -1, -1 ],
  [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, -1, -1, -1 ] ]
O......
O......
O......
.OO....
.O.....
..OOO..
.....O.
....O.O
.....O.
.......
..OOOO.
OOO.O.O
OOOO...
O..OO..
.......
.......

2097152 iterations:
[ [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, -1 ],
  [ 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, -1 ],
  [ 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, -1 ],
  [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, -1 ],
  [ 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, -1 ] ]
O......
O......
O......
.OO....
.O.....
..OOO..
.....O.
....O.O
....O.O
.OOO.O.
.......
.......
...OOOO
OOOO.OO
.O.OOO.
O..OOO.
.......

3145728 iterations:
[ [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1, -1, -1, -1, -1 ],
  [ 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, -1, -1, -1, -1, -1 ],
  [ 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, -1, -1, -1, -1, -1, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, -1, -1, -1, -1, -1, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, -1, -1, -1, -1, -1, -1 ],
  [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, -1, -1, -1, -1, -1, -1 ],
  [ 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, -1, -1, -1, -1, -1, -1 ] ]
O......
O......
O......
.OO....
.O.....
..OOO..
.....O.
....O.O
.O.O..O
O.O.OO.
..OO...
.......
.......
.......
.......
.......
.......

Completed in 3438226 iterations
Result:
[ [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, -1 ] ]
O......
O......
O......
.OO....
.O.....
..OOO..
.....O.
....OO.
......O
......O
......O
.......
.......
.......
.......
.......
.......
.......
.......
And this is the oscillator that you get:

Code: Select all

x = 7, y = 11, rule = B3/S2
o$o$o$b2o$bo$2b3o$5bo$4b2o$6bo$6bo$6bo!
Like before, we're searching at a lower width than other programs would be able to find such an oscillator at, because this one phase has a lower width than the other two phases. This one phase is what allows it to be found with JSeeker.
With some small modifications, one can enter the search parameters directly into the source code of the program. While this isn't necessary, it can make it possible to run JSeeker from a web browser on a site like JSFiddle. This should make it possible to run JSeeker in places where other search programs can't run, like a school computer. Indeed, I have been able to find these patterns on a school computer, since browsers don't require administrator permissions to run.
Good luck, and happy searching!

Post Reply