diff options
Diffstat (limited to 'jscalc/chainreaction.js')
-rw-r--r-- | jscalc/chainreaction.js | 108 |
1 files changed, 108 insertions, 0 deletions
diff --git a/jscalc/chainreaction.js b/jscalc/chainreaction.js new file mode 100644 index 0000000..b1ffbbe --- /dev/null +++ b/jscalc/chainreaction.js @@ -0,0 +1,108 @@ +#!/usr/bin/env node +var b=[[1,2,1],[1,4,2],[1,2,1]]; + +S=JSON.stringify.bind(JSON); +Eq=function(a,b){return a.map(function(r,i){return r.map(function(v,j){return b[i][j]==v;}).reduce(function(a,b){return a&&b;});}).reduce(function(a,b){return a&&b;});}; + +printboard=function(b){ + if(!Array.isArray(b)){ + console.log(b); + return; + } + b.forEach(function(r){ + console.log(r.join(" ")); + }); +}; + +evolve=function(b){ + var w=b[0].length,h=b.length,x,y,nnei,dif; + var nb=b.map(function(r){return r.slice(0);}); + for(y=0;y<h;y++)for(x=0;x<w;x++){ + nnei=(x>0)+(x<w-1)+(y>0)+(y<h-1); + if(b[y][x]>=nnei){ + dif=~~(b[y][x]/nnei); + nb[y][x]-=dif*nnei; + if(x>0)nb[y][x-1]+=dif; + if(y>0)nb[y-1][x]+=dif; + if(x<w-1)nb[y][x+1]+=dif; + if(y<h-1)nb[y+1][x]+=dif; + } + } + return nb; +}; + +fullevolve=function(b){ + var nb,lst,i; + nb=evolve(b); + lst=[b,nb]; + while(true){ + b=nb; + nb=evolve(nb); + if(Eq(b,nb))return lst; + for(i=0;i<lst.length;i++)if(Eq(nb,lst[i]))return lst.concat([nb,Infinity]); + lst.push(nb); + } +}; + +repcheck=function(b){ + var nb,lst,i; + nb=evolve(b); + lst=[b,nb]; + while(true){ + b=nb; + nb=evolve(nb); + if(Eq(b,nb))return false; + for(i=0;i<lst.length;i++)if(Eq(nb,lst[i]))return true; + lst.push(nb); + } +}; + +convform=function(a,w,h){ + var y,res; + res=new Array(h); + for(y=0;y<h;y++)res[y]=a.slice(w*y,w*y+w); + return res; +}; + +solvewh=function(w,h){ + var maxmap,x,y,stk,i; + var res=[]; + maxmap=new Array(w*h); + maxmap[0]=maxmap[w-1]=maxmap[w*(h-1)]=maxmap[w*(h-1)+w-1]=2; + for(x=1;x<w-1;x++)maxmap[x]=maxmap[w*(h-1)+x]=3; + for(y=1;y<h-1;y++)maxmap[w*y]=maxmap[w*y+w-1]=3; + for(y=1;y<h-1;y++)for(x=1;x<w-1;x++)maxmap[w*y+x]=4; + console.log("maxmap="+S(maxmap)); + stk=new Array(w*h).fill(0); + while(true){ + //console.log("stk="+S(stk)); + for(i=0;i<w*h;i++){ + stk[i]++; + if(repcheck(convform(stk,w,h)))res.push(convform(stk,w,h)); + stk[i]--; + } + stk[stk.length-1]++; + while(stk[stk.length-1]>=maxmap[stk.length-1]){stk.pop();stk[stk.length-1]++;} + if(stk.length==0)break; + while(stk.length<w*h)stk.push(0); + } + return res; +}; + +solveallminimal=function(w,h){ + var res=solvewh(w,h); + var ressorted=res.map(function(b){return [b,b.reduce(function(a,b){return a+b.reduce(function(a,b){return a+b;});},0)];}).sort(function(a,b){return a[1]-b[1];}); + var smallest=ressorted.filter(function(r){return r[1]==ressorted[0][1];}).map(function(r){return r[0];}); + return smallest; +}; + +printboardlist=function(blist){ + blist.forEach(function(b){printboard(b);console.log();}); +}; + +printallminimal=function(w,h){printboardlist(solveallminimal(w,h));} + +printallminimal(3,3); + + +require("repl").start({prompt:"> ",useGlobal:true}).context=this; |