質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.22%

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

受付中

回答 1

投稿

  • 評価
  • クリップ 3
  • VIEW 3,800

katoy

CoffeeScript総合1位

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

覆面算とは: 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での虫食い算画像の検索

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

+1

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


演算子は+,-,*限定で。
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);
        }
    }

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2014/12/17 23:40

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

    キャンセル

  • 2014/12/18 13:01

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.22%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る