#OK to post homework
#Michael Yen, 10/25/20, Assignment 13
#1. Let A be the set of letters in your name e.g. in my case it is {b,d,e,i,g, o,l, r,n,z}.
#A=[m,i,c,h,a,e,l,y,n]=[a,c,e,h,i,l,m,n,y]

#(i) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two consonants can be
#adjacent?
G:=[{seq(i,i=1..9)},{1,3,5},{seq(i,i=1..9)},{1,3,5},{seq(i,i=1..9)},{1,3,5}$4];
normal(add(convert(GFt(G,i,t), `+`),i=1..9));
f:=%;
coeff(taylor(f,t=0,101),t,100);

#5226548988000567248773522137264977941817881695114675433474341352228679239341009

#(ii) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be 
#adjacent?
G:=[{2,4,6,7,8,9},{seq(i,i=1..9)},{2,4,6,7,8,9},{seq(i,i=1..9)},{2,4,6,7,8,9},{seq(i,i=1..9)}$4];
normal(add(convert(GFt(G,i,t), `+`),i=1..9));
f:=%;
coeff(taylor(f,t=0,101),t,100);

#202754070861600536180436660918725228517598077673149561660158560432399425152362436796384018432

#(iii) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be #adjacent and no consonants can be adjacent?
G:=[{2,4,6,7,8,9},{1,3,5},{2,4,6,7,8,9},{1,3,5},{2,4,6,7,8,9},{1,3,5}$4];
normal(add(convert(GFt(G,i,t), `+`),i=1..9));
f:=%;
coeff(taylor(f,t=0,101),t,100);

#5222371523228586691507591059411304343770770758809435324721135616

#(iv): Let a(n) be the number of n-letters of words in that alphabet that have neither adjacent vowels nor 
#adjacent consonants, and let
#f(t)=Sum(a(n)*t^n,n=0..infinity)

#Find f(t) explicilty.

G := [{2, 4, 6, 7, 8, 9}, {1, 3, 5}, {2, 4, 6, 7, 8, 9}, {1, 3, 5}, {2, 4, 6, 7, 8, 9}, {1, 3, 5} $ 4];
f := normal(add(convert(GFt(G, i, t), `+`), i = 1 .. 9));
a := proc(n, f) option remember; 
coeff(taylor(f, t = 0, n + 1), t, n); 
end proc;
add(a(n,f)*t^n, n = 0 .. infinity);

#2. Using the appropriate procedure in M13.txt solve the following ancient puzzle (no credit for other methods!)
#A farmer, a wolf, a sheep, and a (very big) cabbage have to cross a river using a row boat that can only have 
#the farmer and one of the other animals/vegetable. The wolf and the sheep can't be left unsupervised, and 
#neither can the sheep and the cabbage (but the wolf and the cabbage can be left safely alone). How can this be 
#done?

#[{F,W,S,C}, {}], ..... [{},{F,W,S,C}]
#1=[{F,W,S,C},{}] Followers(1)=2=[{W,C},{F,S}] Follower(1)={2}
#2=[{W,C},{F,S}], Followers(2)= [{W,C,F},{S}]=3 Followers(2)={3}
#3=[{W,C,F},{S}] Followers(3)={4=[{W},{F,C,S}], 5=[{C},{F,S,W}]}, Followers(3)=(4,5)

#4=[{W},{F,C,S}]
#5=[{C},{F,S,W}]
#Follower(4)={[{F,S,W},{C}]=6, [{F,W,C},{S}]=3} Followers(4)={3,6}
#Followers(5)={7=[{F,C,S},{W}],3=[{F,W,C},{S}]} Follower(5)={3,7}
#Followers(6)={[{S},{F,W,C}]=8,[{W},{F,S,C}]=4} Followers(6)={7,4}
#Followers(7)={[{S},{F,C,W}]=8, [{C},{F,S,W}]=5} Followers(7)={8,5}
#Followers(8)={[{F,S},{C,W}]=9, [{S,F,C},{W}]=7, [{F,W,S},{C}]=4} Followers(8)={4,7,9}
#Followers(9)={[{},{F,S,C,W}]=10, [{S},{F,C,W}]=8} Followers(9)={10,8}
#Followers(10)={[{F,S},{C,W}]=9} Followers(10)={9}

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

findPath:=proc(G,start,finish) local i, pathSet:
for i from 0 to infinity do
 pathSet:=Paths(G,start,finish,i)
 if pathSet <> {} then
  return pathSet:
 fi:
od:
end:


findPath(G, 1, 10);
                  #{[1, 2, 3, 5, 7, 8, 9, 10]}

#This means 
#{[{F,W,S,C},{}],
#[{W,C},{F,S}],
#[{W,C,F},{S}],
#[{C},{F,S,W}],
#[{F,C,S},{W}],
#[{S},{F,C,W}],
#[{F,S},{C,W}],
#[{},{F,S,C,W}]}

#3. [Optional Challenge] Write a Maple program that inputs a set of entities S, and a set of pairs {s1,s2} where 
#s1 and s2 are not to be left alone unsupervised. Write a Maple program that
#(i) Finds all the way ofs crossing the river safely (where each crossing should have the farmer, since he is 
#the only one who knows how to row)
#The number of ways of doing it

#4. Using the appropriate procedure in M13.txt solve the following more challenging puzzle
#3 Missionaries and 3 Canibals have to cross a river using a row boat that can have at most two passengers (and 
#at least one, it is not a self-driving boat). At no time can the canniabls outnumber the missionaries on either 
#river-bank (unless there are no missionaries, of course). How to do it?

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

G2:=[{2,3,4},{1,5},{1},{5},{6,2,4},{5,7},{6,8},{7,9},{8,10},{9,11},{10,12},{11,13},{12,14},{}]

findPath:=proc(G,start,finish) local i, pathSet:
for i from 0 to infinity do
 pathSet:=Paths(G,start,finish,i)
 if pathSet <> {} then
  return pathSet:
 fi:
od:
end:

findPath(G2, 1, 14);
                  #{[1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], [1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]}                 
#Meaning
#{[[3,3,1],[0,0,0]],
#[[2,2,0],[1,1,1]],
#[[3,2,1],[0,1,0]],
#[[3,0,0],[0,3,1]],
#[[1,1,0],[2,2,1]],
#[[3,1,1],[0,2,0]],
#[[2,2,1],[1,1,0]],
#[[0,2,0],[3,1,1]],
#[[0,3,1],[3,0,0]],
#[[0,1,0],[3,2,1]],
#[[0,2,1],[3,1,0]],
#[[0,0,0],[3,3,0]]}
#Or 
#{[[3,3,1],[0,0,0]],
#[[3,1,0],[0,2,1]],
#[[3,2,1],[0,1,0]],
#[[3,0,0],[0,3,1]],
#[[1,1,0],[2,2,1]],
#[[3,1,1],[0,2,0]],
#[[2,2,1],[1,1,0]],
#[[0,2,0],[3,1,1]],
#[[0,3,1],[3,0,0]],
#[[0,1,0],[3,2,1]],
#[[0,2,1],[3,1,0]],
#[[0,0,0],[3,3,0]]}

#5. [Optional Challenge] Write a Maple procedure MC(n,k), that generalizes the above from n=3 to general n and 
#the maximum capacity of the boat is k. The above clasical puzzle would be the case MC(3,2).