#OK to post homework
#Karnaa Mistry, 10/25/20, Assignment HW #13

with(combinat):

# 1. 

# i)
# Vi:= [a=1,i=2,k=3,m=4,n=5,r=6,s=7,t=8,y=9]
# Gi:= [{2,3,4,5,6,7,8,9}, {1,3,4,5,6,7,8,9}, {1,2,9}, {1,2,9}, {1,2,9}, {1,2,9}, {1,2,9}, {1,2,9}, {1,2,3,4,5,6,7,8}]
# coeff(taylor(normal(add(convert(GFt(Gi,i,t),`+`),i=1..9)),t=0,101),t,100)
# = 66968118251560957429577618130322703527325362864114617575105760736139280384 words

# ii)
# Vii:= [a=1,i=2,k=3,m=4,n=5,r=6,s=7,t=8,y=9]
# Gii:= [{3,4,5,6,7,8}, {3,4,5,6,7,8}, {1,2,4,5,6,7,8,9}, {1,2,3,5,6,7,8,9}, {1,2,3,4,6,7,8,9}, {1,2,3,4,5,7,8,9}, {1,2,3,4,5,6,8,9}, {1,2,3,4,5,6,7,9}, {3,4,5,6,7,8}]
# coeff(taylor(normal(add(convert(GFt(Gii,i,t),`+`),i=1..9)),t=0,101),t,100)
# = 10387526331734988770675763643075223648752673215357741801324138989326035535638432972412616 words

# iii)
# Viii:= [a=1,i=2,k=3,m=4,n=5,r=6,s=7,t=8,y=9]
# Giii:= [{3,4,5,6,7,8}, {3,4,5,6,7,8}, {1,2,9}, {1,2,9}, {1,2,9}, {1,2,9}, {1,2,9}, {1,2,9}, {3,4,5,6,7,8}]
# coeff(taylor(normal(add(convert(GFt(Giii,i,t),`+`),i=1..9)),t=0,101),t,100)
# = 5222371523228586691507591059411304343770770758809435324721135616

# iv)
# f(t) is the generating function for the number of n-lettered words in my alphabet where no two vowels nor consonants are adjacent
# f(t) = sum( a(n) * t^n, n=0..infinity) by definition of a generating function, where a(n) = 9,36,162,648,2916,... otherly
# written as a(n) = 9*product((17/4 + 1/4 * (-1)^i),i=1..n). (first number is 9, then it alternates multiplying by 4 and 4.5 forever)
# However, since this sequence is alternating, I'm not sure how to write it as a C-recursive sequence, and thus obtain the specific
# generating function in its own simple form, as I have a(0) = 9, a(1) = 4*a(0), a(1) = 4.5*a(2), a(3) = 4*a(2), ...




# 2.

# Let Gx be our graph of possible groups to be left on each side, with lowercase meaning on the initial side of the river, and capital @ the destination
# Gx:= [{fwsc}, {fws C},{fwc S},{fcs W},{csw F}, {fw SC},{fs WC},{fc WS},{sc FW},{ws FC},{wc FS}, {c FWS},{s FWC},{w FCS},{f CSW}, {FWSC}  ]
# Manually eliminate all possibilities that aren't allowed to get Gy
# Gy:= [{fwsc}, {fws C},{fwc S},{fcs W}, {fs WC},{wc FS}, {c FWS},{s FWC},{w FCS}, {FWSC}  ]
# assigning numbers to each element of Gy, 1 to 10, then finding which elements can be adjacent events to get relationships
# We know that only the farmer must always row the boat, and that there will be a single extra passenger, so don't necessarily have to worry
# about keeping track of the boat as an object (for this simpler problem), as we just have to make sure the farmer alternates lowercase f
# and capital F.  So, we have:
# 1 {6} ; 2 {8,9} ; 3 {6,7,9} ; 4 {7,8} ; 5 {8,10} ; 6 {1,3} ; 7 {3,4} ; 8 {2,4,5} ; 9 {2,3} ; 10 {5}
# So, Gz:= [{6}, {8,9}, {6,7,9}, {7,8}, {8,10}, {1,3}, {3,4}, {2,4,5}, {2,3}, {5}]

# We do seq(Paths(Gz,1,10,i),i=1..9) and find the shortest paths to be where i=7, which are {[1, 6, 3, 7, 4, 8, 5, 10], [1, 6, 3, 9, 2, 8, 5, 10]}
# So, the farmer must bring the sheep over first, then come back, then there are two options:
#	a) Bring the cabbage over
#		- Then, the farmer must bring the sheep back, then pick up the wolf, bring the wolf over to the cabbage, then come back for the sheep
#	b) Bring the wolf over
#		- Then, the farmer will again bring the sheep back, then pick up the cabbage, bring that to the lone wolf, then come back for the sheep
# Then, all 4 have crossed the river.




# 4.

# Let Gx be our graph of possible groups to be left on each side, with lowercase meaning on the initial side of the river, and capital @ the destination
# Gx:= [{mmmccc}, {mmmcc C}, {mmccc M}, {mmcc MC}, {mccc MM}, {mmmc CC}, {mmm CCC}, {ccc MMM}, {mc MMCC}, {mm MCCC}, {cc, MMMC}, {c MMMCC}, {m MMCCC}, {MMMCCC} ]
# Manually eliminate all possibilities that aren't allowed to get Gy; we must also keep track of possible boat {B} locations!

# Gy:= [{mmmcccb}, {mmmccb C}, {mmccb MC}, {mmmcb CC}, {cccb MMM}, {mcb MMCC}, {ccb MMMC}, {cb MMMCC},
#	{mmmcc CB}, {mmcc MCB}, {mmmc CCB}, {mmm CCCB}, {mc MMCCB}, {cc MMMCB}, {c MMMCCB}, {MMMCCCB}]
#	note: mmmb CCC  and  ccc MMMB won't work, because in order to bring the boat back, the missionaries would be outnumbered
	
# assigning numbers to each element of Gy, 1 to 10, then finding which elements can be adjacent events to get relationships

# We know that only 1 or 2 people may move across, so accounting for which side the boat is on, we get:
# 1 {11,10,9} ; 2 {11,10,12} ; 3 {13,14} ; 4 {12,13} ; 5 {14,15} ; 6 {15,16} ; 7 {15,16} ; 8 {16} ; 9 {1} ; 10 {1,2} ;
# 11 {1,2} ; 12 {2,4} ; 13 {3,4} ; 14 {3,5} ; 15 {5,6,7} ; 16 {6,7,8}

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

# We do seq(Paths(Gz,1,10,i),i=1..16) and find the shortest paths to be where i=11, which are {[1,10,2,12,4,13,3,14,5,15,6,16], [1,11,2,12,4,13,3,14,5,15,6,16]}
# So, we have steps like:
#  1) Bring either 2 cannibals or 1 of each over first (mmmcccb -> mmcc MCB or mmmc CCB)
#  2) Send 1 cannibal back, and pick up a cannibal to go across (mmcc MCB or mmmc CCB -> mmmccb C -> mmm CCCB)
#  3) Send another cannibal back, and have 2 missionaries cross (mmm CCCB -> mmmcb CC -> mc MMCCB)
#  4) Have a pair of MC go back, then send the 2 missionaries across (mc MMCCB -> mmccb MC -> cc MMMCB)
#  5) One cannibal goes back to bring a cannibal friend over (cc MMMCB -> cccb MMM -> c CCMMM)
#  6) Send either 1 more cannibal back to get the last cannibal friend, or send 1 missionary to do the job (c CCMMM -> ccb MMMC or mcb MMCC -> MMMCCCB)

# Then, all 6 have crossed the river, and nobody was eaten.