Ninety-Nine Scala Problemsを解いてみた

ドワンゴが公開してい新卒エンジニア向けのScalaの研修資料で一通り終わった後に説明があるNinety-Nine Scala Problemsについてリスト操作の問題を解いてみました。 せっかくなので何問かまとめてみようと思います。

P19 (**) Rotate a list N places to the left.

P19 (**) Rotate a list N places to the left.
Examples:
scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)
scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)

引数で受け取った数によりリストの順番をずらす問題になっています。ずらす数として負の数も受け取るのがポイントになっていると思います。 これを以下のように実装しました。

import P17.split;

object P19 {
  def rotate[A](n: Int, list: List[A]): List[A] = {
    val length = list.length
    val k = n % length
    split(if(k >= 0) k else k + length , list).foldRight(List.empty[A])((cur, acc) => {
      acc ::: cur
    })
  }
}

まずずらす数がリストの数より大きくなる可能性があるので剰余を計算しています。次にsplitでリストを分割するのですが、負の数を渡さないように if(k >= 0) k else k + length としています。splitの結果長さ2のリストになり、順番を入れ替えてリストの中身のリストを連結させたものが求めたかった答えになります、実際の実装ではリストの順番を入れ替えるのではなくfoldRightを使っています。

例えばずらす数が8でリストがList(1,2,3,4,5)の場合であれば、以下のようになります。
1.ずらす数の剰余を計算
8 % 5 で3

2.splitする
List(List(1,2,3), List(4,5))

3.リストの順番を入れ替えて中身を連結する。
List(4,5) ::: List(1,2,3)

P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.

P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(123) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, thisresult may be great. But we want to really generate all the possibilities.
Example:
scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ...

引数で受け取った数の分だけリストから取り出す場合の組み合わせのパターンをすべて求めるようです。長さ6のリストから3件取り出す場合のパターンであれば(6 * 5 * 4)/(3 * 2 * 1) = 20パターンになるかと思います。

実装は以下のようになりました。

import P04.length
import P05.reverse
import P22.range

object P26 {

  def combinations[T](k: Int, list: List[T]): List[List[T]] = {
    val listSize = length(list)
    def select[T](currentIndex: Int, k: Int): List[Int] = range(currentIndex, listSize - k)
    def appendSelect(list: List[Int], k: Int): List[List[Int]] = select(list.head+1, k).map(_ :: list)

    reverse(range(1, k - 1)).foldLeft(select(0, k).map(List(_))){
      case (acc, cur) => acc.flatMap(appendSelect(_,cur))
    }.map(reverse).map(_.map(list(_)))
  }
}

いくつか関数を定義しているのですが、それぞれの用途は以下のようになっています。

• select
  リスト中からひとつ選択できる候補のインデックスのリストを返す。このとき選べるインデックスの候補はcurrentIndex以降で残りの選択数とリストのサイズを考慮する。

• appendSelect 降順のインデックスのリストと残りの選択数を引数で受け取ります。それからselect関数を呼び出し次に選べる候補のインデックスのリストを取得しそれぞれに引数で受けとったリストを追加することで、選択後のインデックスのリストのリストを返しています。

なので以下の処理では組み合わせのパターンのインデックスのリストを取得しています。

reverse(range(1, k - 1)).foldLeft(select(0, k).map(List(_))){
    case (acc, cur) => acc.flatMap(appendSelect(_,cur))
}

それからリスト上の値に変換しないといけないので最後tに map(reverse).map(_.map(list(_))) としています。 map(reverse) で逆順になる対象は List[List[Int]] のうちの内側のリストになるのが慣れるまで分かりづらい気がします。

P27 (**) Group the elements of a set into disjoint subsets.

P27 (**) Group the elements of a set into disjoint subsets.
b) Generalize the above predicate in a way that we can specify a list of group sizes and the predicate willreturn a list of groups.
Example:
scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo Ida)), ...
Note that we do not want permutations of the group members; i.e. ((Aldo, Beat), ...) is the same solutionas ((Beat, Aldo), ...). However, we make a difference between ((Aldo, Beat), (Carla, David), ...) and (Carla, David), (Aldo, Beat), ...).
You may find more about this combinatorial problem in a good book on discrete mathematics under the term"multinomial coefficients".

今度は選択対象となるリストの長さを複数同時に受け取って、その時のパターンすべて求めるのが課題のようです。この時2人、2人、5人のグループで分ける場合の時最初の2人と次の2人を逆にした場合であっても区別してカウントするようです。 9人から2人、2人、5人のグループに分ける場合 9 * 8 / ( 2 * 1 ) * 7 * 6 / ( 2 * 1 ) * 5 * 4 * 3 * 2 * 1 / ( 5 * 4 * 3 * 2 * 1 ) = 756でちょっといじっただけでもパターンの数が大きく増えるのがわかると思います。

これは以下のように実装しました。

import P04.length

object P27 {

  def group[T](setting: List[Int], list: List[T]): List[List[List[T]]] = {
    def select[T](nokori: Int, list: List[T]): List[(List[T], List[T])] =
      list match {
        case _ if nokori == 0 => List((Nil, list))
        case _ if nokori == length(list) => List((list, Nil))
        case x :: xs if nokori > 0 =>
          select(nokori - 1, xs).map(a => (x :: a._1, a._2)) ++ select(nokori, xs).map(a => (a._1, x :: a._2))
      }

    setting.tail.foldLeft(select(setting.head, list).map(a=>(List(a._1), a._2))) {
      case (acc, cur) =>
        acc.flatMap(a => select(cur, a._2).map(b=>(a._1 :+ b._1, b._2)))
    }.map(a=>a._1)
  }

}

今回は select 関数で指定された数の分選んだものと残り物のペアのリストを返すようにしています。 例えばselect(2, List(1,2,3))であればList( ( List(1,2), List(3)), (List(1,3), List(2)), (List(2,3), List(1)))となります。これを利用し、人数のリストの長さ分select関数を実行し、次実行するときは残ったリストから選ぶように気を付けるだけです。 select関数でリストがネストしても大丈夫なようにflatMapを使っているのがポイントになるかと思います。

P28 (**) Sorting a list of lists according to length of sublists.

P28 (**) Sorting a list of lists according to length of sublists.
a) We suppose that a list contains elements that are lists themselves. The objective is to sort theelements of the list according to their length. E.g. short lists first, longer lists later, or vice versa.
Example:
scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), Lis('m, 'n), List('o)))
res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('d, 'e), List('m, 'n), List('a, 'b, 'c), Lis('f, 'g, 'h), List('i, 'j, 'k, 'l))
b) Again, we suppose that a list contains elements that are lists themselves. But this time the objectiveis to sort the elements according to their length frequency; i.e. in the default, sorting is doneascendingly, lists with rare lengths are placed, others with a more frequent length come later.
Example:
scala> lsortFreq(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l),List('m, 'n), List('o)))
res1: List[List[Symbol]] = List(List('i, 'j, 'k, 'l), List('o), List('a, 'b, 'c), List('f, 'g, 'h), List('d 'e), List('d, 'e), List('m, 'n))
Note that in the above example, the first two lists in the result have length 4 and 1 and both lengthsappear just once. The third and fourth lists have length 3 and there are two list of this length. Finally,the last three lists have length 2. This is the most frequent length.

次はリストのソートですが、ソートの条件を渡せれるように出来たら便利かと思います。

実装は以下のようになっています。

import P04.length

object P28 {
  private def sort[T](list: List[T])(implicit compare: (T, T) => Int): List[T] = {
    length(list) / 2 match {
      case x if x >= 1 =>
        list.splitAt(x) match { case (a,b) => mergeBySort(sort(a), sort(b))}
      case x if x == 0 =>
        list
    }
  }

  private def mergeBySort[T](list1: List[T], list2: List[T])(implicit compare: (T, T) => Int): List[T] = {
    if(list1.headOption.isEmpty || list2.headOption.isEmpty) {
      list1 ++ list2
    } else {
      compare(list1.head, list2.head) match {
        case x if x < 0 => list1.head :: mergeBySort(list1.tail, list2)(compare)
        case _ => list2.head :: mergeBySort(list1, list2.tail)(compare)
      }
    }
  }

  def lsort[T](list: List[List[T]]) = sort(list)(compByListLength)
  private def compByListLength[T](a: List[T], b:List[T]): Int = a.length - b.length

  def lsortFreq[T](list: List[List[T]]) = {
    val freqMap: Map[Int, Int] = list.foldLeft(Map[Int ,Int]().withDefaultValue(0)){
      (map,key) =>map + (key.length -> (map(key.length) + 1))
    }
    val freqOrderMap = freqMap.toList.sortWith {(a, b) =>
      if (a._2 < b._2 )  true
      else if (a._2 == b._2 && a._1 > b._1) true
      else false
    }.zipWithIndex.map(a => (a._1._1, a._2)).toMap[Int, Int]
    def compByFreq[T](a: List[T], b:List[T]): Int = {
      freqOrderMap.getOrElse(a.length, 0) - freqOrderMap.getOrElse(b.length, 0)
    }
    sort(list)(compByFreq)
  }
}

ソートにはマージソートを使っていますが、これはjavaの標準のソート関数でも使われておりデータの内容にかかわらず安定した性能が出せるという特徴があるようです。

実装はこのあたりです。

  private def sort[T](list: List[T])(implicit compare: (T, T) => Int): List[T] = {
    length(list) / 2 match {
      case x if x >= 1 =>
        list.splitAt(x) match { case (a,b) => mergeBySort(sort(a), sort(b))}
      case x if x == 0 =>
        list
    }
  }

  private def mergeBySort[T](list1: List[T], list2: List[T])(implicit compare: (T, T) => Int): List[T] = {
    if(list1.headOption.isEmpty || list2.headOption.isEmpty) {
      list1 ++ list2
    } else {
      compare(list1.head, list2.head) match {
        case x if x < 0 => list1.head :: mergeBySort(list1.tail, list2)(compare)
        case _ => list2.head :: mergeBySort(list1, list2.tail)(compare)
      }
    }
  }

最初にsort関数で分割していき、分割が完了したらマージソートで二つのリストの先頭の要素を比較する形にしています。ソートの条件にかかわらず使いまわせれるよう比較用の関数を暗黙の引数で受け取れるようにしています。問題ではリストの中にリストがあって、内側のリストの長さによりソートを行うのですが、ここでは型パラメータでは二重のリストとかを気にする必要がないのもポイントかもしれないです。

リストの長さで短いほうが先に来るについては以下になります。

  def lsort[T](list: List[List[T]]) = sort(list)(compByListLength)
  private def compByListLength[T](a: List[T], b:List[T]): Int = a.length - b.length

単純に長さを比較しているだけです。

次がわかりづらいですが、リストの長さの頻度でソートするというもので例えば長さ2のリストはたくさんあるから後の方に配置するといったものです。実装は以下のようになりました。

  def lsortFreq[T](list: List[List[T]]) = {
    val freqMap: Map[Int, Int] = list.foldLeft(Map[Int ,Int]().withDefaultValue(0)){
      (map,key) =>map + (key.length -> (map(key.length) + 1))
    }
    val freqOrderMap = freqMap.toList.sortWith {(a, b) =>
      if (a._2 < b._2 )  true
      else if (a._2 == b._2 && a._1 > b._1) true
      else false
    }.zipWithIndex.map(a => (a._1._1, a._2)).toMap[Int, Int]
    def compByFreq[T](a: List[T], b:List[T]): Int = {
      freqOrderMap.getOrElse(a.length, 0) - freqOrderMap.getOrElse(b.length, 0)
    }
    sort(list)(compByFreq)
  }

リストの長さでソートをしなければいけないのですがクロージャを使っています。最初に長さ毎の件数を freqMap に保存し、それから長さ毎のオーダー結果を freqOrderMap に保持するようにしています。あとは比較関数を作成しソート関数を呼び出すだけです。