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

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

#Help procedure
Help:=proc():
print(` Timid(N) , Bold(N) , TimidVsBold(N,p) , Neigs(L) `):
print(` BestNeig(N,p,L,i) `):
end:

##Auxiliary Procedures
#Timid strategy
Timid:=proc(N) local i:
[seq(1,i=1..N-1)]:
end:

#Bold strategy
Bold:=proc(N) local i:
[seq(min(i,N-i),i=1..N-1)]:
end:

##Problem 1
#TimidVsBold(N,p): inputs a positive integer N and a SYMBOL p,
#and outputs a list of length N-1 whose i-th item is the set of
#p's for which the Timid Strategy (always betting 1 dollar) is
#strictly better than the Bold Stragegy
#(betting min(i,N-i) dollars).
TimidVsBold:=proc(N,p) local i,timid,bold:
timid:=VGW(p,N,Timid(N)):
bold:=VGW(p,N,Bold(N)):
solve({seq(timid[i]>bold[i],i=1..N-1), 0<=p, p<=1},{p}):
end:

#TimidVsBold(N,p) always returns {1/2 < p, p < 1}, as it should

##Problem 2
#Neigs(L): return the neighbors of L
#Define the set of neighbors of a strategy, L, to be the set of
#(legal!) strategies where all the components are the same except
#at one entry, where it is off by one (so there must be at most
#2*nops(L) neighbors).
Neigs:=proc(L) local N,ret,i:
N:=nops(L)+1:
ret:={}:
for i from 1 to N-1 do
    if L[i] > 1 then
        ret:=ret union {[op(1..i-1,L),L[i]-1,op(i+1..N-1,L)]}:
    fi:
    if L[i] < min(i, N-i) then
        ret:=ret union {[op(1..i-1,L),L[i]+1,op(i+1..N-1,L)]}:
    fi:
od:
ret:
end:

#BestNeig(N,p,L,i): inputs N, (numeric) prob. p, a stragegy L
#(a legal list of integers of length N-1), and an integer i
#between 1 and N-1, and outputs the best neighboring strategy in
#the sense that the prob. of winning with that p and N, if you
#currently have i dollars is highest. If L is better than all
#its neighbors, return L.
BestNeig:=proc(N,p,L,i) local rec,champ,neigs,neig,cand:
champ:=L:
rec:=VGW(p,N,L)[i]:
neigs:=Neigs(L):
for neig in neigs do
    cand:=VGW(p,N,neig)[i]:
    if cand > rec then
        champ:=neig:
        rec:=cand:
    fi:
od:
champ:
end:

##Problem 3
#BestStraFast(p,N,i): inputs p and N and i as above and outputs
#the strategy that maximizes the probability of winning if you
#have i dollars. (well, at least finds a local maximum that is
#hopefully a global one).
BestStraFast:=proc(p,N,i) local L,L2:
L:=Timid(N):
while true do
    L2:=BestNeig(N,p,L,i):
    if L2=L then
        return L:
    fi:
    L:=L2:
od:
end:

##Problem 4
#If p<1/2, it is indeed going to be timid
#If p>1/2, there are a lot of equivalent possibilities
#one of these is bold; a different one is likely to be returned
#but at least it will be bold in position i