S-99: Ninety-Nine Scala Problemsというのは、P-99: Ninety-Nine Prolog Problemsが元ネタの、99個の小問題をScalaで解いてみるというもので、実際に99個の難易度の異なる問題が用意されている。一気に99個やるのはきついので、今日はとりあえず最初の10問(P01-P10)を解いてみた。ただ、問題によっては組み込みメソッドを使うとそのまま解けてしまうものもあるので、
- 基本的なメソッド(List#headやList#tailなど)を除いて、問題をそのまま解けるような組み込みのメソッドは使わない
- 高階関数に関しても、組み込みのものは使用せず、必要なら自分で定義して使うようにする
という縛りをつけてみた。
P01-P10まで、テキトーに問題文を意訳してみると
- P01(*) リストの最後の要素を見つけよ
- P02(*) リストの最後の一つ前の要素を見つけよ
- P03(*) リストのK番目の要素を見つけよ
- 慣例により、リストの最初の要素を0とする
- P04(*) リストの要素数を見つけよ
- P05(*) リストを反転せよ
- P06(*) リストが回文かどうか調べよ
- P07(**) ネストしたリストを平らにせよ
- P08(**) リストの要素の中で連続した重複要素を取り除け
- リストが要素の繰り返しを含んでいるならば、要素の単一のコピーで置き換えよ。要素の順番は変えてはいけない。
- P09(**) リストの要素の中で連続した重複要素をサブリストにまとめよ。
- リストが要素の繰り返しを含んでいるならば、別々のサブリストに分けよ。
- P10(*) リストのランレングスエンコーディング
- P09の結果を使って、いわゆるランレングスデータ圧縮法を実装せよ。連続した重複要素は、NがEの重複した要素数であるようなタプル(N, E)としてエンコードされる。
以下が、回答のコード。
回答を作るまでに40分ちょっとかかった(その後、若干コードを整理した)。
object P01toP10 {
def append[T](a: List[T], b: List[T]): List[T] = a match {
case Nil => b
case x::xs => x::append(xs, b)
}
def foldLeft[A, B](list: List[A], b: B)(f: (B, A) => B): B = {
list match {
case x::xs => foldLeft(xs, f(b, x))(f)
case Nil => b
}
}
def map[A, B](list: List[A])(f: A => B): List[B] = list match {
case x::xs => f(x)::map(xs)(f)
case Nil => Nil
}
def last[T](list: List[T]): T = {
foldLeft(list, List[T]()){(b, a) => a::b}.head
}
def penultimate[T](list: List[T]): T = {
foldLeft(list, List[T]()){(b, a) => a::b}.tail.head
}
def nth[T](index: Int, list: List[T]): T = list match {
case x::_ if index == 0 => x
case _::xs if index > 0 => nth(index - 1, xs)
case _ => error("")
}
def length[T](list: List[T]): Int = foldLeft(list, 0){(b, a) => b + 1}
def reverse[T](list: List[T]): List[T] = {
foldLeft(list, List[T]()){(b, a) => a::b}
}
def isPalindrome[T](list: List[T]): Boolean = list == reverse(list)
def flatten(list: List[Any]): List[Any] = list match {
case (x:List[_])::xs => append(flatten(x), flatten(xs))
case x::xs => x::flatten(xs)
case Nil => Nil
}
def compress[T](list: List[T]): List[T] = {
def compress1(pre: T, rest: List[T]): List[T] = rest match {
case x::xs if pre == x => compress1(pre, xs)
case x::xs => pre::compress1(x, xs)
case Nil => pre::Nil
}
list match {
case x::xs => compress1(x, xs)
case Nil => Nil
}
}
def pack[T](list: List[T]): List[List[T]] = {
def pack1(pre: List[T], rest: List[T]): List[List[T]] = rest match {
case x::xs if pre.head == x => pack1(x::pre, xs)
case x::xs => pre::pack1(List(x), xs)
case Nil => pre::Nil
}
list match {
case x::xs => pack1(List(x), xs)
case Nil => Nil
}
}
def encode[T](list: List[T]): List[(Int, T)] = {
map(pack(list)){x => (length(x), x.head)}
}
}動作例。これ以外の入力ではテストしてないので、ひょっとしたらどっかにバグがあるかもしれないけど、一応一発で正しい出力を得ることができた。
scala> import P01toP10._
import P01toP10._
scala> last(List(1, 1, 2, 3, 5, 8))
res1: Int = 8
scala> penultimate(List(1, 1, 2, 3, 5, 8))
res2: Int = 5
scala> nth(2, List(1, 1, 2, 3, 5, 8))
res3: Int = 2
scala> length(List(1, 1, 2, 3, 5, 8))
res4: Int = 6
scala> reverse(List(1, 1, 2, 3, 5, 8))
res5: List[Int] = List(8, 5, 3, 2, 1, 1)
scala> isPalindrome(List(1, 2, 3, 2, 1))
res6: Boolean = true
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8)))
| )
res7: List[Any] = List(1, 1, 2, 3, 5, 8)
scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res8: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)
scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res9: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), Li
st('a, 'a), List('d), List('e, 'e, 'e, 'e))
scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res10: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e)
)
