#OK to post homework
#William Wang, 10/21/2020, Assignment 14

#1.
CountRuns := proc(L, k) local total, count, val, i:
total := 0:
count := 1:
val := L[1]:
for i from 2 to nops(L) do
 if val = L[i] then
  ++count:
 elif k <= count then
  total := total + count - k + 1:
  val := L[i]:
  count := 1:
 else
  val := L[i]:
  count := 1:
 fi:
od:
if k <= count then
 total := total + count - k + 1:
fi:
total:
end:

CountRuns([1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2], 3);
                               4

CountRuns([1, 1, 1, 2, 2, 2, 2, 3, 3], 3);
                               3



#2.
with(Statistics):
AvePathRuns := proc(m, n, k, N) local S, i:
S := [seq(CountRuns(RPath(m, n), k), i = 1 .. N)]:
[Mean(S), StandardDeviation(S)]:
end:

[seq(AvePathRuns(200, 200, 5, 3000), i = 1 .. 10)];
            [[24.0556666666667, 7.35630837987929], 

              [24.2436666666667, 7.47651384728594], 

              [24.0573333333333, 7.44883936987556], 

              [24.3406666666667, 7.59792882280126], 

              [24.1946666666667, 7.45036515005665], 

              [23.9220000000000, 7.52684974977704], 

              [24.1956666666667, 7.47529316425245], 

              [24.0396666666667, 7.47016472437023], 

              [24.0170000000000, 7.49951944664747], 

              [24.1816666666667, 7.43812963585036]]



#3.
AvePathGRuns := proc(m, n, k, N) local S, i:
S := [seq(CountRuns(RGPath(m, n), k), i = 1 .. N)]:
[Mean(S), StandardDeviation(S)]:
end:

[seq(AvePathGRuns(200, 200, 5, 3000), i = 1 .. 10)];
            [[24.0823333333333, 7.34340042025033], 

              [24.1623333333333, 7.31362729911173], 

              [24.0916666666667, 7.46618009229701], 

              [24.2600000000000, 7.46719400637054], 

              [23.9516666666667, 7.46917622097839], 

              [24.3683333333333, 7.35051067781214], 

              [24.2653333333333, 7.66393133472567], 

              [23.7916666666667, 7.45927682995013], 

              [24.2123333333333, 7.51687539434573], 

              [23.9690000000000, 7.42803905851010]]



#4.
CountMaximalRuns := proc(L, k) local total, count, val, i:
total := 0:
count := 1:
val := L[1]:
for i from 2 to nops(L) do
 if val = L[i] then
  ++count:
 elif count = k then
  total := total + count - k + 1:
  val := L[i]:
  count := 1:
 else
  val := L[i]:
  count := 1:
 fi:
od:
if count = k then
 total := total + count - k + 1:
fi:
total:
end:

AvePathMaximalRuns := proc(m, n, k, N) local S, i:
S := [seq(CountMaximalRuns(RPath(m, n), k), i = 1 .. N)]:
[Mean(S), StandardDeviation(S)]:
end:

AveGPathMaximalRuns := proc(m, n, k, N) local S, i:
S := [seq(CountMaximalRuns(RGPath(m, n), k), i = 1 .. N)]:
[Mean(S), StandardDeviation(S)]:
end:

[seq(AvePathMaximalRuns(200, 200, 5, 3000), i = 1 .. 10)];
            [[6.19866666666667, 2.33359810498596], 

              [6.18433333333333, 2.38807918551451], 

              [6.23533333333333, 2.36315037935818], 

              [6.22966666666667, 2.31978023722189], 

              [6.13800000000000, 2.30970436306213], 

              [6.18400000000000, 2.35329343615826], 

              [6.14800000000000, 2.37261580720300], 

              [6.19666666666667, 2.39023568526187], 

              [6.23666666666667, 2.41314386433802], 

              [6.17966666666667, 2.39066761654002]]


[seq(AveGPathMaximalRuns(200, 200, 5, 3000), i = 1 .. 10)];
            [[6.26033333333333, 2.37538222239209], 

              [6.20633333333333, 2.34512112407534], 

              [6.23133333333333, 2.39173403331508], 

              [6.23166666666667, 2.34815569485458], 

              [6.17100000000000, 2.37914111340188], 

              [6.22766666666667, 2.31623751105640], 

              [6.11066666666667, 2.33300246943640], 

              [6.19366666666667, 2.36135947321512], 

              [6.24566666666667, 2.32904616547258], 

              [6.27166666666667, 2.33702470041982]]



#5.
ListSum := proc(L) local sum, tf, i:
sum := 0:
tf := true:
for i to nops(L) do
 if tf = false then
  break:
 fi:
 if L[i] = 1 then
  ++sum:
 else
  --sum:
 fi:
 if sum < 0 then
  tf := false:
 fi:
od:
if tf = false then
 RETURN(false):
elif tf = true then
 RETURN(true):
fi:
end:

GoodBrother := proc(L) local S, s, T:
S := CycShi(L):
T : []:
for s in S do
 if ListSum(s) = true and s[nops(s)] = 1 then
  T := [op(T), s]:
 fi:
od:
T := op([op(2 .. nops(T), T)]):
end:

GoodBrother([1, -1, -1, 1, 1, 1, 1, -1, -1, -1, 1]);
             [1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1]



#6.
#Let L be some cyclic shift of a word in {1,-1} that adds up to 1.
#If nops(L) = 1, then L must be [1]
#If nops(L) = 3, then L must be [1,1,-1],[1,-1,1], or [-1,1,1].
#The above for the case where nops(L) = 3, it is very apparent that all of them are identical cyclic shifts
#If induction is used on L of greater lengths, then there is a word w in L that is repeated k times, but k must be 1.