Project Euler で紹介されている問題18を解いてみました。素直な解き方は、bit全検索を使います。bit全検索についてのコードパターンも紹介します。
Project Euler 問題18（最大の経路和Ⅰ）
下の三角形の頂点から始めて、下の行の隣り合う数字に移動することで、上から下への合計の最大が23になる。
3
7 4
2 4 6
8 5 9 3
赤字の経路の 3 + 7 + 4 + 9 = 23 となる。
下の三角形の上から下への合計の最大を求めよ。
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
注：経路は、16384通り（214）しかないため、すべてのルートを試せば、この問題を解くことができます。しかし、問題67は、三角形が100行になるため、すべての経路を計算することができないので、別の賢い方法が必要となります。;o)
考察（bit全検索）
注は気にしないで、まずは全通りの合計値を計算して、最大値を求めましょう。
この問題は、bit全検索と呼ばれる手法を使う典型問題となります。
例になっている三角形で説明しましょう。
3
7 4
2 4 6
8 5 9 3
赤字にした、3→7→2→8 を左を選択し続けるという意味で、0→0→0 と表現します。
3
7 4
2 4 6
8 5 9 3
赤字にした、3→4→6→3 を右を選択し続けるという意味で、1→1→1 と表現します。
3
7 4
2 4 6
8 5 9 3
最大値をとる、上の場合は、左→右→右 と選択するため、0→1→1 と表現します。
つまり、4段の三角形の場合、3回左か右を選択するため、2進数で、000 から 111 の8通りの場合に和を求めて、その最大値を求めればよいことになります。
実際に解く問題は、三角形が15段あるため、14回左か右を選択するため、2進数で、00000000000000 から 11111111111111 まで調べればよいことになります。これが問題文中にある16384通り（214）の意味です。
このように、すべての 2N 通りについて、それぞれ 0 から 2N-1 を対応させて調べることをbit全検索と呼びます。
解答例
bit全検索は、コードのパターンがありますが、まず、C のプログラムを紹介します。
なお、問題は標準入力から読んだり、ファイルから読む方法もありますが、問題の構造を分かりやすくするため、2次元配列 problem に代入しておきます。
#include <stdio.h>
int problem[15][15] = {
{75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{95, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{17, 47, 82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{18, 35, 87, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{20, 4, 82, 47, 65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{19, 1, 23, 75, 3, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{88, 2, 77, 73, 7, 63, 67, 0, 0, 0, 0, 0, 0, 0, 0},
{99, 65, 4, 28, 6, 16, 70, 92, 0, 0, 0, 0, 0, 0, 0},
{41, 41, 26, 56, 83, 40, 80, 70, 33, 0, 0, 0, 0, 0, 0},
{41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 0, 0, 0, 0, 0},
{53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 0, 0, 0, 0},
{70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 0, 0, 0},
{91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 0, 0},
{63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 0},
{ 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23}
};
int main(void)
{
int bit;
int i, j;
int sum, max;
max = 0;
for (bit = 0; bit < (1 << 14); ++bit) {
sum = problem[0][0];
j = 0;
for (i = 0; i < 14; ++i) {
if ((bit & (1 << i)) != 0) {
++j;
}
sum += problem[i + 1][j];
}
if (sum > max) {
max = sum;
}
}
printf("Problem018: %d\n", max);
return 0;
}bit全検索のコードパターンは、背景色を変更しています。以下、解説します。
- 23行目：すべての通りを表現する変数 bit を宣言する。
- 28行目：for 文ですべての場合を繰り返す。
- 32行目：1 が立っているときの処理（この場合は、右の数字をみる）をする。
ビット演算子を使っていますので、読みにくいと感じる人がいるかもしれませんが、コードのパターンは同じとなります。
2N 通りのすべてを調べる場合に、役立つコードパターンです。
補足
上記プログラムの変数 problem の定義は、問題11と同様にプログラムで変換して生成しました。
問題から、マス目の数字だけをテキストファイルとして保存しておきます。このファイル名を「problem018.txt」とします。内容は以下となります。
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23この数字列のテキストから変数定義のプログラムに変換してみましょう。言語は awk を使います。
BEGIN {
printf("int problem[15][15] = {\n");
}
# 読まれないフィールドデータは、0であることを仮定している。
{
printf("\t{");
for (i = 1; i < 15; ++i) {
printf("%2d, ", $i);
}
printf("%2d}", $15);
if (NR != 15) {
printf(",\n");
} else {
printf("\n");
}
}
END {
printf("};\n");
}以下のコマンドで、出力リダイレクトを使い変数定義を行う temp018.c を生成します。あとは、これをソースコードに貼り付けます。
$ gawk -f convert018.awk problem018.txt > temp018.c最後に
bit全検索についてのコードパターンを紹介して、問題を解いてみました。bit全検索は、2N 通りある場合の全検索に使えることが多い手法です。
次回は、問題の注にある賢い方法について、考えてみます。
