#OK to post homework 
#Zhizhang Deng, 10/26/2020, Assignment 14

1. 
    CountRuns := proc(L, k) local i, n, counter: 
        n := nops(L);
        counter := 0;
        for i from 1 to n - k + 1 by 1 do
            if nops({op(i..i + k - 1, L)}) = 1 then
                counter := counter + 1; 
            end if; 
        end do;
        return counter;
    end:

2.
    AvePathRuns := proc(m, n, k, N) local sum_, sum_square_, i, tmp, avg, var: 
        sum_ := 0; 
        sum_square_ := 0;
        var := 0; 
        # first pass to calculate sum_ and remember result 
        for i from 1 to N by 1 do
            tmp := CountRuns(RPath(m, n), k); 
            sum_ := sum_ + tmp; 
            sum_square_ := sum_square_ + tmp ^ 2; 
        end do;
        # second pass to calculate variance 
        avg := sum_ / N; 
        var := sum_square_ - sum_ ^ 2 / N;   # calculate variance 
        var := var / (N - 1);
        return [evalf(avg), evalf(sqrt(var))]; 
    end:

    seq(AvePathRuns(200, 200, 5, 3000), i = 1 .. 10) = [24.20533333, 7.509281014], [23.98700000, 7.535853901], [24.01266667, 7.428205186], [24.01933333, 7.348579916], [24.26700000, 7.512158270], [24.06700000, 7.445154205], [24.27000000, 7.540825862], [24.19800000, 7.482877819], [23.94633333, 7.551189313], [24.19966667, 7.446449921]

    Between each run, the result are pretty close. 

3. 
    AveGPathRuns := proc(m, n, k, N) local sum_, sum_square_, i, tmp, avg, var: 
        sum_ := 0; 
        sum_square_ := 0;
        var := 0; 
        # first pass to calculate sum_ and remember result 
        for i from 1 to N by 1 do
            tmp := CountRuns(RGPath(m, n), k); 
            sum_ := sum_ + tmp; 
            sum_square_ := sum_square_ + tmp ^ 2; 
        end do;
        # second pass to calculate variance 
        avg := sum_ / N; 
        var := sum_square_ - sum_ ^ 2 / N;   # calculate variance 
        var := var / (N - 1);
        return [evalf(avg), evalf(sqrt(var))]; 
    end:
    seq(AveGPathRuns(200, 200, 5, 3000), i = 1 .. 10) = [24.31933333, 7.467302932], [24.00800000, 7.438753101], [24.26000000, 7.521563975], [24.10966667, 7.518054732], [24.20533333, 7.524806473], [24.02633333, 7.343587859], [24.07166667, 7.325600228], [24.23433333, 7.305469038], [23.98533333, 7.497011849], [24.32433333, 7.495678952]. 
    Between runes, the results are similar. 

4. 
    CountMaximalRuns := proc(L, k) local i, n, counter: 
        n := nops(L);
        counter := 0;
        for i from 2 to n - k by 1 do
            if nops({op(i..i + k - 1, L)}) = 1 and L[i - 1] != L[i] and L[i + k] != L[i] then
                counter := counter + 1; 
            end if; 
        end do;
        return counter;
    end:

    AvePathMaximalRuns := proc(m, n, k, N) local sum_, sum_square_, i, tmp, avg, var: 
        sum_ := 0; 
        sum_square_ := 0;
        var := 0; 
        # first pass to calculate sum_ and remember result 
        for i from 1 to N by 1 do
            tmp := CountMaximalRuns(RPath(m, n), k); 
            sum_ := sum_ + tmp; 
            sum_square_ := sum_square_ + tmp ^ 2; 
        end do;
        # second pass to calculate variance 
        avg := sum_ / N; 
        var := sum_square_ - sum_ ^ 2 / N;   # calculate variance 
        var := var / (N - 1);
        return [evalf(avg), evalf(sqrt(var))]; 
    end:

    AvePathMaximalRuns := proc(m, n, k, N) local sum_, sum_square_, i, tmp, avg, var: 
        sum_ := 0; 
        sum_square_ := 0;
        var := 0; 
        # first pass to calculate sum_ and remember result 
        for i from 1 to N by 1 do
            tmp := CountMaximalRuns(RPath(m, n), k); 
            sum_ := sum_ + tmp; 
            sum_square_ := sum_square_ + tmp ^ 2; 
        end do;
        # second pass to calculate variance 
        avg := sum_ / N; 
        var := sum_square_ - sum_ ^ 2 / N;   # calculate variance 
        var := var / (N - 1);
        return [evalf(avg), evalf(sqrt(var))]; 
    end:

    AveGPathMaximalRuns := proc(m, n, k, N) local sum_, sum_square_, i, tmp, avg, var: 
        sum_ := 0; 
        sum_square_ := 0;
        var := 0; 
        # first pass to calculate sum_ and remember result 
        for i from 1 to N by 1 do
            tmp := CountMaximalRuns(RGPath(m, n), k); 
            sum_ := sum_ + tmp; 
            sum_square_ := sum_square_ + tmp ^ 2; 
        end do;
        # second pass to calculate variance 
        avg := sum_ / N; 
        var := sum_square_ - sum_ ^ 2 / N;   # calculate variance 
        var := var / (N - 1);
        return [evalf(avg), evalf(sqrt(var))]; 
    end:

    seq(AvePathMaximalRuns(200, 200, 5, 3000), i = 1..10) = [6.172333333, 2.331332865], [6.136333333, 2.341845704], [6.086333333, 2.326947525], [6.144333333, 2.325791118], [6.155333333, 2.335313567], [6.194333333, 2.342875208], [6.070666667, 2.273777234], [6.089666667, 2.328254027], [6.163000000, 2.356328025], [6.210000000, 2.374822082]

    seq(AveGPathMaximalRuns(200, 200, 5, 3000), i = 1..10) = 

5. 
    GoodBrother := proc(L) local shifts, n, x, y, good, i, j:
        shifts := CycShi(L); 
        n := nops(shifts);
        for i from 1 to n by 1 do
            # check every possible shift 
            if shifts[i][n] != 1 then
                next;   # not possible, this is not ending with 1
            end if; 

            # check validity of this shift
            x := 0;
            y := 0;
            good := true; 

            for j from 1 to n - 1 do
                # start from 0, 0 check every step that x >= y. 
                if shifts[i][j] = 1 then
                    x := x + 1; 
                else
                    y := y + 1; 
                end if; 

                if x < y then:  
                    good := false;
                    break; 
                end if; 
            end do; 

            if good then
                return shifts[i]; 
            end if;
        end do;
    end: 

6. 
    If cyclic shifts of a word L are not distinct. Then that means L has to be of some other word W repeated. Assume this W is repeated k times. 
    Then the sum of K = k * sum of W. Since sum of K = 1, then sum of W = 1 / k. Because we only have 1 and -1 in our dictionary, so sum of W has to be integer. 1 / k is only integer when k = 1 for k >= 0. And this is a contradiction, thus cyclic shifts of L are distinct.