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