#Yusra Naqvi
#HW 18

#OK to post

################################################################################

#2
#AllWords(A,n): inputs an alphabet A, and a positive integer n, and 
#outputs the set of all nops(A)^n words of length n. 

AllWords:=proc(A,n) local S,i,v:

S[0]:={[]}:

for i from 1 to n do
 S[i]:=`union`(seq({seq([A[j], op(v)], v in S[i-1])},j=1..nops(A))):
od:

S[n]:

end:

###

#IsBad2(w,fp1,B): returns true iff the word w is equal to a pattern fp1.
#It assumes that nops(w)=nops(fp1), which is fine because this is how it is 
#used in the procedure `IsBad1` below.

IsBad2:=proc(w,fp1,B) local i:   

for i from 1 to nops(fp1) do
 if w[i]<>fp1[i] and fp1[i]<>B then
  return(false):
 fi:
od:

true:

end:

###

#IsBad1(w,fp1,B): returns true iff the word w contains the pattern fp1.

IsBad1:=proc(w,fp1,B) local i:   

if fp1=[] then
 return(true):
elif nops(fp1)>nops(w) then
 return(false):
fi:

for i from 1 to nops(w)-nops(fp1)+1 do
 if IsBad2(w[i..i+nops(fp1)-1],fp1,B) then
  return(true):
 fi:
od:

false: 

end:

###

#IsBad(w,FP,B): returns true iff the word w contains at least one of 
#the members of the set of patterns FP.

IsBad:=proc(w,FP,B) local fp1:

for fp1 in FP do
 if IsBad1(w,fp1,B) then
  return(true):
 fi:
od:

false:

end:

###

#SetWnS(A,FP,B,n): contructs the set of n-letter words in the alphabet A 
#not containing any of the patterns of FP 

SetWnS:=proc(A,FP,B,n) local S,T,w:

S:=AllWords(A,n):
T:={}:

for w in S do
 if not IsBad(w,FP,B) then
  T:=T union {w}:
 fi: 
od:

T:

end:

###

#WnS(A,FP,B,n): 
#Inputs
#(i) A: a set of symbols (the alphabet)
#(ii) FP: a set of forbidden patterns, given as a list
#(iii) B: a symbol for blank
#(iv) n: a positive integer
#Outputs:
#the number of words in A of length n that AVOID all patterns in FP.  

WnS:=proc(A,FP,B,n):

nops(SetWnS(A,FP,B,n)):

end:

################################################################################

#3
#The first 15 terms of:

#WnS({0,1},{[1,1,1],[1,B,1,B,1],[1,B,B,1,B,B,1],[1,B,B,B,1,B,B,B,1],
#[1,B$4,1,B$4,1],[1,B$5,1,B$5,1]},B,n); 

#2, 4, 7, 13, 23, 40, 65, 106, 169, 278, 443, 705, 1117, 1760, 2807

#WnS({0,1}, { [1,1,1],[1,B,1,B,1],[1,B,B,1,B,B,1],[1,B,B,B,1,B,B,B,1], 
#[1,B$4,1,B$4,1],[1,B$5,1,B$5,1],[0,0,0],[0,B,0,B,0],[0,B,B,0,B,B,0],
#[0,B,B,B,0,B,B,B,0], [0,B$4,0,B$4,0],[0,B$5,0,B$5,0]},B,n); 

#2, 4, 6, 10, 14, 20, 16, 6, 0, 0, 0, 0, 0, 0, 0

################################################################################

#4
#SFP(d,n):

SFP:=proc(d,n) local FP,i,j:

FP:={}:

if n<d then
 return(FP):
fi:

for i from 0 to trunc((n-d)/(d-1)) do
 FP:=FP union {[seq(op([1,B$i]),j=1..d-1),1]}:
od: 

end:

################################################################################

#5
#seq(WnS({0,1},SFP(3,n),B,n),n=1..15);
#2, 4, 7, 13, 23, 40, 65, 106, 169, 278, 443, 705, 1117, 1760, 2692

#seq(NdnM(3,n),n=1..15);
#2, 4, 7, 13, 23, 40, 65, 106, 169, 278, 443, 705, 1117, 1760, 2692

#seq(WnS({0,1},SFP(4,n),B,n),n=1..15);
#2, 4, 8, 15, 29, 56, 103, 192, 364, 668, 1222, 2233, 3987, 7138, 12903

#seq(NdnM(4,n),n=1..15);
#2, 4, 8, 15, 29, 56, 103, 192, 364, 668, 1222, 2233, 3987, 7138, 12903

################################################################################

#6
#IsBadB(w,BFP,B): returns true iff the word w begins with any of 
#the members of the set of patterns BFP.

IsBadB:=proc(w,BFP,B) local fp1:

for fp1 in BFP do
 if IsBad2(w[1..nops(fp1)],fp1,B) then
  return(true):
 fi:
od:

false:

end:

###

#SetWGnS(A,FP,B,n,BFP): contructs the set of n-letter words in the alphabet A 
#not containing any of the patterns of FP, or beginning with any pattern in BFP. 

SetWGnS:=proc(A,FP,B,n,BFP) local S,T,w:

S:=AllWords(A,n):
T:={}:

for w in S do
 if not IsBad(w,FP,B) and not IsBadB(w,BFP,B) then
  T:=T union {w}:
 fi: 
od:

T:

end:

###

#WGnS(A,FP,B,n,BFP): 
#Inputs
#(i) A: a set of symbols (the alphabet)
#(ii) FP: a set of forbidden patterns, given as a list
#(iii) B: a symbol for blank
#(iv) n: a positive integer
#(v) BFP: a set of forbidden beginning patterns
#Outputs:
#the number of words in A of length n that avoid all patterns in FP,
#and also avoid any patterns from BFP appearing at the beginning of the word.  

WGnS:=proc(A,FP,B,n,BFP):

nops(SetWGnS(A,FP,B,n,BFP)):

end:

################################################################################