Scala コラッツの問題

友人へ

コラッツの問題 - Wikipedia

が面白かったのでScalaで書いてみよう!という記事。

Scalaをインストールしていなくても、Macユーザーの場合

$ brew install scala

で一発でインストールできるので、実行してみよう!

コラッツの問題

コラッツの問題は、「任意の正の整数 n をとり、

  • n が偶数の場合、n を 2 で割る
  • n が奇数の場合、n に 3 をかけて 1 を足す

いう操作を繰り返すと、どうなるか」というものである。 「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。

例として、初期値を 6 にすると、 6, 3, 10, 5, 16, 8, 4, 2, 1という、1に到達する数列を得る。 このような数列をコラッツ数列と呼ぶ。 (Wikipediaより)

コラッツ数列を求める

例えばcollatz(6)と実行したらList(6, 3, 10, 5, 16, 8, 4, 2, 1)と返る関数を作る。

def collatz(num: Int): List[Int] = {
  def proc(list: List[Int]): List[Int] = {
    if (list.head == 1) list
    else if (list.head % 2 == 0) proc((list.head / 2) :: list)
    else proc((list.head * 3 + 1) :: list)
  }
  if (num <= 0) Nil
  else proc(num :: Nil).reverse
}

これを先ほどインストールしたScalaで実行してみよう。

ターミナルで$ scalaと打つとREPLが実行されるので、そこで試してみる。 REPLで:pasteと打つと複数行のコードのペーストが簡単にできる。 ペーストをしたら、ctrl-Dでペーストモードを終了し、collatz(6)のように実行してみよう。

$ scala
Welcome to Scala 2.12.6 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_172).
Type in expressions for evaluation. Or try :help.

scala> :paste
// Entering paste mode (ctrl-D to finish)

def collatz(num: Int): List[Int] = {
  def proc(list: List[Int]): List[Int] = {
    if (list.head == 1) list
    else if (list.head % 2 == 0) proc((list.head / 2) :: list)
    else proc((list.head * 3 + 1) :: list)
  }
  if (num <= 0) Nil
  else proc(num :: Nil).reverse
}

// Exiting paste mode, now interpreting.

collatz: (num: Int)List[Int]

scala> collatz(6)
res0: List[Int] = List(6, 3, 10, 5, 16, 8, 4, 2, 1)

上記例が正しく求まった。

コラッツ数列をたくさん求める

(1 to 10).map(collatz).foreach(println)

結果は

List(1)
List(2, 1)
List(3, 10, 5, 16, 8, 4, 2, 1)
List(4, 2, 1)
List(5, 16, 8, 4, 2, 1)
List(6, 3, 10, 5, 16, 8, 4, 2, 1)
List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)
List(8, 4, 2, 1)
List(9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)
List(10, 5, 16, 8, 4, 2, 1)

(1 to 10)の部分を書き換えて、君だけのコラッツ数列のリストを生成しよう!

とっても長いコラッツ数列を求める

上記例だとcollatz(9)が数列の長さが大きい。 では、初期値が1から100,000の中で一番長さが大きいコラッツ数列を求めてみよう。

中間リストが大きくなっても、ストリームを使えばへっちゃらだ。

(1 to 100000).toStream.map(collatz).map(xs => (xs.head, xs.length)).maxBy(_._2)

結果は

(77031,351)

初期値77031のコラッツ数列の長さは351ということらしいので、確認してみよう。

println(collatz(77031).mkString(", "))
77031, 231094, 115547, 346642, 173321, 519964, 259982, 129991, 389974, 194987, 584962, 292481, 877444, 438722, 219361, 658084, 329042, 164521, 493564, 246782, 123391, 370174, 185087, 555262, 277631, 832894, 416447, 1249342, 624671, 1874014, 937007, 2811022, 1405511, 4216534, 2108267, 6324802, 3162401, 9487204, 4743602, 2371801, 7115404, 3557702, 1778851, 5336554, 2668277, 8004832, 4002416, 2001208, 1000604, 500302, 250151, 750454, 375227, 1125682, 562841, 1688524, 844262, 422131, 1266394, 633197, 1899592, 949796, 474898, 237449, 712348, 356174, 178087, 534262, 267131, 801394, 400697, 1202092, 601046, 300523, 901570, 450785, 1352356, 676178, 338089, 1014268, 507134, 253567, 760702, 380351, 1141054, 570527, 1711582, 855791, 2567374, 1283687, 3851062, 1925531, 5776594, 2888297, 8664892, 4332446, 2166223, 6498670, 3249335, 9748006, 4874003, 14622010, 7311005, 21933016, 10966508, 5483254, 2741627, 8224882, 4112441, 12337324, 6168662, 3084331, 9252994, 4626497, 13879492, 6939746, 3469873, 10409620, 5204810, 2602405, 7807216, 3903608, 1951804, 975902, 487951, 1463854, 731927, 2195782, 1097891, 3293674, 1646837, 4940512, 2470256, 1235128, 617564, 308782, 154391, 463174, 231587, 694762, 347381, 1042144, 521072, 260536, 130268, 65134, 32567, 97702, 48851, 146554, 73277, 219832, 109916, 54958, 27479, 82438, 41219, 123658, 61829, 185488, 92744, 46372, 23186, 11593, 34780, 17390, 8695, 26086, 13043, 39130, 19565, 58696, 29348, 14674, 7337, 22012, 11006, 5503, 16510, 8255, 24766, 12383, 37150, 18575, 55726, 27863, 83590, 41795, 125386, 62693, 188080, 94040, 47020, 23510, 11755, 35266, 17633, 52900, 26450, 13225, 39676, 19838, 9919, 29758, 14879, 44638, 22319, 66958, 33479, 100438, 50219, 150658, 75329, 225988, 112994, 56497, 169492, 84746, 42373, 127120, 63560, 31780, 15890, 7945, 23836, 11918, 5959, 17878, 8939, 26818, 13409, 40228, 20114, 10057, 30172, 15086, 7543, 22630, 11315, 33946, 16973, 50920, 25460, 12730, 6365, 19096, 9548, 4774, 2387, 7162, 3581, 10744, 5372, 2686, 1343, 4030, 2015, 6046, 3023, 9070, 4535, 13606, 6803, 20410, 10205, 30616, 15308, 7654, 3827, 11482, 5741, 17224, 8612, 4306, 2153, 6460, 3230, 1615, 4846, 2423, 7270, 3635, 10906, 5453, 16360, 8180, 4090, 2045, 6136, 3068, 1534, 767, 2302, 1151, 3454, 1727, 5182, 2591, 7774, 3887, 11662, 5831, 17494, 8747, 26242, 13121, 39364, 19682, 9841, 29524, 14762, 7381, 22144, 11072, 5536, 2768, 1384, 692, 346, 173, 520, 260, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

計算時間を求める

せっかくなので、上記の長さが最大のコラッツ数列を求めるプログラムの計算時間を計測しよう。

scala> :paste
// Entering paste mode (ctrl-D to finish)

def calcTime[A](proc: => A): (A, Long) = {
  val start = System.currentTimeMillis
  (proc, (System.currentTimeMillis - start))
}

// Exiting paste mode, now interpreting.

calcTime: [A](proc: => A)(A, Long)

scala> def longest = (1 to 100000).toStream.map(collatz).map(xs => (xs.head, xs.length)).maxBy(_._2)
longest: (Int, Int)

scala> calcTime(longest)
res11: ((Int, Int), Long) = ((77031,351),586)

586[ms]で実行することができた。

proc: => Aと指定することで、関数を評価せずに渡すことができる。 ジェネリクスを指定したので、どんな関数でもぶちこめる。便利だね。

結論

Scala楽しいよ!