#OK to post homework
#Wanying Rao, 04/25/2021, Assignment 25

#1
HookSet := proc(L,cell) local i,S,R,D,m:

if not cell[1]>=1 and cell[1]<=nops(L) and cell[2]>=1 and cell[2]<=L[cell[1]] then
 RETURN(FAIL):
fi:

S := {cell}:

R := {seq([cell[1],i],i=cell[2]+1..L[cell[1]])}:

m := nops(L):
while L[m] < cell[2] do
m := m-1:
od:

D := {seq([j,cell[2]],j=cell[1]+1..m)}:

S union R union D:
end:

#2
OneStepGNW := proc(L) local n,r,Y,cell,H:

n := add(L):
cell := [1,1]:
while nops(HookSet(L,cell))<>1 do
 H := HookSet(L,cell) minus {cell}:
 r := rand(1..nops(H))():
 cell := H[r]:
od:

cell:
end:

#3
GNW := proc(L) local cell,n,L1,Y1,Y:

n := add(L):

if n = 1 then
 RETURN([[1]]):
fi:

cell := OneStepGNW(L):
L1 := L:
L1[cell[1]] := L1[cell[1]]-1:
Y1 := GNW(L1):

if cell[1] <= nops(Y1) then
 Y := [op(1..cell[1]-1,Y1),[op(Y1[cell[1]]),n],op(cell[1]+1..nops(Y1),Y1)]:
fi:
if cell[1] = nops(Y1)+1 then
 Y := [op(1..cell[1]-1,Y1),[n]]:
fi:

Y:
end: