#Ok to post homework
#Tifany Tong, November 1st, 2020, HW #15

# Question 1

RoG := proc(k, n) local V, E, i, j, T1, v, Neighs, Moves, m, pt:
V := [seq(seq(seq([i, j], j = 1 .. n), i = 1 .. k))]:
for i to nops(V) do T1[V[i]] := i: od:
E := []:
Moves := {}:
for i to k - 1 do 
    Moves := Moves union {[-i, 0], [i, 0]}:
od:
for i to n - 1 do 
    Moves := Moves union {[0, -i], [0, i]}: 
od:
for i to nops(V) do 
    pt := V[i]:
    Neighs := {seq(pt + m, m in Moves)}:
    Neighs := Neighs intersect convert(V, set):
    E := [op(E), {seq(T1[v], v in Neighs)}]:
od:
E, V:
end:

# 2,6,96,3132,252240 --> Not in the OEIS

# Question 2

#Number of ways to walk from [0,0] to [40,40] with atomic steps {[0, 1], [1, 0], [1, 1], [2, 2]}:
# SeqW({[0, 1], [1, 0], [1, 1], [2, 2]}, 40) = 2382564832244243056285491057263

#Number of good ways to walk from [0,0] to [40,40] with atomic steps {[0, 1], [1, 0], [1, 1], [2, 2]}:
# SeqGW({[0, 1], [1, 0], [1, 1], [2, 2]}, 40) = 89322096703094945357683861273

#First 20 terms 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]}:
#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]

#First 20 terms of the good 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]}:
#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]