### written by: aurora hiveley, rutgers university
### last updated: 12/7/24

print(`This is wordle.txt, a Maple package by Aurora Hiveley (Rutgers University)`):
print(`For a list of the functions, type Help(); for help with a specific function type: Help(FunctionName);`):

Help:=proc(): 

if nargs=0 then 

# print(`FUNCTIONS MASTER LIST:`):
# print(`GUESSER: guesser(setP,s,boolSee := false), guesserInpt(setP,iniP,s,boolSee := false)`): 
# print(`NEXT GUESS GENERATOR: nextGuess(setP,p,s,boolSee := false)`):
# print(`COMBINATORIAL TOOLS: avgSpeed(n,s,N), cyclicPerms(n), cyclicPermsGT(n), derange(n), gf(n,s,x), gfAvg(n,s), isDer(p), isPerm(p)`):
# print(`STRATEGIES ANALYSIS: bestStrats(n,setS), cyclicStrats(n,setS), KSCheck(n,setS), rankStrats(n,setS), worstStrats(n,setS)`):
# print(`HELPERS: cyclicPermsGT(n), permChecker(p1,p2), permInd(setP,p), stratChecker(p,s)`):

print(`ALL FUNCTIONS:`):
print(`avgSpeed(n,s,N), bestStrats(n,setS), cyclicPerms(n), cyclicPermsGT(n), cyclicStrats(n,setS), derange(n),`):
print(`gf(n,a=s,var), gfAvg(n,s), guesser(setP,s,boolSee := false), guesserInpt(setP,iniP,s,boolSee := false), guesserOld(setP,s,boolsee := false), `):
print(`inductiveStrat(n), isDer(p), isPerm(p), KSCheck(n), lcCheck(n), nextGuess(setP,p,s,boolSee := false),`):
print(`permChecker(p1,p2), permInd(setP,p), rankStrats(n,setS), stratChecker(p,s), worstStrats(n,setS)`):


## GUESSERS HELP

elif nargs=1 and args[1]=guesserInpt then
print(`guesserInpt(setP, iniP, s, boolSee): starting with initial guess permutation on [n],`):
print(`uses nextGuess and strategy = s to repeatedly attempt to guess fixed permutation`):
print(`inputs: fixed permutation setP, initial guess permutation iniP, strategy s, boolean for printing each guess boolSee (default is false)`):
print(`outputs: number of turns until guesses correctly`):
print(`example: guesserInpt([1,2,3,4],[4,1,3,2],random,true); guesserInpt([1,2,3,4],[4,1,3,2],cyclic,false); `):

elif nargs=1 and args[1]=guesser then
print(`guesserOld(setP, s, boolSee): starting with the trivial permutation on [n],`):
print(`uses nextGuess and strategy = s to repeatedly attempt to guess fixed permutation.`):
print(`note that there is no accounting for an infinite loop, i.e. guessing the same two or more guesses in sequence repeatedly.`):
print(`inputs: fixed permutation setP, strategy s, boolean for printing each guess & incorrect indices boolSee (default is false)`):
print(`outputs: number of turns until guesses correctly`):
print(`example: guesser([4,1,3,2],random,true); guesser([4,1,3,2],cyclic,false); `):

elif nargs=1 and args[1]=guesser then
print(`guesser(setP, s, boolSee): starting with the trivial permutation on [n],`):
print(`uses nextGuess and strategy = s to repeatedly attempt to guess fixed permutation.`):
print(`returns infinity if strategy forces us to guess something that we have already guessed.`):
print(`inputs: fixed permutation setP, strategy s, boolean for printing each guess & incorrect indices boolSee (default is false)`):
print(`outputs: number of turns until guesses correctly`):
print(`example: guesser([4,1,3,2],random,true); guesser([4,1,3,2],cyclic,false); `):


## NEXT GUESS GENERATORS HELP

elif nargs=1 and args[1]=nextGuess then
print(`nextGuess(setP, p, s, boolSee := false): starting with initial guess permutation on [n], locks in correct entries matching final permutation.`):
print(`generates next guess using strategy s, printing locations of incorrect entries if boolSee = true`):
print(`inputs: fixed permutation setP, current guess permutation p, boolean for printing guess's incorrect indices`):
print(`outputs: next permutation`):
print(`--------------------------------------------------------------------------------------------`):
print(`POSSIBLE STRATEGIES: `):
print(`random: locks in correct entries, incorrect entries are permuted randomly to generate next guess`):
print(`example: nextGuess([4,3,2,1],[1,2,3,4], random);`):
print(`cyclic: locks in correct entries, incorrect entries are are cycled one index lower from incorrect indices list (see Kutin & Smithline.)`):
print(`example: nextGuess([4,3,2,1],[1,2,3,4], cyclic);`):
print(`[[1],...]: locks in correct entries, incorrect entries are permuted according to a cyclic permutation from strategy S (a list)`):
print(`example: nextGuess([4,3,2,1],[1,2,3,4],[[1],[2,1],[2,3,1],[2,3,4,1]])`):
print(`note that the above example should produce the same next guess as the cyclic guessing method`):
# S = [[1], [2,1], [2,3,1], [2,..., k,1]] is kutin and smithline


## COMBINATORIAL TOOLS HELP

elif nargs=1 and args[1]=gf then
print(`gf(n,s,var): produces the generating function for strategy s using variable var (default is x)`):
print(`inputs: permutation length n and strategy s`):
print(`outputs: polynomial representing generating function. coefficient a_d represents the number of permutations which took d turns to be guessed correctly.`):
print(`example: gf(4, cyclic, x);`):

elif nargs=1 and args[1]=gfAvg then
print(`gfAvg(n,s): computes the average number of guesses taken by strategy s`):
print(`on a permutation of length n `):
print(`inputs: permutation length n, generating function polynomial p, variable x used in p`):
print(`outputs: average number of guesses for strategy s`):
print(`calculated from generating function by taking weighted average of number of permutations (coefficients)`):
print(`which take N guesses (of x^N)`):
print(`example: gfAvg(4,cyclicStrats(4)[6])`):

elif nargs=1 and args[1]=lcCheck then 
print(`lcCheck(n): identifies strategies with the best worst performance (i.e. fewest number of guessed permutations with the (smallest) largest number of guesses.)`):
print(`Does this by checking degree and leading coefficient of generating function for each strategy.`):
print(`input: permutation length n`):
print(`output: list of strategies with the best worst performance.`):
print(`example: lcCheck(4);`):

elif nargs=1 and args[1]=avgSpeed then
print(`avgSpeed(n,s,N): calculates the average number of turns taken to guess a random permutation on [n] `):
print(`using strategy s averaged over N new games`):
print(`inputs: permutation length n, strategy s, number of trials N`):
print(`outputs: average number of turns`):
print(`example: avgSpeed(4,cyclic,100); avgSpeed(5,random,100);`):

elif nargs=1 and args[1]=cyclicPerms then
print(`cyclicPerms(n): generates a set of all cyclic permutations on [n] `):
print(`inputs: permutation length n`):
print(`outputs: set of cyclic permutations`):
print(`example: cyclicPerms(4);`):

elif nargs=1 and args[1]=isPerm then
print(`isPerm(p): checks whether a list p is a permutation of {1,...,nops(p)} `):
print(`inputs: list p`):
print(`outputs: boolean (is p a permutation?)`):
print(`example: isPerm(randperm(4)); isPerm([1,2,3,2])`):

elif nargs=1 and args[1]=derange then
print(`derange(n): constructs set of permutations on [n] which are derangements `):
print(`inputs: permutation length n`):
print(`outputs: set of derangements`):
print(`example: derange(3)`):

elif nargs=1 and args[1]=isDer then
print(`isDer(p): checks whether a permutation is a derangement (i.e. there are no fixed points) `):
print(`inputs: permutation p`):
print(`outputs: boolean (is p a derangement?)`):
print(`example: isDer([1,2,3]), isDer([3,4,1,2])`):


## STRATEGIES ANALYSIS

elif nargs=1 and args[1]=cyclicStrats then
print(`cyclicStrats(n): generates a collection of strategies for permutations of length n using cyclic permutations`):
print(`inputs: permutation length n`):
print(`outputs: set of strategies (as lists of cyclic permutations)`):
print(`example: cyclicStrats(3);`):

elif nargs=1 and args[1]=rankStrats then
print(`rankStrats(n,setS): ranks all strategies on permutations of length n in setS according to average number of guesses until correct `):
print(`inputs: permutation length n`):
print(`outputs: list L of lists l of form [average, {set of strategies with that average number of guesses}] in increasing order by average`):
print(`example: rankStrats(4, cyclicStrats(4))`):

elif nargs=1 and args[1]=bestStrats then
print(`bestStrats(n,setS): identifies optimal strategies on permutations of length n (those with the smallest number of average guesses)`):
print(`out of possible strategies in setS`):
print(`inputs: permutation length n`):
print(`outputs: list of optimal strategies, i.e. those with the minimum number of average guesses`):
print(`example: bestStrats(5)`):

elif nargs=1 and args[1]=worstStrats then
print(`worstStrats(n): identifies least optimal strategies on permutations of length n (those with the highest number of average guesses)`):
print(`out of possible strategies in setS`):
print(`inputs: permutation length n`):
print(`outputs: list of least optimal strategies, i.e. those with the maximum number of average guesses`):
print(`example: worstStrats(5)`):

elif nargs=1 and args[1]=KSCheck then
print(`KSCheck(n,setS): checks whether or not Kutin-Smithline's strategy has the minimum number of average guesses`):
print(`across all strategies in setS.`):
print(`inputs: permutation length n`):
print(`outputs: boolean representing whether or not Kutin-Smithline's strategy is optimal`):
print(`example: KSCheck(4, cyclicStrats(4));`):

elif nargs=1 and args[1]=inductiveStrat then 
print(`inductiveStrat(n): returns set of strategies on [n] that are optimal for n-1 and smaller`):
print(`using an inductive approach to identification of the best strategies (mostly to save computation time/memory.)`):
print(`inputs: permutation length n`):
print(`outputs: set of strategies S (note: should have nops(S) = 2*(n-1)!)`):
print(`example: inductiveStrat(6);`):


## HELPERS HELP

elif nargs=1 and args[1]=permInd then
print(`permInd(setP, p): compares permutations to check at which indices they agree`):
print(`inputs: fixed permutation setP, guessed permutation p`):
print(`outputs: a list [L1,L2] where L1 is the list of indices where setP and p agree`):
print(`and L2 is the list of indices where setP and p disagree.`):

elif nargs=1 and args[1]=permChecker then
print(`permChecker(p1,p2): checks that two permutations p1 and p2 have same length and are both valid permutations`):
print(`inputs: permutations p1 and p2`):
print(`outputs: if triggered, FAIL returned`):

elif nargs=1 and args[1]=stratChecker then
print(`stratChecker(p,s): checks that strategy list has same length as permutation length,`):
print(`and that each list entry is a permutation of the proper length`):
print(`inputs: permutation p and strategy (list) s`):
print(`outputs: if triggered, FAIL returned`):

elif nargs=1 and args[1]=cyclicPermsGT then
print(`cyclicPermsGT(n): generates all cyclic permutations of [n] using GroupTheory package (to verify validity of our code)`):
print(`inputs: permutation lenght n`):
print(`outputs: set of all cyclic permutations on [n]`):

elif nargs=1 and args[1]=whatsNew then
print(`whatsNew(): outputs handwritten description of what the code's newest features are, along with edit date `):

else
print(`no function of name `, args[1], ` exists.`):

fi:

end:

# a function for Dr Z's weekly meetings
whatsNew := proc()
print(`Updates as of 12/9/24`):
print(`-----------------------------------------------------------------------------`):
print(`(1.) Generalized strategy analysis/ranking to account for non-cyclic strategies `)::
print(`-----------------------------------------------------------------------------`):
print(`(2.) Added procs derange(n) and derangeStrats(n) which generate all derangements on n and all strategies using these derangements.`):
print(`Experimentally proved that cyclic shift is still optimal among all derangement strategies up to n=5.`):
print(`-----------------------------------------------------------------------------`):
print(`(3.) Optimized memory usage to allow code to actually run on compute servers.`):
print(`This allowed us to prove experimentally that cyclic shift is optimal for n=6. Further optimization/tidying can still be done.`):
print(`For example, derangeStrats still uses too much memory for n > 5, so I will continue to examine this.`):
end:



with(combinat):
with(GroupTheory):

## GUESSER (GENERAL, WITH INFINITY)
#
# input setP fixed permutation to guess, s strategy
# guesses random permutations, fixing correct entries, until correct
# or until strategy forces an already seen guess
# output is number of turns taken to guess correctly

guesser := proc(setP, s, boolSee := false) local turns,p,P,i:
turns := 1:
p := [seq(i, i=1..nops(setP))]:
P := {p}: # set of already seen guesses

if type(s,list) then 
    stratChecker(setP,s):
fi:

while not p = setP do
    p := nextGuess(setP,p,s,boolSee):

    if boolSee = true then 
        print(p);
    fi:

    if p in P and not s = random then       # note that a random strategy allows us to break out of a guessing "loop"
        turns := infinity:
        p := setP: # causes break out of while loop
    fi:

    P := P union {p}:
    turns ++ :
od:

return turns:
end:


## GUESSER (GENERAL)
# NO ALLOWANCE FOR INFINITY/LOOPING CASE
#
# input setP fixed permutation to guess, s strategy
# guesses random permutations, fixing correct entries, until correct
# output is number of turns taken to guess correctly

guesserOld := proc(setP, s, boolSee := false) local turns,p,i:
turns := 1:
p := [seq(i, i=1..nops(setP))]:

if type(s,list) then 
    stratChecker(setP,s):
fi:

while not p = setP do
    p := nextGuess(setP,p,s,boolSee):
    if boolSee = true then 
        print(p);
    fi:
    turns ++ :
od:

return turns:
end:


## GUESSER (GENERAL, WITH INPUT)
#
# input setP fixed permutation to guess, iniP first guessed permutation, s strategy
# guesses random permutations, fixing correct entries, until correct
# output is number of turns taken to guess correctly

guesserInpt := proc(setP, iniP, s, boolSee) local turns,p:
turns := 1:
p := iniP:

if type(s,list) then 
    stratChecker(setP,s):
fi:

while not p = setP do
    p := nextGuess(setP,p,s,boolSee):
    if boolSee = true then 
        print(p);
    fi:
    turns ++ :
od:

return turns:
end:



## NEXT GUESS (GENERAL)
#
# inputs setP fixed permutation to guess
# inputs current guess p 
# output is the permutation representing the next guess, generated using strategy s

nextGuess := proc(setP,p,s,boolSee := false) local nextP, corrLoc,incorrLoc, i,j, locPerm, n:

corrLoc := permInd(setP,p)[1]:
incorrLoc := permInd(setP,p)[2]:
nextP := [0$nops(setP)]:

for i from 1 to nops(corrLoc) do
    nextP[corrLoc[i]] := setP[corrLoc[i]]:
od:


## generate next guess using appropriate strategy

if args[3]=random then
    # randomly permute the incorrect entries
    locPerm := randperm(nops(incorrLoc)): 
    
    # make sure the permutation is not trivial, so the next guess will be different from current
    while locperm = permute(nops(setP))[1] do
        locPerm := randperm(nops(incorrLoc)): 
    od:

    for j from 1 to nops(incorrLoc) do
        nextP[incorrLoc[j]] :=  p[incorrLoc[locPerm[j]]]:
    od:

elif args[3]=cyclic then
    for j from 1 to nops(incorrLoc)-1 do
        nextP[incorrLoc[j]] :=  p[incorrLoc[j+1]]:
    od:
    nextP[incorrLoc[nops(incorrLoc)]] := p[incorrLoc[1]]:

elif type(args[3],list) then 
    locPerm := s[nops(incorrLoc)]:
    for j from 1 to nops(incorrLoc) do
        nextP[incorrLoc[j]] :=  p[incorrLoc[locPerm[j]]]:
    od:

else 
    error `No such strategy exists.`:
fi:

if boolSee = true then 
    print(`Incorrect Locations =`, incorrLoc):
fi:

return nextP:
end:




## PERMUTATION INDEX CLASSIFICATION
#
# inputs setP fixed permutation to guess
# inputs p the current guessed permutation
# outputs lists of indices where entries agree, and also disagree

permInd := proc(setP, p) local corrLoc, incorrLoc, i:
permChecker(setP,p):

corrLoc:=[]:
incorrLoc:=[]:

for i from 1 to nops(setP) do
    if setP[i] = p[i] then
        corrLoc := [op(corrLoc), i]:
    else 
        incorrLoc := [op(incorrLoc), i]:
    fi:
od:

[corrLoc, incorrLoc]:
end:



## PERMUTATION ERROR CHECKER
#
# inputs two permutations
# checks if both are same length and valid permutations

permChecker := proc(p1, p2) local n:

if not nops(p1) = nops(p2) then 
    error `input permutations have differing lengths.`:
fi:

n := nops(p1):

# if (not p1 in permute(n)) or (not p2 in permute(n)) then 
if (not isPerm(p1)) or (not isPerm(p2)) then 
    error `at least one of input permutations not a true permutation`:
fi:

end:


## PERMUTATION TYPE CHECKER
# 
# 
# inputs list
# checks if list is a permutation on {1,..,nops(p)}

isPerm := proc(p) local n,i:
n := nops(p):

for i from 1 to n do
    if not member(i,p) then
        false:
    fi:
od:

true:
end:


## STRATEGY ERROR CHECKER
# 
# inputs a potential strategy
# checks that it is a valid strategy
# i.e. s is a list of length n each with a permutation of length equal to position in list

stratChecker := proc(p,s) local i:

if not nops(p) = nops(s) then 
    error `strategy length is not equal to length of permutation`:
fi:

for i from 1 to nops(s) do
    if not nops(s[i])=i then 
        error `strategy component has improper length. Error at index`, i:
    fi:
od:

end:



## GENERATING FUNCTION 
# 
# inputs permutation length n, strategy s, variable var
# outputs the polynomial representing the generating function of strategy s in terms of variable x
# i.e. the coefficient a_d is the number of permutations in [n] which take d turns to guess using strategy s
# sanity check: gf evaluated at x=1 should yield n! (total number of permutations of [n])

gf := proc(n,s,var := x) local P,p: 
# Sn := permute(n): 
# add(var^guesser(p,s), p in Sn):
P := 0: # polynomial

p := firstperm(n):
while not p = FAIL do
    P := P + var^guesser(p,s):
    p := nextperm(p):

od:

P:
end:


## AVERAGE SPEED 
# 
# inputs permutation length n, strategy s, number of trials N
# outputs average number of turns taken to correctly guess a random permutation on [n]
avgSpeed := proc(n,s,N) local i: 
evalf(add(guesser(randperm(n), s), i=1..N)/N);
end:


## CYCLIC PERMUTATION GENERATOR - USING GROUP THEORY PACKAGE
cyclicPermsGT := proc(n) local p,P,C:
C := {}:
P := permute(n):

for p in P do
    if PermCycleType(Perm(p)) = [n] then 
        C := C union {p}:
    fi:
od:

if n = 1 then 
    C := {[1]}:
fi:

C:
end:


## CYCLIC PERMUTATION GENERATOR - ORIGINAL CODE
cyclicPerms := proc(n) local c,C,p,P,i:

# generate cycles representing all cyclic permutations
C := {}:    # set of cycles

for p in permute([seq(2..n)]) do
    C := C union {[1,op(p)]}:   
od:

# turn them into permutations again
P := {}:    # set of permutations

for c in C do
    p := [0$n]:
    for i from 2 to n do
        p[c[i]] := c[i-1]:   # transform each cycle into a permutation
    od:
    p[c[1]] := c[n]:    # "loop around" case in the cycle, i.e. send last entry to first position

    P := {op(P), p}:
od:

P:
end:


## DERANGEMENTS GENERATOR
# 
# 
# inputs permutation length n
# outputs collection (set) of permutations which are derangements on [n]
# i.e. there are no fixed points 

derange := proc(n) local p,P:
P := {}:     # set of derangements

p := firstperm(n):
while not p = FAIL do
    if isDer(p) then 
        P := P union {p}:
    fi:

    p := nextperm(p):
od:

P:
end:


## DERANGEMENT CHECKER
# 
# 
# inputs permutation 
# outputs boolean for if permutation is a derangement 

isDer := proc(p) local n,i:
n := nops(p):

for i from 1 to n do 
    if p[i] = i then 
        return FAIL:
    fi:
od:

true:
end:



## CYCLIC STRATEGY COLLECTION GENERATOR
# 
# inputs length n 
# outputs a collection (set) of all strategies (lists) consisting of cyclic permutations

cyclicStrats := proc(n) local c,C,CC,p,P,s:
if n=1 then 
    RETURN({[[1]]}):
fi:

# recursion:
C := cyclicStrats(n-1):
CC := {}:

P := cyclicPermsGT(n):
for c in C do 
    for p in P do 
        s := [op(c),p]:
        CC := CC union {s}:
    od:
od:

CC:
end:


## DERANGEMENT STRATEGY COLLECTION GENERATOR
# 
# inputs length n 
# outputs a collection (set) of all strategies (lists) consisting of permutations which are derangements

derangeStrats := proc(n) local c,C,CC,p,P,s:
if n=1 then 
    RETURN({[[1]]}):    # needed for completeness, doesn't make sense as a derangement
fi:

# recursion:
C := derangeStrats(n-1):
CC := {}:

P := derange(n):
for c in C do 
    for p in P do 
        s := [op(c),p]:
        CC := CC union {s}:
    od:
od:

CC:
end:


## RANK STRATEGIES
# 
# inputs permutation length n and strategy set setS
# outputs list of strategies in setS which have the lowest average number of guesses
# computed from the generating function

rankStrats := proc(n, setS) local L,A,a,s,i,j:

A:= []: # running list of averages
L:= []: # entry l in L is of the form [avg, {set of strategies with that avg}]

for s in setS do
    a := gfAvg(n,s);

    if not a in A then
        A := sort([op(A),a]);
        member(a,A,'i'):
        L:= [seq(L[j], j=1..i-1), [a,{s}], seq(L[j], j=i..nops(A)-1)]:

    elif a in A then
        member(a,A,'i'):
        L[i][2] := L[i][2] union {s}:

    fi:

od:




L:
end:


## BEST STRATEGIES
# 
# inputs permutation length n and strategy set setS
# outputs list of strategies in setS which have the lowest average number of guesses
# computed from the generating function
# separate from rankStrats(n, setS) since this is faster -- doesn't order ALL (n-1)! strategies

bestStrats := proc(n, setS) local L,s,m,M:
# initialize using trivial strategy
L := []:
m := gfAvg(n,setS[1]):

# check all other strategies
for s in setS do
    M := gfAvg(n,s):

    if M = m then 
        L := [op(L), s]:

    elif M < m then 
        m := M:
        L := [s]:
    fi:
od:

L:
end:


## WORST STRATEGIES
# 
# inputs permutation length n and strategy set setS
# outputs list of strategies in setS which have the highest average number of guesses
# computed from the generating function
# separate from rankStrats(n,setS) since this is faster -- doesn't order ALL (n-1)! strategies

worstStrats := proc(n, setS) local L,s,m,M:
# initialize 
L := []:
m := gfAvg(n,setS[1]):

# check all other strategies
for s in setS do
    M := gfAvg(n,s):

    if M = m then 
        L := [op(L), s]:

    elif M > m then 
        m := M:
        L := [s]:
    fi:
od:

L:
end:


## GEN FUNC TO AVERAGE
# 
# inputs length of permutation n and generating function polynomial for a strategy
# outputs the average number of guesses for that strategy

gfAvg := proc(n,s) local p,d,i,A: 
p := gf(n,s,x):
d := degree(p,x):   # note that infinite degree is not a polynomial, so causes d := FAIL

if d = FAIL then 
    A := infinity:
else 
    A := add(i*coeff(p,x,i), i=1..d)/n!:
fi: 

A:
end:


## KUTIN-SMITHLINE CHECK 
# 
# inputs length of permutation n and setS
# outputs boolean whether or not kutin-smithline strategy has best average performance from setS

KSCheck := proc(n, setS) local L,KS,i:
L := bestStrats(n, setS):

## build K-S strategy
KS := [[1]]:
for i from 2 to n do 
    KS := [op(KS), [seq(2..i), 1]]:
od:

evalb(KS in L):
end:


## LEADING COEFFICIENT ANALYSIS
#
# input permutation length n 
# outputs list of all strategies whose generating function has a coefficient of 1 on the x^n term
# (leading coefficient of the best strategy, which has a max number of guesses equal to n) --> EXAMINE THIS?? COULD CHANGE ESP FOR NOT CYCLIC PERMS
# i.e. all strategies which guess the fewest (only 1) permutation in the maximum number of guesses 

lcCheck := proc(n, setS) local L,s,p,lc,d,minD,minLC:
L := []:
minD := 0:

for s in setS do
    p := gf(n,S):
    d := degree(p,x):
    lc := coeff(p,x,d):

    if minD = 0 then 
        minD := d:
        minLC := lc:
        L := [S]:

    elif d < minD then 
        minD := d:
        L := [s]:

    elif d = minD then 

        if lc < minLC then 
            minLC := lc:
            L := [s]:

        elif lc = minLC then 
            L := [op(L),s]:
        fi:

    fi:

od:

L:
end:



## BEST STRATEGIES - INDUCTIVELY
# 
# input length n
# output is set of strategies on [n] which are optimal for n-1 and smaller

inductiveStrat := proc(n) local S,SInd,s,ss,p:
S := {}:
SInd := bestStrats(n-1, cyclicStrats(n-1)):   # can hard code Kutin-Smithline to save computation time

for s in SInd do 
    for p in cyclicPermsGT(n) do
        ss := [op(s),p]:
        S := S union {ss}:
    od:
od:

S:

end:






# maple -q<inputfilename>outputfilename & (quiet, & lets it keep running)
# ps x | grep maple (status update)


# cyclic shfit always by the same amount... focus on one specific other strategy and prove that cyclic shift is superior