Lua で小町算

「LL魂ブログ:キミならどう書く 2.0 - 2007 - その 2」 [1] より。Lua で挑戦。
これは言語に eval 相当があれば超有利でコルーチンがあればかなり柔軟に書ける種類の問題かなあと思った。

function table.copy(t)
  local t2 = {}
  for k,v in pairs(t) do
    t2[k] = v
  end
  return t2
end

function enum(items, enums, n)
  if n == 0 then
      coroutine.yield(enums)
  else
    for i,v in ipairs(items) do
      local lenums = table.copy(enums)
      table.insert(lenums, v)
      enum(items, lenums, n-1)
    end
  end
end

function make_expr(ops)
  local expr = ""
  for i,v in ipairs(ops) do
    expr = expr .. i .. v
  end
  return expr .. (#ops+1)
end

function gen_expr(ops, n)
  local co = coroutine.create(function() enum(ops, {}, n) end)
  return function()
    local code, res = coroutine.resume(co)
    return res and make_expr(res)
  end
end

i=0
for e in gen_expr({"+", "-", "*", "/", ""}, 8) do
  local result = loadstring("return "..e)()
  if result == 100 then
    print(e.."="..result)
    i = i + 1
  end
end
print(i.." patterns found")

玄箱での実行は5分かかった。

KURO-BOX% time lua komachi.lua
1+2+3+4+5+6+7+8*9=100
1+2+3-4+5+6+78+9=100
1+2+3-4*5+6*7+8*9=100
1+2+3-45+67+8*9=100
1+2+3*4-5-6+7+89=100
1+2+3*4*5/6+78+9=100
1+2+3*4*56/7-8+9=100
1+2+34-5+67-8+9=100
1+2+34*5+6-7-8*9=100
1+2-3*4+5*6+7+8*9=100
1+2-3*4-5+6*7+8*9=100
1+2*3+4+5+67+8+9=100
1+2*3+4*5-6+7+8*9=100
1+2*3-4+56/7+89=100
1+2*3-4-5+6+7+89=100
1+2*3*4*5/6+7+8*9=100
1+2*34-56+78+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
1+23-4+56/7+8*9=100
1+23-4-5+6+7+8*9=100
1+23*4+5-6+7-8+9=100
1+23*4+56/7+8-9=100
1+23*4-5+6+7+8-9=100
1+234-56-7-8*9=100
1+234*5*6/78+9=100
1+234*5/6-7-89=100
1-2+3+45+6+7*8-9=100
1-2+3*4+5+67+8+9=100
1-2+3*4*5+6*7+8-9=100
1-2+3*4*5-6+7*8-9=100
1-2-3+4*5+67+8+9=100
1-2-3+4*56/7+8*9=100
1-2-3+45+6*7+8+9=100
1-2-3+45-6+7*8+9=100
1-2-3+45-6-7+8*9=100
1-2-34+56+7+8*9=100
1-2*3+4*5+6+7+8*9=100
1-2*3-4+5*6+7+8*9=100
1-2*3-4-5+6*7+8*9=100
1-23+4*5+6+7+89=100
1-23-4+5*6+7+89=100
1-23-4-5+6*7+89=100
1*2+3+4*5+6+78-9=100
1*2+3+45+67-8-9=100
1*2+3-4+5*6+78-9=100
1*2+3*4+5-6+78+9=100
1*2+34+5+6*7+8+9=100
1*2+34+5-6+7*8+9=100
1*2+34+5-6-7+8*9=100
1*2+34+56+7-8+9=100
1*2+34-56/7+8*9=100
1*2-3+4+56/7+89=100
1*2-3+4-5+6+7+89=100
1*2-3+4*5-6+78+9=100
1*2*3+4+5+6+7+8*9=100
1*2*3-4+5+6+78+9=100
1*2*3-4*5+6*7+8*9=100
1*2*3-45+67+8*9=100
1*2*3*4+5+6+7*8+9=100
1*2*3*4+5+6-7+8*9=100
1*2*3*4-5-6+78+9=100
1*2*34+56-7-8-9=100
1*2/3+4*5/6+7+89=100
1*23+4+5+67-8+9=100
1*23+4+56/7*8+9=100
1*23-4+5-6-7+89=100
1*23-4-56/7+89=100
1*23*4-56/7/8+9=100
1*234+5-67-8*9=100
1/2*3/4*56+7+8*9=100
1/2*34-5+6-7+89=100
1/2/3*456+7+8+9=100
12+3+4+5-6-7+89=100
12+3+4-56/7+89=100
12+3-4+5+67+8+9=100
12+3*4+5+6+7*8+9=100
12+3*4+5+6-7+8*9=100
12+3*4-5-6+78+9=100
12+3*45+6*7-89=100
12+34+5*6+7+8+9=100
12+34-5+6*7+8+9=100
12+34-5-6+7*8+9=100
12+34-5-6-7+8*9=100
12-3+4*5+6+7*8+9=100
12-3+4*5+6-7+8*9=100
12-3-4+5-6+7+89=100
12-3-4+5*6+7*8+9=100
12-3-4+5*6-7+8*9=100
12*3-4+5-6+78-9=100
12*3-4-5-6+7+8*9=100
12*3-4*5+67+8+9=100
12/3+4*5-6-7+89=100
12/3+4*5*6-7-8-9=100
12/3+4*5*6*7/8-9=100
12/3/4+5*6+78-9=100
123+4-5+67-89=100
123+4*5-6*7+8-9=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
123-45-67+89=100
101 patterns found
lua komachi.lua  304.52s user 0.03s system 99% cpu 5:04.56 total

アルゴリズム的に高速化するのはできるのかなあ。よくわからない。

[1] http://karetta.jp/article/blog/ll-spirit/034942