# OK to post homework
# RDB, 2022-04-24, HW25

# 1.

# Hi, Rebecca!

# 2.

read "C25.txt":

BestPrune := proc(G, R)
    local newG, reward, v, dest, newReward:
    newG := G:
    reward := LaC(newG, R)[1]:
    for v from 1 to nops(newG) do
        for dest in newG[v] do
            newG[v] := newG[v] minus {dest}:
            newReward := LaC(newG, R):

            if newReward = FAIL then
                next;:
            fi:

            newReward := newReward[1]:
            if newReward[1] > reward[1] and newReward[2] > reward[2] then
                return [v, dest]:
            fi:

            newG[v] := newG[v] union {dest}:
        od:
    od:

    FAIL:
end:

BestPrune(Els());
BestPrune(WikiCent(20));

# 3.

RandCent := proc(n, p, K)
    local G, ra, sinks, R:
    G := RDG(n, p):
    ra := rand(0..K):
    sinks := select(i -> G[i] = {}, [seq(1..n)]):
    R := {seq([k, [ra(), ra()]], k in sinks)}:

    G, R:
end:

# 4.

# I assume that "the paradox" here is that there exists an edge that, when
# deleted, would result in a better outcome for both players - the paradox
# being that fewer choices leads to a better outcome.

FindParadox := proc(n, p, K, K1)
    local k, G, R, res:
    for k from 1 to K1 do
        G, R := RandCent(n, p, K):
        res := BestPrune(G, R):
        if res <> FAIL then
            return G, R, res:
        fi:
    od:

    FAIL:
end:

FindParadox(30, 1/2, 100, 1000);

# 5.

# The Sprague-Grundy function of a game G?
# It's a value for every vertex in the graph. We construct it iteratively.
# Every sink has value 0. Then, the vertices in generation i (meaning that they
# are i steps back from a sink) has value one greater than any of its
# descendants.

# Example: G = [{2, 3}, {}, {4}, {}].
# Generations: [{2, 4}, {3}, {1}]
# Iterative values: ( , 0,  , 0)
#                   ( , 0, 1, 0)
#                   (2, 0, 1, 0)

# Claim: SG(G)[i] = 0 iff i is a losing position.

# Seems obvious for sinks. Things one step back from a sink should have value
# 1, which is good. Sounds reasonable to do it by induction on generations.

# Say that the first n generations are labeled "correctly," in that the
# Sprague-Grundy function vanishes exactly on losing positions. Then, a vertex
# in generation n + 1 has Sprague-Grundy value zero iff all of its descendants
# have positive value, i.e., are winning. But this says precisely that this
# vertex is losing. Done.