#Ok to post homework
#Tifany Tong, October 25th, 2020, HW #13

# Question 1

# A:={t,i,f,a,n,y,o,g}

# (i) Consonants: {t(1),f(2),n(3),y(4),g(5)}
#     Vowels: {i(6),a(7),o(8)}

# 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))) =
# -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)


# 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: {t(1),f(2),n(3),y(4),g(5)}
#     Vowels: {i(6),a(7),o(8)}

# 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))) =
# = -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)


# 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))) = 
#        /    2    \         2                   /    2    \
#      5 \12 t  - 1/     90 t        30 t      3 \10 t  - 1/
#      ------------- - --------- - --------- + -------------
#            2             2           2             2      
#        15 t  - 1     15 t  - 1   15 t  - 1     15 t  - 1  

# 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 is 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)))) = 
                           2 (15 t + 4)
                         - ------------
                                2      
                            15 t  - 1  




# Question 2

# I did 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) and found the smallest paths were {[1, 2, 3, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 8, 9, 10]}. 
# [1, 2, 3, 4, 6, 8, 9, 10] represents moving the sheep to the final area, go back and pick up the wolf and bring it to the final area. Take the sheep at the
# final area and bring it back to the starting area. Pick up the cabbage and bring it to the final area. Leave the cabbage and wolf and go back
# to the starting area. Pick up the sheep and bring it to the final area. Now, you have all 3 together in 7 steps.

# I created a graph of the valid paths that could be made from a position. The numbers correspond with the following positions.
# They follow the format of (#1, #2, #3, L/R). #1 corresponds to the number of sheeps on the right side. #2 corresponds to the number of cabbages
# on the right side. #3 corresponds to the number of wolves on the right side. L/R is whether the boat is on the left or right side.
# We are trying to go from the starting state 000L to 111R. 

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

# Question 4

# I did 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)
# and found that the smallest paths were: 
#            [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]

# I created a graph of the valid paths that could be made from a position. I used the notation (#1,#2,R/L) where #1 corresponds to the number of 
# missionaries on the left side and #2 corresponds to the number of cannibals on the left side. R/L is the position of the boat. 
# 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

Here is our answer: 
# 1: 3,3,L
# 3: 3,1,R We bring two cannibals to the right
# 5: 3,2,L We return back with one cannibal
# 6: 3,0,R We bring both cannibals to the right
# 7: 3,1,L We return back with one cannibal to the left
# 8: 1,1,R We bring 2 missionaries to the right
# 9: 2,2,L We return back 1 missionary and 1 cannibal 
# 10: 0,2,R We bring 2 missionaries
# 11: 0,3,L We return with a cannibal 
# 12: 0,1,R We bring 2 cannibals over
# 14: 1,1,L We return with a cannibal
# 15: 0,0,R We bring 1 cannibal and 1 missionary, leaving us with everyone on the right side.