kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

S-99: Ninety-Nine Scala Problems(P21-P28)を解いてみた

S-99: Ninety-Nine Scala Problems(P11-P20)を解いてみたの続き。P21-P30ではなく、P21-P28になっているのは、P27とP28がそれぞれ二問ずつあり、P28で一端問題が区切られているため。今回のは、時間を測り忘れていたが、前回よりもややてこずった気がする。以下、回答のコード。

object P21toP28 {
  import P01toP10._
  import P11toP20._
  def mergeSort[T](list: List[T])(lt: (T, T) => Boolean): List[T] = {
    def merge(list1: List[T], list2: List[T]): List[T] = {
      (list1, list2) match {
        case (x::xs, y::ys) if lt(x, y) => x::merge(xs, list2)
        case (x::xs, y::ys) => y::merge(list1, ys)
        case (Nil, ys) => ys
        case (xs, Nil) => xs
      }
    }
    def mergeSort1(list: List[T], len: Int): List[T] = len match {
      case 0 => Nil
      case 1 => list
      case _ => 
        val m = len / 2
        val (fst, snd) = split(m, list)
        merge(mergeSort1(fst, m), mergeSort1(snd, len - m))
    }
    mergeSort1(list, length(list))
  }
  
  def insertAt[T](e: T, index: Int, list: List[T]): List[T] = list match {
    case x if index == 0 => e::x
    case x::xs if index > 0 => x::insertAt(e, index - 1, xs)
    case _ => error("")
  }
  def range(from: Int, to: Int): List[Int] = {
    if(from == to) List(to)
    else if(from < to) from::range(from + 1, to)
    else error("")
  }
  def randomSelect[T](n: Int, list: List[T]): List[T] = {
    def randomSelect1(n: Int, len: Int, list: List[T]): List[T] = {
      if(n == 0) List[T]()
      else if(n > 0) {
        val (rest, e) = removeAt((Math.random * len).toInt, list)
        e::randomSelect1(n - 1, len - 1, rest)
      } else error("")
    }
    val len = length(list)
    if(n <= len) randomSelect1(n, len, list) else error("")
  }
  def lotto(n: Int, m: Int): List[Int] = randomSelect(n, range(1, m))
  def randomPermute[T](list: List[T]): List[T] = randomSelect(length(list), list)
  def groupInto[T](n: Int, k: Int, list: List[T]): List[(List[T], List[T])] = list match {
    case _ if k == n => List((list, Nil))
    case _ if k == 0 => List((Nil, list))
    case x::xs if k > 0 => 
      append(
        map(groupInto(n - 1, k - 1, xs)){a => (x::a._1, a._2)}, 
        map(groupInto(n - 1, k, xs)){a => (a._1, x::a._2)})
    case _ => error("")
  }
  def combinations[T](k: Int, list: List[T]): List[List[T]] = {
    map(groupInto(length(list), k, list))(_._1)
  }
  def group3[T](list: List[T]): List[List[List[T]]] = {
    flatMap(groupInto(9, 2, list)){ case (s1, r) =>
      flatMap(groupInto(7, 3, r)){ case (s2, r) =>
        map(groupInto(4, 4, r)){ case (s3, r) => List(s1, s2, s3) }}}
  }
  def group[T](setting: List[Int], list: List[T]): List[List[List[T]]] = {
    def group_(setting: List[Int], n: Int, list: List[T]): List[List[List[T]]] = {
      setting match {
        case Nil => List(Nil)
        case x::xs => 
          flatMap(groupInto(n, x, list)){ case (s, r) => map(group_(xs, n - x, r))(k => k.::(s)) }
      }
    }
    group_(setting, length(list), list)
  }

  def lsort[T](list: List[List[T]]): List[List[T]] = {
    map(mergeSort(map(list)(x => (x, length(x))))(_._2 < _._2))(_._1)
  }

  def lsortFreq[T](list: List[List[T]]): List[List[T]] = {
    val listl = map(list)(x => (x, length(x)))
    val freqs = foldLeft(listl, Map[Int, Int]()){ case (map, (lst, len)) =>
      map(len) = map.getOrElse(len, 0) + 1
    }
    map(mergeSort(map(listl)(x => (x._1, freqs(x._2))))(_._2 < _._2))(_._1)
  }
}

実行例。

scala> import P21toP28._
import P21toP28._

scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)

scala> range(4, 9)
res1: List[Int] = List(4, 5, 6, 7, 8, 9)

scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res2: List[Symbol] = List('d, 'b, 'c)

scala> lotto(6, 49)
res3: List[Int] = List(43, 7, 36, 25, 32, 34)

scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
res4: List[Symbol] = List('b, 'f, 'e, 'c, 'd, 'a)

scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res5: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b,
 'e), List('a, 'b, 'f), List('a, 'c, 'd), List('a, 'c, 'e), List('a, 'c, 'f), Li
st('a, 'd, 'e), List('a, 'd, 'f), List('a, 'e, 'f), List('b, 'c, 'd), List('b, '
c, 'e), List('b, 'c, 'f), List('b, 'd, 'e), List('b, 'd, 'f), List('b, 'e, 'f),
List('c, 'd, 'e), List('c, 'd, 'f), List('c, 'e, 'f), List('d, 'e, ...
scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hug
o", "Ida"))
res6: List[List[List[java.lang.String]]] = List(List(List(Aldo, Beat), List(Carl
a, David, Evi), List(Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla,
 David, Flip), List(Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, D
avid, Gary), List(Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Dav
id, Hugo), List(Evi, Flip, Gary, Ida)), List(List(Aldo, Beat), List...
scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip"
, "Gary", "Hugo", "Ida"))
res7: List[List[List[java.lang.String]]] = List(List(List(Aldo, Beat), List(Carl
a, David), List(Evi, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla,
 Evi), List(David, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, F
lip), List(David, Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Gar
y), List(David, Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List...
scala> lsort(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)))
res8: List[List[Symbol]] = List(List('o), List('m, 'n), List('d, 'e), List('d, '
e), List('f, 'g, 'h), List('a, 'b, 'c), List('i, 'j, 'k, 'l))

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)))
res9: List[List[Symbol]] = List(List('o), List('i, 'j, 'k, 'l), List('f, 'g, 'h)
, List('a, 'b, 'c), List('m, 'n), List('d, 'e), List('d, 'e))