#Please do not post homework
#AJ Bu, April 22 2021, Assignment 25


####################	PROBLEM 1	####################

#HookSet(L,cell): inputs a shape L and a cell [i,j], with 1≤ i ≤nops(L), 
#1 ≤ j ≤ L[i], and outputs set set of all cells that are (weakly) to the 
#right in the same row, and (weakly) down in the same column.

HookSet:=proc(L,cell) local k:
	k:=nops(L):
	while L[k]<cell[2] do
		k:=k-1:
	od:

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


####################	PROBLEM 2	####################

#OneStepGNW(L): implements one iteration of the beautiful 
#Greene-Nijenhuis-Wilf algorithm, by starting at cell [1,1] 
#and "walking" to a corner cell, by at each step, 
#(if you are currently at location cell), picking UNIFORMALLY 
#at random a member of HookSet(L,cell) minus {cell}
#and going there, until you hit a corner cell, placing n there.

OneStepGNW:=proc(L) local cell,S,corners,n1,n2,i,H1,k,r:
	cell:=[1,1]:
	S:=convert(L,set):
	corners:={seq([i,L[i]],i=1..nops(L))}: 
	n1:=nops(corners): 
	n2:=nops(S):
	i:=1:
	
	while n1<>n2 do
		if corners[i][2]=corners[i+1][2] then
			corners:=corners minus {corners[i]}: 
			n1:=n1-1: 
		else 
			i:=i+1:
		fi:
	od: 
	

	while not member(cell,corners) do
		H1:=HookSet(L,cell) minus {cell}:
		k:=nops(H1): 
		r:=rand(1..k)(): 
		cell:=H1[r]:
	od:
	cell:
end:


####################	PROBLEM 3	####################
GNW:=proc(L) local n,T,L1,cell:
	n:=add(L):
	T:=[seq([seq(0,j=1..L[i])],i=1..nops(L))]:
	L1:=L:
	
	while n<>0 do
		cell:=OneStepGNW(L1): 
		T:=[ op( T[1..cell[1]-1]),[ op(T[cell[1]][1..cell[2]-1]),n,
		       op( T[cell[1]][cell[2]+1..nops(T[cell[1]])]) ],
				op( T[cell[1]+1..nops(T)])]:
		L1:=[op( L1[1..cell[1]-1]), L1[cell[1]]-1,
			op( L1[ cell[1]+1..nops(L1) ] )]: 
		n:=n-1:
	od:
	T:
end:
		
#it took 0 seconds.

####################	PROBLEM 4	####################

#See attached PDF