「初心者向け(小学生の算数で解くプログラミング)」の「もっと処理を速くしたい(配列の利用)」を Kotlin で実装してみた。
import kotlin.system.measureTimeMillis
import kotlin.time.measureTime
fun main() {
// 2桁の非負整数について、
// その数の各桁を1桁になるまでかけ算する回数を求め、
// その数と回数を出力する。
println("2桁の数すべて")
measureTimeMillis {
numberToCountPairSequence()
.take(100) // 2桁までの数に絞る。
.drop(10) // 2桁の数に絞る。
.forEach { (number, count) ->
println("$number: ${count}回")
}
}.also { println("($it ミリ秒)") }
println()
// 3,000,000 未満の非負整数について、
// その数の各桁を1桁になるまでかけ算する回数が最大になるものを求め、
// その数と回数を出力する。
println("3,000,000 未満の数における最大")
measureTimeMillis {
numberToCountPairSequence()
.take(3_000_000) // 3,000,000 未満に絞る。
.maxBy { it.second }!! // 「かけ算する回数」が最大になる最初のものを取得する。
.let { (number, count) ->
println("$number: ${count}回")
}
}.also { println("($it ミリ秒)") }
println()
// 任意の非負整数について、
// その数の各桁を1桁になるまでかけ算する回数が 9 になるものを求め、
// その数と回数を出力する。
println("かけ算する回数が 9")
measureTimeMillis {
numberToCountPairSequence()
.dropWhile { it.second < 9 } // 「かけ算する回数」が 9 未満のものを除く。
.first() // 「かけ算する回数」が 9 である最初のものを取得する。
.let { (number, count) ->
println("$number: ${count}回")
}
}.also { println("($it ミリ秒)") }
}
/**
* 0 から順に、
* その数の各桁を1桁になるまでかけ算する回数を求め、
* その数とかけ算する回数との [Pair] を要素とするシーケンスを返す。
*/
fun numberToCountPairSequence(): Sequence<Pair<Int, Int>> {
val countList = mutableListOf<Int>() // 各数についての「かけ算する回数」を保持するためのリスト。
return countUpSequence(0) // 0 から順に
.map { number ->
number.toDigitList() // 各桁の値を要素とする配列を生成する。
.takeIf { digitList -> digitList.size > 1 } // 1桁の場合は null を返す。
?.reduce { product, digit -> product * digit } // 各桁をかけ算する。例:[9, 8] → 72
?.let { product -> countList[product] + 1 } // 「かけ算する回数」を求める。「かけ算する回数」は、各桁をかけ算した結果についての「かけ算する回数」に 1 を加えたもの。
.let { product -> product ?: 0 } // 1桁の場合は「かけ算する回数」を 0 とする。
.let { count -> number to count }
}
.onEach { (number, count) ->
countList.add(number, count)
}
}
/**
* 各桁の値を要素とする配列を返す。
*
* 例:
* ```
* 12.toDigitList() // -> [1, 2]
* 0.toDigitList() // -> [0]
* ```
*/
fun Int.toDigitList(): List<Int> {
require(this >= 0)
var int = this
return sequence {
while (int >= 10) {
yield(int % 10)
int /= 10
}
yield(int)
}.toList().asReversed()
}
/**
* 要素の値が1ずつ増加していくシーケンスを返す。
*
* @param from 最初の要素の値。
*/
fun countUpSequence(from: Int): Sequence<Int> = sequence {
var value = from
while (true) {
yield(value)
++value
}
}
結果
結果は元記事のものと一致。
ただし 3,000,000 までの計算は4秒程度(元記事では4分程度)で済んだ。(5年以上前に生産されたノートで実行。)
約 30,000,000 まで計算することになった、かけ算する回数が 9 のものでも、10秒程度で計算できた。
かけ算する回数が 10 のものも求めようとしたが、OutOfMemoryError
がスローされてしまった。(最大使用メモリを10GBにしてみたが、30分ほど計算したあげく OutOfMemoryError
。)
出力例
2桁の数すべて
10: 1回
11: 1回
12: 1回
13: 1回
14: 1回
15: 1回
16: 1回
17: 1回
18: 1回
19: 1回
20: 1回
21: 1回
22: 1回
23: 1回
24: 1回
25: 2回
26: 2回
27: 2回
28: 2回
29: 2回
30: 1回
31: 1回
32: 1回
33: 1回
34: 2回
35: 2回
36: 2回
37: 2回
38: 2回
39: 3回
40: 1回
41: 1回
42: 1回
43: 2回
44: 2回
45: 2回
46: 2回
47: 3回
48: 2回
49: 3回
50: 1回
51: 1回
52: 2回
53: 2回
54: 2回
55: 3回
56: 2回
57: 3回
58: 2回
59: 3回
60: 1回
61: 1回
62: 2回
63: 2回
64: 2回
65: 2回
66: 3回
67: 2回
68: 3回
69: 3回
70: 1回
71: 1回
72: 2回
73: 2回
74: 3回
75: 3回
76: 2回
77: 4回
78: 3回
79: 3回
80: 1回
81: 1回
82: 2回
83: 2回
84: 2回
85: 2回
86: 3回
87: 3回
88: 3回
89: 3回
90: 1回
91: 1回
92: 2回
93: 3回
94: 3回
95: 3回
96: 3回
97: 3回
98: 3回
99: 2回
(91 ミリ秒)
3,000,000 未満の数における最大
2677889: 8回
(4370 ミリ秒)
かけ算する回数が 9
26888999: 9回
(10767 ミリ秒)