-- remove all entries from a table 
local function wipe(t)
    for k in pairs(t) do
        t[k] = nil
    end
end

-- Find if any of the constraints make the set invalid.
-- In particular if there are letters with the same value
-- or leading letters with the value zero.
local tmp = {}
local function is_set_valid(letters, leading)
    wipe(tmp)
    for k, v in pairs(letters) do
        if letters[k] == 0 and leading[k] then
            -- Leading digits can't be zero
            return false 
        end
        if not tmp[v] then
            tmp[v] = true
        else
            -- Found a duplicate.
            return false 
        end
    end
    return true
end

-- Recursive iterator to move the letters table to the
-- next set of values.  Returns true if the letters 
-- table is set at the next state or nil if the
-- table has already reached the end.
local function next_set(letters, leading, index)
    index = next(letters, index)
    if not index then
        -- hit the end
        return
    end

    local cur = letters[index]
    if cur == 9 then -- roll over to next character and reset to our lowest 
        letters[index] = leading[index] and 1 or 0
        return next_set(letters, leading, index)
    else
        cur = cur + 1
        letters[index] = cur
        return true
    end
end

-- Parses the str to setup the letters and leading tables
-- for the iterator.  The values for the letters may or may
-- not be in a valid state under the constraints.
local function setup_state(str, letters, leading)
    for i = 1, #str do
        local letter = str:sub(i, i)
        if not tonumber(letter) then
            if i == 1 then
                leading[letter] = true
                letters[letter] = 1
            else
                letters[letter] = 0
            end
        end
    end
end

-- Replace the letters in the letters table with their values
-- in left right and answer
local function substitute(letters, left, right, answer)
    for k, v in pairs(letters) do
        left = left:gsub(k, v)
        right = right:gsub(k, v)
        answer = answer:gsub(k, v)
    end
    return tonumber(left), tonumber(right), tonumber(answer)
end

-- operation table of the functions to do the actual math.  Answers
-- are placed in the answers table passed in under the key of the
-- operation.
local op = {
    ['+'] = function(left, right, answers) answers['+'] = left + right end,
    ['-'] = function(left, right, answers) answers['-'] = left - right end,
    ['*'] = function(left, right, answers) answers['*'] = left * right end,
    ['^'] = function(left, right, answers) answers['^'] = left ^ right end,
}
op['?'] = function(left, right, answers)
    op['+'](left, right, answers)
    op['-'](left, right, answers)
    op['*'](left, right, answers)
    op['^'](left, right, answers)
end

-- helper function for the table sort
local function sort_results(a, b)
    if not a then
        return false
    elseif not b then
        return true
    end

    local a_left, b_left = a[1], b[1]
    if a_left ~= b_left then
        return a_left < b_left
    end

    local a_op, b_op = a[2], b[2]
    if a_op ~= b_op then
        return a_op < b_op
    end

    local a_right, b_right = a[3], b[3]
    if a_right ~= b_right then
        return a_right < b_right
    end
end

-- Iterate the results and print them
local function print_results(results)
    for i = 1, #results do
        local entry = results[i]
        print(entry[1] .. ' ' .. entry[2] .. ' ' .. entry[3] .. ' = ' .. entry[4])
    end
end

-- Takes left, operation, right and answer which can have letters in them and finds
-- the values for the letters which make the expression that they represent true.
-- operation can be + - * ^ or ?.  ? executes is all of the other operators ( + - * ^).
-- Output is printed to standard output in a sorted order.
function calculate(left, operation, right, answer)
    local results, letters, leading = {}, {}, {}
    setup_state(left, letters, leading)
    setup_state(right, letters, leading)
    setup_state(answer, letters, leading)
    repeat    
        if is_set_valid(letters, leading) then
            local answers = {}
            local s_left, s_right, s_answer = substitute(letters, left, right, answer)
            op[operation](s_left, s_right, answers)
            for op, answer in pairs(answers) do
                if answer == s_answer then
                    results[#results+1] = { s_left, op, s_right, s_answer }
                end
            end
        end
    until not next_set(letters, leading)
    table.sort(results, sort_results)
    print_results(results)
end