Roblox Snack Break #27

function Encode0(t)
    table.sort(t)
    local enc = {} -- string
    local min, max
    local function submit()
        if not min then return end
        enc[#enc+1] = min == max
            and min
            or string.format("%s-%s", min, max)
    end
    local function add(v)
        if max == v - 1 then -- extend max
            max = v
            return
        elseif min then
            submit()
        end
        min, max = v, v
    end
    for i = 1, #t do
        add(t[i])
    end
    submit()
    return table.concat(enc, ", ")
end
function Encode1(t)
    table.sort(t)
    local enc = {} -- string
    local min, max, rep
    local function submit()
        if not min then return end
        enc[#enc+1] =
            min == max and
                (rep == 1 and min
                    or string.format("%s x%s", min, rep))
            or min + 1 == max and string.format("%s, %s", min, max)
            or string.format("%s-%s", min, max)
    end
    local function add(v)
        if v - 1 == max and (not rep or rep == 1) then -- extend max
            max = v
            return
        elseif v == max then -- add repetition
            if min ~= max then
                max = max - 1 -- return max to prev value
                submit()
            end
            min, max = v, v
            rep = rep + 1
            return
        elseif min then -- submit what exists
            submit()
        end
        min, max, rep = v, v, 1
    end
    for i = 1, #t do
        add(t[i])
    end
    submit()
    return table.concat(enc, ", ")
end
--Level 2
--[[Algorithm
As we proceed, reduce to objects, not string
Only stringify at end
Objects:
(Each number given to .Add is wrapped in 'Single')
Single (1)
    .Add(2) -> Range
    .Add(Range(2, 3)) -> Range(1, 3)
    .Add(self) -> Duplicate(self, 2)
Range (1, 2)
    .Add(2) -> Single(1) + Duplicate(2, 2) [this is for duos only]
    .Add(3) -> Range(1, 3)
    .Add(Range(3,4)) -> Range(1, 4)
    .Add(self) -> Duplicate(self, 2)
Duplicate (1 x2)
    .Add(value equivalent to self value) -> Duplicate(self, 3)
    .Add(Duplicate with value equivalent to self value)
        -> Duplicate(self, self rep + arg rep)
More specific algorithm:
1. Wrap all table items in Single
2. Apply Add algorithm
    If NoChange, go to next item
    For all other options, record "changeMade"
    If AbsorbNext or ReplaceBoth, delete next item from table
    If ReplaceBoth, replace cur item with new one
    If ReplaceBothTwoNew, replace cur item with new one and next item with 2nd new one
3. When no more items, repeat entire loop if "changeMade"
4. Now we have to search for multi-item patterns
    -We must attempt to find the largest pattern available
Each type is to have these functions:
:Add(value):Return (see below), value1, value2
:Equals(value):bool
:GetMinValue() -- is to be nil for duplicate
:GetMaxValue() -- is to be nil for duplicate
:GetSingleValue() -- is to be nil for everything except Single
:GetNumRepetitions() -- must be a number (often 1)
:GetInnerValue() -- must return self (if not duplicate) or else the duplicate's contained value
:ToString()
]]
--.Add returns:
local NoChange = 0
local AbsorbNext = 1
local ReplaceBoth = 2
local ReplaceBothTwoNew = 3
local Single, Range, Duplicate
local function IsDuplicate(a, b)
    return a:GetInnerValue():Equals(b:GetInnerValue())
end
local function Merge(a, b)
    return Duplicate(
        a:GetInnerValue(),
        a:GetNumRepetitions() + b:GetNumRepetitions())
end
local function HandleDuplicate(self, v)
    if IsDuplicate(self, v) then
        return ReplaceBoth, Merge(self, v)
    end
    return NoChange
end
function Single(num)
    return {
        GetSingleValue = function() return num end,
        GetMinValue = function() return num end,
        GetMaxValue = function() return num end,
        GetNumRepetitions = function() return 1 end,
        GetInnerValue = function(self) return self end,
        Add = function(self, v)
            if v:GetNumRepetitions() == 1 and v:GetMinValue() == num + 1 then
                -- if num repetitions > 1, it's something like "5, 6 x2" (so no change)
                return ReplaceBoth, Range(num, v:GetMaxValue())
            end
            return HandleDuplicate(self, v)
        end,
        Equals = function(self, v)
            return v:GetSingleValue() == num and v:GetNumRepetitions() == 1
        end,
        ToString = function()
            return num
        end,
    }
end
function Range(min, max)
    return {
        GetSingleValue = function() return nil end,
        GetMinValue = function() return min end,
        GetMaxValue = function() return max end,
        GetNumRepetitions = function() return 1 end,
        GetInnerValue = function(self) return self end,
        Add = function(self, v)
            if v:GetSingleValue() == max and min + 1 == max then -- split duo-range into single & duplicate
                return ReplaceBothTwoNew, Single(min), Duplicate(Single(max), 2)
            elseif v:GetMinValue() == max + 1 and v:GetNumRepetitions() == 1 then -- extend
                max = v:GetMaxValue()
                return AbsorbNext
            end
            return HandleDuplicate(self, v)
        end,
        Equals = function(_, v)
            return v:GetMinValue() == min and v:GetMaxValue() == max and v:GetNumRepetitions() == 1
        end,
        ToString = function()
            return min == max - 1
                and string.format("%s, %s", min, max)
                or string.format("%s-%s", min, max)
        end,
    }
end
function Duplicate(v, count)
    if type(v) ~= "table" then error("v must be an object, not " .. tostring(v)) end
    if type(count) ~= "number" or count < 2 then error("count must be >=2, not " .. tostring(count)) end
    return {
        GetSingleValue = function() return nil end,
        GetMinValue = function() return nil end,
        GetMaxValue = function() return nil end,
        GetNumRepetitions = function() return count end,
        GetInnerValue = function(self) return v end,
        Add = HandleDuplicate,
        Equals = function(_, v2)
            return v2 ~= v2:GetInnerValue() and v2:GetInnerValue():Equals(v) and v2:GetNumRepetitions() == count
        end,
        ToString = function()
            return string.format(
                v:GetSingleValue()
                    and "%s x%s"
                    or "(%s) x%s",
                v:ToString(),
                count)
        end,
        IncrementCount = function() count = count + 1 end, --for ExtendPatterns only
    }
end
local function Pattern(items)
    return {
        IsPatternEqual = function(self, t, i) --t is table of items to compare with, 'i' is t's starting index (for comparison purposes)
            for j = 1, #items do
                if not items[j]:Equals(t[i+j-1]) then
                    return false
                end
            end
            return true
        end,
        GetPatternLength = function() return #items end,
        GetItems = function() return items end,
        Equals = function(self, v)
            v = v.GetItems and v:GetItems()
            if not v then return end
            for i = 1, #items do
                if not items[i]:Equals(v[i]) then
                    return false
                end
            end
            return true
        end,
        ToString = function()
            local s = {}
            for i = 1, #items do
                if i > 1 then
                    s[#s + 1] = ", "
                end
                s[#s + 1] = items[i]:ToString()
            end
            return table.concat(s)
        end,
        --These functions for the sake of Duplicate and merging:
        GetSingleValue = function() return nil end,
        GetNumRepetitions = function() return 1 end,
        GetInnerValue = function(self) return self end,
        --GetMinValue/GetMaxValue/Add not needed
    }
end
function Encode2(t)
    --Wrap all table items in Single
    for i = 1, #t do
        t[i] = Single(t[i])
    end
    --Apply Add to all items
    local noChangesMade, i, status, a, b
    repeat
        noChangesMade = true
        i = 1
        while t[i + 1] do
            status, a, b = t[i]:Add(t[i + 1])
            if status == NoChange then
                i = i + 1
            else
                noChangesMade = false
                if status == AbsorbNext or status == ReplaceBoth then
                    table.remove(t, i + 1)
                end
                if status == ReplaceBoth or status == ReplaceBothTwoNew then
                    t[i] = a
                    if status == ReplaceBothTwoNew then
                        t[i + 1] = b
                    end
                end
            end
        end
    until noChangesMade
    --Look for multi-item patterns.
    --To start with, get rid of any duo-ranges (which can mess up pattern detection when there is a "3, 2, 3, 2" sequence -- the middle "2, 3" is otherwise ignored):
    for i = 1, #t do
        local min, max = t[i]:GetMinValue(), t[i]:GetMaxValue()
        if min and max and min + 1 == max then
            t[i] = Single(min)
            table.insert(t, i + 1, Single(max))
        end
    end
    local function FindPatterns()
        for size = 2, math.floor(#t/2) do
            --a, b, c, d, e
            --size 2 means we want to check (a,b) vs (c,d) and (b,c) vs (d,e)
            --thus, max initial index is 'b', or #t - size*2 + 1
            local equal
            for i = 1, #t - size * 2 + 1 do
                equal = true
                for j = i, i + size - 1 do
                    if not t[j]:Equals(t[j + size]) then
                        equal = false
                        break
                    end
                end
                if equal then
                    --Gather items that are duplicates
                    local items = {}
                    for j = i, i + size - 1 do
                        items[#items+1] = t[j]
                    end
                    --Remove them from the table in both places they exist
                    for j = i + size * 2 - 1, i + size, -1 do
                        table.remove(t, j)
                    end
                    for j = i + size - 1, i + 1, -1 do
                        table.remove(t, j)
                    end
                    t[i] = Duplicate(Pattern(items), 2)
                    return true
                end
            end
        end
        return false
    end
    local function ExtendPatterns()
        local pattern
        for i = 1, #t - 1 do
            pattern = t[i]:GetInnerValue()
            pattern = pattern.IsPatternEqual and pattern or nil
            if pattern and pattern:IsPatternEqual(t, i + 1) then
                for j = i + pattern:GetPatternLength(), i + 1, -1 do
                    table.remove(t, j)
                end
                t[i]:IncrementCount()
                return true
            end
        end
        return false
    end
    while FindPatterns() do while ExtendPatterns() do end end
    --ToString
    local enc = {}
    for i = 1, #t do
        enc[i] = t[i]:ToString()
    end
    return table.concat(enc, ", ")
end

local function Test(a, b)
    return {Data = a, Expected = b}
end
local function RunTests(setName, tests, func)
    local total, good = 0, 0
    for i = 1, #tests do
        total = total + 1
        local v = func(tests[i].Data)
        if v == tests[i].Expected then
            good = good + 1
        else
            print(setName, "Test", i, "failed:", v, "~=", tests[i].Expected)
        end
    end
    print(string.format("%s tests: %s/%s correct", setName, good, total))
end
local tests0 = {
    Test({1, 2, 3, 4}, "1-4"),
    Test({7, 4, 6, 2, 8}, "2, 4, 6-8"),
    Test({1, -2, 3, -4, 5, 6}, "-4, -2, 1, 3, 5-6"),
    Test({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, "1-10"),
    Test({1, 2, 5, 6, 7}, "1-2, 5-7"),
    Test({0}, "0"),
    Test({}, ""),
}
local tests1 = {
    Test({2, 1, 1, 1, 0}, "0, 1 x3, 2"),
    Test({1, 2, 5, 6, 7}, "1, 2, 5-7"),
    Test({1, 1, 2, 3, 4}, "1 x2, 2-4"),
    Test({1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 2, 2, 3, 3, 4, 4}, "1 x4, 2 x4, 3 x4, 4 x4"),
}
local tests2 = {
    Test({1, 2, 3, 4}, "1-4"),
    Test({4, 2, 3, 1}, "4, 2, 3, 1"),
    Test({1, 2, 1, 2}, "(1, 2) x2"),
    Test({1, 2, 1, 2, 1, 2, 1, 2}, "(1, 2) x4"),
    Test({1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7}, "(1 x2, 2 x2, 3 x2, 4 x2) x2, 5-7"),
    Test({0, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2}, "0, (1 x2, 2 x2) x3"),
    Test({1, 1, 1, 1, 5, 1, 5}, "1 x4, 5, 1, 5"), --[[NOTE: Original test requires this:
    Test({1, 1, 1, 1, 5, 1, 5}, "1 x3, (1, 5) x2"),
    but without a more complicated algorithm, I don't see how to do that.
    Further, if you consider how you'd encode the representation, it is less efficient than "1 x4, 5, 1, 5":
    #s to encode each component:
        Single = 2: Type + Value
        List of single = 2 + #values: Type + Count + Values (good for 2+)
        Range = 3: Type + Min + Max
        Duplicate = 2+valueCost: Type + (Value Encoding) + Duplicate Count
        Pattern = 2+valueCost: Type + Length + (values encoding)
        (There may be more efficient encodings but this is the easiest I could think of)
    "1 x3, (1, 5) x2": Duplicate(Single), Duplicate(Pattern(Single, Single))
        = 2+2 + 2+2+2+2 = 12
    "1, 1, 1, 1, 5, 1, 5" is just a list of 7 singles, or 2+7=9
        If you don't allow List, it's 2*7=14
    "1 x4, 5, 1, 5" = Duplicate(Single), List<Single> = 4 + 5=9
        or (if you disallow List) 4 + 2*3=10
    Thus, "1 x4, 5, 1, 5" ties with "1, 1, 1, 1, 5, 1, 5" if you allow List<Single>
        and in all cases "1 x3, (1, 5) x2" is less efficient than "1 x4, 5, 1, 5"
    ]]
    Test({1, 1, 1, 1, 5, 1, 5, 1}, "1 x4, (5, 1) x2"),
}
tests3 = {
    Test({1, 3, 5, 1, 2, 1, 2, 1, 2, 7, 9, 5, 1, 3, 5, 1, 2, 1, 2, 1, 2, 7, 9, 5},
        "(1, 3, 5, (1, 2) x3, 7, 9, 5) x2"),
    Test({6, 2, 2, 6, 2, 2, 6, 2, 2, 1, 3, 2, 3, 2, 5, 1, 3, 2, 3, 2, 5, 7},
        "(6, 2 x2) x3, (1, (3, 2) x2, 5) x2, 7"),
}
local function Set(a, b, c)
    return {Name = a, Tests = b, Func = c}
end
local allTests = {
    Set("Level 0", tests0, Encode0),
    Set("Level 1", tests1, Encode1),
    Set("Level 2", tests2, Encode2),
    Set("Level 3", tests3, Encode2), -- Could make Encode2 fit "Level2"'s implied limitation by refusing to allow a Pattern in a Pattern, but not worth it
}
for i = 1, #allTests do
    RunTests(allTests[i].Name, allTests[i].Tests, allTests[i].Func)
end