Best Cow Line

quiz .hs

『プログラミングコンテストチャレンジブック』 から

N 文字の文字列 S が与えられ、N 文字の文字列 T を作ります。はじめは T は長さ 0 の文字列で、次のいずれかの操作が行えます。

  • S の先端を 1 文字削除し、T の末尾に追加する
  • S の末尾を 1 文字削除し、T の末尾に追加する

辞書順比較でできるだけ小さくなるように T を作ってください。


簡単だと思ったら、案の定 BBBABB のような場合に対応していなかった。
Haskell なので書籍とは違うロジックで、Arrow の練習も兼ねる。

import Control.Arrow
import Test.HUnit


solve :: (Ord a) => [a] -> [a]
solve []  = []
solve xs = merge . (head &&& last) $ xs
  where merge (h,l)
          | h < l = h:(solve $ tail xs)
          | h > l = l:(solve $ init xs)
          | h == l && xs < (reverse xs) = h:(solve $ tail xs)
          | otherwise                   = l:(solve $ init xs)


solve' :: (Ord a) => [a] -> [a]
solve' xs = merge . (id *** reverse) . splitAt n $ xs
  where n = length xs `div` 2
        merge (l, []) = solve l
        merge ([], l) = solve l
        merge (l1@(x:xs), l2@(y:ys))
          | l1 <= l2 = x: (merge (xs, l2))
          | l1 >  l2 = y: (merge (l1, ys))


solve'' :: (Ord a) => [a] -> [a]
solve'' = merge . (length &&& (id &&& reverse))
  where merge (0, _) = []
        merge (n, (l1@(x:xs), l2@(y:ys)))
          | l1 <= l2 = x:(merge (n-1, (xs, l2)))
          | l1 >  l2 = y:(merge (n-1, (l1, ys)))


testSolve = runTestTT $ test [
  "ABCBCD" ~=? solve "ACDBCB",
  "BBABBB" ~=? solve "BBBABB",
  "CCXAXX" ~=? solve "CCXXAX",
  "ABCBCD" ~=? solve' "ACDBCB",
  "BBABBB" ~=? solve' "BBBABB",
--  "CCXAXX" ~=? solve' "CCXXAX", failure
  "ABCBCD" ~=? solve'' "ACDBCB",
  "BBABBB" ~=? solve'' "BBBABB",
  "CCXAXX" ~=? solve'' "CCXXAX"]
  • solve
    • tail と init も &&& で生成していたが毎回両方とも必要になるわけではないので head と last だけにした
  • solve'
    • 最初に分割しておけば reverse の負担も半分になると思ったがバグってしまった
  • solve''
    • reverse を最初の1回だけにする
    • n は必要な長さ
    • Haskell も代入できないだけで引数を変数代わりに使っていけばよいのかな

2011-07-19 追記

id:akihiro4chawon 氏がO(n)のアルゴリズムで実装されているのでそれを Groovy で

// https://gist.github.com/997704 を参考
// 毎回先頭から比較しないでまだ比較していない文字で比較する
// O(n)
def solve3(s) {
  def sb = new StringBuilder(s.size())
  def merge = { n, l, r, i=0 ->
    if (n == 0) return
    if (n <= i) {
      sb << l[0..<n]
    } else if (l[i] < r[i]) {
      sb << l[0..i]
      call(n-i-1, l[i+1..<n], r)
    } else if (l[i] > r[i]) {
      sb << r[0..i]
      call(n-i-1, l, r[i+1..<n])
    } else if (i > 0 && l[i-1] < l[i]) {
      // 文字が大きくなればそれまでの文字は確定する
      sb << l[0..<i] << r[0..<i]
      call(n-i*2, l[i..<n], r[i..<n])
    } else {
      call(n, l, r, i+1)
    }
  }
  merge(s.size(), s, s.reverse())
  sb as String
}

assert "ABCBCD" == solve3("ACDBCB")
assert "BBABBB" == solve3("BBBABB")
assert "AABBBC" == solve3("ABBCBA")