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

1. 
    (i). 
        We can formulate this problem by creating a complete graph with degree 10 and removing edges that connect two consonants. Then we can fix the first and the last character of the 100-letter words. Then for every possible pairs of the first and last character, we use a NuPaths or GFt to get how many 99-steps walk are between the first and the last character, then we sum this number up for every possible pairs. And that's gonna be the result. 

        one_one := proc() local G, beg, goal, result, t, tmp:

            result := 0;
            G := [[3, 4, 6], [3, 4, 6], [1, 2, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 5, 6, 7, 8, 9, 10], [3, 4, 6], [1, 2, 3, 4, 5, 7, 8, 9, 10], [3, 4, 6], [3, 4, 6], [3, 4, 6], [3, 4, 6]];

            for beg from 1 to 10 do
                for goal from 1 to 10 do
                    result := result + NuPaths(G, beg, goal, 99):
                end do;
            end do;

            return result;

        end:        

        ==========
        one_one() = 5199283173280955437616266585884442715909693086072936470285076341722275955220

    (ii). 
        Similar as above, but this time we remove edges between vowels from complete graph. 

        one_two := proc() local G, beg, goal, result, t, tmp:

            result := 0;
            G := [[2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 5, 7, 8, 9, 10], [1, 2, 5, 7, 8, 9, 10], [1, 2, 3, 4, 6, 7, 8, 9, 10], [1, 2, 5, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 10], [1, 2, 3, 4, 5, 6, 7, 8, 9]];

            for beg from 1 to 10 do
                for goal from 1 to 10 do
                    result := result + NuPaths(G, beg, goal, 99):
                end do;
            end do;

            return result;

        end:
        ======================
        one_two() = 783515768268526573772156204992554998900693123006070632082209531592152300643025269949784955744

    (iii). 
        Similar to above, but this time we remove both edges between vowels and between consonants at the same time from complete graph K10. 

        one_three := proc() local G, beg, goal, result, t, tmp:

            result := 0;
            G := [[3, 4, 6], [3, 4, 6], [1, 2, 5, 7, 8, 9, 10], [1, 2, 5, 7, 8, 9, 10], [3, 4, 6], [1, 2, 5, 7, 8, 9, 10], [3, 4, 6], [3, 4, 6], [3, 4, 6], [3, 4, 6]];

            for beg from 1 to 10 do
                for goal from 1 to 10 do
                    result := result + NuPaths(G, beg, goal, 99):
                end do;
            end do;

            return result;

        end:
        ========================
        one_three() = 2582228870101438052772912951293257333108178445822374648987674582002

    (iv). 
        The graph is exactly the same as part (iii). However we need to modify the procedure so that it can use the GFt. 
        The following procedure will return the LIST OF POLYNOMIALS that contain the generating functions of number of words that satisfy the condition with length n. 

        one_four := proc(t) local G, beg, goal, result, tmp:

            result := [];
            G := [[3, 4, 6], [3, 4, 6], [1, 2, 5, 7, 8, 9, 10], [1, 2, 5, 7, 8, 9, 10], [3, 4, 6], [1, 2, 5, 7, 8, 9, 10], [3, 4, 6], [3, 4, 6], [3, 4, 6], [3, 4, 6]];

            for beg from 1 to 10 do
                tmp := GFt(G, beg, t):
                for goal from 1 to 10 do
                    result :=  [op(result), tmp[goal]]
                end do;
            end do;

            return result;

        end:
        ==============================
        NOTE THAT The result of this is that a(n) = sum_i=1 to 100(coeff(taylor(one_four(t)[i], t, n + 1), t, n))
        Observe that a(n)*t^n is actually the nth term of the sum of the nth term of the individual taylor expansion which means that a(n)*t^n = sum_i=1 to 100(op(n, taylor(one_four(t))[i], t, n + 1)) for a given n.     <- statement 1
        The question is asking f(t) = sum_n=0 to infinity(a(n)*t^n). 
        By using statement 1, we can switch sum place, so the question is equal to sum_i=1 to 100(sum_n=0 to infinity(nth term of taylor expansion of one_four(t)[i]))
        Observe that the inner sum is actually equal to the generating function itself which is one_four(t)[i]. 
        So the answer to the question is actually sum_i=1 to 100(one_four(t)[i]) which is the polynomial sum of one_four(t)'s result. 

        So the final result is 
        ans := one_four(t):
        simplify(add(ans[i], i = 1 .. nops(ans)))   # note nops(ans) = 100
        = (-42*t - 10)/(21*t^2 - 1)

2. 
    We can formulate this problem as a graph path finding problem.
    For each object (farmer, wolf, sheep, cabbage) we assign two number (NOT VERTEX). One number represent this object is on the left side, the other number represent this object is on the right side. 
    Number assign as follows:
    OBJECT      LEFT        RIGHT 
    farmer      1           2
    wolf        3           4
    sheep       5           6
    cabbage     7           8

    Each vertex in our graph represent a state. Each vertex is composed with 4 number. For example (2,4,6,8) means at current state, farmer is on the right, wolf is on the right, sheep is on the right and cabbage is on the right. 
    By doing 2^4 we can find out that we have 16 possible vertex in our graph. We then remove some vertex from these 16 by checking if the state is valid by checking if wolf and sheep is together without farmer or if sheep and cabbage is together without farmer. After this, we then add edges in our graph. An edge will only be added if a state can transit to another state. This is defined by we have to change farmer from 1 to 2 or 2 to 1 and/or change one of the other three object's value. 

    After formulating the graph, we can then try to find path from state (1,3,5,7) to state (2,4,6,8). And that path would be the way we can solve this problem. 

    totally 10 valid state(vertex): 
    1: (1, 3, 5, 7)
    2: (1, 3, 5, 8)
    3: (1, 3, 6, 7)
    4: (1, 4, 5, 7)
    5: (1, 4, 5, 8)
    6: (2, 3, 6, 7)
    7: (2, 3, 6, 8)
    8: (2, 4, 5, 8)
    9: (2, 4, 6, 7)
    10: (2, 4, 6, 8)

    Graph adjancency list notation: [[6], [8, 7], [6, 9, 7], [9, 8], [8, 10], [1, 3], [2, 3], [2, 4, 5], [3, 4], [5]]

    Now our goal is to find path from 1 -> 10. 

    G := [[6], [8, 7], [6, 9, 7], [9, 8], [8, 10], [1, 3], [2, 3], [2, 4, 5], [3, 4], [5]]
    Paths(G, 1, 10, 7) = {[1, 6, 3, 7, 2, 8, 5, 10], [1, 6, 3, 9, 4, 8, 5, 10]}

    As we can see we have two solution to the problem, explained as follows: 
    Solution 1: 
        farmer go to the right with sheep 
        farmer come back
        farmer go to the right with cabbage
        farmer come back with sheep
        farmer go to the right with wolf
        farmer come back
        farmer bring sheep to the right
    Solution 2: 
        farmer go to the right with sheep
        farmer come back
        farmer go to the right with wolf 
        farmer come back with sheep
        farmer go to the right with cabbage 
        farmer come back
        farmer bring sheep to the right 
        
4.
    We can formulate this problem as a graph path finding problem using a similar idea as above. We assign two number for each person. one number for left, another number for right. NOTE THAT WE NEED ONE MORE object called ship that also has two numbers to keep track of where the ship is. 
    And vertex in the graph represent the current state. We only keep valid state(a.k.a. no canibal outnumber) vertices in our graph. And we only add edges when we have a valid transition, a.k.a(only one or two person's number can be flipped, note that we need to flip the ship every round and when the ship is on the left, we can only flip people's number that are already on the left, and when the ship is on the right, we can only ship the people's number that are on the right. )

    m as missionaries, c as canibals 

    PERSON      LEFT    RIGHT
    m1          1       2
    m2          3       4
    m3          5       6
    c1          7       8
    c2          9       10
    c3          11      12
    ship        13      14

    NOTE that for coding simplicity, some 'invalid' state that only involve ship errors are still kept in the graph. But they can't be reached anyways. [ex. state 67]
    
    Totally 68 valid states: 
    1: (1, 3, 5, 7, 9, 11, 13)
    2: (1, 3, 5, 7, 9, 11, 14)
    3: (1, 3, 5, 7, 9, 12, 13)
    4: (1, 3, 5, 7, 9, 12, 14)
    5: (1, 3, 5, 7, 10, 11, 13)
    6: (1, 3, 5, 7, 10, 11, 14)
    7: (1, 3, 5, 7, 10, 12, 13)
    8: (1, 3, 5, 7, 10, 12, 14)
    9: (1, 3, 5, 8, 9, 11, 13)
    10: (1, 3, 5, 8, 9, 11, 14)
    11: (1, 3, 5, 8, 9, 12, 13)
    12: (1, 3, 5, 8, 9, 12, 14)
    13: (1, 3, 5, 8, 10, 11, 13)
    14: (1, 3, 5, 8, 10, 11, 14)
    15: (1, 3, 5, 8, 10, 12, 13)
    16: (1, 3, 5, 8, 10, 12, 14)
    17: (1, 3, 6, 7, 9, 12, 13)
    18: (1, 3, 6, 7, 9, 12, 14)
    19: (1, 3, 6, 7, 10, 11, 13)
    20: (1, 3, 6, 7, 10, 11, 14)
    21: (1, 3, 6, 8, 9, 11, 13)
    22: (1, 3, 6, 8, 9, 11, 14)
    23: (1, 4, 5, 7, 9, 12, 13)
    24: (1, 4, 5, 7, 9, 12, 14)
    25: (1, 4, 5, 7, 10, 11, 13)
    26: (1, 4, 5, 7, 10, 11, 14)
    27: (1, 4, 5, 8, 9, 11, 13)
    28: (1, 4, 5, 8, 9, 11, 14)
    29: (1, 4, 6, 7, 10, 12, 13)
    30: (1, 4, 6, 7, 10, 12, 14)
    31: (1, 4, 6, 8, 9, 12, 13)
    32: (1, 4, 6, 8, 9, 12, 14)
    33: (1, 4, 6, 8, 10, 11, 13)
    34: (1, 4, 6, 8, 10, 11, 14)
    35: (2, 3, 5, 7, 9, 12, 13)
    36: (2, 3, 5, 7, 9, 12, 14)
    37: (2, 3, 5, 7, 10, 11, 13)
    38: (2, 3, 5, 7, 10, 11, 14)
    39: (2, 3, 5, 8, 9, 11, 13)
    40: (2, 3, 5, 8, 9, 11, 14)
    41: (2, 3, 6, 7, 10, 12, 13)
    42: (2, 3, 6, 7, 10, 12, 14)
    43: (2, 3, 6, 8, 9, 12, 13)
    44: (2, 3, 6, 8, 9, 12, 14)
    45: (2, 3, 6, 8, 10, 11, 13)
    46: (2, 3, 6, 8, 10, 11, 14)
    47: (2, 4, 5, 7, 10, 12, 13)
    48: (2, 4, 5, 7, 10, 12, 14)
    49: (2, 4, 5, 8, 9, 12, 13)
    50: (2, 4, 5, 8, 9, 12, 14)
    51: (2, 4, 5, 8, 10, 11, 13)
    52: (2, 4, 5, 8, 10, 11, 14)
    53: (2, 4, 6, 7, 9, 11, 13)
    54: (2, 4, 6, 7, 9, 11, 14)
    55: (2, 4, 6, 7, 9, 12, 13)
    56: (2, 4, 6, 7, 9, 12, 14)
    57: (2, 4, 6, 7, 10, 11, 13)
    58: (2, 4, 6, 7, 10, 11, 14)
    59: (2, 4, 6, 7, 10, 12, 13)
    60: (2, 4, 6, 7, 10, 12, 14)
    61: (2, 4, 6, 8, 9, 11, 13)
    62: (2, 4, 6, 8, 9, 11, 14)
    63: (2, 4, 6, 8, 9, 12, 13)
    64: (2, 4, 6, 8, 9, 12, 14)
    65: (2, 4, 6, 8, 10, 11, 13)
    66: (2, 4, 6, 8, 10, 11, 14)
    67: (2, 4, 6, 8, 10, 12, 13)
    68: (2, 4, 6, 8, 10, 12, 14)

    Valid Graph: [[10, 6, 4, 40, 38, 36, 28, 26, 24, 22, 20, 18, 14, 12, 8], [], [36, 24, 18, 12, 8, 16], [1], [38, 26, 20, 14, 8, 16], [1], [16, 48, 42, 30], [1, 3, 5], [40, 28, 22, 14, 12, 16], [1], [16, 50, 44, 32], [1, 3, 9], [16, 52, 46, 34], [1, 5, 9], [], [3, 5, 7, 9, 11, 13], [56, 44, 42, 32, 30], [1, 3], [58, 46, 42, 34, 30], [1, 5], [62, 46, 44, 34, 32], [1, 9], [56, 50, 48, 32, 30], [1, 3], [58, 52, 48, 34, 30], [1, 5], [62, 52, 50, 34, 32], [1, 9], [60, 68], [7, 17, 19, 23, 25], [64, 68], [11, 17, 21, 23, 27], [66, 68], [13, 19, 21, 25, 27], [56, 50, 48, 44, 42], [1, 3], [58, 52, 48, 46, 42], [1, 5], [62, 52, 50, 46, 44], [1, 9], [60, 68], [7, 17, 19, 35, 37], [64, 68], [11, 17, 21, 35, 39], [66, 68], [13, 19, 21, 37, 39], [60, 68], [7, 23, 25, 35, 37], [64, 68], [11, 23, 27, 35, 39], [66, 68], [13, 25, 27, 37, 39], [62, 58, 56, 66, 64, 60], [], [64, 60, 68], [17, 23, 35, 53], [66, 60, 68], [19, 25, 37, 53], [68], [29, 41, 47, 53, 55, 57], [66, 64, 68], [21, 27, 39, 53], [68], [31, 43, 49, 53, 55, 61], [68], [33, 45, 51, 53, 57, 61], [], [29, 31, 33, 41, 43, 45, 47, 49, 51, 55, 57, 59, 61, 63, 65]]



    Now our goal is to find path from state 1 -> 68
    G := [[10, 6, 4, 40, 38, 36, 28, 26, 24, 22, 20, 18, 14, 12, 8], [], [36, 24, 18, 12, 8, 16], [1], [38, 26, 20, 14, 8, 16], [1], [16, 48, 42, 30], [1, 3, 5], [40, 28, 22, 14, 12, 16], [1], [16, 50, 44, 32], [1, 3, 9], [16, 52, 46, 34], [1, 5, 9], [], [3, 5, 7, 9, 11, 13], [56, 44, 42, 32, 30], [1, 3], [58, 46, 42, 34, 30], [1, 5], [62, 46, 44, 34, 32], [1, 9], [56, 50, 48, 32, 30], [1, 3], [58, 52, 48, 34, 30], [1, 5], [62, 52, 50, 34, 32], [1, 9], [60, 68], [7, 17, 19, 23, 25], [64, 68], [11, 17, 21, 23, 27], [66, 68], [13, 19, 21, 25, 27], [56, 50, 48, 44, 42], [1, 3], [58, 52, 48, 46, 42], [1, 5], [62, 52, 50, 46, 44], [1, 9], [60, 68], [7, 17, 19, 35, 37], [64, 68], [11, 17, 21, 35, 39], [66, 68], [13, 19, 21, 37, 39], [60, 68], [7, 23, 25, 35, 37], [64, 68], [11, 23, 27, 35, 39], [66, 68], [13, 25, 27, 37, 39], [62, 58, 56, 66, 64, 60], [], [64, 60, 68], [17, 23, 35, 53], [66, 60, 68], [19, 25, 37, 53], [68], [29, 41, 47, 53, 55, 57], [66, 64, 68], [21, 27, 39, 53], [68], [31, 43, 49, 53, 55, 61], [68], [33, 45, 51, 53, 57, 61], [], [29, 31, 33, 41, 43, 45, 47, 49, 51, 55, 57, 59, 61, 63, 65]]


    NuPaths(G, 1, 68, 1 -> 10) = 0
    NuPaths(G, 1, 68, 11) = 8100
    Because the output is too large, I only include couple example of Paths(G, 1, 68, 11) in here. 

    Minimally, we can finish this in 11 steps. 

    [NOTE: L, R means the amount of missionaries - amount of canibals, hasL means whether there are missionaries on the left side, similarly hasR means whether there are missionaries on the right side. L or R's negative number is only valid when their side's hasX = False]
    Example1: [1, 40, 9, 16, 13, 52, 39, 62, 53, 66, 61, 68]
    
        m1 passed with c1 with SHIP  [now L: 0 hasL: True R: 0 hasR: True]
        m1 passed with SHIP  [now L: 1 hasL: True R: -1 hasR: False]
        c2 passed with c3 with SHIP  [now L: 3 hasL: True R: -3 hasR: False]
        c3 passed with SHIP  [now L: 2 hasL: True R: -2 hasR: False]
        m1 passed with m2 with SHIP  [now L: 0 hasL: True R: 0 hasR: True]
        m2 passed with c2 with SHIP  [now L: 0 hasL: True R: 0 hasR: True]
        m2 passed with m3 with SHIP  [now L: -2 hasL: False R: 2 hasR: True]
        c1 passed with SHIP  [now L: -3 hasL: False R: 3 hasR: True]
        c1 passed with c2 with SHIP  [now L: -1 hasL: False R: 1 hasR: True]
        c2 passed with SHIP  [now L: -2 hasL: False R: 2 hasR: True]
        c2 passed with c3 with SHIP  [now L: 0 hasL: False R: 0 hasR: True]
    
    Example2: [1, 8, 3, 16, 11, 32, 21, 62, 53, 60, 57, 68]
        c2 passed with c3 with SHIP  [now L: 2 hasL: True R: -2 hasR: False]
        c2 passed with SHIP  [now L: 1 hasL: True R: -1 hasR: False]
        c1 passed with c2 with SHIP  [now L: 3 hasL: True R: -3 hasR: False]
        c2 passed with SHIP  [now L: 2 hasL: True R: -2 hasR: False]
        m2 passed with m3 with SHIP  [now L: 0 hasL: True R: 0 hasR: True]
        m2 passed with c3 with SHIP  [now L: 0 hasL: True R: 0 hasR: True]
        m1 passed with m2 with SHIP  [now L: -2 hasL: False R: 2 hasR: True]
        c1 passed with SHIP  [now L: -3 hasL: False R: 3 hasR: True]
        c2 passed with c3 with SHIP  [now L: -1 hasL: False R: 1 hasR: True]
        c3 passed with SHIP  [now L: -2 hasL: False R: 2 hasR: True]
        c1 passed with c3 with SHIP  [now L: 0 hasL: False R: 0 hasR: True]

    Example3: [1, 8, 3, 16, 11, 44, 39, 62, 53, 66, 61, 68]
        c2 passed with c3 with SHIP  [now L: 2 hasL: True R: -2 hasR: False]
        c2 passed with SHIP  [now L: 1 hasL: True R: -1 hasR: False]
        c1 passed with c2 with SHIP  [now L: 3 hasL: True R: -3 hasR: False]
        c2 passed with SHIP  [now L: 2 hasL: True R: -2 hasR: False]
        m1 passed with m3 with SHIP  [now L: 0 hasL: True R: 0 hasR: True]
        m3 passed with c3 with SHIP  [now L: 0 hasL: True R: 0 hasR: True]
        m2 passed with m3 with SHIP  [now L: -2 hasL: False R: 2 hasR: True]
        c1 passed with SHIP  [now L: -3 hasL: False R: 3 hasR: True]
        c1 passed with c2 with SHIP  [now L: -1 hasL: False R: 1 hasR: True]
        c2 passed with SHIP  [now L: -2 hasL: False R: 2 hasR: True]
        c2 passed with c3 with SHIP  [now L: 0 hasL: False R: 0 hasR: True]