> #Weiji Zheng, 10/25/2020, Assignment 13
;
> #OK TO POST HOMEWORK
;
> 
;
> #Code for understanding
;
> 
> Help13:=proc(): print(` RandDG(n,k),LC(p) , RandG(n,p), Paths(G,u,v,k) , NuPaths(G,u,v,k), GFt(G,v,t) `): end:
> 
> #LC(p): inputs a rational number p outputs 1 with probability p (and 0 otherwise)
> #LC is short for "Loaded Coin"
> LC:=proc(p) local a,b,r:
> a:=numer(p):
> b:=denom(p):
> r:=rand(1..b)():
> if  r<=a then
>   RETURN(1):
> else
>  RETURN(0):
> fi:
> end:
> 
> 
> #RandDG(n,k): A random DIRECTED graph (IN CANONICAL FORM) on the set of vertices {1, ..., n} where each vetrex has up to k neighors 
> #It uses the data structure of list where the i-th entry is the set of neigbors of vertex i  .
> #Try:
> #RandDG(10,4):
> RandDG:=proc(n,k) local ra,i:
> 
> ra:=rand(1..n):
> 
> [seq({seq(ra(),i=1..k)},i=1..n)]:
> end:
> 
> #RandG(n,p): inputs a positive integer n and rational positive number between 0 and 1, outputs
> #a graph (in CANONICAL FORM) where each edge has probability p of being picked. Try:
> #RandG(20,1/4);
> RandG:=proc(n,p) local T,i,j,r:
> 
> #T is as a TABLE where T[i] (ultimately) is the set of neighbors ("friends") of vertex i.
> #They start out empty
> for i from 1 to n do
>  T[i]:={}:
> od:
> 
> for i from 1 to n do
>  for j from i+1 to n do
>    r:=LC(p):
>   # i and j have to decide whether or not to become friends, they toss a loaded coin with probaility p of deciding
>   #whether to be friends of each other
> 
>    if r=1 then
>    #if the coin comes out YES,  j is joined to T[i], and i is joined to T[j]
>      T[i]:=T[i] union {j}:
>      T[j]:=T[j] union {i}:
>    fi:
> od:
> od:
> 
> 
> #We finally convert the table data-structure to a list of sets (our convention for describing graphs)
> [seq(T[i],i=1..n)]:
> end:
> 
> #Paths(G,u,v,k): Inputs a graph G (on {1, ..., nops(G)}), (either directed or undirected) vertices u and v , and
> #a positive integer k, uses "Dynamical programming" to find the SET of paths , of length k, from u to v.
> #Try: Paths([{1,2},{2,3},{3,4},{1,2}],3);
> #We assume that the inputs are valid
> 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:
> 
> 
> 
> 
> #NuPaths(G,u,v,k): Inputs a graph G (on {1, ..., nops(G)}), (either directed or undirected) vertices u and v , and
> #a positive integer k, uses "Dynamical programming" to find the NUMBER of paths , of length k, from u to v.
> #Try: NuPaths([{1,2},{2,3},{3,4},{1,2}],3);
> #We assume that the inputs are valid
> NuPaths:=proc(G,u,v,k)  local Neighs,nei:
> option remember:
> 
> #INITIAL CONDITIONS, paths of length 0 are just lists of length 1
> if k=0 then
>  if u=v then
>    RETURN(1):
>   else
>    RETURN(0):
>  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]:
> 
> #The number of paths of length k from u to v is the sum of the number of paths from each neighbor of u to v, of length k-1
> 
> add(NuPaths(G,nei,v,k-1),nei in Neighs):
> 
> end:
> 
> 
> #GFt(G,v,t): Inputs a graph G in CANONICAL FORM, and a vertex v (a positive inetgers from 1 to n=nops(G)) outputs
> #the List of rational function in t whose u-th entry is
> #the rational function whose coefficient of t^k is NuPaths(G,u,v,k). Try:
> #GFt([{2,3,4},{1,4},{1,2},{1,2,3}],4,t)
> 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:
> 
;
> 
;
> #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}.
;
> #How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two consonants can be adjacent?
;
> #How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be adjacent?
;
> #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?
;
> #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.
;
> 
;
> A := {w,e,i,j,i}
A := {e, i, j, w}
;
> sort(A)
{e, i, j, w}
;
> #Let e=1, i=2, j=3, w=4
;
> 
;
> #i)
;
> #we have consonants j,w and vowels e,i
;
> #so,
;
> G := [{1,2,3,4},{1,2,3,4},{1,2},{1,2}]
G := [{1, 2, 3, 4}, {1, 2, 3, 4}, {1, 2}, {1, 2}]
;
> f := add(seq(add(GFt(G, i, t), i = 1 .. 4)))
f := -8*t/(4*t^2+2*t-1)+2*(t+1)*(2*t-1)/(4*t^2+2*t-1)-2*t*(2*t+1)/(4*t^2+2*t-1)+2*(2*t^2+2*t-1)/(4*t^2+2*t-1)-4*t^2/(4*t^2+2*t-1)
;
> coeff(taylor(f, t = 0, 101), t, 100)
3804271516754912896031502162844070752712851460194304
;
> 
;
> #ii)
;
> G := [{1,2,3,4},{1,2,3,4},{3,4},{3,4}]
G := [{1, 2, 3, 4}, {1, 2, 3, 4}, {3, 4}, {3, 4}]
;
> f := add(seq(add(GFt(G, i, t), i = 1 .. 4)))
f := 4*t/(2*t-1)^2+4*(t-1)/(2*t-1)-4*t/(2*t-1)
;
> coeff(taylor(f, t = 0, 101), t, 100)
258600722446558797905327453896704
;
> 
;
> #iii)
;
> G := [{3,4},{3,4},{1,2},{1,2}]
G := [{3, 4}, {3, 4}, {1, 2}, {1, 2}]
;
> f := add(seq(add(GFt(G, i, t), i = 1 .. 4)))
f := 4*(2*t^2-1)/((2*t-1)*(2*t+1))-8*t^2/((2*t-1)*(2*t+1))-8*t/((2*t-1)*(2*t+1))
;
> coeff(taylor(f, t = 0, 101), t, 100)
5070602400912917605986812821504
;
> 
;
> #iv)
;
> #still
;
> G := [{3,4},{3,4},{1,2},{1,2}]
G := [{3, 4}, {3, 4}, {1, 2}, {1, 2}]
;
> factor(add(seq(add(GFt(G, i, t), i = 1 .. 4))))
-4/(2*t-1)
;
> f(t) := -4/(2*t-1)
f(t) := -4/(2*t-1)
;
> 
;
> #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?
> 

;
> #WE SET farmer=f, wolf=w,sheep=s,cabbage=c
;
> #The condition of "cannot being together" forces the farmer have possibility to take people with him on the return journey, or the possibility of not taking people when crossing the river
;
> #let the orginal side be side A,and the opposite side side B
;
> # A      B
;
> #fwsc   [ ]
> #wc     fs     farmer takes sheep
> #wcf    s      farmer returns
> #c      fsw    farmer takes wolf
> #csf    w      farmer returns with sheep
> #s      fcw    farmer takes cabbage
> #fs     cw     farmer returns
> #[]     fscw   farmer takes sheep

;
> #7 steps
;
> 
;
> 
;
> #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?
;
> 
;
> #WE SET missonaries = m, canibals = c
;
> #thus the initial state is {3M3C,[]}, destinate state is {[],3M3C}
;
> #Accordingto constraint, the possible staff combination of the opposite side is
;
> #[],C,2C,3C,CM,3M,3MC,2M2C,3M2C,3M3C   10
;
> #A         B
;
> #3M3C      []       
> #3MC       2C       2C GO         
> #3M2C      C        1C RETURN
> #3M        3C       2C GO
> #3MC       2C       1C RETURN
> #MC        2M2C     2M GO
> #2M2C      MC       1M1C RETURN - balanced
> #2C        3MC      2M GO
> #3C        3M       1C RETURN
> #C         3M2C     2C GO 
> #MC        2M2C     1M RETURN
> #[]        3M3C     1M1C GO

;
> #11 steps
;
> #tried to build graph for a numerical solution but it is hard.sorry.
;