# OK to post homework
# Vikrant, Apr 03 2022, Assignment 18

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

read("C18.txt"):

# ================================================================================
# 1. Read alternative proof of Arrow's Theorem.
# ================================================================================

# Done. Prefer Yu's proof.

# ================================================================================
# 2. Inefficient enumeration of number of voting profiles that lead to 1231.
# ================================================================================

SeqCoStupid:=
    proc(N)
        local n:
        [seq(nops(NuC(2*n-1,[[0,1,1],[0,0,1]])),n=1..N)]:
    end:

# ================================================================================
# 3. Efficient enumeration of number of voting profiles that lead to 1231.
# ================================================================================

# Basically done for us in class already. The procedure Zs(N) is in C19.txt.
read("C19.txt"):
SeqCoSmart:= Zs:

# ================================================================================
# 4. Estimate limiting probability of condorcet paradox occuring.
# ================================================================================

EstimateP:=
    proc()
        local zs,n:
        local N:= 20:
        while time(Zs(N)) < 1 do
            zs:= Zs(N):
            N:= N+1:
        od:
        2*evalf([seq(zs[n]/6^(2*n-1),n=1..nops(zs),2)]):
    end:

# ================================================================================
# 5. <Skipped, or rather, unsuccessful>
# ================================================================================

# ================================================================================
# 6. Quasipolynomial stuff.
# ================================================================================

# Had to change two invocations of subs(..) in GP1 to algsubs(..).
# Why? We are passing in variables that are not purely symbolic.
# They are of the form (n-qpi+p)/p where only n is a symbol.
GQP1:=
    proc(L,p,n)
        local i,qpi:
        local qp:= [seq(GP([seq(L[i],i=qpi..nops(L),p)],(n-qpi+p)/p),qpi=1..p)]:
        if not FAIL in qp then
            return(qp):
        fi:
        FAIL:
    end:

GQP:=
    proc(L,n)
        local qp,p:
        for p from 1 to nops(L) do
            qp:= GQP1(L,p,n):
            if qp<>FAIL then
                return(qp):
            fi:
        od:
        FAIL:
    end: