#its ok to post
#TaerimKim,10/23/2020,Assignment 14

#1.Using the hint given, we can evaluate 
#valid "run" by assessing i from 1 to nops(L)-k+1,
#and see if it satisfies the condition (nops({op(i..i+k-1,L)})=1)

CountRuns := proc(L, k) local a, l, i; 
a := 0; #number of runs
l := nops(L); 

for i to l - k + 1 do 
if nops({op(i .. i + k - 1, L)}) = 1 then 
a++; 
fi; 
od; 

a; 
end proc

#lets see if it is correct with professor's example
CountRuns([1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2], 3)
4

#true

#################################################################

#2.

AvePathRuns:=proc(m,n,k,N) local(A, i, C, c) ;
A:={};
for i from 1 to N do
C := RPath(m, n);
c := CountRuns(C, k);
A := [op(A), c];
od;

[Statistics[Mean](A), Statistics[StandardDeviation](A)];

end;

#now try 10 times of AvePathRuns(200,200,5,3000)

#1.[24.3406666666667, 7.60972506253662]
#2.[24.1710000000000, 7.46272893167791]
#3.[23.9493333333333, 7.51577863775489]
#4.[24.0353333333333, 7.35931188219039]
#5.[24.1853333333333, 7.47459752037433]
#6.[24.1776666666667, 7.38473285334868]
#7.[24.0493333333333, 7.54594018617428]
#8.[24.2293333333333, 7.43100348718110]
#9.[24.1273333333333, 7.57017538815039]
#10.[23.9853333333333, 7.47937822204616]

#this took me 2hours to compile....
#Comparing the numbers, they are roughly similar. mean as 24, standard, dev. as 7.5
####################################################################

#3. Samething only with changing 'RPath' into 'GPaths'


AveGPathRuns:=proc(m,n,k,N) local A, i, C, c ;
A:={};
for i from 1 to N do
C := GPaths(m, n);
c := CountRuns(C, k);
A := [op(A), c];
od;

[Statistics[Mean](A), Statistics[StandardDeviation](A)];

end;

#now try 10 times of AveGPathRuns(200,200,5,3000)

seq(AveGPathRuns(200,200,5,3000),i=1..10)
#this seq would end up in error since computer is heavily overloaded
#So I had to only do 3 trials

#1.[24.0733333333333, 7.35549613078539]
#2.[24.1710000000000, 7.46272893167791]
#3.[24.0086666666667, 7.64740168116247]

#This is also similar result with all paths but it is ok because we have seen in the lecture that at large counters, Good path and all path shows similarity.
#so this is true even with just 3 trials

#################################################################

#4. Also using the given hints, 'CountMaximalRuns' is a #1 with few more conditions on if.
#maximal runs have to satisfy 3 condition; 
#1) L[i - 1] <> L[i]
#2) L[i + k] <> L[i]
#3) nops({op(i .. i + k - 1, L)}) = 1

CountMaximalRuns := proc(L, k) local a, l, i; 
a := 0; #number of runs
l := nops(L); 

for i to l - k + 1 do

#here we know that L[i-1] does not exist for i=1 so we isolate when i=1 and compare only condition 2,3 
if i = 1 then
if L[i + k] <> L[i] and nops({op(i .. i + k - 1, L)}) = 1 then 
a++; 
next; 
fi;
fi;

#here we are comparing all 3 condition for maximal runs
if i>1 and i<l-k+1 then  
if L[i-1]<>L[i] and L[i+k]<>L[i] and nops({op(i .. i + k - 1, L)}) = 1 then   
a++;   
next;
fi;
fi;

#for i=l-k+1 we know that L[l+k] does not exist so for this case we only compare the condition 1,3
if i = l - k + 1 then
if L[i - 1] <> L[i] and nops({op(i .. i + k - 1, L)}) = 1 then 
a++; 
next; 
fi;
fi;

a;
 
end;

#lets test this out with [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] and by hand we know there is 3 runs of maximal length 5

CountMaximalRuns([1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4], 5);
                               3
#true, so this proc is good




#also AvePath and AveGPath is just a copy and paste of #2 & #3 with a change from 'CountRuns' to 'CountMaximalRuns'


AvePathMaximalRuns:=proc(m,n,k,N) ;
A:={};
for i from 1 to N do
C := RPath(m, n);
c := CountMaximalRuns(C, k);
A := [op(A), c];
od;

[Statistics[Mean](A), Statistics[StandardDeviation](A)]

end;
#doing 3 times of check
seq(AvePathMaximalRuns(200,200,5,3000),i=1..3)
[6.14933333333333, 2.27905629331197],[6.19066666666667,2.39643356960019],[6.150666667, 2.367241890]
#here mean converges to 6.16 and standard deviation of 2.3



AveGPathMaximalRuns:=proc(m,n,k,N) ;
A:={};
for i from 1 to N do
C := GPaths(m, n);
c := CountMaximalRuns(C, k);
A := [op(A), c];
od;

[Statistics[Mean](A), Statistics[StandardDeviation](A)]

end;

#doing 3 times of check
#just a prediction before an hour of compiling we will know that AveGPathMaximalRuns will also generate about 6.16 as mean and std as 2.3
#same as the AvePathMaximalRuns
seq(AveGPathMaximalRuns(200,200,5,3000),i=1..3)
[6.159000000, 2.422603696],[6.23066666666667,2.33465409832131],[6.22433333333333, 2.33762615793037]
#just like the prediction, we have the anticipated result after an hour of wait...


############################################################################

#5. 

GoodBrother:=proc(L) local a, s, l, i, b, j, S;
option remember:
l:=nops(L);
a:=add(L[i],i=1..l);

#this is 2 condition for good input of set
if l mod 2 = 0 then
printf("this is not odd set");
fi;

if a<>1 then
printf("the sum of the set is not 1");
fi;

#initiating all possible cycles.
S:= CycShi(L);

for i from 1 to l do #lets evaluate each cycles
s:=S[i];
b:=0;

#we want our target cycle to remain positive till the very end, 
#so for statement with j will be our main evaluating method
for j from 1 to l do
b:=b+s[j];
if b<0 then
break;
fi;
od;

#`even though a cycle has passed, we want to have '1' as the last element, so this is another evalution`

if s[l] = -1 then
    next;
fi;

#if a cycle has passed every condition, that's our cycle. otherwise, do the for loop again
if b>=0 then
break;
fi;
od;

return(s);

end;

#let's check
GoodBrother([1, -1, -1, 1, 1, 1, 1, -1, -1, -1, 1])
[1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1]

#gooooddd

##########################################################################

#6

#to think this very simple, let's see the hint given
#Sum of L = 1 = k * Sum of W -> for this to happen Sum of w can never be a fraction with given -1 or 1
#So. there is no way that k can be greater than 1 and it has to be 1 for all cases.
#So, that means since k=1, there are no identical cycles that adds up to 1
#meaning, every cycle that adds up to 1 are distinct Q.E.D