スケジュールの重なりを判定する問題

以下のように、作業A と 作業B があり、 それぞれに、開始日、終了日のペアが与えられている場合に、この２つの作業のスケジュールが重なるか否かを判定する問題を考えます。

作業	開始日	終了日
A	5/1	5/20
B	4/1	5/3

解答

２つのスケジュールが 重ならない 場合というのは、以下の式になりますね。

終了日B < 開始日A ∨ 終了日A < 開始日B

よって、２つのスケジュールが重なる場合は、上の否定になります。これを Ruby で書いたものが以下です。

def overlapped?(x1, x2, y1, y2)
  not (y2 < x1 or x2 < y1)
end

Aの 開始日, 終了日 を、 x1, x2 、 Bの 開始日, 終了日 を y1, y2 としています。

検証

以前、以下のエントリで作成しました、Rubyスクリプトを使用します。

順序関係列挙と事前条件

まずは、今回の問題で起こり得る論理式を、すべて列挙してみます。

irb(main):021:0> i = 0; apply_cond(gen_norder([:x1, :x2, :y1, :y2]), [:x1, :x2,:y1, :y2], ['x1<=x2', 'y1<=y2']).each {|v| print("#{i += 1}:"); p v }; nil
1:[:x1, :x2, :y1, :y2]
2:[:x1, :y1, :x2, :y2]
3:[:x1, :y1, :y2, :x2]
4:[:y1, :x1, :x2, :y2]
5:[:y1, :x1, :y2, :x2]
6:[:y1, :y2, :x1, :x2]
7:[[:x1, :x2], :y1, :y2]
8:[:y1, [:x1, :x2], :y2]
9:[:y1, :y2, [:x1, :x2]]
10:[[:x1, :y1], :x2, :y2]
11:[[:x1, :y1], :y2, :x2]
12:[:y1, [:x1, :y2], :x2]
13:[:x1, [:x2, :y1], :y2]
14:[:x1, :y1, [:x2, :y2]]
15:[:y1, :x1, [:x2, :y2]]
16:[[:y1, :y2], :x1, :x2]
17:[:x1, [:y1, :y2], :x2]
18:[:x1, :x2, [:y1, :y2]]
19:[[:x1, :x2, :y1], :y2]
20:[:y1, [:x1, :x2, :y2]]
21:[[:x1, :y1, :y2], :x2]
22:[:x1, [:x2, :y1, :y2]]
23:[[:x1, :x2, :y1, :y2]]
=> nil

全部で23個ありますね。

上の論理式で表される、各々のケースについて、 overlapped? を評価した結果を付与したいと思います。

def gen_implication(src_a, cond_a)
  res_a = []
  src_a.each do |exp|
    res_a.push([exp, cond?(exp, cond_a)])
  end
  res_a
end

ついでに、シンボルの配列として表現されている論理式を、文字列に変換するメソッドも用意しておきます。

def print_exp(exp)
  res = ''
  exp.each do |term|
    res += ' < ' if res != ''
    if term.instance_of?(Array)
      res += "#{term.join(' = ')}"
    else
      res += "#{term}"
    end
  end
  res
end

以下を実行して、評価結果を得ます。

irb(main):022:0> i = 0; gen_implication(apply_cond(gen_norder([:x1, :x2, :y1, :y2]), [:x1, :x2, :y1, :y2], ['x1<=x2', 'y1<=y2']), ['overlapped?(x1, x2, y1, y2)']).each {|v| puts "#{i += 1} : #{print_exp(v[0])} : #{v[1]}" }; nil
1 : x1 < x2 < y1 < y2 : false
2 : x1 < y1 < x2 < y2 : true
3 : x1 < y1 < y2 < x2 : true
4 : y1 < x1 < x2 < y2 : true
5 : y1 < x1 < y2 < x2 : true
6 : y1 < y2 < x1 < x2 : false
7 : x1 = x2 < y1 < y2 : false
8 : y1 < x1 = x2 < y2 : true
9 : y1 < y2 < x1 = x2 : false
10 : x1 = y1 < x2 < y2 : true
11 : x1 = y1 < y2 < x2 : true
12 : y1 < x1 = y2 < x2 : true
13 : x1 < x2 = y1 < y2 : true
14 : x1 < y1 < x2 = y2 : true
15 : y1 < x1 < x2 = y2 : true
16 : y1 = y2 < x1 < x2 : false
17 : x1 < y1 = y2 < x2 : true
18 : x1 < x2 < y1 = y2 : false
19 : x1 = x2 = y1 < y2 : true
20 : y1 < x1 = x2 = y2 : true
21 : x1 = y1 = y2 < x2 : true
22 : x1 < x2 = y1 = y2 : true
23 : x1 = x2 = y1 = y2 : true
=> nil

感想とか考察とか

このネタはずいぶん前に仕込んでいたのですが、これって何か意味あるのかなあ、と悩んでしまいまして。つまり、「解答」と「検証」の間に、何か本質的な違いがあるのかと。同じことの、単なる言い換えにすぎないようにも思えるのですよね。

しかしまあ、同じことを違う表現にしてみて、結果が同一になることを確かめる、というのは検証の本質ですかね。例えば、テストなんてのは、抽象化された形で表現されたプログラムに対し、具体的な入力出力の組で表現されたテストケースによって、プログラムの意図と、テストケースが一致するかを確かめるわけですしね。その意味では、上で行なっている検証というのは、具体的な値を使ったテストケースと、プログラムそのものとの中間表現にあたりますかね。

あまり便利という感じがしないのが残念ですが。結局、上のプログラムも検証も、”重なり”という概念の定義を確かめる以上のものではないわけでして、これ以上の簡単化はなさそうにも思えますね。