######################################################################
## OneUp.txt Save this file as  OneUp.txt  to use it,                #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read `OneUp.txt` <Enter>                          #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Doron Zeilberger, Rutgers University ,                 #
##  DoronZeil at gmail dot com                                       # 
######################################################################


print(`First Written: April 2024: tested for Maple 2020 `):
print(`Version  : April 2024:  `):
print():
print(`This is OneUp.txt, A Maple package to solve and generate One Up puzzles as appearing (starting April  2024) in the New York Times magazine`):
print(`created by Rodolfo Kurchan`):
print(`accompanying Shalsoh B. Ekhad's book  `):
print(`Fifty OneUp puzzles `):
print(`  `):

print():
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/OneUp.txt .`):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):
print():
print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):
print(`For a list of the supporting functions type: ezra1();`):
print():
 



ezraDB:=proc()

print(`The prec-computed datab-base procedures are`):
print(`  DB66 `):


end:

ezra1:=proc()
if args=NULL then

print(`The SUPPORTING procedures are:  Ptor, RecToPuz,  Yel `):
print(` `):

else
ezra(args):

fi:

end:

ezra:=proc()
if args=NULL then

print(` OneUp.txt: A Maple package for  solving and creating One Up puzzles`):

print(`The MAIN procedures are: DrawPu, MakePuz, MakeRP66, Sol, Sol1`):
print(` `):

elif nargs=1 and args[1]=DB then
print(`DB66(): a data base of 6 by 6 One Up puzzles. For example the puzzle from April 21, 2024`):
print(` DB66()[1];`):

elif nargs=1 and args[1]=DrawPu then
print(`DrawPu(P,Pols):Draws the puzzle P. Try:`):
print(`DrawPu(DB66()[1]);`):

elif nargs=1 and args[1]=MakeRP66 then
print(`MakeRP66(): makes a random 6x6 puzzle. Try:`):
print(`MakeRP66();`):

elif nargs=1 and args[1]=MakePuz then
print(`MakePuz(Ver,Hoz): inputs  tries to make a puzzle with unique solution by adding the fifth componet of clues`).
print(` of the form [nops(Hor),nops(Ver),Ver,Hor,Clues]`):
print(`Try:`):
print(`MakePuz([[2],[3],[5],[4],[],[]],[[],[5],[4],[2],[3],[]]);`):


elif nargs=1 and args[1]=Ptor then
print(`Ptor(P): solves the puzzle P. Try:`):
print(`Ptor(RecToPuz(DB66()[1]));`):


elif nargs=1 and args[1]=RecToPuz then
print(`RecToPuz(P): inputs a rectangular puzzle P=[M,N,ListOfRowbars, ListOfColBars,SetOfCurrentClues] outputs`):
print(`the general puzzle of the from [UnderLyingSet, SetOfSubsets]. Try:`):
print(`RecToPuz(DB66()[1]);`):


elif nargs=1 and args[1]=Sol then
print(`Sol(P): solves the One Up puzzle in the formt [M,N,ListOfVerticalBarLists,ListOfHozintoallBarLists,PatrialClues] `):
print(` where ListOfVerticalBars separates the boxes in rows (going from left to right), and ListOfHorizonatalBars separates the boxes in colums (going up)`):
print(``):
print(`outputs the set of all solutions that are compatible with them. The output is a set of`):
print(`M by N matrices but with the indexing a Cartesian way. Try:`):
print(`Sol(DB66()[1]);`):
print(`Sol(DB66()[2]);`):
print(`Sol(DB66()[3]);`):
print(`Sol(DB66()[4]);`):


elif nargs=1 and args[1]=Sol1 then
print(`Sol1(P): Like Sol(P) but in a format suitable for drawing. Try`):
print(`Sol1(DB66()[1]);`):

elif nargs=1 and args[1]=Yel then
print(`Yel(P): The children of the partially solved puzzle P. Try:`):
print(`Yel(RecToPuz(DB66()[1]));`):


else
 print(`There is no such thing as`, args):

fi:


end:

with(plots):


#start pre-computed puzzles and solutions
#DB66(): A pre-computed list of 6 by 6 OpeUp puzzles
DB66:=proc():
#[6,6,[[],[],[],[],[],[]],[[],[],[],[],[],[]],{[[,],]}]
[
#April 21, 2024
[6,6,[[2],[3],[5],[4],[],[]],[[],[5],[4],[2],[3],[]],{[[1,5],4],[[2,1],1],[[3,4],2]}],

#April 28, 2024
[6,6,[[1,4],[],[],[3],[2],[4]],[[],[4],[3],[2],[],[3,5]],{[[4,1],2],[[4,4],1],[[5,3],6]}],

#May5, 2024
[6,6,[[1],[3],[2],[5],[4],[]],[[3],[],[4],[1],[5],[2]],{[[2,4],3]}],

#May12, 2024
[6,6,[[2],[4],[],[1],[3],[]],[[],[5],[],[2],[3],[4]],{[[6,3],4]}],

#May19, 2024
[6,6,[[3],[],[2],[2],[5],[]],[[3],[5],[],[2],[2],[]],{[[3,2],5], [[3,4],2], [[4,1],1], [[4,3],4]}],

#May26, 2024
[6,6,[[],[3],[5],[2],[4],[]],[[],[2],[4],[3],[5],[]],{[[1,3],5], [[3,3],1]}]



]:
end:


#RecToPuz(P): inputs a rectangular puzzle P=[M,N,ListOfRowbars, ListOfColBars,SetOfCurrentClues] outputs
#the general puzzle of the from [UnderLyingSet, SetOfSubsets]. Try:
#RecToPuz(DB66()[1]);
RecToPuz:=proc(P) local M,N,i,j,kv,S,lu,k1:
M:=P[1]:
N:=P[2]:
kv:={seq(seq([i,j],j=1..M),i=1..N)}:

S:={}:

 
for i from 1 to N do


 lu:=P[4][i]:

if lu=[] then
 S:=S union {{seq([i,j],j=1..M)}}:

else
 S:=S union {{seq([i,j],j=1..lu[1])}}:
 for k1 from 1 to nops(lu)-1 do
  S:=S union {{seq([i,j],j=lu[k1]+1..lu[k1+1])}}:
 od:
 S:=S union {{seq([i,j],j=lu[nops(lu)]+1..M)}}:
fi:

od:


 
for j from 1 to M do


 lu:=P[3][j]:

if lu=[] then
 S:=S union {{seq([i,j],i=1..N)}}:

else
 S:=S union {{seq([i,j],i=1..lu[1])}}:
 for k1 from 1 to nops(lu)-1 do
  S:=S union {{seq([i,j],i=lu[k1]+1..lu[k1+1])}}:
 od:
 S:=S union {{seq([i,j],i=lu[nops(lu)]+1..N)}}:
fi:

od:

[kv,S,P[5]]:


end:


#Yel(P): The children of the partially solved puzzle P. Try:
#Yel(RecToPuz(DB66()[1]));
Yel:=proc(P) local a,kv,b,s,T1,T2,k,kv1,si,aluf,T3,i1,a1,yofee,v,kha,kv2:

kv:=P[1]:

for a in kv do
 T1[a]:=0:
 T2[a]:={}:
od:


for b in P[3] do
 T1[b[1]]:=b[2]:
od:

for s in P[2] do
 for a in s do
  T2[a]:=T2[a] union {s}:
 od:
od:


for a in kv do
k:=min(seq(nops(kv1), kv1 in T2[a])):

T3[a]:={seq(i1,i1=1..k)} minus {seq(seq(T1[a1],a1 in kv1),kv1 in T2[a])}:

od:



si:=nops(kv):

kv2:=kv minus {seq(a[1],a in P[3])}:
for a in kv2 do
if nops(T3[a])<si then
  si:=nops(T3[a]):

  aluf:=a:

fi:
od:

yofee:={}:

for v in T3[aluf] do
 kha:=P[3] union {[aluf,v]}:
 yofee:=yofee union {[P[1],P[2],kha]}:
od:
yofee:

end:



#Ptor(P): finds all solutions of the generalized One Up puzzle P. Try:
#Ptor(RecToPuz(DB66()[1]));
Ptor:=proc(P) local gu,gu1:
gu:={P}:

while gu<>{} and nops(gu[1][3])<nops(gu[1][1]) do
 gu:={seq(op(Yel(gu1)),gu1 in gu)}:
od:
gu:
end:


#Sol(P): solves the One Up puzzle in the formt [M,N,ListOfVerticalBarLists,ListOfHozintoallBarLists,PatrialClues] and
#outputs the set of all solutions that are compatible with them. The output is a set of
#M by N matrices but with the indexing a Cartesian way. Try:
#Sol(DB66()[1]);
Sol:=proc(P) local P1,M,N,gu,gu1,mu,i,j,a,T3,mu1:
M:=P[1]:
N:=P[2]:
P1:=RecToPuz(P):
gu:=Ptor(P1):

mu:={}:

for gu1 in gu do
 for a in gu1[3] do
   T3[a[1]]:=a[2]:
 od:
mu1:=[seq([seq(T3[[j,M+1-i]],j=1..N)],i=1..M)]:
mu:=mu union {mu1}:
od:
mu:
end:



#Sol1(P): solves the One Up puzzle in the formt [M,N,ListOfVerticalBarLists,ListOfHozintoallBarLists,PatrialClues] and
#outputs the set of all solutions that are compatible with them. The output is a set of
#M by N matrices but with the indexing a Cartesian way. Try:
#Sol1(DB66()[1]);
Sol1:=proc(P) local P1,M,N,gu,gu1,mu,i,j,a,T3,mu1:
M:=P[1]:
N:=P[2]:
P1:=RecToPuz(P):
gu:=Ptor(P1):

{seq([op(1..4,P),gu1[3]],gu1 in gu)}:
end:




#DrawPu(P):Draws the puzzle P. Try
#DrawPu(DB66()[1]);
DrawPu:=proc(P) local M,N,Ver,Hor,S,d,i,j,lu,j1,j11,i1,i11,s:

M:=P[1]: N:=P[2]: Ver:=P[3]: Hor:=P[4]: S:=P[5]:




d:=plot([[0,0],[N,0]],axes=none,color=black,thickness=5, scaling=constrained):
d:=d,plot([[N,0],[N,M]],axes=none,color=black,thickness=5, scaling=constrained):
d:=d,plot([[N,M],[0,M]],axes=none,color=black,thickness=5, scaling=constrained):
d:=d,plot([[0,M],[0,0]],axes=none,color=black,thickness=5, scaling=constrained):



for i from 1 to  M do
  lu:=Ver[i]:
  
if lu=[] then
for j11 from 1 to N do
 d:=d,plot([[j11,i-1],[j11,i]],axes=none,color=black,thickness=1, scaling=constrained):
od:

else

for j11 from 1 to lu[1]-1 do
 d:=d,plot([[j11,i-1],[j11,i]],axes=none,color=black,thickness=1, scaling=constrained):
od:
 d:=d,plot([[lu[1],i-1],[lu[1],i]],axes=none,color=black,thickness=5, scaling=constrained):

for j1 from 1 to nops(lu)-1 do
for j11 from lu[j1]+1 to lu[j1+1]-1 do
 d:=d,plot([[j11,i-1],[j11,i]],axes=none,color=black,thickness=1, scaling=constrained):
od:
 d:=d,plot([[lu[j1+1],i-1],[lu[j1+1],i]],axes=none,color=black,thickness=5, scaling=constrained):
od:


for j11 from lu[nops(lu)]+1 to N do
 d:=d,plot([[j11,i-1],[j11,i]],axes=none,color=black,thickness=1, scaling=constrained):
od:

fi:

od:




for j from 1 to  M do
  lu:=Hor[j]:
  
if lu=[] then
for i11 from 1 to M do
 d:=d,plot([[j-1,i11],[j,i11]],axes=none,color=black,thickness=1, scaling=constrained):
od:

else

for i11 from 1 to lu[1]-1 do
 d:=d,plot([[j-1,i11],[j,i11]],axes=none,color=black,thickness=1, scaling=constrained):
od:
 d:=d,plot([[j-1,lu[1]],[j,lu[1]]],axes=none,color=black,thickness=5, scaling=constrained):

for i1 from 1 to nops(lu)-1 do
for i11 from lu[i1]+1 to lu[i1+1]-1 do
 d:=d,plot([[j-1,i11],[j,i11]],axes=none,color=black,thickness=1, scaling=constrained):
od:
 d:=d,plot([[j-1,lu[i1+1]],[j,lu[i1+1]]],axes=none,color=black,thickness=5, scaling=constrained):
od:


for i11 from lu[nops(lu)]+1 to M do
 d:=d,plot([[j-1,i11],[j,i11]],axes=none,color=black,thickness=1, scaling=constrained):
od:

fi:

od:





for s in S do
    d:=d,textplot([s[1][1]-1/2,s[1][2]-1/2,s[2]]):
od:
display(d);


end:



MakePuz:=proc(Ver,Hor) local m,n,P,gu,M,i,j,CL,cl,P1:
m:=nops(Ver):
n:=nops(Hor):
P:=[m,n,Ver,Hor,{}]:

if Sol(P)={} then
 RETURN(FAIL):
fi:

gu:=Sol(P):

M:=gu[rand(1..nops(gu))()]:

CL:={seq(seq([[j,n+1-i],M[i][j]],i=1..m),j=1..n)}:

while nops(Sol(P))>1 do

cl:=CL[rand(1..nops(CL))()]:

P1:=[op(1..4,P),P[5] union {cl}]:

if nops(Sol(P1))<nops(Sol(P)) then
P:=P1:
CL:=CL minus {cl}:
fi:

od:

P:

end:




#MakeRP66(): makes a random 6x6 puzzle. Try:
#MakeRP66();
MakeRP66:=proc() local gu,Ver,Hor,P:
 gu:=convert(DB66(),set):
 P:=gu[rand(1..nops(gu))()]:
 Ver:=P[3]:
 Hor:=P[4]:
MakePuz(Ver,Hor):
end: