######################################################################################################
##This is ComboProject5.txt, a Maple package to generate and investigate integer sequences counting  #
#final Tie positions in k by n generalized TicTaoToe for specific (small) k                          #
####It is the Maple package created by Team 5 in Dr. Z.'s Combinatorics Class at                     #
#Rutgers University, Fall 2020.                                                                      #
# Save this file as `ComboProject5.txt`, to use it                                                   #
#Type, in a Maple session                                                                            #
#read `ComboProject5.txt`):                                                                          #
#and then to get a list of the functions type                                                        #
#Help():                                                                                             #
#For Help with any of the functions, type                                                            # 
#Help(FunctionName)                                                                                  #
#Team Leader:                                                                                        #
#Team members:                                                                                       #
######################################################################################################


print(`This is ComboProject5.txt, a Maple package that is part of Project 5 in Dr. Z.'s Combinatorics Class at Rutgers University`):
print(`Its purpose is the generate and study sequences enumerating Final tie positions in a k by n generalized TicTacToe`):
print(`in a k by n board, for fixed k. The classical case is k=3 and n=3.`):
print(``):
print(`Team Leader: tbd `):
print(``):
print(`Other Team members: tbd `):
print(`For a list of all the functions type: Help(); `):
print(`For Help with any of the functions, type  Help(FunctionName):`):                                                                        
with(combinat):
Help:=proc()
if nargs=0 then
print(`The available procedures are: Alph3, EvenTTT3, GF3tx, IsBad, Followers3, OddTTT3, TicB, VecToMat  `):
print(` `): 


elif nargs=1 and args[1]=Alph3 then
print(`Alpha3(): The "alphabet" in a 3 by n Tic-Tac-Toe board in other words the set of pairs`):
print(`[v1,v2] where v1 and v2 are {[0,0,1],[0,1,0],[1,0,0],[0,1,1],[1,0,1],[1,1,0]}:`):
print(`There are  36 "letters" . Try:`):
print(`Alph3(); `):


elif nargs=1 and args[1]=EvenTTT3k then
print(`EvenTTT3(N): The first N terms of the sequence number of Tic-Tac-Toe positiong on a (2*k+1)x3 board`):
print(`that ended in a tie, i.e. the number of (2*k)*3 0-1 (or O-X) matrices with 3*k 1 (X) and 3*k 0's (O)`):
print(`without conecutive horizonal,vertical or diagonal  triple of 111 and 000.`):
print(` Try: `):
print(`EvenTTT3(30);`):

elif nargs=1 and args[1]=IsBad then
print(`IsBad(A,k): Given a 0-1 matrix A (expressed as a list of lists) outputs true if there exist k consecutive`):
print(`1's or 0's  either horizonally, vertically, or diagonally. Try:`):
print(`IsBad([[1,1,0],[0,1,0],[1,0,1]],3);`):

elif nargs=1 and args[1]=Followers3 then
print(`Followers3(L): Given a letter L in Alph3(), outputs the set of letters that can follow it legally without causing harm. Try:`):
print(`Followers3([[1,0,1],[0,0,1]]);`):

elif nargs=1 and args[1]=GF3tx then
print(`GF3tx(t,x): The rational function in x and t such that the coefficients of x^m*t^n is the exact number`):
print(`of 3xn 0-1 matrices without three consectutive ones (horiz., vertically, and diagonally)`):
print(`with n ones altogetger. Try:`):
print(`GF3tx(t,x);`):

elif nargs=1 and args[1]=OddTTT3 then
print(`OddTTT3(N): The first N terms of the sequence number of Tic-Tac-Toe positiong on a (2*k+1)x3 board`):
print(`that ended in a tie, i.e. the number of (2*k+1)*3 0-1 (or O-X) matrices with 3*k+2 1 (X) and 3*k+1 0's (O)`):
print(`without conecutive horizonal,vertical or diagonal  triple of 111 and 000.`):
print(` Try: `):
print(`OddTTT3(30);`):

elif nargs=1 and args[1]=TicB then
print(`TicB(m,n,k): Given pos. integers m,n,k, finds the set of all m by n matrices (given as lists-of-lists)`):
print(`with m*n/2 1's (if m*n is even) or (m*n+1)/2 1's (if m*n is odd) that do NOT have a horiz. vertical`):
print(`of diagonal k-streak of 1s. Try:`):
print(`TicB(3,3,3);`):

elif nargs=1 and args[1]=VecToMat then
print(`VecToMat(v,m,n): Inputs a vector of length m*n fits it, row-by-row into an m by n matrix given as list of lists. Try`):
print(`VecToMat([1,1,0,1],2,2);`);


else
 print(`There is no Help for`):

print(args):
fi:

end:


####START ENUMERATING
#IsBad(A,k): Given a 0-1 matrix A (expressed as a list of lists) outputs true if there exist k consecutive
#1's or 0's either horizonally, vertically, or diagonally. Try:
#IsBad([[1,1,0],[0,1,0],[1,0,1]],3):
IsBad:=proc(A,k) local i, j,r:

#Looking for horizontal occurrences of a streak of k 1's
for  i from 1 to nops(A) do
 for j from 1 to nops(A[1])-k+1 do
   if {seq(A[i][j+r],r=0..k-1)}={1}  or {seq(A[i][j+r],r=0..k-1)}={0} 
then
     RETURN(true):
   fi:
 od:
od:


#Looking for vertical occurrences of a streak of k 1's
for  i from 1 to nops(A)-k+1 do
 for j from 1 to nops(A[1]) do
   if {seq(A[i+r][j],r=0..k-1)}={1} or {seq(A[i+r][j],r=0..k-1)}={0} 
then
     RETURN(true):
   fi:
 od:
od:



#Looking for NW-SE diagonal occurrences of a streak of k 1's
for  i from 1 to nops(A)-k+1 do
 for j from 1 to nops(A[1])-k+1 do
   if {seq(A[i+r][j+r],r=0..k-1)}={1}  or {seq(A[i+r][j+r],r=0..k-1)}={0} 
then
     RETURN(true):
   fi:
 od:
od:


#Looking for NE-SW diagonal occurrences of a streak of k 1's
for  i from k to nops(A) do
 for j from 1 to nops(A[1])-k+1 do
   if {seq(A[i-r][j+r],r=0..k-1)}={1}  or {seq(A[i-r][j+r],r=0..k-1)}={0} 
then
     RETURN(true):
   fi:
 od:
od:


false:


end:


#VecToMat(v,m,n): Inputs a vector of length m*n fits it, row-by-row into an m by n matrix given as list of lists
VecToMat:=proc(v,m,n) local A,A1,v1,i,j:

if nops(v)<>m*n then
 RETURN(FAIL):
fi:

A:=[]:

v1:=v:

for i from 1 to m do
 A1:=[]:
 for j from 1 to n do
   A1:=[op(A1),v1[1]]:
  v1:=[op(2..nops(v1),v1)]:
 od:
 A:=[op(A),A1]:
od:
A:

end:


#TicB(m,n,k): Given pos. integers m,n,k, finds the set of all m by n matrices (given as lists-of-lists)
#with m*n/2 1's (if m*n is even) or (m*n+1)/2 1's (if m*n is odd) that do NOT have a horiz. vertical
#of diagonal k-streak of 1s. Try:
#TicB(3,3,3);

TicB:=proc(m,n,k) local Vecs, Cands,v,G,g:

if type(m*n/2, integer) then

Vecs:=permute([1$(m*n/2),0$(m*n/2)]):

else

Vecs:=permute([1$((m*n+1)/2),0$((m*n-1)/2)]):

fi:


Cands:={seq(VecToMat(v,m,n) , v in Vecs)}:


G:={}:

for g in Cands do
 if not IsBad(g,k) then
    G:=G union {g}:
 fi:
od:
G:

end:


Kulam:=proc(m,n,k) local Vecs, Cands,v,G,g:

if type(m*n/2, integer) then

Vecs:=permute([1$(m*n/2),0$(m*n/2)]):

else

Vecs:=permute([1$((m*n+1)/2),0$((m*n-1)/2)]):

fi:


{seq(VecToMat(v,m,n) , v in Vecs)}:

end:

#Alph3(): The "alphabet" in a 3 by n Tic-Tac-Toe board in other words the set of pairs
#[v1,v2] where v1 and v2 are {[0,0,1],[0,1,0],[1,0,0],[0,1,1],[1,0,1],[1,1,0]}:
#There are  36 "letters" 
Alph3:=proc() local V,v1,v2:
V:={[0,0,1],[0,1,0],[1,0,0],[0,1,1],[1,0,1],[1,1,0]}:

{seq(seq([v1,v2],v1 in V),v2 in V)}:
end:

#Followers3(L): Given a letter L in Alph3(), outputs the set of letters that can follow it legally without causing harm. Try:
#Followers3([[1,0,1],[0,0,1]]);
Followers3:=proc(L) local V,v,cand,F:
V:={[0,0,1],[0,1,0],[1,0,0],[0,1,1],[1,0,1],[1,1,0]}:

F:={}:
for v in V do
 cand:=[op(L),v]:

if not IsBad(cand,3) then
 F:=F union {[L[2],v]}:
fi:
od:

F:

end:


#GF3tx(t,x): The rational function in x and t such that the coefficients of x^m*t^n is the exact number
#of 3xn 0-1 matrices without three consectutive ones (horiz., vertically, and diagonally)
#with n ones altogetger. Try:
#GF3tx(t,x);
GF3tx:=proc(t,x) local A,eq,var,a,eq1,X,F,f:
A:=Alph3():

eq:={}:
var:={}:
for a in A do
   var:=var union {X[a]}:
 eq1:=X[a]-x^2*t^(a[1][1]+a[1][2]+a[1][3]+a[2][1]+a[2][2]+a[2][3]):
  F:=Followers3(a):
  eq1:=eq1 -x*add(X[f]*t^(a[1][1]+a[1][2]+a[1][3]), f in F):
 eq:=eq union {eq1}:
od:

var:=solve(eq,var):

normal(add(subs(var,X[a]), a in A)):

end:

#OddTTT3(N): The first N terms of the sequence number of Tic-Tac-Toe positiong on a (2*k+1)x3 board
#that ended in a tie, i.e. the number of (2*k+1)*3 0-1 (or O-X) matrices with 3*k+2 1 (X) and 3*k+1 0's (O)
#without conecutive horizonal,vertical or diagonal  triple of 111 and 000.
#Try:
#OddTTT3(30);
OddTTT3:=proc(N) local f,i,t,x:

#This is the weight-enumerator of all k by 3 0-1 matrices with these restrictions according to the weight
#x^k*t^NumberOfOnes
f:=GF3tx(t,x):

#Take the Taylor expansion up to x^(2*N+2)
f:=taylor(f,x=0,2*N+3):

#Extract the coefficients of x^(2*i+1)*t^(3*i+2)
[seq(coeff(coeff(f,x,2*i+1),t,3*i+2),i=1..N)]:

end:


#EvenTTT3(N): The first N terms of the sequence number of Tic-Tac-Toe positiong on a (2*k)x3 board
#that ended in a tie, i.e. the number of (2*k)*3 0-1 (or O-X) matrices with 3*k 1 (X) and 3*k 0's (O)
#without conecutive horizonal,vertical or diagonal  triple of 111 and 000.
#Try:
#EvenTTT3(30);
EvenTTT3:=proc(N) local f,i,t,x:

#This is the weight-enumerator of all k by 3 0-1 matrices with these restrictions according to the weight
#x^k*t^NumberOfOnes
f:=GF3tx(t,x):

#Take the Taylor expansion up to x^(2*N+2)
f:=taylor(f,x=0,2*N+3):

#Extract the coefficients of x^(2*i)*t^(3*i)
[seq(coeff(coeff(f,x,2*i),t,3*i),i=1..N)]:

end:

###END ENUMERATING