#OK to post homework
#Hari Amoor, October 25, HW #14

# Question 1

CountRuns := proc(L, k) local i, count, ans; 
ans := 0; 
count := 0; 
for i from 2 to nops(L) do 
    if L[i] = L[i - 1] then count := count + 1: fi: 
    if L[i] <> L[i - 1] and k <= count then ans := ans + count - k + 1: count := 1: fi:
    if L[i] <> L[i - 1] and count < k then count := 1: fi:
od:
if k <= count then ans := ans + count - k + 1: fi:
ans:
end:


# Question 2

with(Statistics);
AvePathRuns := proc(m, n, k, N) local i, total, currL, runs, path:
currL := []:
for i to N do 
  path := RPath(m, n):
  runs := CountRuns(path, k): 
  currL := [op(currL), runs]: 
od:
print(StandardDeviation(currL)):
print(Mean(currL)):
end:

#Standard Deviation: 7.48732098600057
#Mean: 24.0933333333333

#Standard Deviation: 7.61013518986958
#Mean: 24.3273333333333

# ...

# The results for each of the 10 computations are trivially close.

# Question 3
with(Statistics):
AveGPathRuns := proc(m, n, k, N) local i, ans, total, currL, runs, path:
currL := []; 
for i to N do 
   path := RGPath(m, n):
   runs := CountRuns(path, k): 
   currL := [op(currL), runs]:
od: 
print(StandardDeviation(currL)): 
print(Mean(currL)): 
end proc:

#Standard Deviation: 7.64740168116247
#Mean: 24.0086666666667

#Standard Deviation: 7.51583696393309
#Mean: 23.9680000000000

# ...

# The results for each of the 10 computations are trivially close.


# Question 4

CountMaximalRuns := proc(L, k) local i, count, ans:
ans := 0:
count := 0:
for i from 2 to nops(L) do 
   if L[i] = L[i - 1] then count := count + 1: 
   elif L[i] <> L[i - 1] and k < count then count := 1: 
   elif L[i] <> L[i - 1] and count = k then ans := ans + 1: count := 1: 
   elif L[i] <> L[i - 1] and count < k then count := 1: fi:
od:
if count = k then ans := ans + 1: fi:
ans:
end:

with(Statistics):

AvePathMaximalRuns := proc(m, n, k, N) local i, ans, total, currL, runs, path:
currL := []: 
for i to N do 
  path := RPath(m, n):
  runs := CountMaximalRuns(path, k):
  currL := [op(currL), runs]:
od:
print(StandardDeviation(currL)):
print(Mean(currL)):
end:

# Standard Deviation: 2.38129273167193
# Mean: 6.16533333333333

# Standard Deviation: 2.39643356960019
# Mean: 6.19066666666667

# ...
# The results for each of the computations are trivially close.

with(Statistics);
AveGPathMaximalRuns := proc(m, n, k, N) local i, ans, total, currL, runs, path:
currL := []:
for i to N do 
   path := RGPath(m, n):
   runs := CountMaximalRuns(path, k): 
   currL := [op(currL), runs]:
od:
print(StandardDeviation(currL)):
print(Mean(currL)): 
end:

# Standard Deviation: 2.36087472462588
# Mean: 6.15533333333333

# Standard Deviation: 2.33465409832131
# Mean: 6.23066666666667
# ...
# The results for each of the computations are trivially close.

# Question 5

check := proc(L) local j, curr, ans:
curr := 0:
for j to nops(L) - 1 do
   curr := curr + L[j]:
   if curr < 0 then return false: fi:
od:
if curr = 0 then return true: fi:
return false:
end:

GoodBrother := proc(L) local i, set, curr, ans:
for i to nops(L) do 
  set := [op(i .. nops(L), L), op(1 .. i - 1, L)]:
  if check(set) = true then return set: fi:
od:
return L:
end:


# Question 6

# Spse. there is a repeated cyclic shift. Then there must be a repeated word w within Lk times, with k >= 1.
# It follows from this that the sum(L) = k*sum(w). Thus, since the shifts are all distinct and cyclic, then k=1.

# In order for sum(w) * k = 1, each sum(w) and k also have to equal 1. However, if k=1, then sum(w) must be fractional; this is a contradiction.
# Thus, the claim holds.