read(`code_utilities.txt`):

##NOTE: If S=0, a filter returns its description

Help_filters:=proc()
    print(` AndFilters(f1,f2) , OrFilters(f1,f2) `):
    print(` XorFilters(f1,f2) , NotFilter(f1) `):
    print(` RedescribeFilter(f1,disc) , MakeSizeNFilter(n) `):
    print(` MakeSizeAtLeastNFilter(n) `):
    print(` MakeSizeGreaterThanNFilter(n) `):
    print(` MakeSizeNotNFilter(n) , MakeSizeAtMostNFilter(n) `):
    print(` MakeSizeLessThanNFilter(n) , MakeContainsNFilter(n) `):
    print(` MakeMaxNFilter(n) , MakeMinNFilter(n) `):
    print(` MakeCapNFilter(n) , MakeFloorNFilter(n) `):
    print(` MakeAtLeastTPeriodFilter(T) `):
    print(` MakeAtMostTPeriodFilter(T) `):
    print(` MakeAtLeastTPrefixFilter(T) `):
    print(` MakeAtMostTPrefixFilter(T) `):
    print(` MakeEqualMaxNimFilter(val) `):
    print(` MakeAtLeastMaxNimFilter(val) `):
    print(` MakeGreaterThanMaxNimFilter(val) `):
    print(` MakeNotEqualMaxNimFilter(val) `):
    print(` MakeAtMostMaxNimFilter(val) `):
    print(` MakeLessThanMaxNimFilter(val) `):
    print(` MakeEqualMaxNimPeriodFilter(val) `):
    print(` MakeAtLeastMaxNimPeriodFilter(val) `):
    print(` MakeGreaterThanMaxNimPeriodFilter(val) `):
    print(` MakeNotEqualMaxNimPeriodFilter(val) `):
    print(` MakeAtMostMaxNimPeriodFilter(val) `):
    print(` MakeLessThanMaxNimPeriodFilter(val) `):
    print(` MakeLongestPrefixSoFarFilter() `):
    print(` MakeStrictlyLongestPrefixSoFarFilter() `):
    print(` MakeLongestPeriodSoFarFilter() `):
    print(` MakeStrictlyLongestPeriodSoFarFilter() `):
    print(` MakeNewPrefixFilter() , MakeNewPeriodFilter() `):
    print(` IdentityFilter(S,F,P,G,L,E) `):
    print(` RelPrimeFilter(S,F,P,G,L,E) `):
    print(` PairRelPrimeFilter(S,F,P,G,L,E) `):
    print(` PrimitiveFilter(S,F,P,G,L,E) `):
    print(` MaxNimPossibleFilter(S,F,P,G,L,E) `):
    print(` MaxNimPossiblePeriodFilter(S,F,P,G,L,E) `):
end:

##FILTER MANIPULATORS

#Returns a filter that is the and of f1 and f2
AndFilters:=proc(f1,f2) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat(f1(S,F,P,G,L,E)," and ",
                f2(S,F,P,G,L,E)):
        fi:
        return f1(S,F,P,G,L,E) and f2(S,F,P,G,L,E):
    end:
    return f:
end:

#Returns a filter that is the or of f1 and f2
OrFilters:=proc(f1,f2) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat(f1(S,F,P,G,L,E)," or ",
                f2(S,F,P,G,L,E)):
        fi:
        return f1(S,F,P,G,L,E) or f2(S,F,P,G,L,E):
    end:
    return f:
end:

#Returns a filter that is the xor of f1 and f2
XorFilters:=proc(f1,f2) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat(f1(S,F,P,G,L,E)," exclusive or ",
                f2(S,F,P,G,L,E)):
        fi:
        return f1(S,F,P,G,L,E) xor f2(S,F,P,G,L,E):
    end:
    return f:
end:

#Returns a filter that is the not of f1
NotFilter:=proc(f1) local f:
    f:=proc(S,F,P,G,L,E) local str,spindex:
        if S=0 then
            str:=f1(S,F,P,G,L,E):
            if length(str) > 4 and str[1..4]="not " then
                return str[5..]:
            else
                return cat("not ",str):
            fi:
        fi:
        return not f1(S,F,P,G,L,E):
    end:
    return f:
end:

#Returns a filter that has the same boolean values as f1 but uses
#disc as its description instead
RedescribeFilter:=proc(f1,disc) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return disc:
        fi:
        return f1(S,F,P,G,L,E):
    end:
    return f:
end:

##FILTER GENERATORS

#Does S have exactly n elements?
MakeSizeNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            if n=1 then
                return cat(cat("having exactly ", convert(n, string)), " subtraction value"):
            else
                return cat(cat("having exactly ", convert(n, string)), " subtraction values"):
            fi:
        fi:
        return evalb(nops(S)=n):
    end:
    return f:
end:

#Does S have at least n elements?
MakeSizeAtLeastNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            if n=1 then
                return cat(cat("having at least ", convert(n, string)), " subtraction value"):
            else
                return cat(cat("having at least ", convert(n, string)), " subtraction values"):
            fi:
        fi:
        return evalb(nops(S)>=n):
    end:
    return f:
end:

#Does S have more than n elements?
MakeSizeGreaterThanNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            if n=1 then
                return cat(cat("having more than ", convert(n, string)), " subtraction value"):
            else
                return cat(cat("having more than ", convert(n, string)), " subtraction values"):
            fi:
        fi:
        return evalb(nops(S)>n):
    end:
    return f:
end:

#Does S not have exactly n elements?
MakeSizeNotNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            if n=1 then
                return cat(cat("not having exactly ", convert(n, string)), " subtraction value"):
            else
                return cat(cat("not having exactly ", convert(n, string)), " subtraction values"):
            fi:
        fi:
        return evalb(nops(S)<>n):
    end:
    return f:
end:

#Does S have at most n elements?
MakeSizeAtMostNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            if n=1 then
                return cat(cat("having at most ", convert(n, string)), " subtraction value"):
            else
                return cat(cat("having at most ", convert(n, string)), " subtraction values"):
            fi:
        fi:
        return evalb(nops(S)<=n):
    end:
    return f:
end:

#Does S have fewer than n elements?
MakeSizeLessThanNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            if n=1 then
                return cat(cat("having fewer than ", convert(n, string)), " subtraction value"):
            else
                return cat(cat("having fewer than ", convert(n, string)), " subtraction values"):
            fi:
        fi:
        return evalb(nops(S)<n):
    end:
    return f:
end:

#Does S contain the element n?
MakeContainsNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having subtraction value ", convert(n, string)):
        fi:
        return evalb(n in S):
    end:
    return f:
end:

#Does S contain the element n as its maximum?
MakeMaxNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum subtraction value ", convert(n, string)):
        fi:
        return evalb(max(S)=n):
    end:
    return f:
end:

#Does S contain the element n as its minimum?
MakeMinNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having minimum subtraction value ", convert(n, string)):
        fi:
        return evalb(min(S)=n):
    end:
    return f:
end:

#Is every element of S less than or equal to n
MakeCapNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum subtraction value at most ", convert(n, string)):
        fi:
        return evalb(max(S)<=n):
    end:
    return f:
end:

#Is every element of S greater than or equal to n
MakeFloorNFilter:=proc(n) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having minimum subtraction value at least ", convert(n, string)):
        fi:
        return evalb(max(S)<=n):
    end:
    return f:
end:

#Is the period at least as long as T?
MakeAtLeastTPeriodFilter:=proc(T) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having period of length at least ", convert(T, string)):
        fi:
        return evalb(L>=T):
    end:
    return f:
end:

#Is the period at most as long as T?
MakeAtMostTPeriodFilter:=proc(T) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having period of length at most ", convert(T, string)):
        fi:
        return evalb(L<=T):
    end:
    return f:
end:

#Is the prefix at least as long as T?
MakeAtLeastTPrefixFilter:=proc(T) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having prefix of length at least ", convert(T, string)):
        fi:
        return evalb(G>=T):
    end:
    return f:
end:

#Is the prefix at most as long as T?
MakeAtMostTPrefixFilter:=proc(T) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having prefix of length at most ", convert(T, string)):
        fi:
        return evalb(G<=T):
    end:
    return f:
end:

#Is the maximum SG value equal to val?
MakeEqualMaxNimFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value equal to ", convert(val, string)):
        fi:
        return evalb(max(max(F),max(P))=val):
    end:
    return f:
end:

#Is the maximum SG value at least val?
MakeAtLeastMaxNimFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value greater than or equal to ", convert(val, string)):
        fi:
        return evalb(max(max(F),max(P))>=val):
    end:
    return f:
end:

#Is the maximum SG value greater than val?
MakeGreaterThanMaxNimFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value greater than ", convert(val, string)):
        fi:
        return evalb(max(max(F),max(P))>val):
    end:
    return f:
end:

#Is the maximum SG value not equal to val?
MakeNotEqualMaxNimFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value not equal to ", convert(val, string)):
        fi:
        return evalb(max(max(F),max(P))<>val):
    end:
    return f:
end:

#Is the maximum SG value at most val?
MakeAtMostMaxNimFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value less than or equal to ", convert(val, string)):
        fi:
        return evalb(max(max(F),max(P))<=val):
    end:
    return f:
end:

#Is the maximum SG value less than val?
MakeLessThanMaxNimFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value less than ", convert(val, string)):
        fi:
        return evalb(max(max(F),max(P))<val):
    end:
    return f:
end:

#Is the maximum period SG value equal to val?
MakeEqualMaxNimPeriodFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value in period equal to ", convert(val, string)):
        fi:
        return evalb(max(P)=val):
    end:
    return f:
end:

#Is the maximum period SG value at least val?
MakeAtLeastMaxNimPeriodFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value in period greater than or equal to ", convert(val, string)):
        fi:
        return evalb(max(P)>=val):
    end:
    return f:
end:

#Is the maximum period SG value greater than val?
MakeGreaterThanMaxNimPeriodFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value in period greater than ", convert(val, string)):
        fi:
        return evalb(max(P)>val):
    end:
    return f:
end:

#Is the maximum period SG value not equal to val?
MakeNotEqualMaxNimPeriodFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value in period not equal to ", convert(val, string)):
        fi:
        return evalb(max(P)<>val):
    end:
    return f:
end:

#Is the maximum period SG value at most val?
MakeAtMostMaxNimPeriodFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value in period less than or equal to ", convert(val, string)):
        fi:
        return evalb(max(P)<=val):
    end:
    return f:
end:

#Is the maximum period SG value less than val?
MakeLessThanMaxNimPeriodFilter:=proc(val) local f:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return cat("having maximum Sprague-Grundy value in period less than ", convert(val, string)):
        fi:
        return evalb(max(P)<val):
    end:
    return f:
end:

##MUTABLE FILTER GENERATORS

#Is the prefix length the longest seen so far
#(or tied for the longest)?
MakeLongestPrefixSoFarFilter:=proc() local rec,f:
    rec:=1:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return "having prefix length no shorter than longest seen before":
        fi:
        if G>=rec then
            rec:=G:
            return true:
        else
            return false:
        fi:
    end:
    return f:
end:

#Is the prefix length strictly the longest seen so far?
MakeStrictlyLongestPrefixSoFarFilter:=proc() local rec,f:
    rec:=0:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return "having strictly longer prefix length than any seen before":
        fi:
        if G>rec then
            rec:=G:
            return true:
        else
            return false:
        fi:
    end:
    return f:
end:

#Is the period length the longest seen so far
#(or tied for the longest)?
MakeLongestPeriodSoFarFilter:=proc() local rec,f:
    rec:=1:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return "having period length no shorter than longest seen before":
        fi:
        if L>=rec then
            rec:=L:
            return true:
        else
            return false:
        fi:
    end:
    return f:
end:

#Is the period length strictly the longest seen so far?
MakeStrictlyLongestPeriodSoFarFilter:=proc() local rec,f:
    rec:=0:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return "having strictly longer period length than any seen before":
        fi:
        if L>rec then
            rec:=L:
            return true:
        else
            return false:
        fi:
    end:
    return f:
end:

#Has this prefix length been seen before?
MakeNewPrefixFilter:=proc() local s,f:
    s:={}:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return "having new prefix length":
        fi:
        if G in s then
            return false:
        else
            s:=s union {G}:
            return true:
        fi:
    end:
    return f:
end:

#Has this period length been seen before?
MakeNewPeriodFilter:=proc() local s,f:
    s:={}:
    f:=proc(S,F,P,G,L,E)
        if S=0 then
            return "having new period length":
        fi:
        if L in s then
            return false:
        else
            s:=s union {L}:
            return true:
        fi:
    end:
    return f:
end:

##FILTERS

#Identity filter
IdentityFilter:=proc(S,F,P,G,L,E)
    if S=0 then
        return "satifying a tautology":
    fi:
    return true:
end:

#Is S relatively prime?
RelPrimeFilter:=proc(S,F,P,G,L,E)
    if S=0 then
        return "having relatively prime subtraction values":
    fi:
    return evalb(igcd(op(S))=1):
end:

#Is S pairwise relatively prime?
PairRelPrimeFilter:=proc(S,F,P,G,L,E) local lst,i,j:
    if S=0 then
        return "having pairwise relatively prime subtraction values":
    fi:
    lst:=[op(S)]:
    for i from 1 to nops(S)-1 do
        for j from i+1 to nops(S) do
            if igcd(lst[i],lst[j])<>1 then
                return false:
            fi:
        od:
    od:
    return true:
end:

#Is S "primitive", i.e. cannot be contracted nontrivially?
PrimitiveFilter:=proc(S,F,P,G,L,E)
    if S=0 then
        return "having no nontrivial contraction":
    fi:
    return evalb(op(E)=S):
end:

#Is the maximum potential SG value obtained?
MaxNimPossibleFilter:=proc(S,F,P,G,L,E)
    if S=0 then
        return "obtaining Sprague-Grundy value equal to size of subtraction set":
    fi:
    return evalb(max(max(F),max(P))=nops(S)):
end:

#Is the maximum potential SG value obtained in the period?
MaxNimPossiblePeriodFilter:=proc(S,F,P,G,L,E)
    if S=0 then
        return "obtaining Sprague-Grundy value in period equal to size of subtraction set":
    fi:
    return evalb(max(P)=nops(S)):
end: