17.lua

-- A hastily-written Lua solution to the arithmetic puzzle 
-- written about in http://composition.al/blog/2016/12/31/a-simple-but-difficult-arithmetic-puzzle-and-the-rabbit-hole-it-took-me-down/
-- Took me longer to write than I initially thought, but at least the first approach I thought of worked.
-- I deliberately kept the code as I wrote it (took me 69 minutes to get to this), no post-facto cleanups done.

local function copy_table(t)
   local u = {}
   for k,v in pairs(t) do
      if type(v) == "table" then
         u[k] = copy_table(v)
      else
         u[k] = v
      end
   end
   return u
end

local function generate(exp, path, new)
   local here = exp
   for i = 1, #path do
      here = here[path[i]]
   end
   if type(here) == "table" then
      table.insert(path, 1)
      generate(exp, path, new)
      table.remove(path)
      table.insert(path, 3)
      generate(exp, path, new)
      table.remove(path)
   elseif here == "*" then
      local copy = copy_table(exp)
      local target = copy
      for i = 1, #path - 1 do
         target = target[path[i]]
      end
      target[path[#path]] = {"*", "_", "*"}
      table.insert(new, copy)
   end
end

local function generate_all(exps)
   local new = {}
   for _, exp in ipairs(exps) do
      table.insert(new, {"*", "_", copy_table(exp)})
      table.insert(new, {copy_table(exp), "_", "*"})
      generate(exp, {}, new)
   end
   return new
end

local ops = {{"*", "_", "*"}}

for _ = 1, 2 do
   ops = generate_all(ops)
end

local function show(op)
   if type(op) ~= "table" then
      return op
   end
   return "("..show(op[1]).." "..op[2].." "..show(op[3])..")"
end

local function showarr(a)
   local out = {}
   for i, n in ipairs(a) do
      out[i] = tostring(n)
   end
   return table.concat(out, " ")
end

local function permutations(l)
   if #l == 1 then
      return {{l[1]}}
   end
   local out = {}
   for i = 1, #l do
      local n = l[i]
      table.remove(l, i)
      local ps = permutations(l)
      table.insert(l, i, n)
      for _, p in ipairs(ps) do
         table.insert(p, 1, n)
         table.insert(out, p)
      end
   end
   return out
end

local function combinations(l, n)
   if n == 1 then
      local out = {}
      for i = 1, #l do
         table.insert(out, { l[i] } )
      end
      return out
   end
   local out = {}
   for i = 1, #l do
      local cs = combinations(l, n-1)
      for _, c in ipairs(cs) do
         table.insert(c, 1, l[i])
         table.insert(out, c)
      end
   end
   return out
end

local function fill(op, mark, ns)
   if type(op) == "table" then
      return {fill(op[1], mark, ns), fill(op[2], mark, ns), fill(op[3], mark, ns)}
   elseif op == mark then
      return table.remove(ns)
   else
      return op
   end
end

local numbers = {6, 6, 5, 2}
local symbols = {"+", "-", "*", "/"}

for _, ns in ipairs(permutations(numbers)) do
   for _, op in ipairs(ops) do
      op = fill(op, "*", copy_table(ns))
      for _, ss in ipairs(combinations(symbols, 3)) do
         local str = show(fill(op, "_", copy_table(ss)))
         local ret = load("return "..str)()
         print(str, ret)
         if ret == 17 then
            os.exit(0)
         end
      end
   end
end