Best Cow Line

best_cow_line.hs

module Main where

import Control.Applicative

-- inspired from deve68's implementation
-- <http://d.hatena.ne.jp/deve68/20110527/1306508915>
solve'''' :: (Ord a) => [a] -> [a]
solve'''' = take <$> length <*> (merge <$> id <*> reverse)
  where merge l1@(x:xs) l2@(y:ys)
          | l1 <= l2  = x : (merge xs l2)
          | otherwise = y : (merge l1 ys)

-- yet another implementation (worst-case performance of O(n))
solveON :: (Ord a) => [a] -> [a]
solveON = take <$> length <*> (merge <$> id <*> reverse)
  where
    merge lhs@(x:xs) rhs@(y:ys) = case x `compare` y of
      LT -> x : merge xs rhs
      GT -> y : merge lhs ys
      EQ -> x : mergeSub xs ys lhs rhs x
    mergeSub lhs@(x:xs) rhs@(y:ys) l r o
      | x < y = merge lhs r
      | x > y = merge l rhs
      | x > o = (takeWhile (y >) r) ++ (merge lhs rhs)
      | otherwise = x : mergeSub xs ys l r (min x o)

best_cow_line.scala

object Main {
  // リファレンス用の naive な実装：O(exp(n))
  def solveRef(str: String): String =
    if (str.isEmpty) ""
    else {
      val l = str.head + solveRef(str.tail)
      val r = str.last + solveRef(str.init)
      if (l <= r) l else r
    }
  
  // アリ本実装：最悪時 O(n^2)
  def solveAri(str: String): String = {
    var a = 0
    var b = str.length - 1
    
    def isLeft: Boolean = {
      var i = 0; while (a + i <= b) {
        if      (str(a + i) < str(b - i)) return true
        else if (str(a + i) > str(b - i)) return false
        i += 1
      }
      false
    }
    
    val ret = new StringBuilder(str.length)
    while (a <= b) {
      if (isLeft) { ret += str(a); a += 1 }
      else        { ret += str(b); b -= 1 }
    }
    ret.toString
  }
  
  // O(N)にした実装
  def solveOn(str: String) = {
    import scalaz._
    import scalaz.Scalaz._
    def merge(lhs: List[Char], rhs: List[Char]): Stream[Char] = {
      val x :: xs = lhs
      val y :: ys = rhs
      implicitly[Order[Char]].order(x, y) match {
        case LT => x #:: merge(xs, rhs)
        case GT => y #:: merge(lhs, ys)
        case EQ => x #:: mergeSub(xs, ys, lhs, rhs, x)
      }
    }
    def mergeSub(lhs: List[Char], rhs: List[Char],
        l: List[Char], r: List[Char], o: Char): Stream[Char] = {
      val x :: xs = lhs
      val y :: ys = rhs
      if      (x < y) merge(lhs, r)
      else if (x > y) merge(l, rhs)
      else if (x > o) r.takeWhile(_ < y).toStream #::: merge(lhs, rhs)
      else            x #:: mergeSub(xs, ys, l, r, x min o)
    }
    if (str.isEmpty) ""
    else merge(str.toList, str.reverse.toList).take(str.length).mkString
  }
  
  def main(args: Array[String]) {
    import org.scalacheck.{Gen, Prop, Test}
    
    Prop.forAll(Gen.alphaStr)((s: String) => solveRef(s) == solveAri(s)).check(Test.Params(maxSize = 12))
    Prop.forAll(Gen.alphaStr)((s: String) => solveAri(s) == solveOn(s)).check
    
    benchmark(solveRef _ -> 15, solveAri _ -> 200, solveOn _ -> 1000)
  }
  
  def benchmark(funcAndMaxLen: ((String => String), Int)*) {
    val result = for {
      (f, maxlen) <- funcAndMaxLen
    } yield for {
      len <- 1 to maxlen
    } yield {
      val arg = "A" * len
      val tims = for (_ <- 1 to 10) yield {
        val t = System.nanoTime
        f(arg)
        System.nanoTime - t
      }
      val ok = tims.sorted.drop(2).dropRight(2)
      ok.sum / ok.size
    }
    println("," + (funcAndMaxLen map {_._1} mkString ","))
    for (idx <- 0 to result.map{_.length}.max) {
      println((idx+1).toString +: (result map {_ lift idx getOrElse ""}) mkString ",")
    }
  }
}