時間帯重複チェック（応用編）
お題：時間帯重複チェック（応用編） - No Programming, No Life を解く。*1
調べてみたら 区間木 - Wikipedia というものがあるみたいだが、手頃な感じではないので Groovy で力づくな方法で解くことにする。
class Time implements Comparable<Time> { int h, m Time(int h, int m) { this.h = h this.m = m } int compareTo(Time t) { h <=> t.h ?: m <=> t.m } } class Period { Time s, e Period(Time s, Time e) { this.s = s this.e = e } def and(Period p) { s < p.e && e > p.s ? new Period([s, p.s].max(), [e, p.e].min()) : null } def or(Period p) { s <= p.e && e >= p.s ? [new Period([s, p.s].min(), [e, p.e].max())] : [this, p] } @Override String toString() { "($s.h, $s.m, $e.h, $e.m)" } } def period(int h1, int m1, int h2, int m2) { def t1 = new Time(h1, m1) def t2 = new Time(h2, m2) assert t1 <= t2 new Period(t1, t2) } def combs(list, n) { if (n == 0 || n > list.size()) return [] if (n == 1) return list.collect { [it] } def (x, xs) = [list.head(), list.tail()] combs(xs, n-1).collect { [x, *it] } + combs(xs, n) } def overlaps(input) { def periods = input.collect { period(it) } def results = combs(periods, 2).collect { p1, p2 -> // 全組合せの重複期間を取得する p1 & p2 }.findAll { it != null }.sort { p1, p2 -> // 期間開始の昇順にソートする p1.s <=> p2.s }.inject([]) { acc, p -> // 重複または連続している重複期間をマージする if (acc.empty) acc += p else acc += acc.pop() | p } println "入力：${periods.join(', ')}" println "出力：${results.join(', ') ?: 'なし'}" } println "例1)" overlaps([[12, 0, 13, 0], [10, 0, 12, 15]]) println "例2)" overlaps([[16, 0, 23, 0], [9, 0, 17, 0], [5, 0, 10, 30]]) println "例3)" overlaps([[12, 0, 23, 0], [13, 0, 14, 0], [15, 0, 16, 0], [17, 0, 18, 0], [19, 0, 20, 0], [21, 0, 22, 0]]) println "例4)" overlaps([[10, 0, 12, 0], [11, 0, 11, 30], [10, 30, 11, 15]]) println "例5)" overlaps([[9, 0, 17, 0], [19, 0, 21, 0]])
最近、Haskell の本を見ながら Groovy で書いているのでその逆をやってみる。
Groovy のコードをそのまま Haskell に置き換える。*2
import Data.List type Period = (Int, Int, Int, Int) type Time = (Int, Int) combinations :: Int -> [a] -> [[a]] combinations 0 _ = [[]] combinations _ [] = [] combinations n (x:xs) = (map (x:) (combinations (n-1) xs)) ++ (combinations n xs) period :: Time -> Time -> Period period (h1, m1) (h2, m2) = (h1, m1, h2, m2) (-&-) :: Period -> Period -> Maybe Period (a1, b1, c1, d1) -&- (a2, b2, c2, d2) | (a1, b1) < (c2, d2) && (c1, d1) > (a2, b2) = Just (period (max (a1, b1) (a2, b2)) (min (c1, d1) (c2, d2))) | otherwise = Nothing (-|-) :: Period -> Period -> [Period] (a1, b1, c1, d1) -|- (a2, b2, c2, d2) | (a1, b1) <= (c2, d2) && (c1, d1) >= (a2, b2) = [period (min (a1, b1) (a2, b2)) (max (c1, d1) (c2, d2))] p1 -|- p2 = [p1, p2] overlapsPeriod :: [Period] -> Maybe Period overlapsPeriod (p1:p2:_) = p1 -&- p2 startAsc :: Maybe Period -> Maybe Period -> Ordering startAsc (Just (a1, b1, c1, d1)) (Just (a2, b2, c2, d2)) = compare (a1, b1) (a2, b2) overlapsOrFollowedBy :: [Period] -> Maybe Period -> [Period] overlapsOrFollowedBy [] (Just p) = [p] overlapsOrFollowedBy (p1:ps) (Just p2) = (p2 -|- p1) ++ ps onlyOverlaps :: Maybe Period -> Bool onlyOverlaps Nothing = False onlyOverlaps _ = True overlaps = reverse . foldl overlapsOrFollowedBy ([]) . sortBy startAsc . filter onlyOverlaps . map overlapsPeriod . combinations 2 ex1 :: [Period] ex1 = [(12, 0, 13, 0), (10, 0, 12, 15)] ex2 :: [Period] ex2 = [(16, 0, 23, 0), (9, 0, 17, 0), (5, 0, 10, 30)] ex3 :: [Period] ex3 = [(12, 0, 23, 0), (13, 0, 14, 0), (15, 0, 16, 0), (17, 0, 18, 0), (19, 0, 20, 0), (21, 0, 22, 0)] ex4 :: [Period] ex4 = [(10, 0, 12, 0), (11, 0, 11, 30), (10, 30, 11, 15)] ex5 :: [Period] ex5 = [(9, 0, 17, 0), (19, 0, 21, 0)]
実行形式では書けなかったが ghci で動作確認するところまで辿り着けた。
*Main> overlaps ex1 [(12,0,12,15)] *Main> overlaps ex2 [(9,0,10,30),(16,0,17,0)] *Main> overlaps ex3 [(13,0,14,0),(15,0,16,0),(17,0,18,0),(19,0,20,0),(21,0,22,0)] *Main> overlaps ex4 [(10,30,11,30)] *Main> overlaps ex5 []
