#Ok to post homework
#Hari Amoor, 10/25, HW #13

# Question 1

# A:={h,a,r,i,m,o}

# (i) Consonants: {h(1),r(2),m(3)}
#     Vowels: {a(4),i(5),o(6)}

# add(seq(add(GFt([{6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}], i, t), i = 1 .. 8)))

# coeff(taylor(-30*t/(15*t^2 + 3*t - 1) + 5*(12*t^2 + 3*t - 1)/(15*t^2 + 3*t - 1) - 60*t^2/(15*t^2 + 3*t - 1) + 3*(10*t^2 + 2*t - 1)/(15*t^2 + 3*t - 1) - 6*t*(5*t + 1)/(15*t^2 + 3*t - 1), t = 0, 101), t, 100) = 
# 12321340393698231163342176217144212209486354822155180752687005498958907412883

# (ii) Consonants: {h(1),r(2),m(3)}
#     Vowels: {a(4),i(5),o(6)}

# add(seq(add(GFt([{1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}], i, t), i = 1 .. 8)))

# coeff(taylor(-30*t/(15*t^2 + 5*t - 1) + 5*(2*t + 1)*(6*t - 1)/(15*t^2 + 5*t - 1) - 20*t*(3*t + 1)/(15*t^2 + 5*t - 1) + 3*(10*t^2 + 5*t - 1)/(15*t^2 + 5*t - 1) - 30*t^2/(15*t^2 + 5*t - 1), t = 0, 101), t, 100) =
# 119524344066206672461536089579447816929356634429481420767160670948214828968048095703125

# (iii) add(seq(add(GFt([{6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}], i, t), i = 1 .. 8)))

# coeff(taylor(%, t = 0, 101), t, 100) =
# 510097200171239669522726245531885069794952869415283203125000

# (iv) 

# a(1) = 30
# a(2) = 120
# a(3) = 450
# a(4) = 1800
# a(5) = 6750
# a(6) = 27000

# The general explicit form can be computed with the following code, as requested: factor(add(seq(add(GFt([{6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}], i, t), i = 1 .. 8))))

# Question 2

# First, I computed the shortest paths in the graph with the following code: 
# seq(Paths([{2},{1,3}, {2,4,5}, {3,6}, {3,7}, {4,8}, {5,8}, {6,7,9}, {8,10}, {9}],1,8,i),i=1..10)

# They are as follows: {[1, 2, 3, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 8, 9, 10]}. 

# We construct the graph described as follows:

# Here, (1) corresponds to the number of sheeps on the right side; (2) corresponds to the number of cabbages
# on the right side, and; (3) corresponds to the number of wolves on the right side. The symbol (3) in {L, R} represents
# whether the boat is on the left or the right side.

# Our initial state is 000L, and a solution state is 111R. We achieve our solution state as follows.

# 1: 000L
# 2: 100R
# 3: 100L
# 4: 101R
# 5: 110R
# 6: 001L
# 7: 010L
# 8: 011R
# 9: 011L
# 10: 111R 

# Question 4

# With the result of the following code:
# seq(Paths[{2,3,4}, {1}, {1,5}, {1,5}, {3,4,6}, {5,7}, {6,8}, {7,9}, {8,10}, {9,11}, {10,12}, {11,13,14}, {12,15}, {12,15}, {13,14}],1,15,i),i=1..15)

# We compute that the desired shortest paths are: 
#            {[1, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15], 
#            [1, 3, 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]}

# In the same notation as before, the following is a graph of 3-tuples of the form (M, C, B),
# where M is the number of missionaries on the left, C is the number of cannibals on
# the left, and B is a symbol in {L,R} to represent whether the boat is at the left or right.
# 1: 3,3,L
# 2: 3,2,R
# 3: 3,1,R
# 4: 2,2,R
# 5: 3,2,L
# 6: 3,0,R
# 7: 3,1,L
# 8: 1,1,R
# 9: 2,2,L
# 10: 0,2,R
# 11: 0,3,L
# 12: 0,1,R
# 13: 0,2,L
# 14: 1,1,L
# 15: 0,0,R

# From this, we can determine a solution.