スケジュールの重なりを判定する問題
以下のように、作業A と 作業B があり、 それぞれに、開始日、終了日のペアが与えられている場合に、この2つの作業のスケジュールが重なるか否かを判定する問題を考えます。
作業 | 開始日 | 終了日 |
A | 5/1 | 5/20 |
B | 4/1 | 5/3 |
解答
2つのスケジュールが 重ならない 場合というのは、以下の式になりますね。
終了日B < 開始日A ∨ 終了日A < 開始日B
よって、2つのスケジュールが重なる場合は、上の否定になります。これを 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
感想とか考察とか
このネタはずいぶん前に仕込んでいたのですが、これって何か意味あるのかなあ、と悩んでしまいまして。つまり、「解答」と「検証」の間に、何か本質的な違いがあるのかと。同じことの、単なる言い換えにすぎないようにも思えるのですよね。
しかしまあ、同じことを違う表現にしてみて、結果が同一になることを確かめる、というのは検証の本質ですかね。例えば、テストなんてのは、抽象化された形で表現されたプログラムに対し、具体的な入力出力の組で表現されたテストケースによって、プログラムの意図と、テストケースが一致するかを確かめるわけですしね。その意味では、上で行なっている検証というのは、具体的な値を使ったテストケースと、プログラムそのものとの中間表現にあたりますかね。
あまり便利という感じがしないのが残念ですが。結局、上のプログラムも検証も、”重なり”という概念の定義を確かめる以上のものではないわけでして、これ以上の簡単化はなさそうにも思えますね。
| 固定リンク
この記事へのコメントは終了しました。
コメント