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

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

#Help procedure
Help:=proc():
print(` sinks(G), nonSinks(G), AllBetterDeals(G,i) `):
print(` problem2(iterations,n,k,Si,L,output:=terminal) `):
print(` OneBetterDeals(G,i,K) `):
print(` problem4(iterations,n,k,Si,L,K,output:=terminal) `):
end:

with(combinat):
##Auxililary Procedures
#Sinks in G
sinks:=proc(G) local i,ret:

ret:={}:

for i from 1 to nops(G) do
    if type(G[i],list) then
        ret:=ret union {i}:
    fi:
od:

ret:

end:

#Non-sinks in G
nonSinks:=proc(G) local i,ret:

ret:={}:

for i from 1 to nops(G) do
    if type(G[i],set) then
        ret:=ret union {i}:
    fi:
od:

ret:

end:

##Problem 1
#AllBetterDeals(G,i): inputs a generalized game G (given in our
#format) and a vertex i (an integer between 1 and nops(G)) that
#is not a sink, and finds ALL the smaller subgames H (obtained by
#deleting some of the edges, i.e. replacing some (or all) of the
#entries of G that are sets by proper subsets and such that the
#payoffs for BOTH players are higher if Player 1 starts at vertex
#i. You also want the improved payoffs. So the output should be
#the a set of pairs {[H,[a,b]}
AllBetterDeals:=proc(G,i)
local H,k,j,edges,edgesets,erems,edge,ok,val,val2,ret:

ret:={}:

val:=P1(G,i)[2]:

edges:={}:
for k from 1 to nops(G) do
    if type(G[k],set) then
        for j in G[k] do
            edges:=edges union {[k,j]}:
        od:
    fi:
od:

edgesets:=powerset(edges) minus {{}}:

for erems in edgesets do
    H:=[seq(G[j], j=1..nops(G))]:
    ok:=true:
    for edge in erems do
        H[edge[1]]:=H[edge[1]] minus {edge[2]}:
        if H[edge[1]] = {} then
            ok:=false:
        fi:
    od:
    if ok then
        val2:=P1(H,i)[2]:
        if val2[1] > val[1] and val2[2] > val[2] then
            ret:=ret union {[H,val2]}:
        fi:
    fi:
od:

ret:

end:

#AllBetterDeals(ElsterG(),1) returns
#{
#[[{2}, {3}, {4}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2}, {3}, {4}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]],
#[[{2}, {3}, {4}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2}, {3}, {8}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2}, {3}, {8}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2}, {3}, {8}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2}, {3}, {4, 8}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2}, {3}, {4, 8}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]],
#[[{2}, {3}, {4, 8}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2}, {3, 7}, {4}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2}, {3, 7}, {4}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]],
#[[{2}, {3, 7}, {4}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2}, {3, 7}, {4, 8}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]],
#[[{2, 6}, {3}, {4}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2, 6}, {3}, {4}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]],
#[[{2, 6}, {3}, {4}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2, 6}, {3}, {8}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2, 6}, {3}, {8}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2, 6}, {3}, {8}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2, 6}, {3}, {4, 8}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2, 6}, {3}, {4, 8}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]],
#[[{2, 6}, {3}, {4, 8}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [4, 1]],
#[[{2, 6}, {3, 7}, {4}, {5}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2, 6}, {3, 7}, {4}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]],
#[[{2, 6}, {3, 7}, {4}, {5, 9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [3, 4]],
#[[{2, 6}, {3, 7}, {4, 8}, {9}, [3, 4], [2, -1], [1, 2], [4, 1], [6, 3]], [6, 3]]
#}

##Problem 2
defaultVals2:=10,6,2,3,10:
problem2:=proc(iterations,n,k,Si,L,output:=terminal) local i,j,G:

for j from 1 to iterations do
    G:=RGG(n,k,Si,L):
    fprintf(output, "Game #%d\n", j):
    fprintf(output, convert(G, string)):
    fprintf(output, "\n"):
    for i in nonSinks(G) do
        fprintf(output, "i = %d\n", i):
        fprintf(output, convert(AllBetterDeals(G, i),string)):
        fprintf(output, "\n\n"):
    od:
od:

end:

#Running problem2(defaultVals2) found no better
#deals when I ran it

##Problem 3
#OneBetterDeals(G,i,K): inputs same as AllBetterDeals, and tries
#to find, by repeated random deletion of edges, K times, ONE
#subgame that is a better deal for BOTH players if player 1
#starts at vertex i. If no better deal is found, return FAIL.
#(It tries to delete each edge with probability 1/2)
OneBetterDeals:=proc(G,i,K)
local H,k,j,erems,edge,ok,val,val2,ra:

val:=P1(G,i)[2]:

ra:=rand(1..2):

k:=1:
while k <= K do
    erems:={}:
    for k from 1 to nops(G) do
        if type(G[k],set) then
            for j in G[k] do
                if ra() = 1 then
                    erems:=erems union {[k,j]}:
                fi:
            od:
        fi:
    od:
    H:=[seq(G[j], j=1..nops(G))]:
    ok:=evalb(nops(erems)>0):
    for edge in erems do
        H[edge[1]]:=H[edge[1]] minus {edge[2]}:
        if H[edge[1]] = {} then
            ok:=false:
        fi:
    od:
    if ok then
        val2:=P1(H,i)[2]:
        if val2[1] > val[1] and val2[2] > val[2] then
            return [H,val2]:
        fi:
        k:=k + 1:
    fi:
od:

FAIL:

end:

##Problem 4
defaultVals4:=10,20,3,4,10,20:
problem4:=proc(iterations,n,k,Si,L,K,output:=terminal)
local i,j,G:

for j from 1 to iterations do
    G:=RGG(n,k,Si,L):
    fprintf(output, "Game #%d\n", j):
    fprintf(output, convert(G, string)):
    fprintf(output, "\n"):
    for i in nonSinks(G) do
        fprintf(output, "i = %d\n", i):
        fprintf(output, convert(OneBetterDeals(G,i,K),string)):
        fprintf(output, "\n\n"):
    od:
od:

end:

#Running problem4(defaultVals4) found no better deals when I ran
#it.  This might be related to the fact that edges were removed
#always with probability 1/2 (that's not a parameter).  More
#likely, though (based on Problem 2) is that pruning a game
#usually doesn't improve it.