#Not ok to post homework
#Sam Minkin, 10/25, Assignment 14

QUESTION #1:

CountRuns:=proc(L,k) local i,j,n,val,b,c:

n:=nops(L):
c:=0:

for i from 1 to n-k+1 do
	val:=L[i]:
	b:=true:
	b:=nops({seq(L[j],j=i..i+k-1)})=1:
	if b then
		c:=c+1:
	fi:
od:

c:

end:


QUESTION #2:

AvePathRuns:=proc(m,n,k,N) local L,i,s,p,c:

L:=[]:
s:=[]:
p:=0:
c:=0:

for i from 1 to N do
	s:=RPath(m,n):
	c:=CountRuns(s,k):
	p:=p+c:
	L:=[op(L),c]:
od:

[(1/N)*p, kthMomentClever(L,2)]:

end:


QUESTION #3:

AveGPathRuns:=proc(m,n,k,N) local L,i,s,p,c:

L:=[]:
s:=[]:
p:=0:
c:=0:

for i from 1 to N do
	s:=RGPath(m,n):
	c:=CountRuns(s,k):
	p:=p+c:
	L:=[op(L),c]:
od:

[(1/N)*p, kthMomentClever(L,2)]:

end:

Running AvePathGRuns(50,50,5,300) ten times gives us:

[263/50, 26431/2500], [424/75, 71474/5625], [549/100, 127299/10000], [1537/300, 1086131/90000], [533/100, 442633/30000], [79/15, 496/45], [279/50, 95527/7500], [1609/300, 1070819/90000], [519/100, 302017/30000], [1711/300, 1205579/90000]


QUESTION #4:


CountMaximalRuns:=proc(L,k) local i,j,n,val,b,c:

n:=nops(L):
c:=0:

for i from 2 to n-k do
	val:=L[i]:
	b:=true:
	b:=nops({seq(L[j],j=i..i+k-1)})=1 and L[i-1]<>L[i] and L[i+k]<>L[i]:
	if b then
		c:=c+1:
	fi:
od:

c:

end:


AvePathMaximalRuns:=proc(m,n,k,N) local L,i,s,p,c:

L:=[]:
s:=[]:
p:=0:
c:=0:

for i from 1 to N do
	s:=RPath(m,n):
	c:=CountMaximalRuns(s,k):
	p:=p+c:
	L:=[op(L),c]:
od:

[(1/N)*p, kthMomentClever(L,2)]:

end:

Running AvePathMaximalRuns(50,50,5,300) ten times we get:
[139/100, 38137/30000], [147/100, 13691/10000], [73/50, 3421/2500], [71/50, 8777/7500], [141/100, 41057/30000], [141/100, 10419/10000], [433/300, 121211/90000], [217/150, 26561/22500], [101/75, 12673/11250], [451/300, 104699/90000]


AveGPathMaximalRuns:=proc(m,n,k,N) local L,i,s,p,c:

L:=[]:
s:=[]:
p:=0:
c:=0:

for i from 1 to N do
	s:=RGPath(m,n):
	c:=CountMaximalRuns(s,k):
	p:=p+c:
	L:=[op(L),c]:
od:

[(1/N)*p, kthMomentClever(L,2)]:

end:

Running AveGPathMaximalRuns(50,50,5,300) ten times we get:

[199/150, 27749/22500], [97/75, 6416/5625], [69/50, 8917/7500], [383/300, 122411/90000], [383/300, 106211/90000], [391/300, 102419/90000], [4/3, 46/45], [27/20, 1313/1200], [367/300, 106811/90000], [69/50, 9817/7500]


QUESTION #5:

GoodBrother:=proc(L) local i,s,S,n,c,b:

S:={}:
S:=CycShi(L):

for s in S do
	n:=nops(s):
	c:=0:
	b:=true:
	for i from 1 to n do
		c:=c+s[i]:
		if c < 0 then
			b:=false:
		fi:
	od:
	
	if b and s[n]=1 then
		RETURN(s):
	fi:
od:

RETURN([]):

end:

QUESTION #6:

Let L be the set of cyclic shifts of a word in {-1,1} whose elements add up to 1. 
For the sake of contradiction assume that two cyclic shifts in L are identical. Following the hint, this implies that there exists a word w such that L is w repeated k times. The sum of L is k times the sum of w. We want to show that this can only happen if k=1.

Since w is the same k times, when we add w to itself k times we get 1+1+1..+1 k times which is k. But if there are any other elements in the set L, then adding it to the to there k w lists will result in a list whose elements do not add up to k. This implies that there are no other elements in the set L, other than w repeated k times. But this is equivalent to a set with 1 w, so k=1.