#OK to post homework
#Lucy Martinez, 03-19-2024, Assignment 16


# Problem 2: Write a procedure generalizing SR, call it qSR(q,INI,L,n)
# that (i) inputs INI (a list of length nops(L) of integers in {0,...,q-1}
# (ii) a list of pairs [c[i],a[i]] , i=1..r where c is in {1, ..., q-1},
# and ai are positive integers and a1<.. x[t]=c[1]*x[t-a[1]]+ ... + c[r]*x[t-a[r]] mod q
qSR:=proc(q,INI,L,n) local r,i,ng,M,S:
r:=nops(L):

#checks that we have enough initial condition for the recurrence
if nops(INI)<>L[r][2] then
 return(FAIL):
fi:

S:={}:
for i from 1 to r do
 S:=S union {L[i][1]}:
od:
#check that c[i]'s are members of {1, ..., q-1}
if not (S subset {seq(i,i=0..q-1)}) then
 return(FAIL):
fi:

if not (convert(INI,set) subset {seq(i,i=0..q-1)}) then
 return(FAIL):
fi:

if not ({seq(type(L[i][2],posint),i=1..nops(L))}={true} and sort([seq(L[i][2],i=1..r)])=[seq(L[i][2],i=1..r)]) then
 return(FAIL):
fi:

if not type(n,posint) then
 return(FAIL)
fi:

M:=INI:
while nops(M)<n do
 ng:=add(L[i][1]*M[-L[i][2]],i=1..r) mod q:
 M:=[op(M),ng]:
od:
M:
end:




# Problem 3: What are the periods of
# qSR(3,[1,2,1],[[1,2],[2,3]],10000)? ANSWER: 26
# qSR(5,[1,2,4,1,2],[[1,2],[2,5]],10000)? ANSWER: 744
# qSR(11,[3,1,2,4,3],[[1,2],[2,5]],10000)? ANSWER: 3660
# qSR(5,[1,0,0,0,0,0],[[3,4],[2,5],[3,6]],10000)? ANSWER: 744



##################################################### from class:
Help16:=proc():
 print(`SR(INI,L,n),IsPer(L,t),FindPer(L)`):
end:

#SR=Shift Register from Clifford Cocks summary
#SR(INI,L,n): inputs a 0,1 list of length L[nops(L)],
# a list of increasing positive integers L, and 
# outputs the sequence of 0s and 1s generated by them of length n
# outputs the list of length n generated by the recurrence
# x[t]=x[t-L[1]]+..+x[t-L[nops(L)]]
SR:=proc(INI,L,n) local r,i,M,ng:
r:=nops(L):
if nops(INI)<>L[-1] then
 return(FAIL):
fi:

if not (convert(INI,set)={0,1} or convert(INI,set)={1}) then
 return(FAIL):
fi:

if not (type(L,list) and {seq(type(L[i],posint),i=1..nops(L))}={true} and sort(L)=L) then
 return(FAIL):
fi:

if not type(n,posint) then
 return(FAIL)
fi:

M:=INI:
while nops(M)<n do
 ng:=add(M[-L[i]],i=1..r) mod 2:
 M:=[op(M),ng]:
od:
end:

#IsPer(L,t): Is L periodic of period t?
IsPer:=proc(L,t) local i:
if {seq(L[i]-L[i+t],i=1..nops(L)-t)}={0} then
 true:
else
 false:
fi:
end:


#FindPer(L): finds the period of the list L
FindPer:=proc(L) local t:
for t from 1 to trunc(nops(L)/2) while not IsPer(L,t) do od:

if t=trunc(nops(L)/2)+1 then
RETURN(FAIL):
else
 RETURN(t):
fi:

end: