ピラミッド上のルートをたどる問題
きょうの Project Euler は Problem 18 (May 31, 2002) です. 今回の問題は, 大きな数を計算させるようなものではないので, (満足に解くことができるかどうかは別としても) 少し心が休まります.
出題内容は次のとおりです.
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
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 23NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
頂点から出発し, 1 段ずつ下に降りて行き, 底辺にたどる着くまで, 通過した数をすべて足すことにしますと, その最大値はいくらになりますかという問題です. どういう経路をたどったかを答える必要はないようです.
珍しくヒントが掲載されており, 力ずくでもできないことはないけれど, もっと賢いやり方を考えましょうねと述べられています.
事前準備
問題で与えられたピラミッドの高さは 15 段です. 同様に底辺の長さも 15 です. これを, どのようなデータ構造で取り扱うのがよいでしょうか.
二次元の配列も検討しかけたのですが, 可変長の多次元配列を関数間で受け渡しするのはあまり楽ではないような気がしましたので, 次のように一次元の配列で表現することにしました.
unsigned int data[] = { 75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 4, 82, 47, 65, 19, 1, 23, 75, 3, 34, 88, 2, 77, 73, 7, 63, 67, 99, 65, 4, 28, 6, 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, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23 };
力ずくの方法
まずは, いつものように, 力ずくの方法です.
unsigned int _getMaxPartialSum(unsigned int data[], unsigned int size, unsigned int row, unsigned int column) { if (size <= row || size <= column || row < column) return 0; unsigned int itself = data[row * (row + 1) / 2 + column]; if (row == size - 1) return itself; unsigned int left = _getMaxPartialSum(data, size, row + 1, column); unsigned int right = _getMaxPartialSum(data, size, row + 1, column + 1); return itself + (left < right ? right : left); } unsigned int getAnswer0(unsigned int data[], unsigned int size) { return _getMaxPartialSum(data, size, 0, 0); }
指定した場所よりも下に連なる数を合計したときの最大値を _getMaxPartialSum という関数で返すようにします. また, この関数は, みずからを再帰的に呼び出すようにします.
少し賢いかもしれない方法
次は, 少し賢いかもしれない方法です. これは, 手前味噌で 「賢い」 と申しているわけではございません. 今回は Samuel Jack さんの Project Euler Problems 18 and 67: Finding the Maximal Route through a Triangle (Aug 28, 2008) というブログ記事を参考にさせていただいたのですが, わたしにはまったく思いつかない方法でしたので, これは賢いなあと思ったわけです.
unsigned int getAnswer1(unsigned int data[], unsigned int size) { if (size == 0) return 0; unsigned int sum[size], i, j; sum[0] = data[0]; for (j = 1; j < size; j++) sum[j] = 0; for (i = 1; i < size; i++) { unsigned int tmp = i * (i + 1) / 2; sum[i] = sum[i - 1] + data[tmp + i]; for (j = i - 1; 0 < j; --j) { unsigned int itself = data[tmp + j]; unsigned int left = sum[j - 1]; unsigned int right = sum[j]; sum[j] = itself + (left < right ? right : left); } sum[0] += data[tmp]; } unsigned int max = sum[0]; for (j = 1; j < size; j++) if (max < sum[j]) max = sum[j]; return max; }
各段の数を調べるにあたっては, 左端の数については右上のルートからそのまま引き継ぎ, 右端の数については左上のルートからそのまま引き継ぎますが, それ以外の数については右上と左上のどちらのルートから引き継ぐかを判定する必要があります. これは上から下に降りて行く (トップダウン) 方式の場合, そうせざるをえないのだろうと思います. また, 底辺まで来たら, どの数をゴールとするルートが本件の正解なのか, それを判定することも必要です.
ただ, 最初の解き方の計算量が O(2N) と予想されることに比べれば, この解き方の計算量は O(N2) と予想されるので, はるかによい方法だろうと思います.
トップダウンをボトムアップに変更してみた方法
ひとつ前の解き方と似たようなことは, 下から上に登って行く (ボトムアップ) 方式でも考えることができます. この方法なら, 各段の数を調べるにあたって, それが左端の数なのか右端の数なのかそれともそれ以外の数なのかを気にする必要がありません. また, 最後に頂点にたどり着いた時点で, もう本件の正解が得られた状態になります.
(こういうことは絵に描いて説明すればわかりやすく説明することができるんじゃないかと思いますが, どうもわたしのプレゼンスキルはまるでダメですね...)
unsigned int getAnswer2(unsigned int data[], unsigned int size) { if (size == 0) return 0; unsigned int sum[size], i, j; unsigned int tmp = (size - 1) * size / 2; for (j = 0; j < size; j++) sum[j] = data[tmp + j]; for (i = size - 1; 0 < i; --i) { tmp = (i - 1) * i / 2; for (j = 0; j < i; j++) { unsigned int itself = data[tmp + j]; unsigned int left = sum[j]; unsigned int right = sum[j + 1]; sum[j] = itself + (left < right ? right : left); } } return sum[0]; }
この方法も, ひとつ前の方法と同様に, 計算量のオーダーは O(N2) と予想されます.
比較
以下のコードで処理時間を比較してみました.
#include <stdio.h> #include <stdlib.h> #include <time.h> unsigned int _getMaxPartialSum(unsigned int data[], unsigned int size, unsigned int row, unsigned int column); unsigned int getAnswer0(unsigned int data[], unsigned int size); unsigned int getAnswer1(unsigned int data[], unsigned int size); unsigned int getAnswer2(unsigned int data[], unsigned int size); int main(int argc, char **argv) { unsigned int data[] = { 75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 4, 82, 47, 65, 19, 1, 23, 75, 3, 34, 88, 2, 77, 73, 7, 63, 67, 99, 65, 4, 28, 6, 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, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23 }; unsigned int size = 15; unsigned int (*func[])(unsigned int[], unsigned int) = { getAnswer0, getAnswer1, getAnswer2 }; clock_t t0, t1; int i, j, answer; for (i = 0; i < sizeof(func) / sizeof(func[0]); i++) { t0 = clock(); for (j = 0; j < 10000; j++) answer = (*func[i])(data, size); t1 = clock(); printf("Solution #%d\n", i); printf(" Max total sum %u\n", answer); printf(" Elapsed time %u msec.\n", t1 - t0); } return EXIT_SUCCESS; }
それぞれの方法を 10000 回ずつ繰り返しています. 実行結果は, たとえば次のようになりました.
Solution #0 Max total sum 1074 Elapsed time 4144 msec. Solution #1 Max total sum 1074 Elapsed time 15 msec. Solution #2 Max total sum 1074 Elapsed time 16 msec.
2 番目の方法と 3 番目の方法は, ほとんど差はありません. どちらにしても, 1 番目の方法 (力ずくの方法) に比べれば, はるかに賢い方法だったんじゃないかと思います. そういうものを思いつく人はすごいなあと, いつも感心してしまいます.
