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

#1.Write procedures GNuWalks2D(A,pt), and GRandWalk2D(A,pt), that inputs a list of atomic #steps A (in 2 dimensions) and output, respectively, the number of subdiagonal steps using #A and ending at pt, and a (uniformally) at random such good walk.

GNuWalks2D := proc (A, pt)local i,W,W1,w:
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
 W1 := GNuWalks2D(A,pt-A[i]):
 W := W + W1:
od:

W:
end:


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

r:=LD(Die1):

W1:=GRandWalk2D(A,pt-A[r]):

[op(W1),pt]:

end:

#2
#(i)seq(NuWalks2D([[1,0],[0,1]],[i,i]),i=1..20):
#[2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, #155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820]
#A000984

#(ii)seq(GNuWalks2D([[1,0],[0,1]],[i,i]),i=1..20):
#[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, #35357670, 129644790, 477638700, 1767263190, 6564120420]
#A000108

#(iii)seq(NuWalks2D([[1,0],[0,1],[2,0],[0,2]],[i,i]),i=1..20):
#[2, 14, 84, 556, 3736, 25612, 177688, 1244398, 8777612, 62271384, 443847648, 3175924636, #22799963576, 164142004184, 1184574592592, 8567000931404, 62073936511496, 450518481039956, #3274628801768744, 23833760489660324]
#A036692

#(iv)seq(GNuWalks2D([[1,0],[0,1],[2,0],[0,2]],[i,i]),i=1..20):
#[1, 5, 22, 117, 654, 3843, 23323, 145172, 921508, 5942737, 38825546, 256431172, #1709356836, 11485249995, 77703736926, 528893901963, 3619228605738, 24884558358426, #171828674445330, 1191050708958096]
#A122951

#(v)seq(NuWalks2D([[1,0],[0,1],[2,0],[0,2],[3,0],[0,3]],[i,i]),i=1..20):
#[2, 14, 106, 784, 6040, 47332, 375196, 3001966, 24190148, 196034522, 1596030740, #13044459766, 106961525744, 879512777006, 7249483605580, 59881171431050, 495545064567260, #4107666916668414, 34099685718629264, 283454909832384416]
#A122680

#(vi)seq(GNuWalks2D([[1,0],[0,1],[2,0],[0,2],[3,0],[0,3]],[i,i]),i=1..20):
#[1, 5, 29, 170, 1093, 7346, 50957, 362476, 2629150, 19371533, 144585146, 1090886362, #8306621114, 63752890716, 492671044866, 3830272606911, 29937476853483, 235104315621495, #1854181694878573, 14679397763545597]
#A175883

#(vii)seq(NuWalks2D([[1,0],[0,1],[1,1]],[i,i]),i=1..20):
#[3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453, 45046719, 251595969, #1409933619, 7923848253, 44642381823, 252055236609, 1425834724419, 8079317057869, #45849429914943, 260543813797441]
#A001850

#(viii)seq(GNuWalks2D([[1,0],[0,1],[1,1]],[i,i]),i=1..20):
#[2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738, 142078746, #745387038, 3937603038, 20927156706, 111818026018, 600318853926, 3236724317174, #17518619320890]
#A006318

#(ix)seq(NuWalks2D(FootBall(),[i,i]),i=1..20):
#[0, 2, 2, 6, 24, 62, 206, 712, 2076, 7284, 22684, 75222, 246172, 805462, 2658588, #8763448, 28932292, 95870878, 317416080, 1053931874]

#(x) seq(GNuWalks2D(FootBall(),[i,i]),i=1..20):
#[0, 1, 1, 2, 7, 16, 45, 144, 368, 1189, 3379, 10331, 31444, 95903, 296812, 921138, #2870493, 9014628, 28346277, 89641760]


#3.(i)Using NuWalks2D and GNuWalks2D (that you wrote), conjecture an explicit expression #for the probability that in a soccer game that ended with a tie [n,n], the visiting team #was Never (striclty) leading.

#The probability is 1/n.


#4.Estimate the analogous probability for an American football game. Try to conjecture a #form for the asymptotics of that probability. Is it like 1/n^alpha for some alpha?

#seq(NuWalks2D(FootBall(), [i, i]), i = 1 .. 20):
#[0, 2, 2, 6, 24, 62, 206, 712, 2076, 7284, 22684, 75222, 246172, 805462, 2658588, #8763448, 28932292, 95870878, 317416080, 1053931874]

#seq(GNuWalks2D(FootBall(), [i, i]), i = 1 .. 20):
#[0, 1, 1, 2, 7, 16, 45, 144, 368, 1189, 3379, 10331, 31444, 95903, 296812, 921138, #2870493, 9014628, 28346277, 89641760]



#5 Generalize to k-dimensional NuWalks2D(A,pt), GNuWalks2D(A,pt) to write procedures
#NuWalkskD(A,pt) and GNuWalkskD(A,pt)

NuWalkskD := proc(A,pt) local k,i,j,W,W1,w:
option remember:

k := nops(pt):

for j from 1 to k do
 if pt[j]<0 then
  RETURN(0):
 fi:
od:

if pt=[0$k] then
 RETURN(1):
fi:

W:=0:

for i from 1 to nops(A) do
 W1:=NuWalkskD(A,pt-A[i]):
 W:=W + W1:
od:

W:
end:


GNuWalkskD := proc (A, pt) local k,i,j,s,t,W,W1,w:
option remember:

k := nops(pt):
for j from 1 to k do
 if pt[j]<0 then
  RETURN(0):
 fi:
od:

for s from 1 to k-1 do
 for t from s+1 to k do
  if pt[s]<pt[t] then
   RETURN(0):
  fi:
 od:
od:

if pt=[0$k] then
 RETURN(1):
fi:

W:=0:

for i from 1 to nops(A) do
 W1 := GNuWalkskD(A,pt-A[i]):
 W := W + W1:
od:

W:
end:

#(i) seq(NuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..10):
#[6, 90, 1680, 34650, 756756, 17153136, 399072960, 9465511770, 227873431500, #5550996791340]
#A006480

#(ii) seq(GNuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..10):
#[1, 5, 42, 462, 6006, 87516, 1385670, 23371634, 414315330, 7646001090]
#A005789

#(iii) seq(NuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..10):
#[24, 2520, 369600, 63063000, 11732745024, 2308743493056, 472518347558400, #99561092450391000, 21452752266265320000, 4705360871073570227520]
#A008977

#(iv) seq(GNuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..10):
#[1, 14, 462, 24024, 1662804, 140229804, 13672405890, 1489877926680, 177295473274920, #22661585038594320]
#A005790





##FROM C6.txt
FootBall:=proc():
[[0,2],[0,3],[0,6],[0,7],[0,8],[2,0],[3,0],[6,0],[7,0],[8,0]]:
end:

##FROM C4.txt
#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: