[WIP]Solver

local LCF, constant

--Thanks to Xtansia for synthetic division function!
--https://gist.github.com/Xtansia/e4e30318b890ea1dfdfe
local function synthetic_division (polynomial, divisor_factor)
    local degree = table.maxn(polynomial)
    local work_table = {
        [degree] = polynomial[degree]
    }

    for i = degree - 1, 0, -1 do
        work_table[i] = (polynomial[i] or 0) + work_table[i + 1] * divisor_factor
    end

    local result = {}
    local remainder = work_table[0]

    for i = 1, table.maxn(work_table) do
        result[i - 1] = work_table[i]
    end

    return result, remainder
end

local function polynomial_tostring(polynomial)
    local degree = table.maxn(polynomial)
    local str = ""
    for i = degree, 0, -1 do
        local coeff = polynomial[i] or 0
        local abs_coeff = math.abs(coeff)
        if abs_coeff > 0 then
            if i == degree then
                str = str .. (coeff < 0 and "-" or "")
            else
                str = str .. " " .. (coeff > 0 and "+" or "-") .. " "
            end
            if i > 0 then
                str = str .. (abs_coeff > 1 and abs_coeff or "") .. "x"
                if i > 1 then
                    str = str .. "^" .. i
                end
            else
                str = str .. abs_coeff
            end
        end
    end
    return str
end

local tArgs = {...}
local equation = table.concat( tArgs, "" ):gsub( " ", "" )
local synthetic_equation = {}

equation = equation:gsub( "%-x", "-1x" ):gsub( "^%d?x", "1x" ):gsub( "%+x", "+1x" )

local degree = 0

for sign, coef, x, power in equation:gmatch( "([%+%-]?)(%d+)(x?)%^?(%d*)" ) do
    power = tonumber( power ) or (x == "x" and 1 or 0)
    if sign == "-" then
        coef = -tonumber( coef )
    else
        coef = tonumber( coef )
    end
    if power and (power > degree) then
        degree = power
        LCF = coef
    end
    if tonumber( power ) == 0 then
        constant = coef
    end
    synthetic_equation[ power ] = coef
end

constant = constant or 0

print( "Generating Factors of LCF" )
local LCF_factors = {}
for i = 1, math.abs( LCF ) do
    if LCF % i == 0 then
        LCF_factors[ #LCF_factors + 1 ] = i
    end
end

print( "Generating Factors of constant" )
local constant_factors = {}
for i = 1, math.abs( constant ) do
    if constant % i == 0 then
        constant_factors[ #constant_factors + 1 ] = i
    end
end
if constant == 0 then
    constant_factors[ # constant_factors + 1 ] = 0
end

print( "Generating Possible Real Solutions" )
local real_solutions = {}
local _real = {}
for k, l in pairs( LCF_factors ) do
    for k, c in pairs( constant_factors ) do
        if not _real[ c/l ] then
            real_solutions[ #real_solutions + 1 ] = c/l
            _real[ c/l ] = true
        end
    end
end

print( "Generating Solutions" )
solutions = {}

for k, v in pairs( real_solutions ) do
    local e = equation:gsub( 'x', '*(' .. v .. ')' )
    local eneg = equation:gsub( 'x', '*(' .. -v .. ')' )
    if loadstring( "return " .. e )() == 0 then
        solutions[ #solutions + 1 ] = v
        print( v )
    end

    if v ~= 0 and loadstring( "return " .. eneg )() == 0 then
        solutions[ #solutions + 1 ] = -v
        print( -v )
    end
end

if #solutions ~= degree then
    print( "Generating Imaginary Soltions" )
    local eq, rem = synthetic_equation
    local deg = degree
    for k, v in pairs( solutions ) do
        eq, rem = synthetic_division( eq, v )
    end
    print( polynomial_tostring( eq ) )
    if table.maxn( eq ) ~= 2 then
        error( "Unable to compute imaginary solutions", 0 )
    end
    local a, b, c = eq[ 2 ] or 0, eq[ 1 ] or 0, eq[ 0 ] or 0
    --[[ (-b +- sqrt( b^2 - 4*a*c ) ) / 2 *a ]]--
    local root = math.sqrt( math.abs(b^2 - 4*a*c) )
    solution1 = -b / (2*a) .. "+" .. root / (2*a) .. "i"
    solution2 = -b / (2*a) .. "-" .. root / (2*a) .. "i"
    print( solution1 )
    print( solution2 )
end