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)));
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]}
Code: Select all
C:\Users\wwei23\Documents>node ./JSeeker.js
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.
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
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!
Code: Select all
{"period":4,"dx":0,"dy":2,"search":[[0],[1],[1],[1]],"B":[3],"S":[2,3]}
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.
....
....
....
....
....
....
....
....
....
....
Code: Select all
x = 4, y = 5, rule = B3/S23
b3o$o2bo$3bo$3bo$obo!
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]}
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
.......
.......
.......
.......
.......
.......
.......
.......
Code: Select all
x = 7, y = 11, rule = B3/S2
o$o$o$b2o$bo$2b3o$5bo$4b2o$6bo$6bo$6bo!
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!