## symmetric difference

### Data

in lua

#### Tags

backtracking, combination, puzzle

### Source Code

``````-- Symmetric difference implementation
-- See: http://en.wikipedia.org/wiki/Symmetric_difference

-- Returns a copy of a given array t where keys and values were swapped
local function swapKeysAndValues(t)
local _t = {}
for k,v in pairs(t) do _t[v] = k end
return _t
end

-- Returns the symmetric difference of two sets  (i.e, all
-- the elements which are either in first set or the second
-- set, but not in both)
-- s1 : a first set
-- s2 : a second set
-- returns : an array of values from the given sets
local function symmdiff(s1, s2)
local t1 = swapKeysAndValues(s1)
local t2 = swapKeysAndValues(s2)
local r = {}

for _, v in pairs(s1) do
if not t2[v] then table.insert(r, v) end
end

for _, v in pairs(s2) do
if not t1[v] then table.insert(r, v) end
end

return r
end

return symmdiff``````
``````-- Tests for symmdiff.lua
local symdiff = require 'symdiff'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

local function same(t1, t2)
if #t1~=#t2 then return false end
for k,v in pairs(t1) do
if t2[k] ~= v then return false end
end
return true
end

run('Symmetric difference', function()
local s1, s2 = {1, 2, 3, 4}, {3, 4, 5, 6}
assert(same(symdiff(s1,s2),{1,2,5,6}))

local s1, s2 = {}, {}
assert(same(symdiff(s1,s2),{}))

local s1, s2 = {1}, {2}
assert(same(symdiff(s1,s2),{1,2}))

local s1, s2 = {3}, {3}
assert(same(symdiff(s1,s2),{}))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````