--!name Dots and Boxes
--!icon game
--!category Games
local R,j=4,9 local f,S,Y,aO,l,_,x,O,P,a8={},{},{},{},{},{},{},{},{},{}local function bq(e)R,j=e,2*e+1 f,S,Y,aO,l,_,x,O,P={},{},{},{},{},{},{},{},{}a8={-j,j,-1,1}for k=0,j-1 do for u=0,j-1 do local h=k*j+u f[h]=0 if(k+u)%2==1 then l[#l+1]=h _[h]=#l if k%2==0 then O[h],P[h]=k>0 and h-j,k<j-1 and h+j else O[h],P[h]=u>0 and h-1,u<j-1 and h+1 end elseif k%2==1 then x[#x+1]=h S[h]=0 end end end end local function ag(h,t)f[h]=1 local z,b=0,O[h]if b then f[b]=f[b]+1 if f[b]==4 then S[b]=t;z=1 end end b=P[h]if b then f[b]=f[b]+1 if f[b]==4 then S[b]=t;z=z+1 end end return z end local function aL(h)f[h]=0 local b=O[h]if b then if f[b]==4 then S[b]=0 end f[b]=f[b]-1 end b=P[h]if b then if f[b]==4 then S[b]=0 end f[b]=f[b]-1 end end local function X(b,i)for a=1,4 do local c=b+a8[a]if f[c]==0 and c~=i then return c end end end local function ay(c,b)local n=O[c]if n==b then return P[c]end return n end local ah,aC,I,ae,bw=0,0,false,0,360 local function aI(ak)ah=ah+ak if ah>aC then I=true end ae=ae+ak if ae>=bw then ae=0;coroutine.yield()end end local function a3(aa,a9)local e=a9 or 0 for d=1,#l do local c=l[d]if f[c]==0 then local n,b=O[c],P[c]if(not n or f[n]<2)and(not b or f[b]<2)then e=e+1;aa[e]=c end end end return e-(a9 or 0)end local function bd(y)local e,aQ=0,true while aQ do aQ=false for d=1,#x do local b=x[d]if f[b]==3 then local c=X(b)y[#y+1]=c e=e+ag(c,0)aQ=true end end end aI(1+e//4)return e end local function bt(y)for d=#y,1,-1 do aL(y[d]);y[d]=nil end end local Z,au,al,ao={},{},{},{}local function bu(b,c)local e=0 while true do local i=ay(c,b)if not i or f[i]~=2 then return e,c,false end if ao[i]then return e,c,true end ao[i]=true e=e+1 c=X(i,c)b=i end end local function aU()ao={}local a=0 for d=1,#x do local b=x[d]if f[b]==2 and not ao[b]then ao[b]=true local aB=X(b)local bc=X(b,aB)local a_,bC,bH=bu(b,aB)a=a+1 if bH then Z[a],au[a],al[a]=a_+1,1,aB else local bJ=bu(b,bc)local F=a_+bJ+1 Z[a],au[a],al[a]=F,0,bC if F==2 then al[a]=a_==1 and aB or bc end end end end for d=a+1,#Z do Z[d],au[d],al[d]=nil,nil,nil end aI(2)return a end local function bh(d)return string.char((au[d]==1 and 96 or 64)+Z[d])end local function aZ(a,bO)local g={}for d=1,a do if d~=bO then g[#g+1]=bh(d)end end table.sort(g)return table.concat(g)end local function bf(ac,k)if ac>96 then local F=ac-96 return math.max(F+k,F-8-k)end local F=ac-64 if F<=2 then return F+k end return math.max(F+k,F-4-k)end local am,av={},0 local function aM(m)if m==""then return 0 end local p=am[m]if p then return p end aI(1)av=av+1 if av>120 then am,av={},0 end local bn for d=1,#m do local ac=m:byte(d)if ac~=bn then bn=ac local bl=-bf(ac,aM(m:sub(1,d-1)..m:sub(d+1)))if not p or bl>p then p=bl end end end am[m]=p return p end local aw,ax,Q,aP={},0,0,{}local function bk(aH)aI(2)if I then return 0 end local p=aw[Q]if p then return p end local e=a3(aP,aH)if e==0 then p=aM(aZ(aU()))else for d=aH+1,aH+e do local c=aP[d]ag(c,0)Q=Q~(1<<_[c])local i=-bk(aH+e)Q=Q~(1<<_[c])aL(c)if I then return 0 end if not p or i>p then p=i end end end ax=ax+1 if ax>200 then I=true end aw[Q]=p return p end local function bA()local q,aR for d=1,#l do local c=l[d]if f[c]==0 then ag(c,0)local y={}local e=bd(y)bt(y)aL(c)if not aR or e<aR then q,aR=c,e end end end return q end local function bE()local at,bv,aV,a0=nil,nil,nil,0 for d=1,#x do local b=x[d]if f[b]==3 then local i=X(b)local aA=ay(i,b)if not aA or f[aA]~=2 then return i end local E=X(aA,i)local aq=ay(E,aA)local r if not aq or f[aq]<2 then r=2 elseif f[aq]==2 then local ba=ay(X(aq,E),aq)if ba and f[ba]==3 then r=4 end end if not r then return i end a0=a0+1 if a0>1 then return i end at,bv,aV=i,E,r end end if not at then return nil end local y={at}ag(at,0)bd(y)local aa={}local bg=false local a=aU()if a3(aa)==0 and a>0 then bg=aM(aZ(a))<-aV end bt(y)if bg then return bv,aV end return at end local function bD()local a=aU()if a==0 then return nil end local q,T for d=1,a do local p=-bf(bh(d):byte(),aM(aZ(a,d)))if not T or p>T or(p==T and Z[d]<Z[q])then q,T=d,p end end return al[q]end local function bL(G)ae=ae+1 local aT for d=1,#x do if f[x[d]]==3 then aT=x[d];break end end if aT then if G==3 then ah,aC,I=0,1000000,false local c,r=bE()if c then return c,r end end if G>1 or math.random(10)<=9 then return X(aT)end end local aa={}local e=a3(aa)if e>0 then if G==1 and math.random(10)<=3 then e=0 elseif G==3 and e<=16 then ah,aC,I,aw,ax,Q=0,5000,false,{},0,0 local q,T for d=1,e do local c=aa[d]ag(c,0)Q=1<<_[c]local i=-bk(0)aL(c)if I then break end if not T or i>T then q,T=c,i end end aw,aP={},{}if not I then return q end end if e>0 then return aa[math.random(e)]end end if G==3 then ah,aC,I=0,1000000,false local c=bD()if c then return c end end if G>=2 then return bA()end local aE={}for d=1,#l do if f[l[d]]==0 then aE[#aE+1]=l[d]end end return aE[math.random(#aE)]end local v,an,H={},{},{0,0}local N,w,K,L=1,nil,"",0 local o,ad,A,D,W,aj,af=1,0,2,4,4,false,false local ap={0,0,0,0,0,0,0,0,0}local aN={"Easy","Medium","Hard"}local function a6(t)if o==1 then return t==1 and"You"or"Computer"end return t==1 and"Player 1"or"Player 2"end local function a2()bq(W)v,an,H={},{},{0,0}N=(o==1 and ad==1)and 2 or 1 w,K,L=nil,"",R*R end local function aF(c)local t=N local z=ag(c,t)local e=#v+1 v[e],an[e],aO[c]=c,t,e if z>0 then local b=O[c]if b and f[b]==4 and not Y[b]then Y[b]=e end b=P[c]if b and f[b]==4 and not Y[b]then Y[b]=e end H[t]=H[t]+z L=L-z else N=3-t end return z end local function bo(a)if o~=1 or af then return end af=true local d=(A-1)*3+a ap[d]=ap[d]+1 end local function as()w=nil if L>0 then return end local n,b=H[1],H[2]local a4=math.max(n,b).."-"..math.min(n,b)if n==b then w="Draw "..a4 bo(3)elseif o==1 then w=(n>b and"You win "or"Computer wins ")..a4 bo(n>b and 1 or 2)else w=(n>b and"Player 1"or"Player 2").." wins "..a4 end end local a7="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"local function bN()local g={"D1",o,ad,A,W,af and 1 or 0,table.concat(ap,","),":"}for d=1,#v do local a=_[v[d]]g[#g+1]=a7:sub(a,a)end g[#g+1]="|"..K return table.concat(g)end local function bp()snail.save(bN())end local function aG(ar,e)a2()for d=1,e do local c=ar[d]if L==0 or not c or f[c]~=0 then break end aF(c)end as()end local function bM()local m=snail.load()if type(m)~="string"then return false end local aD,aW,G,bR,bB,bP,bj,bS=m:match("^D1(%d)(%d)(%d)(%d)(%d)([%d,]+):(%w*)|?(.*)$")if not aD then return false end local d=0 for p in bP:gmatch("%d+")do d=d+1;ap[d]=tonumber(p)end o,ad,A,D=tonumber(aD),tonumber(aW),tonumber(G),tonumber(bR)if o<1 or o>2 then o=1 end if ad>1 then ad=0 end if A<1 or A>3 then A=2 end if D<3 or D>5 then D=4 end W=D bq(W)local ar={}for a=1,#bj do ar[a]=l[a7:find(bj:sub(a,a),1,true)]end af=true aG(ar,#ar)af=bB=="1"K=bS:sub(1,95)aj=true return true end local U,aK,aX=nil,false,nil local M,B,s="menu",1,1 local aS local function a5()if U and coroutine.status(U)~="dead"then aG(v,#v)end U,aK,aX=nil,false,nil snail.tick(0)end local function bz(G,t)am,ae={},0 local C,V=0,nil while L>0 and N==t do local c,r=bL(G)if not c then break end C=C+aF(c)V=r end am={}return C,V end local aJ local function br()aK=true aX=aS()U=coroutine.create(function()return bz(A,2)end)snail.after(aJ)snail.tick(450)end local function aY()return not w and not aK and(o==2 or N==1)end local function be()if f[s]==0 and _[s]then return end local k,u=s//j,s%j local q,ab for d=1,#l do local c=l[d]if f[c]==0 then local r=(c//j-k)^2+(c%j-u)^2 if not ab or r<ab then q,ab=c,r end end end if q then s=q end end local function az()bp()if not w and o==1 and N==2 then br()else be()end end local function bm(e)return e==1 and"a box"or(e.." boxes")end local function by(C,V)if L==0 then return"Computer took the last "..(C==1 and"box."or(C.." boxes."))end local g=C>0 and("took "..bm(C))or nil if V then return"Computer "..(g and(g.." and ")or"").."left you the last "..V.." boxes."end return"Computer "..(g and(g..", then ")or"").."drew the marked line."end aJ=function()if not U then return end local bK,C,V=coroutine.resume(U)if coroutine.status(U)~="dead"then return end a5()if not bK then aG(v,#v)C,V=0,nil for d=1,#l do if f[l[d]]==0 then C=aF(l[d]);break end end end K=by(C or 0,V)as()az()end local function a1(aD,aW)a5()o,ad,W,aj,af=aD,aW,D,true,false a2()as()s=l[(#l+1)//2]M="play"az()end local function bs()local e=#v if o==1 then while e>0 and an[e]~=1 do e=e-1 end end if e==0 then return nil end return e-1 end local function bT()local e=bs()if not e then return end a5()local c=v[e+1]aG(v,e)K="Took back a line."s=c M="play"az()end local function bi()local g={}if aj then g[#g+1]={"Back to the game","resume"}end g[#g+1]={"New game, you go first","f"}g[#g+1]={"New game, computer first","c"}g[#g+1]={"New game, two players","2"}g[#g+1]={"Computer level: "..aN[A],"lvl"}g[#g+1]={"Board: "..D.."x"..D.." boxes","size"}if aj and bs()then g[#g+1]={"Take back a line","undo"}end return g end local function bI(a)local k,u=s//j,s%j if a=="left"or a=="right"then local r=a=="left"and-2 or 2 local i=u+r while i>=0 and i<j do if f[k*j+i]==0 then s=k*j+i;return end i=i+r end return end local r=a=="up"and-1 or 1 local E=k+r while E>=0 and E<j do local q,ab for i=1-E%2,j-1,2 do if f[E*j+i]==0 then local bb=i-u local m=math.abs(bb)*4+(((bb>0)==(k%2==0))and 0 or 1)if not ab or m<ab then q,ab=E*j+i,m end end end if q then s=q;return end E=E+r end end function key(a)if M=="menu"then local J=bi()if B>#J then B=#J end local n=J[B][2]if a=="up"then B=(B-2)%#J+1 elseif a=="down"then B=B%#J+1 elseif a=="ok"or((a=="left"or a=="right")and(n=="lvl"or n=="size"))then if n=="resume"then M="play"elseif n=="f"then a1(1,0)elseif n=="c"then a1(1,1)elseif n=="2"then a1(2,0)elseif n=="lvl"then A=(A+(a=="left"and 1 or 0))%3+1 if aj then bp()end elseif n=="size"then D=(D-3+(a=="left"and 2 or 1))%3+3 elseif n=="undo"then bT()end end return end if a=="top"then M="menu";B=1;return end if w then if a=="ok"then M="menu";B=2 end return end if not aY()then return end if a=="ok"then if f[s]==0 then local t=N local z=aF(s)if z>0 then K=a6(t).." took "..bm(z)..(L==0 and"."or(o==1 and" - go again."or" - another turn."))else K=o==2 and(a6(t).." drew the marked line.")or""end as()az()end elseif a=="left"or a=="right"or a=="up"or a=="down"then bI(a)end end function tick()aJ()if U then snail.after(aJ)end end local bx="abcdefghijklmnqp"aS=function()local g={}local bF=M=="play"and aY()local ai=#v while ai>1 and an[ai-1]==an[#v]do ai=ai-1 end for k=0,j-1 do if k>0 then g[#g+1]="/"end for u=0,j-1 do local h=k*j+u local a if k%2==0 and u%2==0 then a=1 if k>0 and f[h-j]==1 then a=a+1 end if u<j-1 and f[h+1]==1 then a=a+2 end if k<j-1 and f[h+j]==1 then a=a+4 end if u>0 and f[h-1]==1 then a=a+8 end a=bx:byte(a)elseif k%2==1 and u%2==1 then a=73 if S[h]>0 then a=a+S[h]+(o==2 and 2 or 0)if Y[h]and Y[h]>=ai then a=a+4 end end else a=k%2==0 and 65 or 69 if f[h]==0 then if bF and h==s then a=a+3 end else a=a+((aO[h]or 0)>=ai and 2 or 1)end end g[#g+1]=string.char(a)end end return table.concat(g)end local function bQ()local g if o==1 then g="You "..H[1].."  Computer "..H[2].." - "else g="P1 "..H[1].."  P2 "..H[2].." - "end if w then return g.."game over"end if aK then return g.."thinking..."end if o==1 then return g.."your turn"end return g..a6(N).." to move"end function draw()if M=="menu"then snail.title("Dots and Boxes")local J=bi()if B>#J then B=#J end for d,bG in ipairs(J)do snail.row(bG[1],d==B)end snail.gap()if aj then local ak=o==2 and"Two players"or("You went "..(ad==0 and"first"or"second")..", "..aN[A])ak=ak..", "..W.."x"..W snail.small(ak..(w and(". "..w..".")or(". "..R*R-L.." of "..R*R.." boxes taken.")))else snail.small("Draw lines between dots. Close a box to own it and draw again. Most boxes wins.")end local m=ap snail.small("Won-lost-drawn against the computer:")snail.small("Easy "..m[1].."-"..m[2].."-"..m[3].."   Medium "..m[4].."-"..m[5].."-"..m[6].."   Hard "..m[7].."-"..m[8].."-"..m[9])snail.hint("BACK leave OK choose UP/DN move")return end snail.title(o==1 and("Dots and Boxes - "..aN[A])or"Dots and Boxes - two players")snail.status(bQ())snail.text(K~=""and K or"Arrows move along the lines, OK draws one.")snail.board(aX or aS(),nil,w)if R<5 then snail.small(o==1 and"Y: your boxes   C: the computer's"or"1: player 1's boxes   2: player 2's")end if w then snail.hint("BACK options OK new game")elseif not aY()then snail.hint("BACK options")else snail.hint("BACK options OK draw L/R move UP/DN move")end end function start()math.randomseed(os.time())W=D a2()as()s=l[(#l+1)//2]if bM()then s=l[(#l+1)//2]be()if not w then M="play"if o==1 and N==2 then br()end end end end