Make 100 in several ways を Erlang で解いてみる

  • 2
    いいね
  • 0
    コメント

解こうとしている問題

元ネタのURLの記事が消えてしまっているのでStackoverflowの記事から引用するが、

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. E.g.: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

という問題があるそうな。日本語だと

1から9までの数字を昇順に並べ、それらの間に+, -, あるいは何も演算子を入れない(=桁がつながる)という条件でのすべての場合について結果が100となるものを選べ(例: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100)。

とでもなるだろうか。

そんなに面倒でもなさそうなので解いてみた。安易な方法だけど。

考え方

  • 123456789という数字の列の間に1 X1 2 X2 3 X3 4 X4 5 X5 6 X6 7 X7 8 X8 9という感じでX1~X8の記号が入っていることを仮定する。
  • X1~X8+,-,あるいは空文字(何も入らない)のうちのどれか。
  • 上記の条件を満たすリストOps = [X1, X2, X3, X4, X5, X6, X7, X8]を仮定し、このOpsを引数として対応する数式を文字列として生成し、さらにそれをErlangの数式として評価した結果を付け加える関数comp/1を定義する。
  • Opsとして想定し得るリスト群を生成する関数genlist/0を定義する。
  • genlist/0の生成する各リストに対しcomp/1を適用して、その中で計算値が求めるものを選ぶ関数を使いlists:filter/2にかけて選別すれば答が求まる。

コード

こんな感じ。

give100.erl
-module(give100).

-export([genlist/0, comp/1, comp/2, solve/1]).

genlist() ->
    X = [$+, $-, 0],
    [[A, B, C, D, E, F, G, H] ||
     A <- X, B <- X, C <- X, D <- X,
     E <- X, F <- X, G <- X, H <- X].

comp(Ops) ->
    S = comp(Ops, []),
    % requires period to make a valid Erlang expression
    {ok, Scanned, _} = erl_scan:string(S ++ "."),
    {ok, Parsed} = erl_parse:parse_exprs(Scanned),
    {value, V, []} = erl_eval:exprs(Parsed, []),
    {V, S}.

comp([], A) ->
    lists:reverse([$9|A]);
comp(Ops, A) ->
    [O | OT] = Ops,
    C = $8 - length(OT),
    case O of
        0 ->
            comp(OT, [C | A]);
        _X ->
            comp(OT, [_X | [C | A]])
    end.

solve(Val) ->
    lists:filter(fun(X) -> {V, _} = X, V =:= Val end,
                  [comp(L) || L <- genlist()]).

テスト結果

場合数が $3^8 = 6561$通りあるので、手持ちのCore i5のマシンだと1秒弱かかる。なにしろ式の解析が大げさなので、もっとやりようはあるかもしれない。ElixirならStreamが使えそうだ。

Erlang/OTP 19 [erts-8.1.1] [source] [64-bit] [smp:4:4] [async-threads:10] [kernel-poll:false]

Eshell V8.1.1  (abort with ^G)
1> l(give100).
{module,give100}
2> give100:solve(100). % ← Make 100 in several ways の答
[{100,"1+2+3-4+5+6+78+9"},
 {100,"1+2+34-5+67-8+9"},
 {100,"1+23-4+5+6+78-9"},
 {100,"1+23-4+56+7+8+9"},
 {100,"12+3+4+5-6-7+89"},
 {100,"12+3-4+5+67+8+9"},
 {100,"12-3-4+5-6+7+89"},
 {100,"123+4-5+67-89"},
 {100,"123+45-67+8-9"},
 {100,"123-4-5-6-7+8-9"},
 {100,"123-45-67+89"}]
3> give100:solve(42). % ←こんな変わった技も使える
[{42,"1+2+3+4+56-7-8-9"},
 {42,"1+2+3-4-56+7+89"},
 {42,"1+2+3-45-6+78+9"},
 {42,"1+2+34+5+6-7-8+9"},
 {42,"1+2+34+5-6+7+8-9"},
 {42,"1+2-3-4+56+7-8-9"},
 {42,"1+2-34+5+67-8+9"},
 {42,"1+23-45-6+78-9"},
 {42,"1-2+34+5-6-7+8+9"},
 {42,"1-2+34-5+6+7-8+9"},
 {42,"1-2-3-4+56-7-8+9"},
 {42,"1-23-4+5-6+78-9"},
 {42,"12+3+4+5-6+7+8+9"},
 {42,"12+3+45+6-7-8-9"},
 {42,"12+3-4-56+78+9"},
 {42,"12-3+45-6-7-8+9"},
 {42,"12-34+56+7-8+9"},
 {42,"123+4+5+6-7-89"}]
4>

参考文献

  • ネタ元のブログエントリ。関数型では無理という話があったけど、可能性のある要素を生成してそれにフィルタをかけていくというのは、関数型では定番だし、論理型でも十分いけるだろう。現にPrologのコードも次に述べるRedditのスレには出てるくらいだから。
  • このRedditのスレが勉強になる。
  • Erlang CentralのWikiにある"String Eval"のエントリを、comp/1の中の数式評価のコードとして参照した。もっとも数式だけでなく、Erlangの式として評価しているので、いささかオーバースペックであることは否めない。

まとめと感想

Make 100 in several ways はErlangでもまあ普通に解けることを示した。ただやり方としては雑なのは否めない。より面白いコードがあったら教えて欲しい。