# OK to post homework
# Vikrant, Apr 24 2022, Assignment 25

# ================================================================================
# 0. Code that has been given.
# ================================================================================

read("C25.txt"):

# ================================================================================
# 1. Project.
# ================================================================================

# Working on it.

# ================================================================================
# 2. Edge to prune (without creating any new sinks).
# ================================================================================

# This is really "better" prune since we return any improving edge rather than the "best" improving edge.
BestPrune:=
    proc(G,R)
        local u,v,i,r:
        local l:= LaC(G,R)[1]:
        for u from 1 to nops(G) do
            for v in G[u] while nops(G[u])>1 do
                r:= LaC([seq(G[i] minus [{}$(u-1),{v},{}$(nops(G)-u)][i],i=1..nops(G))],R)[1]:
                if r[1]>=l[1] and r[2]>=l[1] and add(r-l)>0 then
                    return([u,v]):
                fi:
            od:
        od:
        FAIL:
    end:

# [3,8]
# BestPrune(Els());
# [2,43]
# BestPrune(WikiCent(20));

# ================================================================================
# 3. Random centipede.
# ================================================================================

RandCent:=
    proc(n,p,K)
        local i:
        local G:= RDG(n,p):
        local ra:=rand(0..K):
        G,{seq(`if`(G[i]={},[i,[ra(),ra()]],NULL),i=1..n)}:
    end:

# ================================================================================
# 4. Find paradox.
# ================================================================================

FindParadox:=
    proc(n,p,K,K1)
        local i,C:
        for i from 1 to K1 do
            C:= RandCent(n,p,K):
            if BestPrune(C)<>FAIL then
                return(i,C):
            fi:
        od:
        FAIL:
    end:

# randomize(1101345648):
# 30, [{3, 4, 5, 7, 8, 9, 10, 12, 13, 16, 19, 20, 24, 29}, ..., {}], {[28, [70, 26]], [29, [60, 27]], [30, [96, 58]]}
# FindParadox(30, 1/2, 100, 1000);

# ================================================================================
# 5. Sprague-Grundy.
# ================================================================================

(*
    # We can show LaGn(G)[i]=0 iff SG(G)[i]=0 by induction on the generations of G.
    # Base case: This is certainly true for the sinks (generation 1) in G.
    # Inductive step:
    #  (==>)
    #  If LaGn(G)[i]=0, then for all arcs (i,j), LaGn(G)[j]=1.
    #  By induction, SG(G)[j]<>0.
    #  The mex of SG(G)[j] over all j such that (i,j) is an arc is thus 0, and consequently SG(G)[i]=0.
    #  (<==)
    #  If, on the other hand, LaGn(G)[i]<>0, then there is some (i,j) such that LaGn(G)[j]=0.
    #  By induction, SG(G)[j]=0.
    #  The mex of SG(G)[j] over all j such that (i,j) is an arc is thus greater than 0, so SG(G)[i]<>0.
*)