#!/usr/local/bin/maple
# -*- maplev -*-

# Nathaniel Shar
# HW 8
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

Help := proc(): print(`RollLD(L), RandGame1(n), NuGames1(n), part(n,k), Games(n,r), SetG(n,r), G2(n)`): end:

# From c8.txt

RollLD:=proc(L) local i,r,N:
    N:=convert(L,`+`):
    r:=rand(1..N)():

    for i from 1 to nops(L) while convert([op(1..i,L)],`+`)<r do od:
    return i:
end:

RandGame1:=proc(n) local L,m:
    if n=1 then
        RETURN([{},{}]):
    fi:
    L:=[seq(NuGames1(m)*NuGames1(n-1-m),m=0..n-1)]:
    m:=RollLD(L)-1:
    if m=0 then
        RETURN([{},{RandGame1(n-1)}]):
    elif m=n-1 then
        RETURN([{RandGame1(n-1)},{}]):
    else
        RETURN([{RandGame1(m)},{RandGame1(n-1-m)}]):
    fi:
end:

NuGames1:=proc(n) local m:
#every game is [L,R] let Size(L)=m
option remember:
    if n=0 then
        RETURN(1):
    fi:
    add(NuGames1(m)*NuGames1(n-1-m),m=0..n-1):
end:


#############
# Problem 4 #
#############

with(combinat):

part := proc(n,k):
    return select(x->evalb(nops(x)<=k), partition(n)):
end:

# The set of all games of "size" n such that each player has at most r
# options from any position.
# Size(L|R) = Size(L)+Size(R)+1 and Size(S) = sum(|i|, i in L)
Games := proc(n,r) local i, p, q, S: option remember:
    if n = 1 then:
        return {[{}, {}]}:
    else:
        S := {}:
        for i from 0 to n-1 do:
            S := S union {seq(seq([p,q], p in SetG(i,r)), q in SetG(n-1-i, r))}:
        od:
    fi:
    return S:
end:

SetG := proc(n,r) local m, p, S, S1, G1, i, j, T, U: option remember:
    S := {}:
    if r = 0 then:
        if n = 0 then
            return {{}}:
        else:
            return {}:
        fi:
    fi:
    for p in part(n,r) do:
        T := cartprod([seq(Games(i,r), i in p)]):
        while not T['finished'] do:
            U := convert(T['nextvalue'](), set):
            if nops(U)=nops(p) then:
                S := S union {U}:
            fi:
        od:
    od:
    return S:
end:

G2 := proc(n):
    return Games(n, 2):
end: