#OK to post homework
#Tianyi Liu, Oct 25, Assignment 14



1.
CountRuns:=proc(L,k) local i,n,N,a,j:
n:=nops(L):
N:=0:
for i from 1 to n-k+1 do
 a:=1:
 for j from i to i+k-2 do
  if L[j]<>L[j+1] then
   a:=0:
  fi:
 od:
N:=N+a: 
od:

N:
end:

2.
AvePathRuns:=proc(m,n,k,N) local i,rp,a,sumx,x2,sumx2,var,std,u:
sumx:=0:
sumx2:=0:
for i from 1 to N do
 rp:=RPath(m,n):
 a:=CountRuns(rp,k):
 sumx:=sumx+a:
 x2:=a^2:
 sumx2:=sumx2+x2:
od:
u:=sumx/N:
var:=sumx2/N-u^2:
std:=sqrt(var):

[u,std]:
end:

They are close to each other.

3.
AveGPathRuns:=proc(m,n,k,N) local i,rp,a,sumx,x2,sumx2,var,std,u:
sumx:=0:
sumx2:=0:
for i from 1 to N do
 rp:=RGPath(m,n):
 a:=CountRuns(rp,k):
 sumx:=sumx+a:
 x2:=a^2:
 sumx2:=sumx2+x2:
od:
u:=sumx/N:
var:=sumx2/N-u^2:
std:=sqrt(var):

[u,std]:
end:


4.
CountMaximalRuns:=proc(L,k) local i,n,N,a,j:
n:=nops(L):
N:=0:
for i from 2 to n-k do
 a:=0:
 if L[i-1]<>L[i] then
  if L[i]<>L[i+k] then 
   a:=1:
   for j from i to i+k-2 do
    if L[j]<>L[j+1] then
     a:=0:
    fi:
   od:
  fi:
 fi:
N:=N+a: 
od:

N:
end:


AvePathMaximalRuns:=proc(m,n,k,N) local i,rp,a,sumx,x2,sumx2,var,std,u:
sumx:=0:
sumx2:=0:
for i from 1 to N do
 rp:=RPath(m,n):
 a:=CountMaximalRuns(rp,k):
 sumx:=sumx+a:
 x2:=a^2:
 sumx2:=sumx2+x2:
od:
u:=sumx/N:
var:=sumx2/N-u^2:
std:=sqrt(var):

[u,std]:
end:


AveGPathMaximalRuns:=proc(m,n,k,N) local i,rp,a,sumx,x2,sumx2,var,std,u:
sumx:=0:
sumx2:=0:
for i from 1 to N do
 rp:=RGPath(m,n):
 a:=CountMaximalRuns(rp,k):
 sumx:=sumx+a:
 x2:=a^2:
 sumx2:=sumx2+x2:
od:
u:=sumx/N:
var:=sumx2/N-u^2:
std:=sqrt(var):

[u,std]:
end:


5.
Dyckcheck:=proc(L) local l,c,i,n:
n:=nops(L):
l:=0:
c:=1:

for i from 1 to n do
 if L[i]=-1 then
  l:=l+1:
 fi:
 if l>i/2 then
  c:=0:
 fi:
od:

c:
end:

GoodBrother:=proc(L) local n,l,i,j,k,n1,S,s,S1,lf,tf:
n:=nops(L):
l:=0:
for j from 1 to n do
 l:=l+L[j]:
od:
if l<>1 then
 RETURN(false):
fi:

if type(n,odd)=false then
 RETURN(false):
fi:

n1:=0:
for i from 1 to n do
 if L[i]=1 then
  n1:=n1+1:
 fi:
od:

if n1+n1-1<>n then
 RETURN(false):
fi:

S:=CycShi(L):
s:=nops(S):
for k from 1 to s do
 if S[k][n]=1 then
  S1:=[op(1..n-1,S[k])]:
  tf:=Dyckcheck(S1):
  if tf=1 then
  lf:=S1:
  fi:
 fi:
od:

[op(lf),1]:
end:


6.
Consider a word L in {1,-1} that adds up to 1, if there are two cyclic shifts of L are identical, then it means there is a
pattern in L that makes two shifts the same. So we assume it as a sub word w repeated k times in L, then k*sum of w= sum of L.
Since w is in {1,-1}, sum of w can only be an integer. To make the equation valid is only when k=1. Therefore, sum of w=sum of L.
All cyclic shifts are distinct.