#OK to post homework
#Kent Mei, 10/25/20, Assignment 14

#---------------------------------
#Part 1

CountRuns:=proc(L,k) local n, i, count:

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

for i from 1 to n-k+1 do 
 if nops({op(i..i+k-1,L)}) = 1 then
  count := count + 1:
 fi:
od:

count:

end:



#---------------------------------
#Part 2

#Outputs a list [x,y] where x = the sample mean and y = sample std. deviation.
#Note: Uses Statistics Package to calculate the necessary values.

AvePathRuns:=proc(m,n,k,N) local i, count, counts, mean, stddev:

with(Statistics):

counts := []:

for i from 1 to N do
	count := CountRuns(RPath(m,n),k):
	counts := [op(counts), count]:
od:

mean := Mean(counts):
stddev := StandardDeviation(counts):

[mean, stddev]:

end:


#[23.9700000000000, 7.53520801216499]
#[24.0440000000000, 7.39362016920007]
#[23.9476666666667, 7.31223295620593]
#[24.2886666666667, 7.51466310684820]
#[24.0460000000000, 7.45151387435286]
#[24.2873333333333, 7.58959640209792]
#[24.1713333333333, 7.45742466381175]
#[23.8740000000000, 7.56900834295784]
#[24.3263333333333, 7.46322583084260]
#[24.0270000000000, 7.40706144070612]

#Yes, the values are pretty close to each other.


#---------------------------------
#Part 3

AveGPathRuns:=proc(m,n,k,N) local i, count, counts, mean, stddev:

with(Statistics):

counts := []:

for i from 1 to N do
	count := CountRuns(RGPath(m,n),k):
	counts := [op(counts), count]:
od:

mean := Mean(counts):
stddev := StandardDeviation(counts):

[mean, stddev]:

end:

#[24.0883333333333, 7.44098918125500]
#[24.3016666666667, 7.52016277560617]
#[24.1576666666667, 7.55750266320763]
#[24.0923333333333, 7.47536631807557]
#[24.1116666666667, 7.36486779569768]
#[24.0733333333333, 7.35549613078539]
#[24.1933333333333, 7.38083878358497]
#[24.0673333333333, 7.41919679272889]
#[24.2580000000000, 7.47543064675550]
#[23.9413333333333, 7.47978658059969]

#It is pretty similar to the values for the previous output. There may be a chance that the average number of runs is higher for the set of Good Paths, but not enough trials have been done to decide that conclusively.

#---------------------------------
#Part 4

CountMaximalRuns:=proc(L,k) local n, i, count:

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

for i from 1 to n-k+1 do 

 if i - 1 >= 1 and L[i-1] = L[i] then
 	next:
 fi:
 if i < n - k + 1 and L[i+k] = L[i] then
 	next:
 fi:

 if nops({op(i..i+k-1,L)}) = 1 then
  count := count + 1:
 fi:
od:

count:

end:

#--------

AvePathMaximalRuns:=proc(m,n,k,N) local i, count, counts, mean, stddev:

with(Statistics):

counts := []:

for i from 1 to N do
	count := CountMaximalRuns(RPath(m,n),k):
	counts := [op(counts), count]:
od:

mean := Mean(counts):
stddev := StandardDeviation(counts):

[mean, stddev]:

end:

#[6.18500000000000, 2.36431208964026]
#[6.14166666666667, 2.33511201835550]
#[6.20500000000000, 2.33412175663387]
#[6.22900000000000, 2.35692116098941]
#[6.22000000000000, 2.35558547449303]
#[6.14933333333333, 2.27905629331197]
#[6.14133333333333, 2.33563195183381]
#[6.24400000000000, 2.37367691863025]
#[6.25166666666667, 2.38541973203632]
#[6.25833333333333, 2.37560063598299]

#The values are close together.

#-------

AveGPathMaximalRuns:=proc(m,n,k,N) local i, count, counts, mean, stddev:

with(Statistics):

counts := []:

for i from 1 to N do
	count := CountMaximalRuns(RGPath(m,n),k):
	counts := [op(counts), count]:
od:

mean := Mean(counts):
stddev := StandardDeviation(counts):

[mean, stddev]:

end:

#[6.15800000000000, 2.32927266982424]
#[6.20500000000000, 2.32309576312333]
#[6.29433333333333, 2.33670450668017]
#[6.19633333333333, 2.34285072907668]
#[6.13300000000000, 2.35169892402842]
#[6.16600000000000, 2.38054608578694]
#[6.20966666666667, 2.35631576057696]
#[6.22433333333333, 2.33762615793037]
#[6.21566666666667, 2.33158743968250]
#[6.27100000000000, 2.33353254202898]

#The values seem close to the same as the previous output.


#---------------------------------
#Part 5
#I did it the brute force method O(n^2), there's probably a more efficient method of doing it.
#Uses CycShi(L)


GoodBrother:=proc(L) local n, i, j, cycle, cycles, count:

n := nops(L):

cycles := CycShi(L):

for i from 1 to n do:
	cycle := cycles[i]:
	if cycle[n] = -1 then
		next:
	fi:

	count := 0:
	for j from 1 to n do:
		if count < 0 then
			break:
		fi:

		count := count + cycle[j]:
	od:

	if count >= 0 then
		break:
	fi:
od:

cycle:

end:


#---------------------------------
#Part 6

#We wish to prove that all cyclic shifts of a word in {1,-1} that adds up to 1 are distinct.
#Suppose there are two cyclic shifts in L that are identical.
#That means there is some word w such that L is w repeated k times (k is clearly a positive integer).
#So, we know that the sum of L is k times the sum of w = 1.
#Since our alphabet is only {1,-1}, that means that the sum of w is also an integer. 
#So the only way we know sum of w * k = 1 is only possible when sum of w is 1 and k is 1. 
#Since k = 1, that means that every cyclic shift that adds up to 1 is distinct because no cyclic shift is in the form of a word repeated more than one time.

#---------------------------------
#Part 7

#Optional, did not have time to complete the procedure.