#OK to post homework
#George Spahn, 2/14/2021, Assignment 6

#GNuWalks2D(A,pt) Inputs a list of atomic steps A (in 2 dimensions) and output
#the number of subdiagonal steps using A and ending at pt 
GNuWalks2D:=proc(A,pt) local W,i:
option remember:
if (pt[1]<0 or pt[2]<0 or pt[1]<pt[2]) then
 RETURN(0):
fi:
if pt=[0,0] then
 RETURN(1):
fi:
W:=0:
for i from 1 to nops(A) do
 W:=W + GNuWalks2D(A,pt-A[i])
od:
W:
end:


#GRandWalk2D(A,pt) Inputs a list of atomic steps A (in 2 dimensions) and output
#and a (uniformally) at random such good walk
GRandWalk2D:=proc(A,pt) local i,W1,Die1,r:
if (pt[1]<0 or pt[2]<0 or pt[1]<pt[2]) then
 RETURN(FAIL):
fi:
if pt=[0,0] then
   RETURN([[0,0]]):
fi:
Die1:=[seq(GNuWalks2D(A,pt-A[i]),i=1..nops(A))]:
#Let r be the index in A of the last step in our uniform-random walk
#that ended at pt 
r:=LD(Die1):
W1:=GRandWalk2D(A,pt-A[r]):
[op(W1),pt]:
end:


# (i) A000984 central binomial coefficients

# (ii) A000108 Catalan numbers

# (iii) A036692
 
# (iv) A122951

# (v) A122680

# (vi) A175883

# (vii) A001850 central Delannoy numbers

# (viii) A006318 large schroeder numbes

# (x) not in oeis

# (x) not in oeis


# (3) I verified with maple that the formula 1/(n+1) gives the correct 
# probability for n=1..20





#NuWalkskD(A,pt) NuWalks2D generalized to k dimensions
NuWalkskD:=proc(A,pt) local k,i,W:
option remember:
k:=nops(pt):
if min(pt)<0  then
 RETURN(0):
fi:
if max(pt)=0 then
 RETURN(1):
fi:
W:=0:
for i from 1 to nops(A) do
 W:=W + NuWalkskD(A,pt-A[i])
od:
W:
end:


# Im not sure how to generalize the subdiagonal walks.

# (i) A006480

# (iii) A008977 



#LD(L): Inputs a list of positive integers L (of n:=nops(L) members)
#outputs an integer i from 1 to n with the prob. of i being
#proportional to L[i]
#For example LD([1,2,3]) should output 1 with prob. 1/6
#output 2 with prob. 1/3
#output 3 with prob. 3/6=1/2
LD:=proc(L) local n,i,su,r:
n:=nops(L):
r:=rand(1..convert(L,`+`))():
su:=0:

for i from 1 to n do
 su:=su+L[i]:
  if r<=su then
    RETURN(i):
  fi:
od:
end: