#OK to post homework
#Karnaa Mistry, 11/1/20, Assignment HW #15

with(combinat):

# 1. 

#RoG(k,n): The Rook graph on a k by n board
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:

Moves:={}: 

for i from -k+1 to k-1 do:
  Moves:=Moves union {[i,0]}:
od:

for i from -n+1 to n-1 do:
  Moves:=Moves union {[0,i]}:
od:

Moves:=Moves minus {[0,0]}:

#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]:

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 inetegers from 1 to nops(V)
#together with the "dictionary"
E,V:
end:

# seq(SAWnu(RoG(3,n)[1]),n=1..5) = 2, 6, 96, 3132, 252240
# This does not appear to be in the OEIS




# 2.

# NuW([40,40],{[1,0],[0,1],[1,1],[2,2]}) = 2382564832244243056285491057263
# 89322096703094945357683861273 never go above x=y  (NuGW([40,40],{[1,0],[0,1],[1,1],[2,2]}))



# seq(NuW([n,n,n],{[1,0,0],[0,1,0],[0,0,1],[1,1,1]}),n=0..19)
# = 1, 7, 115, 2371, 54091, 1307377, 32803219, 844910395, 22188235867, 591446519797, 15953338537885, 434479441772845, 11927609772412075, 329653844941016785, 
# 9163407745486783435, 255982736410338609931, 7181987671728091545787, 202271071826031620236525, 5715984422606794841997001, 162016571360163769411597081, 

# The corresponding sequence, seq(NuGW([n,n,n],{[1,0,0],[0,1,0],[0,0,1],[1,1,1]}),n=0..19),
# = 1, 2, 10, 88, 1043, 14778, 236001, 4107925, 76314975, 1491934038, 30389576308, 640286048416, 13877540824735, 308102204007536, 6983346070924707, 
# 161156356282624227, 3778249609096250059, 89826197363219012470, 2162338803354415120414, 52637415804379149938876