> #ok to post
;
> #Yifan Zhang, 10/24/2020 
;
> 
;
> #Q1.
;
> #Use a procedure
> #CountRuns(L,k)
> 
> #that inputs a list L of numbers (or for that matter, any objects) and outputs the number of "runs" of length k in L
> 
> #[A run of length k is a string L is an occurence of an i such that L[i]=L[i+1]=...=L[i+k-1]
> 
> #For example
> 
> #CountRuns([1,2,2,2,1,1,1,1,2,2,2],3)
> 
> #is 4 for the runs starting at i=2, i=5, i=6, i=9. Note that it can be part of a longer run.
> 
> #[Hint: a quick way to find whether location i is the beginning of a run of length k (where i is between 1 and nops(L)-k+1, is to see if nope({op(i..i+k-1,L)})=1]
> 

;
> CountRuns:=proc(L,k) local i, R:
> option remember: R:=[];
> for i from 1 to (nops(L)-k+1) do
> if nops({op(i..i+k-1, L)})=1 then
> R:=[op(R),i]:
> fi:
> od:
> 
> nops(R):end:
> 
;
> CountRuns([1,2,2,2,1,1,1,1,2,2,2],3)
4

;
> 
;
> 
;
> #Q2. 
;
> #Use the above CountRuns(L,k) that you just wrote, combined with procedure RPath in M14.txt to write a procedure
> #AvePathRuns(m,n,k,N)
> 
> #That inputs positive inetgers m,n,k, and a LARGE positive integer N, generated N random paths, for each of them records the number of runs, and finds the sample average and #standard-deviation (the squre-root of the variance)
> 
> #Run
> 
> #AvePathRuns(200,200,5,3000)
> 
> #ten times and see what you get. Are they close to each other?
;
> NuPaths:=proc(m,n) option remember:
> if m<0 or n<0 then 
> 0:
> elif m=0 and n=0 then
> 1:
> else
> NuPaths(m-1,n)+NuPaths(m,n-1):
> fi:
> end:
> LDie:=proc(A) local N,i,j,r:
> 
> N:=add(A[i],i=1..nops(A)):
> r:=rand(1..N)():
> 
> for i from 1 to nops(A) while add(A[j],j=1..i-1)<r do od:
> i-1:
> 
> end:
> RPath:=proc(m,n) local c:
> if m=0 and n=0 then
>  RETURN([]):
> fi:
> 
> c:=LDie([NuPaths(m-1,n),NuPaths(m,n-1)]):
> 
> if c=1 then
>  [op(RPath(m-1,n)),1]:
> else
>  [op(RPath(m,n-1)),2]:
> fi:
> end:
> 
;
> #AvePathRuns
;
> AvePathRuns:=proc(m,n,k,N) local i, total, ave,varT:
> option remember:
> 
> total:=0:
> 
> for i from 1 to N do
> total:= total+CountRuns(RPath(m,n), k):
> od:
> 
> ave:= (total/N):
> varT:=0:
> for i from 1 to N do
> 
> varT:=varT+(CountRuns(RPath(m,n), k)-ave)^2:
> od:
> 
> RETURN((varT/N)^(0.5), ave):
> 
> end:
> AvePathRuns(200,200,5,401)
7.381216293, 9613/401

;
> AvePathRuns(200,200,5,300)
7.164886601, 1203/50

;
> AvePathRuns(200,200,5,500)
7.408724587, 241/10

;
> AvePathRuns(200,200,5,499)
7.694246742, 12204/499

;
> AvePathRuns(200,200,5,200)
7.205713011, 2469/100

;
> AvePathRuns(200,200,5,450)
7.641169841, 5557/225

;
> AvePathRuns(200,200,5,350)
7.836567866, 8349/350

;
> AvePathRuns(200,200,5,150)
7.541614917, 3577/150

;
> AvePathRuns(200,200,5,301)
7.397004558, 7185/301

;
> #Maple might has temporary memory, so if I run 10 times exactly same command, it will not run the command actually. 
;
> #The average number of runs is nearly same with a number of 24. And the SD is nearly between 7.3-7.8.
;
> 
;
> 
;
> #Q3. 
;
> #Do the analogous thing for Good paths, writing
> #AveGPathRuns(m,n,k,N)
> 
> #[Hint: you only have to change one word in the code]
> 
> #Run
> 
> #AvePathGRuns(200,200,5,3000)
> 
> #ten times. How does it compare with the previous output for all paths?
;
> NuGPaths:=proc(m,n) option remember:
> if (m<0 or n<0 or m<n)  then 
> 0:
> elif m=0 and n=0 then
> 1:
> else
> NuGPaths(m-1,n)+NuGPaths(m,n-1):
> fi:
> end:
> RGPath:=proc(m,n) local c:
> if m=0 and n=0 then
>  RETURN([]):
> fi:
> 
> c:=LDie([NuGPaths(m-1,n),NuGPaths(m,n-1)]):
> 
> if c=1 then
>  [op(RGPath(m-1,n)),1]:
> else
>  [op(RGPath(m,n-1)),2]:
> fi:
> end:
> AvePathGRuns:=proc(m,n,k,N) local i, total, ave,varT:
> option remember:
> 
> total:=0:
> 
> for i from 1 to N do
> total:= total+CountRuns(RGPath(m,n), k):
> od:
> 
> ave:= (total/N):
> varT:=0:
> for i from 1 to N do
> 
> varT:=varT+(CountRuns(RGPath(m,n), k)-ave)^2:
> od:
> 
> RETURN((varT/N)^(0.5), ave):
> 
> end:
> 
;
> 
;
> AvePathGRuns(200,200,5,100)
7.071230445, 2421/100

;
> AvePathGRuns(200,200,5,200)
7.867942870, 4873/200

;
> AvePathGRuns(200,200,5,300)
7.613438411, 1837/75

;
> AvePathGRuns(200,200,5,400)
7.672803024, 9827/400

;
> AvePathGRuns(200,200,5,500)
7.831842440, 12149/500

;
> #The output is similar to AvePathRuns. 
;
> 
;
> 
;
> #Q4. 
;
> #A maximal run is a run L[i]=L[i+1]=...L[i+k-1] AND L[i-1]<> L[i] and L[i+k]<>L[i]
> #[Hint: a quick way to find whether location i is the beginning of a MAXIMAL run of length k (where i is between 1 and nops(L)-k+1, is to see if nope({op(i..i+k-1,L)})=1 and L[i-1]<>L#[i] and L[i+k]<>L[i]]
> 
> #Write procedures
> 
> #CountMaximalRuns(L,k), AvePathMaximalRuns(m,n,k,N), and AveGPathMaximalRuns(m,n,k,N)
> 
> #and do the analogous thing for the above two problems, (that you did for Runs) for Maximal Runs.
;
> CountMaximalRuns:=proc(L,k) local i, R:
> option remember:
> R:=[]:
> for i from 1 to (nops(L)-k+1) do
> if i=1 then 
>     if nops({op(i..i+k-1, L)})=1 and L[i+k]<>L[i] then 
>     R:=[op(R), i]:
>     fi:fi:
> if i=(nops(L)-k+1) then
>     if nops({op(i..i+k-1,L)})=1 and L[i]<>L[i-1] then
>     R:=[op(R), i]:
>     fi:fi:
> if i<>1 and i<>(nops(L)-k+1) and nops({op(i..i+k-1,L)})=1 and L[i+k]<>L[i] and L[i]<>L[i-1] then
>     R:=[op(R), i]:
> fi:
> od:
> nops(R):
> end:
> 
> 
;
> CountMaximalRuns([1,2,2,2,2,3,3,3,3],4)
2

;
> 
;
> AvePathMaximalRuns:=proc(m,n,k,N) local i, total, ave, varT:
> option remember:
> total:=0:
> 
> for i from 1 to N do
> total:=total+CountMaximalRuns(RPath(m,n),k):
> od:
> ave:=(total/N):
> varT:=0:
> for i from 1 to N do
> varT:=varT+(CountMaximalRuns(RPath(m,n), k)-ave)^2:
> od:
> RETURN((varT/N)^(0.5), ave);
> end:
> 
;
> AveGPathMaximalRuns:=proc(m,n,k,N) local i, total, ave, varT:
> option remember:
> total:=0:
> 
> for i from 1 to N do
> total:=total+CountMaximalRuns(RGPath(m,n),k):
> od:
> ave:=(total/N):
> varT:=0:
> for i from 1 to N do
> varT:=varT+(CountMaximalRuns(RGPath(m,n), k)-ave)^2:
> od:
> RETURN((varT/N)^(0.5), ave);
> end:
> 
;
> AvePathMaximalRuns(200,200,5,100)
2.438606159, 317/50

;
> AvePathMaximalRuns(200,200,5,200)
2.354076252, 1231/200

;
> AveGPathMaximalRuns(200,200,5,100)
2.278157150, 6

;
> AveGPathMaximalRuns(200,200,5,200)
2.375184203, 611/100

;
> #The average and SD in my AvePathMaximalRuns and AveGPathMaximalRuns are also similar with SD in a range of 2.3-2.5 and average around to 6.
;
> 
;
> 
;
> 
;
> #Q5.
;
> #Write a procedure
> #GoodBrother(L)
> 
> #that inputs an arbitrary list of ODD length that adds up to 1 (so if the length is 2*n+1 it must have n+1 1's and n -1's), and outputs the UNIQUE cyclic shift that is a so-called Dyck path of length 2*n with 1 appended at the end.
> 
> #For example
> 
> #GoodBrother([[1,-1,-1,1,1,1,1,-1,-1,-1,1]=[1,1,1,-1,-1,-1,1,1,-1,-1,1]
;
> CycShi:=proc(L) local i:
> {seq([op(i..nops(L),L),op(1..i-1,L)],i=1..nops(L))}:
> end:
> GoodBrother:=proc(L) local i, num, r,S:
> S:=CycShi(L): num:=nops(S[1]):
> for i from 1 to nops(S) do
> 
> if S[i][num] =1 then
> r:=S[i]
> fi:
> od:
> 
> r:
> 
> end:
> 
;
> 
;
> 
;
> #Q6
;
> #[Human exercise] Prove that the all the cyclic shifts of a word in {1,-1} that adds up to 1 are distinct.
> #[Hint: if two cyclic shifts of such an L are identical, it means that there is some word w such that L is w repeated k times. The sum of L is k times the sum of w. Show that this can only happen if k=1]
;
> #for example
;
> CycShi([1,-1,1,1,-1,-1,1])
{[-1, -1, 1, 1, -1, 1, 1], [-1, 1, 1, -1, -1, 1, 1], [-1, 1, 1, -1, 1, 1, -1],
[1, -1, -1, 1, 1, -1, 1], [1, -1, 1, 1, -1, -1, 1], [1, 1, -1, -1, 1, 1, -1], [
1, 1, -1, 1, 1, -1, -1]}

;
> #Suppose L equals to one of its cyclic shifts, so L = L1 L1 L1 k times 
;
> #Sum(L)=Sum(L1)*k
;
> #Sum(L1) AND k are integer. And by the lemma, if a*b=1 and a, b are integers, a=1, b=1. 
;
> #so we get k must be 1. 
;
> 
;
> 
;
> 
;