# Joey Reichert
# 640:640 Spring 2013
# April 29, 2013
# hw26.txt
# I give permission to post

Help26:=proc() : print("AllBetterDeals(G,i);"): end:


# Problem #1
# Write a program AllBetterDeals(G,i) [as described on the webpage].
# What is AllBetterDeals(ElsterG(),1)? 

AllBetterDeals:=proc(G,i) local pay1,pay2,j,k,vtemp,Gtemp,allbetter,payoffs:
option remember:

pay1:=P1(G,i):
pay2:=P2(G,i):
allbetter:={}:


for j from 1 to nops(G) do
 for k from 1 to nops(G[j]) do
  vtemp:=G[j] minus {k}:
  Gtemp:=[{op(1..j-1,G)}, vtemp, {op(j+1..nops(G),G)}]:
  
  if P1(Gtemp,i) > pay1 and P2(Gtemp,i) > pay2 then
   payoffs:=[P1(Gtemp,i),P2(Gtemp,i)]:
   allbetter:=allbetter union {[Gtemp,payoffs]}:
  fi:
 od:
od:

allbetter:
end:

# This isn't quite right because it only removes a single edge at
# a time. Shouldn't be impossible to modify (though may be easier
# to make a recursive call) though.

# In fact, this seems to have a major bug, because various inputs
# give DIFFERENT error messages including too many levels of 
# recusion in P1, invalid subscript selector, and
# (among others) being unable to determine if 
# (DrZ, [-infinity, -infinity]) < (DrZ, [-infinity, -infinity])


# Problem #2
# Experiment with ten random graphs with n=6, k=2, Si=3, and L=10 
# (using RGG(n,k,Si,L) ).

# Of course, I can create the random graphs using the procedure
# that exists, but without fixing my AllBetterDeals(G,i), I 
# cannot actually use them for anything useful.


# Problem #3
# Write a program OneBetterDeals(G,i,K) 

OneBetterDeals:=proc(G,i,K) local j,k,ra,better,K1:
option remember:

pay1:=P1(G,i):
pay2:=P2(G,i):
better:=[]:
numedges:=0:

for j from 1 to nops(G) do
 for k from 1 to nops(G[j]) do
  numedges:=numedges+1:
 od:
od:

K1:=0:

while K1 < K do
 ra:=rand(1..numedges):
 
 # Here we should really have a way to directly get to
 # a specific edge of G. One way to do this is by
 # checking each vertex to see how many edges exist
 # there, but this seems more complicated than needed!
 # I will brainstorm a bit and fix this if time permits.
 
 K1:=K1+1:
 numedges:=numedges-1:
 if numedges < 1 then
  break:
 fi: 

od:

if better = [] then
 return Fail:
fi:

return better:

end:


# Problem #4
# Experiment with ten random graphs with n=20, k=3, Si=4 and L=10 
# (using RGG(n,k,Si,L)).

# As before, I'll experiment with the graphs after refining the 
# program!




####################################################################
#C26.txt: Generalizing the centepede game to general directed graphs
#April 29, 2013

Help:=proc(): print(`ElsterG()  `): 
print(`P1(G,i), P2(G,i), RandGame(n,k) , RGG(n,k,Si,L) `):
end:

#ElsterG():
ElsterG:=proc()
[{2,6},{3,7},{4,8},{5,9},[3,4],[2,-1],[1,2],[4,1],
[6,3]]:
end:

#P1(G,i): The best move, followed by the pair
#[payOff of I, payoff of II] in a game given
#by the generalized directed graph G where
#the sinks are labeled by payoofs
#If player I is moving
P1:=proc(G,i) local  champ, rec, GoHome,S,s, ross,DrZ:
option remember:

if type(G[i],list) then
 RETURN(GoHome,G[i]):
fi:

S:=G[i]:

champ:=DrZ:

rec:=[-infinity, -infinity]:
#infinity is OK here, it is a symbol!
#(the "real" infinity is nonsense)
 
for s in S do

ross:=P2(G,s)[2]:

if ross[1]>rec[1] then

   champ:=s:
    rec:=ross:
fi:
od:

champ, rec:
end:



#P2(G,i): The best move, followed by the pair
#[payOff of I, payoff of II] in a game given
#by the generalized directed graph G where
#the sinks are labeled by payoofs
#If player II is moving
P2:=proc(G,i) local  champ, rec, GoHome,S,s, ross,DrZ:
option remember:

if type(G[i],list) then
 RETURN(GoHome,G[i]):
fi:

S:=G[i]:

champ:=DrZ:

rec:=[-infinity, -infinity]:
#infinity is OK here, it is a symbol!
#(the "real" infinity is nonsense)
 
for s in S do

ross:=P1(G,s)[2]:

if ross[2]>rec[2] then

   champ:=s:
    rec:=ross:
fi:
od:

champ, rec:
end:



#RandDi(n,k): a random directed graph with n
#vertices and (usually) outdegree k 
RandDi:=proc(n,k) local ra,i,j:
ra:=rand(1..n):

[seq({seq(ra(),i=1..k)} minus {j} ,j=1..n)]:

end:

#RandGame(n,k): inputs pos. integers n and k
#and outputs a random digraph that has the
#property that out of vertex i all the labels
#are less i, and there are (usually) k outgoing
#edges
RandGame:=proc(n,k) local L,i,tomas,j:

L:=[{}]:
for i from 2 to n do
 
tomas:={seq(rand(1..i-1)(),j=1..k)}:

L:=[op(L), tomas]:
od:

L:

end:

#RGG(n,k,Si,L): a random centepede-style
#game with n vertices, roughly outdegree k 
#for non-sinks, and roughly Si sinks
RGG:=proc(n,k,Si,L) local G, ra,i, t,a, b:

ra:=rand(0..L):

G:=RandGame(n,k):


for i from 2 to Si do

t:=rand(2..n)():

a:=ra(): b:=ra():

G:=[op(1..t-1,G)   , [a,b], op(t+1..n,G)]: 


od:

a:=ra(): b:=ra():

G:=[[a,b],op(2..nops(G),G)]:


end: