覆面算をとくプログラムは？

Question

覆面算をプログラムで解くとした場合、皆さんなら風にふうにしますか？
(利用言語は問いません。)

覆面算とは： http://ja.wikipedia.org/wiki/%E8%A6%86%E9%9D%A2%E7%AE%97

こんな例があります。
SEND + MORE == MONEY
twelve + twenty == answer
みず * みず = 飲みみず
ぴよ * ぴよ = ひよこ

私は、こんなふうにしました。
https://gist.github.com/katoy/2dfd7d41b342ddb70aaf

これを書くのに参考にしたのは次のページ。
Dive Into Python 3の覆面算をRubyで書いてみた http://web-salad.hateblo.jp/entry/2014/04/06/164312

筆算型の覆面算をとけるようにもしたいです。
さらには虫食い算もとけるようにしたいです。

googleでの虫食い算画像の検索

Answer 1

Javaで書いてみました。
evalやpermutationが標準で使えないので、いろいろと苦しいですが...

演算子は+,-,*限定で。
permutationは、Uncommons Mathsというライブラリーを使いました。10文字中n文字みたいに使えないのが難点です。
Uncommons Maths - Random number generators, probability distributions, combinatorics and statistics for Java

// --- JUnitテスト ---
// ※Alphametics.solveをstatic-import
// assertEquals("9567 + 1085 = 10652", solve("SEND + MORE = MONEY"));
// assertEquals("87 + 12 = 99", solve("AB + 12 = 99"));
// assertEquals("407927 + 407146 = 815073", solve("twelve + twenty = answer"));
// assertEquals("142857 * 2 = 285714", solve("ABCDEF * C = CDEFAB"));
// assertEquals("5943 * 143 = 849849", solve("kore * are = iroiro"));
// // これはサポートしない assertEquals("1 + 3 + 9 = 13 && 3 + 3 + 3 = 9", solve("a + b + c = ab && b + b + b = c"));
// assertEquals("76 * 76 = 5776", solve("みず * みず = 飲みみず"));


// --- メイン ---

import java.util.*;
import java.util.regex.*;
import java.util.stream.*;
import org.uncommons.maths.combinatorics.PermutationGenerator;

final class Alphametics {

    static Pattern p = Pattern.compile("([^\+\-\*]+)([\+\-\*])([^\+\-\*]+?)={1,2}([^\+\-\*=]+)");

    static String solve(String expr) {
        char[] uniqueChars = uniqueChars(expr);
        if (uniqueChars.length > 10)
            throw new IllegalArgumentException("chars > 10");
        PermutationGenerator<Character> gen
            = new PermutationGenerator<>(Arrays.asList('0', '1', '2', '3', '4', '5', '6', '7', '8', '9'));
        Character[] numbers = new Character[10];
        while (gen.hasMore()) {
            gen.nextPermutationAsArray(numbers);
            String replaced = replaceCharsToNumbers(expr, uniqueChars, numbers);
            if (evaluate(replaced))
                return replaced;
        }
        return "(failed)";
    }

    private static char[] uniqueChars(String expr) {
        Matcher m = p.matcher(expr.replaceAll("\s", ""));
        if (!m.matches())
            throw new IllegalArgumentException("bad format: " + expr);
        String s = m.group(1) + m.group(3) + m.group(4);
        Set<Character> set = s.replaceAll("\d+", "").chars().mapToObj(c -> (char)c).collect(Collectors.toSet());
        char[] chars = new char[set.size()];
        int i = 0;
        for (Character c : set)
            chars[i++] = c;
        return chars;
    }

    private static String replaceCharsToNumbers(String expr, char[] uniqueChars, Character[] numbers) {
        String s = expr;
        for (int i = 0, n = uniqueChars.length; i < n; i++)
            s = s.replace(uniqueChars[i], numbers[i]);
        return s;
    }

    private static boolean evaluate(String expr) {
        String s = expr.replaceAll("\s", "");
        Matcher m = p.matcher(s);
        if (!m.matches())
            throw new IllegalArgumentException("bad format: " + expr);
        String sa = m.group(1);
        String sb = m.group(3);
        String sc = m.group(4);
        if (Stream.of(sa, sb, sc).anyMatch(x -> x.startsWith("0")))
            return false;
        int a = Integer.parseInt(sa);
        int b = Integer.parseInt(sb);
        int c = Integer.parseInt(sc);
        int d;
        switch (m.group(2)) {
            case "+":
                d = a + b;
                break;
            case "-":
                d = a - b;
                break;
            case "*":
                d = a * b;
                break;
            default:
                return false;
        }
        return c == d;
    }

}

---

追記： evalをScripting(JavaScript)で。これなら&&も使えます。
さすがに遅いですね。

// 上のコードの、uniqueCharsメソッドとevaluateメソッドを書き換える

// import javax.script.*; // import追加

    private static char[] uniqueChars(String expr) {
        String s = expr.replaceAll("[\s\+\-\*=&\|\d]", "");
        Set<Character> set = s.chars().mapToObj(c -> (char)c).collect(Collectors.toSet());
        char[] chars = new char[set.size()];
        int i = 0;
        for (Character c : set)
            chars[i++] = c;
        return chars;
    }

    private static ScriptEngine engine = new ScriptEngineManager().getEngineByName("js");

    private static boolean evaluate(String expr) {
        for (String x : expr.split("\D"))
            if (x.startsWith("0"))
                return false;
        try {
            return (boolean)engine.eval(expr);
        } catch (ScriptException e) {
            throw new RuntimeException(e);
        }
    }

Comments

[katoy]

java での記述はなかなか苦しいですね。
javascript あどのスクリプト を java から呼び出す方法を使って、eval のようなことはできそうですが...

[argius]

Scriptingでeval版を追加してみました。
パフォーマンスはかなり落ちますが...