Scalaで灰色問題を解いた時に面白く感じたことや関数など

はじめに

2022/07から株式会社FOLIOで働いている田口と申します。

私が所属しているチームは、4RAP というプロダクト(金融機関の「投資一任サービス」を実現する SaaS 型プラットフォーム)において、金融機関とのデータのやり取りを行うインターフェイス部分の開発・運用を担当しています。

弊チームではバックエンドの開発言語として Scala を採用していますが、参画するメンバーのうちで Scala を使ったことのある方は2,3割で、大半の方は Scala に親しみがない状態で入社されます。そのため、弊チームでは Scala やライブラリ学習のための知の高速道路としてチュートリアルリポジトリが用意されていることを以下記事では紹介しました。

https://zenn.dev/nozomitaguchi/articles/c3fd36dfc69797

個人的には Scala に限らず「新しい言語の書き方を勉強するときは競プロなどでめっちゃ簡単な問題をたくさん解く」というのが良いと感じていています。私は本当に簡単な問題しかやったことがないのですが「どうすれば標準関数を使ってシンプルに書けるのか」を勉強しながら問題を解くという細かいステップを繰り返すことは、書き方の勉強として本当に有用だなと思っています。

私が利用しているのは AtCoder でして、AtCoder Problems と言うサイトを使うと、解いた問題の管理や難易度の確認などができます。難易度として一番低いレベルが灰色で表現されており、プログラミング初学者向けでも解けるかなくらいの簡単な問題が多いと思います。

簡単な問題しか解いていない(==解けない)ことの証明の図

2021年を最後に(子供が生まれて以来)問題をほとんど全く解いていませんが、当時のメモなどを掘り起こして、Scala で解いた時に個人的に面白く感じた関数や書き方をいくつか紹介しようと思います。

※ 実務ではおそらくほとんど役に立たないと思います。
※「Scala で解いた」と言いつつ Java のメソッドの話も混ざります。
※ 2021年が最新のメモを見ているのでコード例は Scala2 です。

いくつか Tips を紹介

標準入出力について

まず「問題を解くための入出力」どう書くの？というのがあると思いますのでそちらから紹介します。

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N: String = sc.next()
  println(N)
}

Scala と言いつつ、Java の Scanner を使うんかい！とみなさん心の中でツッコミをいただいていると思いますが、Scanner::next()をはじめScanner::nextInt()など便利な関数が用意されていて、Scala の標準出力より便利なのでこちらを使っています。

Java の Scanner は遅いという話もあるんですが、灰色問題を解く中でネックになったことはなくて、個人的には問題ないかなと思っています。

IterableFactory::fill

これもまた標準出力の話ですが、よくある入力のパターンとして

$$NA1...AN N\newline A_1 ... A_N$$

というようなものがあります。
一行目に数値が与えられて、二行目はその数値分の要素があることを示していますが、これを受け取るときに役にたつのが IterableFactory:fill です。Array を例として紹介します。

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N = sc.nextInt()
  val A = Array.fill(N)(sc.next())
  println(A.toList)
}

このように第一引数に要素数を入れて、入力をその分だけ受け取るというようなことをシンプルに書くことができます。

一次元の配列の他に、二次元(それ以上)の配列に対応することも可能で、2 x 3 の二次元配列に 0 を埋めたものを作る場合は、以下のように書くことができます。

Array.fill(2, 3)(0)

また、fill と類似した tabulate という関数があり、こちらは第二引数として index to ??? の関数を受け取る部分に違いがあります。

val table = Map(0 -> "test0", 2 -> "test2")
val maybeValues: List[Option[String]] = List.tabulate(2)(table.get)
println(maybeValues) // List(Some(test0), None)

Iterable::sliding

さて唐突ですが、問題です。

val string = "nozomitaguchi"
def f(string: String): String = ???
f(string) // "nzmtgci"

この文字列を、前から数えて奇数文字目だけ抜き出して nzmtgci という文字列にしたいとします。
どうするでしょうか。「タイトルに書いてあるじゃん」と言わずに考えてみてください。

index を付与して、そのなかで 2 で割り切れるものだけ集める？シンプルでいいですよね。

string.zipWithIndex.collect {
  case (char, index) if index % 2 == 0 => char
}.mkString

次に sliding という関数を使ってみましょう。

string.sliding(1, 2).mkString

何やってるんだか、わかりづらいですね。
こんなわかりづらい処理書くんじゃないとコードレビューでは指摘されてしまうかもしれません。
Scala の docs に書いてある例を見てみましょう。

Example:
List(1, 2, 3, 4, 5).sliding(2, 2) = Iterator(List(1, 2), List(3, 4), List(5))
Example:
List(1, 2, 3, 4, 5, 6).sliding(2, 3) = Iterator(List(1, 2), List(4, 5))

• 第一引数 = size(要素数)
• 第二引数 = step(取得する間隔)

と書いてあるように、分割された各リストが持つ要素数と、分割する時の幅を指定する形です。

string.sliding(1, 2).mkString

このコードを改めて見ると「サイズが1の配列を2個おきに作って合体している」んですね。面白いですね、いろんな活用方法があると思います。

同じような概念で、Stream 系のライブラリでは Windowing というものがあったかと思います。

split(**, -1)

※これは Scala というより Java です。

A, B という二種類の文字があり AABBBAAAAA のようにランダムに繰り返される文字列が入力される場合、A を繰り返した最大値を(AABBBAAAAA の場合は 5 というふうに)返したいとします。

この問題は、あなたならどう実装しますか？

正規表現で抜き出して max 値を取るでしょうか。

val string = "AABBBAAAAA"
val matches = "A+".r.findAllMatchIn(string)
matches.map(_.matched.length).maxOption.getOrElse(0)

それも良いと思います。

今回は B を split することも考えてみたいです。

val string = "AABBBAAAAA"
string.split("B").map(_.length).maxOption.getOrElse(0)

良さそうですね。速度がどうとかは置いておいて、シンプルに書けます。
split メソッドの定義を眺めていると、第二引数に limit という数値を受け取るメソッドも用意されていることを発見できます。

public String[] split(String regex, int limit)

ここに -1 を入れると面白いことが起きます。

val string = "AABBBAAAAA"
string.split("B", -1).map(_.length).max

なんと maxOption.getOrElse(0) と書かなくて良くなりました。

タイピング数がとても減ったぞ！が、それと引き換えに、わかりづらくなったのと max を見ると maxOption 使わなくて平気なのか、心配になる方が多いかと思いますので、プロダクトコードではやらないかなと思います。

実際のコードは説明しませんが、具体的には、-1 をつけないとどういうことが起きるかというと、

val string = "BBBB"
string.split("B").map(_.length).max
// Exception in thread "main" java.lang.ExceptionInInitializerError
//	 at Main.main(Main.scala)
// Caused by: java.lang.UnsupportedOperationException: empty.max

空の配列に対して max を当てることになり、empty.max といって怒られてしまいます。-1 をつけると、空文字を持つ配列として結果が買えるので max だけでも怒られなくなるんですね。

まぁでも実務で NonEmptyList とかじゃない普通の List などで maxOption じゃなくて max を使っているのをみたら警戒しますよね。要注意。

ArrayOps::transpose

続いて問題です。

以下のような N * N のマスを右に 90 度回転させたい時どうやって書きますか？

val square = Array(
  Array(1, 2, 3),
  Array(4, 5, 6),
  Array(7, 8, 9)
)

これを以下のようにしたい場合です。

7, 4, 1
8, 5, 2
9, 6, 3

二重ループで index 使ってコネコネしますか？

/*
 * 7, 4, 1
 * 8, 5, 2
 * 9, 6, 3
 */
(0 to 2).map(i => (0 to 2).map(j => square(2 - j)(i)))

それもいいですね。こういう処理をバグらずに書けるのは、言語によらないスキルの一つとして良いと思います。早そうだし。
今回は、transpose を使った書き方を紹介します。

transpose は、二重になっている配列を縦に持ち直すことができる関数です。

/*
 * 1, 4, 7
 * 2, 5, 8
 * 3, 6, 9
 */
square.transpose

square に transpose を当ててみるとこんな感じで、縦に 1, 2, 3 という風に変化しました。
ですので、transpose を２回連続で当てて見ると、

/*
 * 1, 2, 3
 * 4, 5, 6
 * 7, 8, 9
 */
square.transpose.transpose

元に戻ります。

この transpose と reverse を併用すると、さっきやりたかったことをシュッと書くことができるんですね。

/*
 * 7, 4, 1
 * 8, 5, 2
 * 9, 6, 3
 */
square.reverse.transpose

reverse してから transpose すると右に 90 度回転させることができました。
ちなみに transpose してから reverse すると左に 90 度回転させることができます。

/*
 * 3, 6, 9
 * 2, 5, 8
 * 1, 4, 7
 */
square.transpose.reverse

180 度回転させたい場合は、それらを 2 回使うことで対応できます。

/*
 * 9, 8, 7
 * 6, 5, 4
 * 3, 2, 1
 */
square.reverse.transpose.reverse.transpose

こんなに連続して関数使って大丈夫なのかしら？と思うかもしれないですが、今のところこれが原因でタイムアウト判定されたことないし大丈夫だと思います(ホントかな)。シンプルにreverse.transpose.reverse.transposeはいくらなんでもダサいけれども、きっと大丈夫。

個人的には添え字で頭を悩ませるより、100倍マシだなと感じています。

数値の各桁の和のやり方あれこれ

※ これは言語や競プロによらない基礎的な教養な気もします。

続いて問題です。

val string = "12345"

このような数字のみを含む文字列を各桁の和を取りたい場合(今回で言うと 15 と出力したい場合)どう言うふうに実装するのがいいでしょうか？

普通に char を int にして足し算する？

string.toSeq.map(_.toInt).sum // 255

あああああ！想定と違う出力になってしまいました。なぜでしょう。char を Int に変換する場合は、
'1' は 1にならないんですよね。そうなんですよ。実務あるあるだったりするようなレベルでしょうか。

じゃあどうするかというといろんなパターンがあると思いますが、まずは

string.split("").map(_.toInt).sum

char ではなく文字として一文字一文字を扱うようにsplit("")してから toInt しようぜと言う書き方ですね。続いては、

string.toSeq.map(_.toString.toInt).sum

char.toString.toInt と言う処理を行うようにしました。他には、

string.toSeq.map(_ - '0').sum

これは何をやっているんでしょうね。。。？
char から'0'を引くと、数字の char の場合は、対応する数字に変換されるんですね。

'0' == 48 // true
'1' == 49 // true
'9' == 57 // true

char の '0' ~ '9' は数値としては 48 ~ 57 に対応しているので、 '9' - '0' = 9と言うふうに計算ができるということを利用して、数値変換ができるんですね。実務でなんのコメントもなく書いてたら怒られそうなコードですが、こう言うこともできるようです。

最低限 char to int にはこういう罠があることだけ、覚えておきたいところです。

LazyList

個人的には実務では何回かしか使ったことのない無限リストですが、競プロの簡単な問題だと使うチャンスはそこそこあります。

フィボナッチ数列やコラッツ数列みたいな前の値を使って次の値を作り続けて、その何番目がどう言う値なんだっけ、みたいな問題がたまにあります。そう言うときに LazyList チャンス〜！と目を輝かせながら使うと良いと思います。

フィボナッチ数列の N 番目の数字教えて的な問題の時は、以下のように LazyList を使ってフィボナッチ数列を作るのがシンプルで良いですね。

val N = 6
val fibs: LazyList[Int] = 1 #:: fibs.scanLeft(1)(_ + _)
fibs(N) // 13

Seq::combinations

問題です。

val ints = List(1, 2, 3)

重複ありの組み合わせを作る時どう実装していますか？
今回は、2つの重複あり組み合わせにする場合を考えてみましょう。

(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)

二重ループで順番が違うだけの要素をフィルタしながら集積していきますかね？

val comb = scala.collection.mutable.LinkedHashSet.empty[(Int, Int)]
for {
  i <- ints
  j <- ints if !comb.contains(j -> i)
} comb.add(i -> j)

これも良いですが mutable になってしまっているのが少し残念なのと、3つ4つの重複ありなどにしたい場合の汎用性が低いですよね。

そこで combinations を使いましょう。

ints.combinations(2)
// List(1, 2)
// List(1, 3)
// List(2, 3)

単純に ints に combinations(2) を当てると、重複なしの組み合わせになります。
重複ありの組み合わせにしたい場合は、ひと工夫して、

(ints ::: ints).combinations(2)

や、汎用的に使えるように

List.fill(2)(ints).flatten.combinations(2)

とすると、重複ありの組み合わせが生成できます。処理自体は遅そうに思うので、速度が必要な場合は別の手段を考える必要があるかもしれません。

Int の切り上げ

実務でもあることかと思いますが、Int の割り算の時に切り上げを行いたいことが度々あります。
皆さんはどうやっていますか？

math.ceil(i / j.toDouble).toInt

とやるのが素直な書き方でしょうか。これでも良いのですが、Double への変換などを挟まないシンプルな方法があります。

(i + j - 1) / j
// i = 6, j = 3 のとき, (6 + 3 - 1) / 3
// i = 7, j = 3 のとき, (7 + 3 - 1) / 3

よくあるテクニックだと思いますが、面白いですよね。

配列の中の最大値を特別扱いする処理

問題です。

配列のうち、最大値は 2 倍にしてそれ以外の値はそのまま、そしてそれを合算した値を出力したい場合どう言う処理を書くでしょうか？

val ints = List(110, 50, 10, 400)

つまりこれを、400 * 2 + 110 + 50 + 10 = 970 と言うふうに加工したい場合です。

ソートして最大値とそれ以外を分けた後で計算するでしょうか？

val ints = List(110, 50, 10, 400)
val sortedInt = ints.sorted
val max = sortedInt.last
val other = sortedInt.init
max * 2 + other.sum

もう少し工夫をする余地がありますよね。

逆順に sorted すると、max と other をパターンマッチできるようになってシンプルに書くことができそうです。

val ints = List(110, 50, 10, 400)
val max :: other = ints.sorted(Ordering[Int].reverse)
max * 2 + other.sum

逆順でソートする場合は、sorted(Ordering[Int].reverse)のように書くことができます。すっきりとしたコードになりました。

...なお、この問題に対するアプローチは、

ints.sum + ints.max

とすればもっと良い。と社内の競プロニキにツッコミをいただきました。

おわりに

昔のメモを頼りに、Scala で競プロの簡単な問題を解いた時に面白いなぁと思った事柄についてつらつらと紹介させていただきました。

Scala を勉強しようかなぁ、Scala で競プロ始めてみようかなぁと思った時に、この記事のことを少しでも思い出していただけると幸いです。