#OK to post homework 
#Zhizhang Deng, 10/30/2020, Assignment 15

1. 
    #RoG(k,n): The Rook graph on a k by n board
    RoG:=proc(k,n) local V,E,i,j,T1,v,x,y,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:
        end do; 

        # dynamicaly construct Moves 
        # horizontally we can move [0, -n] -> [0, n]. The intersection would remove invalid points anyways
        # vertically we can move [-k, 0] -> [k, 0]. 
        Moves := {};

        # horizontally 
        for x from -n to n by 1 do
            if x = 0 then
                next;   # can't stay in place 
            end if; 
            Moves := Moves union {[0, x]}; 
        end do;

        # vertically
        for y from -k to k by 1 do
            if y = 0 then
                next;
            end if; 
            Moves := Moves union {[y, 0]}; 
        end do;

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

            
            #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)}]:
        end do; 

        #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"
        return E,V:
    end:
    ============================
    seq(SAWnu(RoG(3, n)[1]), n = 1 .. 5);
    = 2, 6, 96, 3132, 252240
    This is not in OEIS. 

2. 
    Part 1. 

    NuW([40, 40], {[0, 1], [1, 0], [1, 1], [2, 2]});
     = 2382564832244243056285491057263 ways to walk to 40,40 using given atomic steps

    NuGW([40, 40], {[0, 1], [1, 0], [1, 1], [2, 2]});
     = 89322096703094945357683861273 ways to walk to 40,40 using given atomic steps while never go above x=y. 

    =======================
    Part 2. 

    seq(NuW([n, n, n], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]}), n = 1 .. 20);
        7, 115, 2371, 54091, 1307377, 32803219, 844910395, 22188235867, 

        591446519797, 15953338537885, 434479441772845, 

        11927609772412075, 329653844941016785, 9163407745486783435, 

        255982736410338609931, 7181987671728091545787, 

        202271071826031620236525, 5715984422606794841997001, 

        162016571360163769411597081, 4604748196249289767697705221

    seq(NuGW([n, n, n], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]}), n = 1 .. 20);
    2, 10, 88, 1043, 14778, 236001, 4107925, 76314975, 1491934038, 

    30389576308, 640286048416, 13877540824735, 308102204007536, 

    6983346070924707, 161156356282624227, 3778249609096250059, 

    89826197363219012470, 2162338803354415120414, 

    52637415804379149938876, 1294313658632145337351381