キミならどう書く 2.0 - ROUND 2 - ― Lightweight Language Ring を受けて。
前回、いろいろな(変なw)処理系でさんざん書き散らかしてしまったのを反省して、今回は、知らない人でも Smalltalk がどんな言語だかが分かるように、オーソドックスなのをひとつだけ。
クラス「Integer」に次の二つのメソッド、#collatz と #collatzSteps:max: を定義します。
Integer >> collatz "Answer the Collatz steps and the maximum value reached, of the receiver." ^ self collatzSteps: 0 max: self
Integer >> collatzSteps: steps max: upto self = 1 ifTrue: [^ steps+1 -> upto]. self even ifTrue: [^ (self/2) collatzSteps: steps+1 max: (self max: upto)]. self odd ifTrue: [^ (3*self + 1) collatzSteps: steps+1 max: (self max: upto)]
この二つのメソッドの追加により、整数へのメッセージ「collatz」の送信で、1に到達するまでのステップ数と、その過程で生じた最大の数を“->”で結びつけたかたちで返してくるようになります。
3 collatz " => 8 -> 16 "
27 collatz " => 112 -> 9232 "
お題は、100 までの自然数 k で、ステップ数 g(k) が最大になる k を求めよ、ということですから、それを(ほぼ)そのまま Smalltalk 風味で書き下すと…
((1 to: 100) collect: [:k | k collatz -> k]) max
=> 119 -> 9232 -> 97
で、条件を満たす k 、つまり、h(100) は、ステップ数が最大の 119 で、その際の最大到達数が 9232 の「97」であることが分かります。
Haskell、Ruby、Python 同様、Smalltalk も無限多倍長整数(俗に言う Bignum)を扱うためのクラス LargeInteger がシステムに標準で組み込まれていますので、404 Blog Not Found:LLR2006 - Collatz予想は113383に気をつけろ! で指摘されているような問題は、特に意識する必要はありません。
113383 collatz " => 248 -> 2482111348 "
8528817511 collatz " => 727 -> 18144594937356598024 "
ふるい落としなどの工夫は施してありませんが、大きめの n についての h(n) も調べてみましょう。
(1 to: 1000000) inject: 0->0->0 into: [:assoc :n | assoc max: n collatz -> n]
=> 525 -> 2974984576 -> 837799
ブチキレやすい(^_^;)私でもなんとか我慢できる計算時間内に戻ってきてくれるようです。
“->”についての補足
特に最大ステップ数を求めるコードを比較的、短く簡潔にできている要因は、関連付けオブジェクト(Association のインスタンス)と、それを生成する #-> メソッドの利用にあります。関連付けオブジェクトは、Smalltalk では辞書オブジェクト(Dictionary のインスタンス)の要素として使われているオブジェクトで、「キー(key)」とそれに関連付けする「値(value)」のみからなり、key -> value で生成できます。
3 -> 4 " => 3 -> 4 " (3 -> 4) class " => Association "
二成分(以上)で比較的扱いやすい and/or 簡潔な(リテラルっぽい…)記述で生成できるオブジェクトは他に、配列(an Array)と座標(a Point)があります(分数もそうなのですが、こちらは分子と分母の組み合わせによっては約分されてしまう!のでパス)。
#(3 4) " => #(3 4) " " ただし、構成要素がリテラルの場合のみ使用可能な記法 " #(3 4) class " => Array " {3. 4} " => #(3 4) " " 要素がリテラルでなくても使用できる Squeak 独自の記法 "
3 @ 4 " => 3 @ 4 " (3 @ 4) class " => Point "
ただ、これらでは、これらを要素とするコレクションから“最大値”を求めようしようとしたとき、便利な max の送信が使用できないようです。
#(1 2 3) max " => 3 "
#((1 1) (1 2) (2 1)) max " => MessageNotUnderstood: Array>>max: "
{1@1. 1@2. 2@1} max " => 2@2 "
配列が要素の場合、レシーバとパラメータを比較して大きい方を返すメソッド #max: を起動できないため多態できず、エラーになっています。座標のほうはうまくいっているように見えますが、x 座標、y 座標、それぞれ独立した max を求めてしまっています。この点、関連付けオブジェクトの場合、期待どおりの挙動をしてくれました。
{1->1. 1->2. 2->1} max " => 2->1 "
{1->1. 1->2. 2->1. 2->2} max " => 2->2 "
今回、ステップ数と最大到達値の保持に関連付けオブジェクトを使うことが決まるまでの経緯は、ざっとこんな感じです。参考まで。