> #ok to post
;
> #Yifan Zhang, 10/21/2020
;
> 
;
> 
;
> #Q1.
;
> #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}.
> #(i) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two consonants can be adjacent?
> #(ii) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be adjacent?
> #(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?(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.
;
> 
;
> #(i) 
;
> #let b=1, d=2, e=3, i=4, g=5, o=6, l=7, r=8, n=9, z=10
;
> G1:=[{3,4,6},{3,4,6},{1,2,3,4,5,6,7,8,9,10}$2,{3,4,6},{1,2,3,4,5,6,7,8,9,10},{3,4,6}$4];
Typesetting:-mprintslash([(G1 := [{3, 4, 6}, {3, 4, 6}, {1, 2, 3, 4, 5, 6, 7, 8
, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {3, 4, 6}, {1, 2, 3, 4, 5, 6, 7, 8,
9, 10}, {3, 4, 6}, {3, 4, 6}, {3, 4, 6}, {3, 4, 6}])],[[{3, 4, 6}, {3, 4, 6}, {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {3, 4, 6}, {1,
2, 3, 4, 5, 6, 7, 8, 9, 10}, {3, 4, 6}, {3, 4, 6}, {3, 4, 6}, {3, 4, 6}]])

;
> GFt:=proc(G,v,t)  local n,eq,var,X,u,Neighs,eq1,nei:
> 
> n:=nops(G):
> 
> #var is the set of desired quantities. The outputs is going to be [X[1], ..., X[n]] after it is SOLVED
> var:={seq(X[u],u=1..n)}:
> 
> #We now use the powerful technique of weight-enumerators to set a SYSTEM of equations for these quantities
> #The weight enumerator according to the weight t^LengthOfPath of all paths from u to v 
> #is t times the sum of the weight enumerators of all path from neighbors of u and if u=v you have to add
> #1 for the weight of the empty path
> eq:={}:
> 
> 
> #Neig is the set of neighbors of u
> for u from 1 to n do
>  Neighs:=G[u]:
>  if u=v then
>   eq1:=X[u]=1+t*add(X[nei],nei in Neighs):
>  else
>   eq1:=X[u]=t*add(X[nei],nei in Neighs):
>  fi:
> eq:=eq union {eq1}:
> od:
> 
> 
> 
> #We now let Maple solve the linear system of equations
> var:=solve(eq,var):
> 
> #we now plug the solution into seq vector of unknowns [X[1], ..., X[n]]:
> 
> factor(subs(var,[seq(X[u], u=1..n)])):
> 
> end:
> normal(add(convert(GFt(G1, i, t), `+`), i=1..10));
-(21*t+10)/(21*t^2+3*t-1)

;
> f1:=%
Typesetting:-mprintslash([(f1 := -(21*t+10)/(21*t^2+3*t-1))],[-(21*t+10)/(21*t^
2+3*t-1)])

;
> coeff(taylor(f1,t=0, 101), t, 100)
1060264768077696641472515894614400208129649909390294358819730691587072945238062\
423

;
> #(ii)
;
> G2:=[{1,2,3,4,5,6,7,8,9,10}$2, {1,2,5,7,8,9,10}$2, {1,2,3,4,5,6,7,8,9,10}, {1,2,5,7,8,9,10}, {1,2,3,4,5,6,7,8,9,10}$4];
Typesetting:-mprintslash([(G2 := [{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 2, 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
, 5, 6, 7, 8, 9, 10}, {1, 2, 5, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 2, 3, 4,
5, 6, 7, 8, 9, 10}])],[[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 2, 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, 5, 6, 7
, 8, 9, 10}, {1, 2, 5, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 2, 3,
4, 5, 6, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8
, 9, 10}]])

;
> f2:=normal(add(convert(GFt(G2, i, t), `+`), i=1..10));
Typesetting:-mprintslash([(f2 := -(21*t+10)/(21*t^2+7*t-1))],[-(21*t+10)/(21*t^
2+7*t-1)])

;
> coeff(taylor(f2,t=0, 101), t, 100)
4833264670588341120161699245628887231514355947854273604880803174607612704491154\
162

;
> 
;
> #(iii)
;
> G3:=[{3,4,6}$2, {1,2,5,7,8,9,10}$2, {3,4,6},{1,2,5,7,8,9,10}, {3,4,6}$4];
Typesetting:-mprintslash([(G3 := [{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}])],[[{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}]])

;
> f3:=normal(add(convert(GFt(G3, i,t), `+`), i=1..10))
Typesetting:-mprintslash([(f3 := -2*(21*t+5)/(21*t^2-1))],[-2*(21*t+5)/(21*t^2-\
1)])

;
> coeff(taylor(f3,t=0, 101), t, 100)
12911144350507190263864564756466286665540892229111873244938372910010

;
> #(iv)
;
> f:=taylor(f3, t=0, 20);
Typesetting:-mprintslash([(f := series(10+42*t+210*t^2+882*t^3+4410*t^4+18522*t
^5+92610*t^6+388962*t^7+1944810*t^8+8168202*t^9+40841010*t^10+171532242*t^11+
857661210*t^12+3602177082*t^13+18010885410*t^14+75645718722*t^15+378228593610*t
^16+1588560093162*t^17+7942800465810*t^18+33359761956402*t^19+O(t^20),t,20))],[
series(10+42*t+210*t^2+882*t^3+4410*t^4+18522*t^5+92610*t^6+388962*t^7+1944810*
t^8+8168202*t^9+40841010*t^10+171532242*t^11+857661210*t^12+3602177082*t^13+
18010885410*t^14+75645718722*t^15+378228593610*t^16+1588560093162*t^17+
7942800465810*t^18+33359761956402*t^19+O(t^20),t,20)])

;
> 
;
> 
;
> 
;
> #Q2. 
;
> #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?
;
> 
;
> #farmer:=f, wolf:=w, sheep:=s, cabbage:=c
;
> #s1:=[{f,w,s,c},{}]
> #follower(s1)=[{w,c},{f,s}]:=s2
;
> #follower(s2):=[{f,w,c},{s}]=s3
;
> #follower(s3):=[{w},{f,s,c}]=s4, =[{c},{f,w,s}]=s5
;
> #follower(s4):=[{f,w,s},{c}]=s6, =[{f,w,c},{s}]=s3
;
> #follower(s5):=[{f,s,c},{w}]=s7, =[{f,w,c},{s}]=s3
;
> #follower(s6):=[{w},{f,s,c}]=s4, =[{s},{f,w,c}]=s8
;
> #follower(s7):=[{c},{f,w,s}]=s5, =[{s},{f,w,c}]=s8
;
> #follower(s8):=[{f,w,s},{c}]=s6, =[{f,s,c},{w}]=s7, =[{f,s},{w,c}]=s9
;
> #follower(s9):=[{},{f,w,s,c}] 
;
> 
;
> 
;
> 
;
> #Q3. 
;
> #[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)
> #(ii)The number of ways of doing it
;
> G:=[{2},{1,3},{4,5},{6,3},{7,3},{4,8},{5,8},{6,7,9},{8}]
Typesetting:-mprintslash([(G := [{2}, {1, 3}, {4, 5}, {3, 6}, {3, 7}, {4, 8}, {
5, 8}, {6, 7, 9}, {8}])],[[{2}, {1, 3}, {4, 5}, {3, 6}, {3, 7}, {4, 8}, {5, 8},
{6, 7, 9}, {8}]])

;
> #Start from state 1 and the destination is state 9, so run Paths(G,1,9, k) 

;
> Paths:=proc(G,u,v,k)  local Neighs, PA,nei,PA1,pa1:
> option remember:
> 
> #INITIAL CONDITIONS, paths of length 0 are just lists of length 1
> if k=0 then
>  if u=v then
>    RETURN({[u]}):
>   else
>    RETURN({}):
>  fi:
> fi:
> 
> #Every path from u to v of length k starts with a first step that is towards one of the neighbors of u
> #so let's find the set of neighbors of u
> Neighs:=G[u]:
> 
> #We will dynamically construct all the paths from u to v of length k by 
> #going through all the options for first step
> #PA is the desired output
> #We start out PA the empty set
> PA:={}:
> 
> for nei in Neighs do
>  #We call the procedure recursively to find the set of paths from a typical neighbor of u, to v of length one less, i.e. k-1
>  PA1:=Paths(G,nei,v,k-1):
> 
>  #For each of these paths we stick u at the beginning and add these to our desired output
> PA:=PA union {seq([u,op(pa1)], pa1 in PA1)}:
> od:
> 
> PA:
> 
> end:

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

;
> 
;
> 
;
> #Q4.
;
> #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,B}, { } ] s1-> [ [{}, {3,3,B} ]
;
> #follower(s1):= [{3,1},{0,2,B}]s2 , [{3,2},{0,1,B}]s3, [{2,2}, {1,1,B}]s4    GList:={s2,s3,s4}
;
> #follower(s2):=[{3,2,B},{0,1}]s5, [{3,3,B},{0,0}]s1 GList:={s3,s4,s5}
;
> #follower(s3):=[{3,3,B},{0,0}]s1 GList:={s4,s5}
;
> #follower(s4):=[{3,2,B},{0,1}]s5, [{2,3,B},{1,0}]error, [{3,3,B},{0,0}]s1 GList:={s5}
;
> #follower(s5):=[{2,2},{1,1,B}]s4, [{3,1},{0,2,B}]s2, [{3,0},{0,3,B}]s6 GList:={s6}
;
> #follower(s6):=[{3,1,B},{0,2}]s7, [{3,2,B},{0,1}]s5 GList:={s7}
;
> #follower(s7):=[{1,1},{2,2,B}]s8, [{2,1},{1,2,B}]error, [{3,0},{0,3,B}]s6 GList:={s8}
;
> #follower(s8):=[{2,1,B},{1,2}]error, [{3,1,B},{0,2}]s7, [{1,2,B},{2,1}]error, [{1,3,B},{2,0}]error, [{2,2,B},{1,1}]s9 GList:={s9}
;
> #follower(s9):=[{0,2},{3,1,B}]s10, [{1,1},{2,2,B}]s8 GList:= {s10}
;
> #follower(s10):=[{0,3,B},{3,0}]s11, [{2,2,B},{1,1}]s9 GList:={s11}
;
> #follower(s11):=[{0,1},{3,2,B}]s12, [{0,2},{3,1,B}]s10 GList:={s12}
;
> #follower(s12):=[{1,1,B},{2,2}]s13, [{0,2,B},{3,1}]s14, [{0,3,B},{3,0}]s11 GList:={s13,s14}
;
> #follower(s13):=[{0,0},{3,3,B}]s15, [{0,1},{3,2,B}]s12 GList:={s14,s15}
;
> #follower(s14):=[{0,0},{3,3,B}]s15 GList:={s15}
;
> #s15 is the final state. 
;
> G4:=[{2,3,4},{1,5},{1},{1,5},{2,4,6},{5,7},{6,8},{7,9},{8,10},{9,11},{10,12},{11,13,14},{12,15},{15}, {13,14}]
Typesetting:-mprintslash([(G4 := [{2, 3, 4}, {1, 5}, {1}, {1, 5}, {2, 4, 6}, {5
, 7}, {6, 8}, {7, 9}, {8, 10}, {9, 11}, {10, 12}, {11, 13, 14}, {12, 15}, {15},
{13, 14}])],[[{2, 3, 4}, {1, 5}, {1}, {1, 5}, {2, 4, 6}, {5, 7}, {6, 8}, {7, 9}
, {8, 10}, {9, 11}, {10, 12}, {11, 13, 14}, {12, 15}, {15}, {13, 14}]])

;
> Paths(G4, 1,15,10)
{}

;
> Paths(G4, 1,15,11)
{[1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15], [1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 
14, 15], [1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15], [1, 4, 5, 6, 7, 8, 9, 10, 
11, 12, 14, 15]}

;
> #I find that the smallest paths is 11 steps. 
;
> #Paths(G4,1,15,13) #13-steps-Path
;
> 
;
> #Q5.
;
> #[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).
;
> 
;
> #checkList is to check if a list is in a list of the list. For example, checkList([[1,2,3]], [1,2,3]) return 1
;
> checkList:= proc(L, s) local i:
> option remember:
> for i from 1 to nops(L) do
> if L[i]=s then
> RETURN(1)
> else RETURN(0)
> fi:
> od:
> end:
> 
;
> #every step i need to check the glist.
;
> can<=miss {num of missionaries, num of cannibals, B/-}
;
> #[{3,3,B},{0,0}]  -> [{0,0},{3,3,B}], initial state->final state, n=3, k=2
;
> #[{i, j, B}, {3-i, 3-j} ] 1-> [{i-1, j},{4-i, j, B}],       2     [{i, j-1},{3-i, 4-j, B}], 3     [{i-1, j-1},{4-i, 4-j, B}] 4
;
> #[{i, j}, {3-i, 3-j, B}]  5 -> [{i+1, j, B},{2-i, 3-j}],  6 [{i, j+1, B},{3-i, 2-i}],   7  [{i+1,j+1, B},{2-i, 2-j}]  8
;
> #1->2,3,4
;
> #2->6,7,8
;
> #3->6,7,8
;
> #4->6,7,8
;
> #5->6,7,8
;
> #6->2,3,4
;
> #7->2,3,4
;
> #8->2,3,4
;
> #and the initial condition is for i<0, j<0 return "invalid i or j"; for any i and j in any bank should less than or equal to 3 and larger than 0.  and the number of 
;
> #i should never larger than the number of j. 
;
> #and the start state is 1, and the final state is one of 2,3,4 that equals to [{0,0},{3,3,B}]
;
> #
;
> #
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;