#OK to post homework
#Kent Mei, 10/25/20, Assignment 13

#---------------------------------
#Part 1

#A = {e,i,k,m,n,t}
#Key:
#1 = e
#2 = i
#3 = k
#4 = m
#5 = n
#6 = t

#i)
#G := [{1,2,3,4,5,6}, {1,2,3,4,5,6}, {1,2}, {1,2}, {1,2}, {1,2}];
#f :=normal(add(convert(GFt(G,i,t), `+`),i = 1..6));
#coeff(taylor(f, t = 0,100),t,99) = 2142584059011987034055949456454460919829527915243224879333376;

#ii)
#G := [{3,4,5,6}, {3,4,5,6}, {1,2,3,4,5,6}$4];
#f := normal(add(convert(GFt(G,i,t), `+`),i = 1..6));
#coeff(taylor(f, t = 0,100),t,99) = 60846226641686563481763935995433673397377747138135465038504447362329477120;

#iii)
#G := [{3,4,5,6}, {3,4,5,6}, {1,2}$4];
#f := normal(add(convert(GFt(G,i,t), `+`),i = 1..6));
#coeff(taylor(f, t = 0,100),t,99) = 2854495385411919762116571938898990272765493248;

#iv)
#Need to find a generating function for the sequence of n-letter words in the above alphabet that have neither adjacent vowels nor adjacent consonants. Can be found from part iii
#G := [{3,4,5,6}, {3,4,5,6}, {1,2}$4];
#f := normal(add(convert(GFt(G,i,t), `+`),i = 1..6)) 
#-2*(8*t+3)/(8*t^2-1)


#---------------------------------
#Part 2

#To solve this problem, we define the problem using graphs where each node is valid state in the problem and each edge is a valid transition from one state to another.
#Convention: F = Farmer, W = Wolf, S = Sheep, C = Cabbage
#{[L],[R]} means the items in the first list are on the left bank and the items in the second list are on the right bank.
#Note that I do not count edges that return to a previous node so as to prevent cycles in the graph. It should be intuitive that returning to a prior state doesn't help solve the problem. 
#Goal: {[F,W,S,C],[]} -> ... -> {[],[F,W,S,C]}

#1: {[F,W,S,C],[]} Edges: 1->2 = {2}
#2: {[W,C], [F,S]} Edges: 2->3 = {3}
#3: {[F,W,C], [S]} Edges: 3->4, 3->5 = {4,5}
#4: {[C], [F,W,S]} Edges: 4->6 = {6} 
#5: {[W], [F,S,C]} Edges: 5->7 = {7}
#6: {[F,S,C], [W]} Edges: 6->8 = {8}
#7: {[F,W,S], [C]} Edges: 7->8 = {8}
#8: {[S], [F,W,C]} Edges: 8->9 = {9}
#9: {[F,S], [W,C]} Edges: 9->10 = {10}
#10:{[],[F,W,S,C]} Edges: {}

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

#Answer:
#{[1, 2, 3, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 8, 9, 10]}


#---------------------------------
#Part 3

#Optional, did not have time to create the program.


#---------------------------------
#Part 4

#Similar idea as Part 2
#Convention: [M,C,B] represents a river bank with M missionaries and C cannibals. B = 0 if the boat isn't there while B = 1 if the boat is there.
#Goal: {[3,3,1],[0,0,0]} -> ... -> {[0,0,0],[3,3,1]}

#1: {[3,3,1],[0,0,0]} Edges: 1->2, 1->3 = {2,3}
#2: {[3,2,0],[0,1,1]} Edges: {}
#3: {[2,2,0],[1,1,1]} Edges: 3->4 = {4}
#4: {[3,2,1],[0,1,0]} Edges: 4->5, 4->6 = {5,6}
#5: {[3,1,0],[0,2,1]} Edges: {}
#6: {[3,0,0],[0,3,1]} Edges: 6->7 = {7}
#7: {[3,1,1],[0,2,0]} Edges: 7->8 = {8}
#8: {[1,1,0],[2,2,1]} Edges: 8->9 = {9}
#9: {[2,2,1],[1,1,0]} Edges: 9->10 = {10}
#10:{[0,2,0],[3,1,1]} Edges: 10->11 = {11}
#11:{[0,3,1],[3,0,0]} Edges: 11->12 = {12}
#12:{[0,1,0],[3,2,1]} Edges: 12->13 = {13}
#13:{[0,2,1],[3,1,0]} Edges: 13->14 = {14}
#14:{[0,0,0],[3,3,1]} Edges: {}

#G := [{2,3},{},{4},{5,6},{},{7},{8},{9},{10},{11},{12},{13},{14},{}]
#{seq(op(Paths(G,1,14,i)), i = 1..14)}

#Answer:
#{[1, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14]}


#---------------------------------
#Part 5

#Optional, did not have time to create the program.