【ITニュース解説】Weekly Challenge: Maximum climb

この記事では、プログラミングの週ごとの課題に挑戦した結果が紹介されている。具体的には「Max Diff（最大差分）」と「Peak Point（最高到達点）」という二つの課題があり、それぞれPython言語でどのように解決されたかが説明されている。

まず一つ目の課題は「Max Diff（最大差分）」だ。この課題では、四つ以上の整数を含む数字のリストが与えられる。目標は、このリストの中から四つの数字を選び、それらを二組のペアに分け、それぞれのペアの積（掛け算の結果）の差が最も大きくなるようにすることだ。最終的にその最大差分を返す必要がある。例えば、(a, b) と (c, d) という二組のペアを選んだ場合、計算するのは (a * b) - (c * d) の値だ。

この課題の解決策を考える際、記事の筆者は最初は「リストの中から最も小さい積のペアと、最も大きい積のペアを見つければよいのではないか」と考えたようだ。しかし、例えばリストが -4, -10, 2, 0 だった場合、最小の積は -4 × 2 = -8 で、最大の積は -4 × -10 = 40 となる。この例では -4 という数字を二回使ってしまっている。しかし課題の要件では、選んだ四つの数字はそれぞれ異なるペアに属する必要があるため、同じ数字を複数回使うことはできない。この方法ではうまくいかないと筆者は気づき、別の方法を模索することになった。

筆者が最終的に採用したのは「総当たり」と呼ばれるアプローチだ。これは、考えられるすべての可能性を一つずつ試していく方法である。具体的には、与えられた整数のリストから、重複なしで四つの数字を選ぶすべての組み合わせを生成する。例えば、リストに多くの数字があっても、そこから常に四つの数字だけを取り出して考える。Pythonというプログラミング言語にはitertools.combinationsという便利な機能があり、これを使うとこのような組み合わせを簡単に生成できる。Perlという別の言語にも同様の機能がある。

四つの数字の組み合わせが一つ見つかるたびに、その四つの数字を使って可能な三通りのペアの作り方をすべて試す。例えば、選んだ四つの数字が c[0], c[1], c[2], c[3] だとすると、考えられるペアの組み合わせは以下の三通りになる。

1. (c[0] と c[1]) の積 と (c[2] と c[3]) の積の差
2. (c[0] と c[2]) の積 と (c[1] と c[3]) の積の差
3. (c[0] と c[3]) の積 と (c[1] と c[2]) の積の差

これらの三通りの積の差を計算し、それぞれの絶対値（数値の符号を無視した大きさ）を求める。なぜ絶対値かというと、積の差は正の値にも負の値にもなりうるが、ここでは差の「大きさ」が最大であればよいためだ。これら三つの絶対値の中で最も大きい値を見つける。この最大値が、これまでに記録した最大差分よりも大きければ、その値を新しい最大差分として更新していく。この処理をすべての四つの数字の組み合わせに対して繰り返し、最終的に見つかった最大差分を結果として返す。

筆者はこの「総当たり」のアプローチについて、以前「ただ力任せに解を導き出す」のは良くないと評されていたことを気にしており、今回はそれに該当すると感じているようだ。しかし、たとえリストに100個の数字があったとしても、そこから四つの数字を選ぶ組み合わせの数は400万通り以下であり、現代のコンピュータであれば比較的短時間で計算できると述べている。このことから、必ずしも「最適」なアルゴリズムでなくても、実用上問題ないケースもあるという現実的な視点も示されている。

二つ目の課題は「Peak Point（最高到達点）」だ。この課題では、高度の変化を表す数字のリストが与えられる。目標は、そのリストのすべての変化を考慮した結果、到達した最も高い地点（最高到達点）を見つけることだ。

この課題の解決策は、一つ目の課題に比べて比較的シンプルだ。筆者は二つの変数を用意している。一つはcurrent_altitude（現在の高度）で、もう一つはpeak（最高高度）だ。どちらも最初は0で初期化される。これは、開始地点の高度を0と仮定し、まだ移動していないため最高到達点も0と考えるからだ。

次に、与えられた高度変化のリストの各要素（gain、つまり高度がどれだけ増減したか）について順番に処理を行う。ループの中で、current_altitudeに現在のgainの値を加算していく。これにより、現在の移動による高度の変化がcurrent_altitudeに反映される。加算後、もしcurrent_altitudeがpeakの値よりも大きければ、そのcurrent_altitudeがこれまでの最高高度を更新したことになるため、peakの値をcurrent_altitudeの値で上書きする。この処理をリストのすべての要素に対して繰り返し行い、すべての変化を計算し終えた後、最終的なpeakの値を結果として返す。

このアプローチは、現在の状態（current_altitude）を常に追跡し、その過程で記録された最高の状態（peak）を保持するという、プログラミングの基本的な考え方に基づいている。非常に直接的で分かりやすく、効率的な解決策だと言えるだろう。

これら二つの課題の解決策は、プログラミングにおける異なる問題解決のパターンを示している。Max Diffでは「考えられるすべての可能性を試して最適なものを見つける」という総当たり的なアプローチを、Peak Pointでは「現在の状態を追跡しながら、条件に応じて最高記録を更新していく」という状態管理のアプローチを取っている。どちらも、プログラミングで問題解決を行う上で役立つ基本的な思考プロセスである。