時間帯重複チェック（応用編）その3

quiz .hs .groovy

お題：時間帯重複チェック（応用編） - No Programming, No Life
Haskell で解答されていたのでそれを Groovy で書いてみる。


Control.Applicative モジュールの知識がないので読めない部分がある。
ghci に type コマンドがあることを思い出したのでとりあえず型を調べた。

Prelude> import Control.Applicative
Prelude Control.Applicative> :type ((,) <$> head <*> length)
((,) <$> head <*> length) :: [a] -> (a, Int)


直訳だが Applicative の部分は調べた型情報から想像した。

// Haskell の List 操作関数
class ListOps {
  // List#flatten は再帰的に処理される
  static def concat(List self) {
    self.inject([]) { acc, v -> acc + v }
  }

  static def group(List self) {
    self.inject([]) { acc, v ->
      acc && acc.last()[0] == v ? acc <<= acc.pop() << v :
                                  acc <<  [v]
    }
  }

  static def span(List self, Closure p) {
    def b = true
    def (fst, snd) = [[], []]
    self.each {
      b = b && p(it)
      b ? fst << it : snd << it
    }
    [fst, snd]
  }
}

def solve(input) {
  def divMod = { int o1, int o2 ->
    [o1.intdiv(o2), o1 % o2]
  }

  def conv = { int h1, int m1, int h2, int m2 ->
    (h1 * 60 + m1 .. h2 * 60 + m2).collect(divMod.rcurry(60))
  }

  // List のための compare
  def listAsc = { List l1, List l2, int i = 0 ->
    l1.size() < i && l2.size() < i ? 0 : l1[i] <=> l2[i] ?: call(l1, l2, i+1)
  }

  def parse = { List xs ->
    def (ys, zs) = xs.span { it[1] <= 1 }[1].span { 1 < it[1] }
    ys.empty       ? [] :
    ys.size() == 1 ? call(zs) :
                     [[*ys.head()[0], *ys.last()[0]], *call(zs)]
  }

  use (ListOps) {
    parse(input.collect(conv).concat().sort(listAsc).group().collect {
      [it.head(), it.size()]
    })
  }
}

def samples = [
  // 例1(出力：(12, 0, 12, 15))
  [[12, 0, 13, 0], [10, 0, 12, 15]],
  // 例2(出力：(9, 0, 10, 30), (16, 0, 17, 0))
  [[16, 0, 23, 0], [9, 0, 17, 0], [5, 0, 10, 30]],
  // 例3(出力：(13, 0, 14, 0), (15, 0, 16, 0), (17, 0, 18, 0), (19, 0, 20, 0), (21, 0, 22, 0))
  [[12, 0, 23, 0], [13, 0, 14, 0], [15, 0, 16, 0], [17, 0, 18, 0], [19, 0, 20, 0], [21, 0, 22, 0]],
  // 例4(出力：(10, 30, 11, 30))
  [[10, 0, 12, 0], [11, 0, 11, 30], [10, 30, 11, 15]],
  // 例5(出力：なし)
  [[9, 0, 17, 0], [19, 0, 21, 0]],
  // コーナケース1(出力：なし)
  [[1, 0, 2, 0], [2, 0, 3, 0]],
  // コーナケース2(出力：(1, 59, 2, 0))
  [[1, 0, 2, 0], [1, 59, 3, 0]],
  // コーナケース3(出力：(0, 0, 0, 1), (23, 59, 24, 0))
  [[0, 0, 24, 0], [0, 0, 0, 1], [23, 59, 24, 0]]
]

samples.each {
  println solve(it)
}

考え方は 前回 実装したものと同じだが、時間を1分単位に展開して重複の数を予め数えてあるので変数を受け渡す処理がない。

ViewPatterns？

コメントにあったので検索した結果だけ

Groovy での実装メモ

Haskell の List 操作関数

List 型のタプルの注意点

  • List の + 演算子は引数の型で add か addAll を切り替えるので << 演算子を使用する
  • 引数で渡す場合は展開されないように仮引数の型を List で宣言する

List の compare

  • Haskell では List や Tuple は 要素が比較できれば Comparable である
    • ghci の :info Ord で調べられる
  • クロージャでデフォルト引数が使えたので再帰的に定義した
    • List#getAt は index >= size の場合に null を返す
    • Groovy では null も比較可能である
groovy:000> null <=> 0
===> -1
groovy:000> 0 <=> null
===> 1
  • Groovy 1.8 の新機能である trampoline *1 を試してみた
  def listAsc = { List l1, List l2, int i = 0 ->
    l1.size() < i && l2.size() < i ? 0 : l1[i] <=> l2[i] ?: trampoline(l1, l2, i+1)
  }.trampoline()

例外を throw して stacktrace を見てみたが確かに違った。

関連エントリ

修正 2011/04/03

  • 例外を throw しているコードをアップしていたので修正
  • null と比較できることを書き忘れたので追記

*1:参考: Closure#trampoline()とは何か - uehaj's blog