Initial commit.

1 files changed, 326 insertions, 0 deletions

diff --git a/SameGameJS/samegame.js b/SameGameJS/samegame.js
new file mode 100755
index 0000000..6bac624
--- /dev/null
+++ b/SameGameJS/samegame.js
@@ -0,0 +1,326 @@
+var dimpx,dim,cc;
+var seed,cscore;
+var board=null;
+var boarde=null;
+var dx=[0,1,0,-1];
+var dy=[-1,0,1,0];
+var pendingrem=[];
+var sol=[];
+var optscore;
+var ismobile;
+String.prototype.getHash=function()
+{
+	var ret=0,ch;
+	if(this.length===0)return ret;
+	for(var i=0;i<this.length;++i)
+	{
+		ch=this.charCodeAt(i);
+		ret=((ret<<5)-ret)+ch;ret>>>=0;
+	}
+	return ret;
+}
+function randomInt(min,max)
+{
+	seed*=214013;seed+=2531011;seed&=0xffffffff;
+	return min+(seed^seed>>15)%(max-min+1);
+}
+
+function init()
+{
+	if( navigator.userAgent.match(/Android/i)
+ || navigator.userAgent.match(/webOS/i)
+ || navigator.userAgent.match(/iPhone/i)
+ || navigator.userAgent.match(/iPad/i)
+ || navigator.userAgent.match(/iPod/i)
+ || navigator.userAgent.match(/BlackBerry/i)
+ || navigator.userAgent.match(/Windows Phone/i)
+ )
+	ismobile=true;
+	dimpx=(window.innerWidth>window.innerHeight?window.innerHeight:window.innerWidth)*(ismobile?0.9:0.75);
+	document.getElementById("containerDiv").style.width=dimpx+"px";
+	document.getElementById("containerDiv").style.height=dimpx+"px";
+}
+function gameInit()
+{
+	for(var e=document.getElementById("containerDiv").children,i=0;i<e.length;++i)
+		if(e[i].id!=="endgameDiv"&&e[i].id!=="scDiv"){e[i].remove();e=document.getElementById("containerDiv").children;--i;}
+	if(document.getElementById("bsize").value=="1")dim=6;
+	if(document.getElementById("bsize").value=="2")dim=12;
+	if(document.getElementById("bsize").value=="3")dim=20;
+	cc=parseInt(document.getElementById("ccnt").value);
+	if(document.getElementById("seed").value.length!==0)
+		if(!isNaN(parseInt(document.getElementById("seed").value)))
+			seed=parseInt(document.getElementById("seed").value);
+		else
+			seed=document.getElementById("seed").value.getHash();
+	else
+		seed=Math.floor(Math.random()*2000000000);
+	document.getElementById("cseed").innerHTML=seed.toString();
+	document.getElementById("seed").value="";
+	document.getElementById("score").innerHTML="0";
+	cscore=0;
+	board=new Array(dim+4);for(var i=0;i<dim+4;++i)board[i]=new Array(dim+4);
+	boarde=new Array(dim+4);for(var i=0;i<dim+4;++i)boarde[i]=new Array(dim+4);
+	for(var i=0;i<dim;++i)
+	for(var j=0;j<dim;++j)
+	{
+		board[i][j]=randomInt(1,cc);
+		boarde[i][j]=document.createElement("div");
+		boarde[i][j].classList.add("clickable");
+		boarde[i][j].classList.add(board[i][j]==1?"red":board[i][j]==2?"green":board[i][j]==3?"blue":"orange");
+		boarde[i][j].style.bottom=i*dimpx/dim+"px";
+		boarde[i][j].style.left=j*dimpx/dim+"px";
+		boarde[i][j].style.width=boarde[i][j].style.height=dimpx/dim*.95+"px";
+		boarde[i][j].i=i;boarde[i][j].j=j;boarde[i][j].h=0;
+		boarde[i][j].addEventListener("mouseenter",menter);
+		boarde[i][j].addEventListener("mouseleave",mleave);
+		boarde[i][j].addEventListener("click",mclick);
+		document.getElementById("containerDiv").appendChild(boarde[i][j]);
+	}
+	document.getElementById("endgameDiv").style.fontSize="0px";
+	document.getElementById("endgameDiv").style.border="0px 0px";
+	document.getElementById("endgameDiv").style.transform="translate(-50%,-50%) rotate(180deg)";
+	document.getElementById("endgameDiv").style.WebkitTransform="translate(-50%,-50%) rotate(180deg)";
+	document.getElementById("scoreopt").innerHTML=solve().toString();
+}
+function getBGColor(c,a)
+{
+	return "rgba("+(c==1?"255,0,0,":c==2?"0,255,0,":c==3?"0,0,255,":"255,192,0,")+a+")";
+}
+function menter(e)
+{
+	if(e===null)return;
+	var i=e.target?e.target.i:e.i,j=e.target?e.target.j:e.j;
+	if(boarde[i][j].h===1)return;
+	if(e.target!==undefined)
+	{
+		var s=0;
+		for(var k=0;k<4;++k)
+		if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])++s;
+		if(s===0)return;
+	}
+	boarde[i][j].style.backgroundColor=getBGColor(board[i][j],0.8);
+	boarde[i][j].h=1;
+	for(var k=0;k<4;++k)
+	if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])
+		menter(boarde[i+dx[k]][j+dy[k]]);
+}
+function mleave(e)
+{
+	if(e===null)return;
+	var i=e.target?e.target.i:e.i,j=e.target?e.target.j:e.j;
+	if(boarde[i][j].h===0)return;
+	if(e.target!==undefined)
+	{
+		var s=0;
+		for(var k=0;k<4;++k)
+		if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])++s;
+		if(s===0)return;
+	}
+	boarde[i][j].style.backgroundColor=getBGColor(board[i][j],0.6);
+	boarde[i][j].h=0;
+	for(var k=0;k<4;++k)
+	if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])
+		mleave(boarde[i+dx[k]][j+dy[k]]);
+}
+function mclick(e)
+{
+	var i,j,c;
+	if(e.target!==undefined)
+	{
+		if(pendingrem.length!==0)return;
+		var s=0;
+		i=e.target.i;j=e.target.j;
+		for(var k=0;k<4;++k)
+		if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])++s;
+		if(s===0)return;
+	}else{i=e.i;j=e.j;}
+	c=board[i][j];board[i][j]=0;
+	for(var k=0;k<4;++k)
+	if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==c)
+		mclick(boarde[i+dx[k]][j+dy[k]]);
+	pendingrem.push(boarde[i][j]);
+	boarde[i][j].style.width=boarde[i][j].style.height=1.5*dimpx/dim*.95+"px";
+	boarde[i][j].style.transform="translate(-16.66%,16.66%)";
+	boarde[i][j].style.WebkitTransform="translate(-16.66%,16.66%)";
+	boarde[i][j].style.backgroundColor=getBGColor(board[i][j],0);
+	boarde[i][j].removeEventListener("mouseenter",menter);
+	boarde[i][j].removeEventListener("mouseleave",mleave);
+	boarde[i][j].removeEventListener("click",mclick);
+	if(e.target!==undefined)
+	{
+		var tilesremoved=pendingrem.length;
+		cscore+=(tilesremoved-2)*(tilesremoved-2);
+		document.getElementById("scDiv").innerHTML="+"+((tilesremoved-2)*(tilesremoved-2)).toString();
+		document.getElementById("scDiv").style.transition="none";
+		document.getElementById("scDiv").style.color=(thm==0?"rgba(0,0,0,1)":"rgba(255,255,255,1)");
+		document.getElementById("scDiv").style.transition="0.4s";
+		document.getElementById("scDiv").style.top="10%";
+		setTimeout(function(){document.getElementById("scDiv").style.color=(thm==0?"rgba(0,0,0,0)":"rgba(255,255,255,0)");},200);
+		document.getElementById("score").innerHTML=cscore.toString();
+		setTimeout(doTilesRemove,512);
+	}
+}
+function doTilesRemove()
+{
+	for(var i=0;i<pendingrem.length;++i)
+	{
+		boarde[pendingrem[i].i][pendingrem[i].j]=null;
+		pendingrem[i].remove();
+	}
+	pendingrem.length=0;
+	document.getElementById("scDiv").style.transition="none";
+	document.getElementById("scDiv").style.top="50%";
+	document.getElementById("scDiv").style.color=(thm==0?"rgba(0,0,0,0)":"rgba(255,255,255,0)");
+	updateBoard();
+}
+function updateBoard()
+{
+	//drop down
+	for(var j=0;j<dim;++j)
+	{
+		var rc=[],re=[];
+		for(var i=0;i<dim;++i)
+		if(board[i][j]!==0){rc.push(board[i][j]);re.push(boarde[i][j]);}
+		for(var i=0;i<rc.length;++i)
+		{
+			board[i][j]=rc[i];
+			boarde[i][j]=re[i];
+			boarde[i][j].i=i;
+			boarde[i][j].style.bottom=i*dimpx/dim+"px";
+		}
+		for(var i=rc.length;i<dim;++i){board[i][j]=0;boarde[i][j]=null;}
+	}
+	//shift left
+	for(var j=0;j<dim;++j)
+	{
+		var empty=true;
+		for(var i=0;i<dim;++i)if(board[i][j]!==0){empty=false;break;}
+		if(empty)
+		{
+			var nec=-1;
+			for(var k=j+1;k<dim;++k)
+			{
+				var e2=true;
+				for(var i=0;i<dim;++i)if(board[i][k]!==0){e2=false;break;}
+				if(!e2){nec=k;break;}
+			}
+			if(nec>-1)
+			for(var i=0;i<dim;++i)
+			{
+				board[i][j]=board[i][nec];board[i][nec]=0;
+				boarde[i][j]=boarde[i][nec];boarde[i][nec]=null;
+				if(boarde[i][j]!==null)
+				{
+					boarde[i][j].j=j;
+					boarde[i][j].style.left=j*dimpx/dim+"px";
+				}
+			}
+		}
+	}
+	if(checkEndGame())
+	{
+		document.getElementById("egscore").innerHTML=cscore.toString();
+		document.getElementById("endgameDiv").style.fontSize="2em";
+		document.getElementById("endgameDiv").style.border="0.5em 2em";
+		document.getElementById("endgameDiv").style.transform="translate(-50%,-50%)";
+		document.getElementById("endgameDiv").style.WebkitTransform="translate(-50%,-50%)";
+	}
+}
+function checkEndGame()
+{
+	var e=true,nsn=true;
+	for(var i=0;i<dim;++i)
+	for(var j=0;j<dim;++j)
+	{
+		if(board[i][j]!==0)e=false;
+		var s=0;
+		for(var k=0;k<4;++k)
+		if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j]&&board[i][j]!==0)++s;
+		if(s!==0)nsn=false;
+	}
+	return e||nsn;
+}
+//======================================================================================
+//=                         The Same Game AI - Greedy AI                               =
+//=                                   poj 1027                                         =
+//======================================================================================
+var b,v;
+var q=[];
+function Int(v){this.v=v;}
+function Pnt(x,y){this.x=x;this.y=y;}
+function inBound(p){return (p.x>=0&&p.x<dim&&p.y>=0&&p.y<dim);}
+function bfs(x,y,s,rmv)
+{
+	q[0]=new Pnt(x,y);var col=b[y][x];
+	var ret=0,L=0,R=0;
+	while(L<=R)
+	{
+		var cur=q[L++];
+		if(v[cur.y][cur.x]===0)++ret;else continue;
+		v[cur.y][cur.x]=s;
+		for(var i=0;i<4;++i)
+		{
+			var np=new Pnt(cur.x+dx[i],cur.y+dy[i]);
+			if(inBound(np)&&v[np.y][np.x]===0&&col==b[np.y][np.x])
+			q[++R]=new Pnt(np.x,np.y);
+		}
+	}
+	if(rmv)
+	for(var i=0;i<dim;++i)for(var j=0;j<dim;++j)if(v[i][j]===s)b[i][j]=0;
+	return ret;
+}
+function solverUpdateBoard(x,y,s)
+{
+	for(var i=0;i<dim+4;++i)for(var j=0;j<dim+4;++j)v[i][j]=0;
+	var col=b[y][x];
+	bfs(x,y,s,true);
+	for(var j=0;j<dim;++j)
+	for(var i=dim;i>0;--i)
+	for(var k=dim-1;k>=0;--k)
+	if(b[k][j]===0){var t=b[k][j];b[k][j]=b[k+1][j];b[k+1][j]=t;}
+	for(var k=0;k<dim;++k)
+	for(var j=0;j<dim-1;++j)
+	{
+		var s=0;
+		for(var i=0;i<dim;++i)if(b[i][j]===0)++s;
+		if(s===dim)for(var i=0;i<dim;++i){var t=b[i][j];b[i][j]=b[i][j+1];b[i][j+1]=t;}
+	}
+}
+function solve()
+{
+	b=new Array(dim+4);for(var i=0;i<dim+4;++i)b[i]=new Array(dim+4);
+	for(var i=0;i<dim;++i)for(var j=0;j<dim;++j)b[i][j]=board[i][j];
+	v=new Array(dim+4);for(var i=0;i<dim+4;++i)v[i]=new Array(dim+4);
+	for(var j=0;j<dim+2;++j)b[dim][j]=0;
+	for(var i=0;i<dim+2;++i)b[i][dim]=0;
+	var s=0;optscore=0;sol.length=0;
+	var col,finalcol;
+	for(;;)
+	{
+		++s;
+		for(var i=0;i<dim+4;++i)for(var j=0;j<dim+4;++j)v[i][j]=0;
+		var stPnt=new Pnt(1<<25,1<<25),maxn=-1;
+		for(j=0;j<dim;++j)
+		for(i=0;i<dim;++i)
+		if(v[i][j]===0&&b[i][j]!==0)
+		{
+			col=b[i][j];
+			var num=bfs(j,i,s,false);
+			if(num>maxn){stPnt=new Pnt(j,i);maxn=num;finalcol=col;}
+			else if(num==maxn)
+			{
+				if(j<stPnt.x){stPnt=new Pnt(j,i);finalcol=col;}
+				else if(j==stPnt.x&&i<stPnt.y)
+				{stPnt=new Pnt(j,i);finalcol=col;}
+			}
+		}
+		if(maxn<=1)break;
+		optscore+=(maxn-2)*(maxn-2);
+		console.log("Move "+s+" at ("+stPnt.y+","+stPnt.x+"): removed "+maxn+" balls of color "+finalcol+", got "+(maxn-2)*(maxn-2)+" points.");
+		sol.push(new Pnt(stPnt.y,stPnt.x));
+		solverUpdateBoard(stPnt.x,stPnt.y,s);
+	}
+	console.log("Optimal score: "+optscore);
+	return optscore;
+}
\ No newline at end of file