S-99: Ninety-Nine Scala Problems(P01-P10)を解いてみたの続き。今回は、表題の通り、P11-P20までを解いてみた。とりあえず最初の回答を作るまでに大体50分くらい。その後、dropとrotateについて題意を勘違いしていたのに気づいてコードを修正。
以下、回答のコード。
object P11toP20 {
import P01toP10._
def flatMap[A, B](list: List[A])(f: A => List[B]): List[B] = {
foldLeft(list, List[B]()){(b, a) => append(b, f(a))}
}
def copyN[T](t: T, n: Int): List[T] = n match {
case 0 => List()
case n if n > 0 => t::copyN(t, n - 1)
case _ => error("")
}
def encodeModified(list: List[Any]): List[Any] = {
map(pack(list)){x =>
length(x) match { case 1 => x.head case n => (n, x.head) }
}
}
def decode[T](encoded: List[(Int, T)]): List[T] = {
flatMap(encoded){ case (n, e) => copyN(e, n) }
}
def encodeDirect[T](list: List[T]): List[(Int, T)] = {
def encodeDirect1(pre: T, n: Int, rest: List[T]): List[(Int, T)] = {
rest match {
case x::xs if pre == x => encodeDirect1(pre, n + 1, xs)
case x::xs => (n, pre)::encodeDirect1(x, 1, xs)
case _ => List((n, pre))
}
}
list match { case x::xs => encodeDirect1(x, 1, xs) case _ => List() }
}
def duplicate[T](list: List[T]): List[T] = {
flatMap(list){ case x => List(x, x) }
}
def duplicateN[T](n: Int, list: List[T]): List[T] = {
flatMap(list){ case x => copyN(x, n) }
}
def drop[T](nth: Int, list: List[T]): List[T] = {
def drop1[T](mth: Int, list: List[T]): List[T] = list match {
case x::xs if mth == 1 => drop1(nth, xs)
case x::xs if mth > 1 => x::drop1(mth - 1, xs)
case _ => List[T]()
}
if(nth > 0) drop1(nth, list) else error("")
}
def split[T](n: Int, list: List[T]): (List[T], List[T]) = list match {
case xs if n == 0 => (List[T](), xs)
case x::xs if n > 0 =>
split(n - 1, xs) match { case (a, b) => (x::a, b) }
case _ => error("")
}
def slice[T](i: Int, k: Int, list: List[T]): List[T] = {
def slice1[T](i: Int, k: Int, list: List[T]): List[T] = list match {
case x::xs if i > 0 => slice(i - 1, k - 1, xs)
case x::xs if k > 0 => x::slice(0, k - 1, xs)
case _ if i == 0 => List[T]()
case _ => error("")
}
if(0 <= i && i <= k) slice1(i, k, list) else error("")
}
/* abs(n) <= length(list)を仮定してしまっていたので、間違い。
def rotate[T](n: Int, list: List[T]): List[T] = {
def rotate_+(n: Int, list1: List[T], list2: List[T]): List[T] = list1 match {
case x::xs if n > 0 => rotate_+(n - 1, xs, x::list2)
case _ if n == 0 => append(list1, reverse(list2))
case _ => error("")
}
def rotate_-(n: Int, list1: List[T], list2: List[T]): List[T] = list1 match {
case x::xs if n > 0 => rotate_-(n - 1, xs, x::list2)
case _ if n == 0 => append(list2, reverse(list1))
case _ => error("")
}
if(n > 0) rotate_+(n, list, List[T]())
else if(n < 0) rotate_-(-n, reverse(list), List[T]())
else List[T]()
}
*/
def rotate[T](n: Int, list: List[T]): List[T] = {
def rotate_+-(n: Int, visit: List[T], rest: List[T]): List[T] = n match {
case n if n > 0 =>
rest match {
case Nil => rotate_+-(n, Nil, reverse(visit))
case x::xs => rotate_+-(n - 1, x::visit, xs)
}
case n if n < 0 =>
visit match {
case Nil => rotate_+-(n, reverse(rest), Nil)
case x::xs => rotate_+-(n + 1, xs, x::rest)
}
case 0 => append(rest, reverse(visit))
}
list match {
case Nil => error("")
case _ => rotate_+-(n, Nil, list)
}
}
def removeAt[T](nth: Int, list: List[T]): (List[T], T) = list match {
case x::xs if nth == 0 => (xs, x)
case x::xs if nth > 0 =>
removeAt(nth - 1, xs) match { case (ys, y) => (x::ys, y) }
case _ => error("")
}
}実行例。
scala> import P11toP20._
import P11toP20._
scala> encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))
scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
res1: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
scala> encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res2: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
scala> duplicate(List('a, 'b, 'c, 'c, 'd))
res3: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)
scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
res4: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)
scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res5: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)
scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res6: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res7: List[Symbol] = List('d, 'e, 'f, 'g)
scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res8: 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))
res9: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)
scala> removeAt(1, List('a, 'b, 'c, 'd))
res10: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)追記：
nの絶対値がlength(list)より小さいことを仮定してしまっていたため、rotateの定義を修正。これで、以下のように動作するようになった。
scala> rotate(5, List('a, 'b, 'c))
res6: List[Symbol] = List('c, 'a, 'b)
