#Ok to post homework
#Michael Yen, 11/1/20, Assignment 15

#Lecture 15: Due Nov. 1, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

#hw15FirstLast.txt

#Indicate whether it is OK to post

#1. Using the same methods in procedures KtG and KiG in ComboProj1.txt, write analogous 
#procedures RoG(k,n), for the graph of a rook on a k by n chess-board, and use SAWnu(G), to find 
#the first few terms of the number of Hamiltonian cycles in a 3 by n chessboard. Is it in the 
#OEIS?

RoG:=proc(k,n) local V,E,i,j,T1,v,Neighs,Moves,m,pt:
#The set the list of  vertices in the k by n board (using matrix indexing)
V:=[seq(seq(seq([i,j],j=1..n),i=1..k))]:

#T1 is a labelling of the vertices in V

for i from 1 to nops(V) do
T1[V[i]]:=i:
od:

#E is a list such that its i-th entry is the set of neighbors of V[i] using the above-indexing

E:=[]:

for i from 1 to nops(V) do
 pt:=V[i]:

#for pt = [x,y], Moves = {[1,0],[2,0],...,[k-x,0], [-1,0],[-2,0],...,[-(x-1)], [0,1],[0,2],...,[n-y],[0,-1],[0,-2],...,[0,-(y-1)]}

Moves:={seq([i,0], i=1..k-pt[1]),seq([-i,0], i=1..pt[1]-1),seq([0,i], i=1..n-pt[2]),seq([0,-i], i=1..pt[2]-1)}:
#There are up to 8 neighbors of any vertex 
Neighs:={seq(pt+m,m in Moves)}:

#But many of them fall off the board, 
Neighs:=Neighs intersect convert(V,set):

#We append to the "list of neighbors" the set of neighbors of the current vertex BUT in terms of their "ids" (given by T1)
#getting a description of the graph in "cannical form"
E:=[op(E),{seq(T1[v],v in Neighs)}]:
od:

#We return the graph in "canonical form" where the vertices (members of V), are labelled by positive integers from 1 to nops(V)
#together with the "dictionary"
E,V:
end:

seq(SAWnu(RoG(3,i)[1],i=1..10) 

#takes too long at i=7 so I just did it individually up until i=6
#2,6,96,3132,252240,36307440
#Not in the OEIS

#2. Start exploring ComboProj2.txt, and use it to find the number of ways of walking from [0,0] 
#to [40,40] with atomic steps {[1,0],[0,1],[1,1],[2,2]}
#How many of these never go above x=y?

NuW([40, 40], {[0, 1], [1, 0], [1, 1], [2, 2]});
                #2382564832244243056285491057263

#Never above x=y:
NuGW([40, 40], {[0, 1], [1, 0], [1, 1], [2, 2]});
                 #89322096703094945357683861273

#Start exploring ComboProj3.txt, and use it to find the first 20 terms of of the sequence 
#enumerating walks from [0,0,0] to [n,n,n] with atomic steps {[1,0,0],[0,1,0],[0,0,1],[1,1,1]}. #What is the corresponding sequence for those walks that stay in x ≥ y ≥ z ?

SeqW({[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]}, 20);
#[7, 115, 2371, 54091, 1307377, 32803219, 844910395, 22188235867, 591446519797, 15953338537885, 434479441772845, 11927609772412075, 329653844941016785, 9163407745486783435, 255982736410338609931, 7181987671728091545787, 202271071826031620236525, 5715984422606794841997001, 162016571360163769411597081, 4604748196249289767697705221]

# x ≥ y ≥ z:
SeqGW({[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]}, 20);
#[2, 10, 88, 1043, 14778, 236001, 4107925, 76314975, 1491934038, 30389576308, 640286048416, 13877540824735, 308102204007536, 6983346070924707, 161156356282624227, 3778249609096250059, 89826197363219012470, 2162338803354415120414, 52637415804379149938876, 1294313658632145337351381]