#Nathan Fox
#Homework 10
#I give permission for this file to be posted online

##Read old files
read(`C10.txt`):

#Help procedure
Help:=proc() :
print(` FG(L,r) , fG(L,r,i) , LegalMovesG(L,i) `):
print(` FP(L,r) , fP(L,r,i) `):
print(` FR(L,r) , fR(L,r,i) , FTest(startr,endr) `):
end:

##Problem 1
#FG(L,r): inputs a list L of nonnegative integers L and
#a positive integer r, and outputs the expected number of
#rolls until the end under GREEDY play
FG:=proc(L,r) local i:
option remember:

add(fG(L,r,i)[2],i=1..r)/r:

end:

#fG(L,r,i): inputs L and r as above and i between 1 and r
#and outputs the GREEDY move, followed by the
#expected length if you do it
fG:=proc(L,r,i) local Moves:
option remember:
Moves:=LegalMovesG(L,i):

if Moves={} then
    RETURN(FAIL,0):
fi:

Moves[1],(1+FG(Moves[1],r)):

end:

#LegalMovesG(L,i): inputs a list of length nops(L)
#of nonnegative integers and a positive integer i telling
#you that you have the option to move any counter i pieces
#towards the end, without waste, and if you must be wasteful,
#minimize it
#returns a singleton set containing the greedy move
LegalMovesG:=proc(L,i) local j:

if i>nops(L) then
    return LegalMovesG(L,nops(L)):
fi:

if L=[0$nops(L)] then
    return {}:
fi:

if L[i]>0 then
    return {[op(1..i-1,L),L[i]-1,op(i+1..nops(L),L)]}:
fi:

for j from i+1 to nops(L) do
    if L[j]>0 then
        return {[op(1..j-i-1,L),L[j-i]+1,op(j-i+1..j-1,L),L[j]-1,
            op(j+1..nops(L),L)]}:
    fi:
od:

for j from i-1 by -1 to 1 while L[j]=0 do od:

{[op(1..j-1,L),L[j]-1,op(j+1..nops(L),L)]}:

end:

##Problem 2
#FP(L,r): inputs a list L of nonnegative integers L and
#a positive integer r, and outputs the expected number of
#rolls until the end under PESSIMAL play
FP:=proc(L,r) local i:
option remember:

add(fP(L,r,i)[2],i=1..r)/r:

end:

#fP(L,r,i): inputs L and r as above and i between 1 and r
#and outputs the PESSIMAL move, followed by the
#expected length if you do it
fP:=proc(L,r,i) local rec,champ,Moves,hopeful:
option remember:
Moves:=LegalMoves(L,i):

if Moves={} then
    RETURN(FAIL,0):
fi:

champ:=Moves[1]:

rec:=FP(champ,r):

for hopeful in Moves minus {Moves[1]} do
    if FP(hopeful,r)>rec then
        champ:=hopeful:
        rec:=FP(champ,r):
    fi:
od:

champ,rec+1:

end:

##Problem 3
#FR(L,r): inputs a list L of nonnegative integers L and
#a positive integer r, and outputs the expected number of
#rolls until the end under RANDOM play
FR:=proc(L,r) local i:
option remember:

add(fR(L,r,i),i=1..r)/r:

end:

#fR(L,r,i): inputs L and r as above and i between 1 and r
#and outputs the expected length for picking a move
#uniformly at RANDOM
fR:=proc(L,r,i) local Moves,m:
option remember:
Moves:=LegalMoves(L,i):

if Moves={} then
    return 0:
fi:

1+add(FR(m,r),m in Moves)/nops(Moves):

end:

##Problem 4
#Test everything!
FTest:=proc(startr,endr) local r:
for r from startr to endr do
    print(["r=",r]):
    print(["F=",seq(1.*F([0$(r-1),n],r), n=1..10)]):
    print(["FG=",seq(1.*FG([0$(r-1),n],r), n=1..10)]):
    print(["FP=",seq(1.*FP([0$(r-1),n],r), n=1..10)]):
    print(["FR=",seq(1.*FR([0$(r-1),n],r), n=1..10)]):
od:
end:

#FTest(2,7); Output:
#["r=", 2]
#["F=", 1.500000000, 2.875000000, 4.218750000, 5.554687500, 6.888671875, 8.222167969, 9.555541992, 10.88888550, 12.22222138, 13.55555534]
#["FG=", 1.500000000, 2.875000000, 4.218750000, 5.554687500, 6.888671875, 8.222167969, 9.555541992, 10.88888550, 12.22222138, 13.55555534]
#["FP=", 1.500000000, 3., 4.500000000, 6., 7.500000000, 9., 10.50000000, 12., 13.50000000, 15.]
#["FR=", 1.500000000, 2.937500000, 4.347656250, 5.743652344, 7.131118774, 8.512819290, 9.890295625, 11.26450197, 12.63607709, 14.00547408]
#["r=", 3]
#["F=", 1.777777778, 3.423868313, 5.017070568, 6.587788673, 8.147260833, 9.698777297, 11.24487117, 12.78689698, 14.32570947, 15.86195348]
#["FG=", 1.777777778, 3.423868313, 5.036274958, 6.633919852, 8.222027364, 9.802945579, 11.37812842, 12.94860056, 14.51512285, 16.07827725]
#["FP=", 1.777777778, 3.567901235, 5.363511660, 7.161560738, 8.960693661, 10.76030829, 12.56013702, 14.36006090, 16.16002707, 17.96001203]
#["FR=", 1.777777778, 3.479423868, 5.149634202, 6.803721026, 8.448206681, 10.08638545, 11.72013729, 13.35063237, 14.97864680, 16.60472076]
#["r=", 4]
#["F=", 1.953125000, 3.737854004, 5.453439951, 7.136894011, 8.803326193, 10.45995656, 12.10984352, 13.75496150, 15.39652611, 17.03526892]
#["FG=", 1.953125000, 3.757629394, 5.511607408, 7.238691297, 8.948487519, 10.64620240, 12.33500353, 14.01693898, 15.69339671, 17.36535737]
#["FP=", 1.953125000, 3.930908203, 5.916690826, 7.905282795, 9.895806694, 11.88794971, 13.88115543, 15.87501069, 17.86933917, 19.86408421]
#["FR=", 1.953125000, 3.825359344, 5.664914338, 7.488307813, 9.302578747, 11.11121800, 12.91615097, 14.71852548, 16.51906744, 18.31825761]
#["r=", 5]
#["F=", 2.073600000, 3.982318592, 5.817832713, 7.614069685, 9.388240968, 11.14843621, 12.89885469, 14.64194632, 16.37927371, 18.11194983]
#["FG=", 2.073600000, 4.011159552, 5.895820812, 7.750220810, 9.584371278, 11.40379473, 13.21189170, 15.01091794, 16.80245783, 18.58767521]
#["FP=", 2.073600000, 4.183144960, 6.303974957, 8.430404947, 10.56097940, 12.69432636, 14.82928760, 16.96534322, 19.10219534, 21.23962332]
#["FR=", 2.073600000, 4.070926872, 6.036737618, 7.986832665, 9.928125214, 11.86407661, 13.79658735, 15.72677477, 17.65533160, 19.58270597]
#["r=", 6]
#["F=", 2.161394033, 4.156345626, 6.061177366, 7.916844622, 9.742931947, 11.55104763, 13.34740069, 15.13529350, 16.91675239, 18.69317785]
#["FG=", 2.161394033, 4.193645141, 6.164777704, 8.098045174, 10.00536546, 11.89375572, 13.76767182, 15.63011132, 17.48318739, 19.32844764]
#["FP=", 2.161394033, 4.367671953, 6.586512929, 8.812133808, 11.04197939, 13.27432148, 15.50886727, 17.74508989, 19.98250704, 22.22082189]
#["FR=", 2.161394033, 4.251786274, 6.312218476, 8.357594400, 10.39458601, 12.42656580, 14.45538164, 16.48210882, 18.50740383, 20.53168360]
#["r=", 7]
#["F=", 2.228187235, 4.295948119, 6.275421935, 8.204190111, 10.10146529, 11.97843530, 13.84127665, 15.69357564, 17.53772377, 19.37533164]
#["FG=", 2.228187235, 4.340119716, 6.389717766, 8.399562297, 10.38208382, 12.34465861, 14.29193349, 16.22700714, 18.15205200, 20.06865653]
#["FP=", 2.228187235, 4.508980812, 6.804047627, 9.107034283, 11.41555818, 13.72875332, 16.04517678, 18.36395898, 20.68453220, 23.00644350]
#["FR=", 2.228187235, 4.392282727, 6.528634308, 8.650757360, 10.76485050, 12.87410976, 14.98031145, 17.08449827, 19.18730932, 21.28915067]

#It appears that greedy tends to be a bit better than random,
#but both are solidly between optimal and pessimal