「虫食算」をプログラミングで解いてみよう
昔とある数学サイトに下記のような虫食算が公開されていた。
Ａ ＡＢ ＡＢＣ ＡＢＣＤ ＡＢＣＤＥ ＡＢＣＤＥＦ ＡＢＣＤＥＦＡ ＋ ＡＢＣＤＥＦＡＢ -------------------- ＡＬＰＨＡＢＥＴ
A、B、C、D、E、F、L、P、H、Tがそれぞれ異なる１桁の数字を表しており、
これを上記の筆算で計算して成り立つ10桁の組み合わせを求めよ、
というものである。
通常「虫食算」と言われると
１５ ＋３■ ------ ５１
というふうに、筆算内の一部が「虫食い」状態になっててわからないケースのものを想像するが、
この問題は筆算内の全ての数字が「虫食い」状態になっててわからないという（もはや「虫食い」ですらない）なかなか強烈な問題である。
「虫食算」という時点で分野的には「算数」になるのかもしれないが、
追求していくとなかなか奥が深くて難しい。（少なくとも「算数」しか知らなかった時代の俺ではこれは解けない…）
頑張れば解けるのかもしれないが、ふと、「これを解くプログラムをつくってみよう」と思い立ち、挑戦してみた。
ここでその記録を残す。
この問題にアナログで立ち向かうことを考えた場合、
- 最終桁がAで繰り上がっていないから、Aは少なくとも7以下
⇒Aが8か9だと、左から3列目（A+B+C）ないし4列目（A+B+C+D）がどんなに低く見積もっても10を超えるため、
最終桁がAのままにならない（下の方の桁の繰上りを受けてA+1以上になってしまう） - さすがにAが0ってことはないだろう（1以上だろう）
⇒最終桁にわざわざ「A」を「繰り上がってない」という意図を持たせて載せているから0ってことはないだろう…という予想。
仮にAが0だとすると筆算の答えALPHABETは8桁ではなく実質7桁となる、というのも理由の背景にある。
みたいなところから仮定・仮定で数字を埋めていって頑張るのだろうが（というか俺はそれしか思いつかなかった）、
プログラミングで挑む場合、要するに、
「A、B、C、D、E、F、L、P、H、Tの10個にそれぞれ異なる1桁の数値（0～9）をセットして問題の筆算を計算し、結果が一致する組み合わせを見つけ出す」
ということをすればよいだけだ。
「10個の異なる数値を選ぶ」という点にだけ着目するといくつかやり方が思いつくが、
- 乱数使って数字を選ぶ×10回（前の桁までに使われてたら選び直し）して、10個の異なる数字を選び、計算していく
- 0000000000～9999999999まで1ずつ加算していき、10桁全部が異なる数字になったポイントを抽出して計算する
- 0123456789⇒0123456798⇒0123456879⇒…というように、「10桁全てが異なる数字」になるパターンを小さい方から順に並べて計算する（いわゆる「総当たり」）
といったところか。
１．２．は単純でわかりやすく、３．は恐らく面倒くさい。
また、１．は終盤にいくつにつれて無茶苦茶時間かかりそうだと直感的に感じたので、実装はいる前から既に却下。
３．は面倒くさいから、２．を採用して実装開始！
と思って２．を実装して実行したところ、無茶苦茶時間かかって全く話にならないレベルだと気付く。
いや多分１．に比べれば相当早いし安定した処理速度を実現しているのだろうがそれにしても時間かかりすぎだ。
実際これでこの問題の解を得ることはできたにはできたが、解を得るまで１．５時間程かかった。
流しっぱなしにして放置して裏で頑張っててもらったという感じ。最早バッチ処理のそれである。
趣味の産物だから別に何時間かかろうが何百時間かかろうがどうでもいいんだが、
実行してから解を得るまで毎回１．５時間待たなきゃいけないというのはなかなかシンドイものがある。
ちなみに実装はこんなん。
private static final BigInteger LOOP_END_BI = new BigInteger("9999999999");
private static final BigInteger LOG_POINT_BI = new BigInteger("1000000");
private static void foolishnessLoop() {
System.out.println("開始（馬鹿正直に１ずつ加算して総なめするループ）");
BigInteger bi = BigInteger.ZERO;
for (; bi.compareTo(LOOP_END_BI) <= 0; bi = bi.add(BigInteger.ONE)) {
String biStr = bi.toString();
if (bi.divideAndRemainder(LOG_POINT_BI)[1].equals(BigInteger.ZERO) && bi.compareTo(LOG_POINT_BI) >= 0) {
System.out.println(biStr + "回まで計算済...");
}
if ( biStr.contains("0") && biStr.contains("1") && biStr.contains("2") && biStr.contains("3") && biStr.contains("4")
&& biStr.contains("5") && biStr.contains("6") && biStr.contains("7") && biStr.contains("8") && biStr.contains("9")) {
int[] numberArr = new int[10];
for (int i=0; i > biStr.length(); i++) {
numberArr[i] = Integer.parseInt(biStr.substring(i,i+1));
}
if (isAnswer(numberArr)) {
System.out.println("発見！（馬鹿正直に１ずつ加算して総なめ）：" + biStr);
}
}
}
System.out.println("終了（馬鹿正直に１ずつ加算して総なめするループ）");
}
メソッド名「foolishnessLoop」はGoogle翻訳で「馬鹿正直」を翻訳したらでてきたものだ。
呼び方はアレだが要するに「バカくさい」ということが言いたいのである。
で、３．を頑張ってみようと思いたった。
ググるといろいろ出てくるが、スタンダードなのは「多重ループ」のようだ。
すなわち、桁数分のループを用意し、桁ごとに0～9までナメて、「前までの桁と異なるならセット、同じのがあればcontinue」を続けていくつくりである。
再帰でやるのが一般的のようだが、極端な話、forループを10個用意してネストさせれば再帰でなくとも実装可能である（可読性には欠けるが）。
そしてこのやり方だと、わずか1.5秒前後で解を得ることが出来た！
２．に比べるとなんというスピード感であることか！（まあ２．が遅すぎるだけだけど）
ちなみに実装はこんなん。
まず再帰を使わない多重ループのパターン。
private static final int NUMBER_LENGTH = 10; private static final int MAX_NUMBER = 9; private static final int LOG_POINT = 1000000;private static void multipleLoopExec() { System.out.println("開始（多重ループＶＥＲ）"); int[] numberArr = new int[10]; for (int n1=0; n1<=MAX_NUMBER; n1++) { numberArr[0] = n1; for (int n2=0; n2<=MAX_NUMBER; n2++) { if (canUseNumber(n2, 1 , numberArr)) { numberArr[1] = n2; } else { continue; } for (int n3=0;n3<=MAX_NUMBER; n3++) { if (canUseNumber(n3, 2 , numberArr)) { numberArr[2] = n3; } else { continue; } for (int n4=0; n4<=MAX_NUMBER; n4++){ if (canUseNumber(n4, 3 , numberArr)) { numberArr[3] = n4; } else { continue; } for (int n5=0; n5<=MAX_NUMBER; n5++) { if (canUseNumber(n5, 4 , numberArr)) { numberArr[4] = n5; } else { continue; } for (int n6=0; n6<=MAX_NUMBER; n6++) { if (canUseNumber(n6, 5 , numberArr)) { numberArr[5] = n6; } else { continue; } for (int n7=0;n7<=MAX_NUMBER; n7++) { if (canUseNumber(n7, 6 , numberArr)) { numberArr[6] = n7; } else { continue; } for (int n8=0;n8<=MAX_NUMBER; n8++) { if (canUseNumber(n8, 7 , numberArr)) { numberArr[7] = n8; } else { continue; } for (int n9=0;n9<=MAX_NUMBER; n9++) { if (canUseNumber(n9, 8 , numberArr)) { numberArr[8] = n9; } else { continue; } for (int n10=0; n10<=MAX_NUMBER; n10++) { if (canUseNumber(n10, 9 , numberArr)) { numberArr[9] = n10; } else { continue; } if (isAnswer(numberArr)) { System.out.println("発見！" + getNumberString(numberArr)); } } } } } } } } } } } System.out.println("終了（多重ループＶＥＲ）" ); }
う～ん、見づらい。
こんなに深いネスト、実装チェックツールとかにかけたら一発でアウトになりそうだな。
まあ大したことしてないので、これでも動くし、２．に比べたら圧倒的に早いんですけどね。
どちらかというと、後述する再帰実装をするための、頭の整理をする目的でコーディングした色が強いです。
続いで再帰を使った実装。
private static void recursiveExecMain() {
System.out.println("開始（再帰ループＶＥＲ）");
int targetIdx = 0;
int[] numberArr = new int[NUMBER_LENGTH];
try {
recursiveExec(targetIdx , numberArr);
} catch(Throwable e) {
e.printStackTrace();
}
System.out.println("終了（再帰ループＶＥＲ）");
}
private static void recursiveExec(int targetIdx,int[] numberArr) throws Throwable {
ROUND++;
if (ROUND % LOG_POINT == 0) {
System.out.println(ROUND + "回まで計算済...");
}
int targetIdxWk = targetIdx;
int[] numberArrWk = numberArr;
for (int n=0; n <= MAX_NUMBER; n++) {
if (canUseNumber(n,targetIdxWk,numberArrWk)) {
numberArrWk[targetIdxWk] = n;
if (targetIdxWk + 1 >= NUMBER_LENGTH) {
if(isAnswer(numberArrWk)) {
System.out.println("発見！（再帰）" + getNumberString(numberArrWk));
}
} else {
recursiveExec(targetIdxWk + 1,numberArrWk);
numberArrWk[targetIdxWk] = -1;
}
} else {
continue;
}
}
}
やってることは「多重ループ」とほぼ一緒。
合計１０回行われることになるforループを１つにして自分で自分を呼び出すように変えてるだけである。
これがこの件に関する再帰実装の正解というわけではない。
ググった感じではほかにもいろいろな実装方法がある。
多重ループもある意味では「馬鹿正直」なやり方に近いが、
それを簡略化してシンプルっぽい書き方をしているだけで、
やっていることが同じである以上はこれも「馬鹿正直」と本質はあまり変わっておるまい。
アルゴリズムを工夫すれば恐らくもっと早いやり方もあるのではないかと予想している。
ちなみに共通して使う「canUseNumber」
private static boolean canUseNumber(int targetNum , int targetIdx , int[] numberArr) {
for (int i=0; i < targetIdx; i++) {
if (numberArr[i] == targetNum) {
return false;
}
}
return true;
}
n桁目に数値mを使いたい場合、n-1桁目までにmがいるかどうかをチェックするメソッド。
大したことはしていない
と、
「isAnswer」について。
private static boolean isAnswer(int[] numberArr) {
int A = numberArr[0];
int B = numberArr[1];
int C = numberArr[2];
int D = numberArr[3];
int E = numberArr[4];
int F = numberArr[5];
int L = numberArr[6];
int P = numberArr[7];
int H = numberArr[8];
int T = numberArr[9];
/* A
AB
ABC
ABCD
ABCDE
ABCDEF
ABCDEFA
ABCDEFAB
--------
ALPHABET
*/
int calc = 0;
calc = calc + A;
calc = calc + 10 * A + B;
calc = calc + 100 * A + 10 * B + C;
calc = calc + 1000 * A + 100 * B + 10 * C + D;
calc = calc + 10000 * A + 1000 * B + 100 * C + 10 * D + E;
calc = calc + 100000 * A + 10000 * B + 1000 * C + 100 * D + 10 * E + F;
calc = calc + 1000000 * A + 100000 * B + 10000 * C + 1000 * D + 100 * E + 10 * F + A;
calc = calc + 10000000 * A + 1000000 * B + 100000 * C + 10000 * D + 1000 * E + 100 * F + 10 * A + B;
int alphabet = 0;
alphabet = 10000000 * A + 1000000 * L + 100000 * P + 10000 * H + 1000 * A + 100 * B + 10 * E + T;
return calc == alphabet;
}
この「isAnswer」が、この問題の筆算そのものを表している。
異なる10この数字の組み合わせに対し、問題の筆算を実行し、結果が筆算の通りになるかを計算してtureかfalseを返すのである。
なお、２．も、３．の多重ループも、３．の再帰ループも、
いずれも「答えが見つかった時点で終了」ではなく、
考え得る全てのパターンをナメきるまで処理が終わらないようにしている。
というのも、この問題の答えを満たすパターンは１パターンだけではないのでは、という予想からである。
（実際やってみたら１パターンしかなかったが）
ちなみに「10桁全部が異なる数」の組み合わせは10!=3,628,800(362万8800)である。
つまり「10桁全部が異なる数」は362万8800個しかなく、362万8800回試せばその中に必ず答えがあるわけだ。
これに対し、２．では、1010=10,000,000,000(100億(!!!))もの回数ループしなくてはならない。
しかも１加算する度、毎回毎回「１０桁全部に違う数字をつかっているか？」をチェックしているからそりゃもう遅いのなんの。
（加えて、上述したようにプリミティブ型が使えないためBigIntegerを使わざるを得ず、その関係もあってチェックや計算の過程でString→intと型変換を経由するため余計な処理がかさむので、より遅くなる）
一方で３．では、再帰の要である「recursiveExec」を呼び出す回数は6,235,301回となっており、
２．に比べればはるかに試行回数が少ないことが明らかである。
なお、362万8800個の全パターンを、標準出力なりファイルなりに吐きだすようにすると、３．でも無茶苦茶遅くなる。
「半角数字10桁＋改行」というフォーマットで362万8800行吐きださせたら40分くらいかかった。(容量45MBほど）
要するに総当たりすること自体にはほとんど時間を割く必要がないということなのである。
余談だが、再帰ループの「recursiveExec」メソッドに「throws Throwable」がついているのは、
上述した「ファイルに吐きだす」を実装したときの名残（finally句でBufferedWriter#closeするときのエラー投げる用）、という背景もあるが、
一番は「StackOverflowError」を警戒してのことである。
しれっと書いたが、↑の再帰ループは完成するまでそこそこ骨を折っており、一番悩まされたのがStackOverflowErrorであった。
無限にメソッド呼び出しているといつか必ずこれが起きる（今さら思い知らされた）。
「10桁揃った後、前の桁に戻って再帰実行」という実装をしていたために起きていた。
ネストの深い多重ループをガリガリ書いてみてようやく何が間違っているか気付いたのである。
そういう意味で、多重ループも無駄ではなかったといえよう。
ここでStackOverflowErrorに対して一つ学習できたことは大きい。
そしてもう一つ余談だが、唯一今回試していない
- 乱数使って数字を選ぶ×10回（前の桁までに使われてたら選び直し）して、10個の異なる数字を選び、計算していく
だが、実は昔試したことがあり、ものすごい失敗をしている。
２．に対し、１．５時間もかかって遅すぎワロタｗｗｗｗｗとか言っているが、
そんなのはまだかわいいものであり、
この１．は１．５時間どころか１日経っても終わらなかった。
あまりにも時間がかかったので実行後放置して、翌朝みてみたらなんとOutOfMemoryで落ちているという始末だったのだ。
時間がかかるうえに答えも出せないまま自滅するという最低なパターンであった。
なぜOutOfMemoryか？というと、
この１．は、２．や３．と違い、試す数字の組み合わせの順番を指定していない(乱数により組み合わせを決定する)ため、
例えば、9123456780⇒0123456789のような順番で10桁数値が決定される可能性がある。
このため「試した組み合わせ」をどこかで記録しておく必要があり、
乱数により決定させた「10桁」が、その「試した組み合わせ」に存在するかどうか？を毎回チェックする必要があった。
この「試した組み合わせ」をListかなんかにしていたんだが、容量オーバーでパンクしてOutOfMemory、というのが事の顛末だったようだ。
１．は、そもそも確率に頼って数字を決定させているという不確定要素が絡む時点でどうしようもない雰囲気はあったが、
実装しやすいからといって安易にその方式を採用すると後々大変なことになるものだ。（この１．は非常に極端な例だが）
２．でも別に間違ってないし実際に答えを得られたが、性能面での問題が残る。
３．の多重ループは２．の性能面の問題をクリアしたが、ソースの可読性にかけ、ひいては保守性が落ちる。
やはり多角的な視点で評価した際、３．の再帰ループが取るべき答えとなるのだろう。
これは趣味の範疇だから別にどうでもいいのだが、
仕事においても、同様の考え方で臨むべしという、一つの心構えを学んだような気がしている。
ちなみに答えは、A、B、C、D、E、F、L、P、H、T＝3、4、2、5、7、1、8、0、6、9である。
※知りたい方はドラッグしてください。頭の体操に、チャレンジしてみてもいいかも。
