矩形を見つける問題
実例として見つけた問題というのが、「どう書く」で出題された中にある矩形を求める部分。
XY平面上にある複数の点のうち、矩形の頂点の位置なる 4 点 {(x1, y1), (x1, y2), (x2, y1), (x2, y2)} を見つけるというもの。
実際に矩形探しをさせてみます。x, y とも 10〜40 の値からなり重複しない点 200 個を用意して実験。
points([
[18, 34], [32, 14], [21, 23], [24, 29], [37, 20], [40, 28], [16, 30], [13, 33], [40, 37], [28, 23],
[30, 38], [23, 37], [29, 20], [34, 14], [25, 26], [12, 27], [10, 19], [30, 18], [13, 26], [18, 13],
[10, 32], [13, 16], [15, 19], [17, 14], [38, 30], [36, 22], [22, 38], [18, 22], [29, 12], [17, 36],
[20, 25], [27, 21], [21, 37], [33, 14], [28, 15], [15, 20], [37, 31], [37, 27], [20, 27], [24, 12],
[18, 21], [32, 19], [33, 19], [27, 18], [32, 39], [10, 36], [37, 19], [28, 16], [32, 32], [31, 12],
[36, 14], [19, 33], [15, 28], [35, 23], [27, 17], [26, 27], [22, 34], [24, 18], [13, 12], [31, 30],
[28, 14], [24, 31], [31, 25], [33, 23], [29, 16], [20, 35], [13, 35], [30, 40], [36, 25], [35, 25],
[11, 19], [26, 17], [37, 28], [10, 25], [20, 22], [35, 31], [20, 17], [31, 32], [33, 33], [35, 40],
[37, 22], [39, 40], [31, 21], [38, 29], [17, 34], [38, 13], [35, 24], [21, 38], [24, 39], [29, 30],
[35, 22], [25, 37], [14, 15], [13, 18], [17, 30], [24, 30], [12, 23], [10, 21], [33, 21], [13, 21],
[32, 28], [26, 31], [27, 31], [23, 11], [14, 21], [33, 34], [12, 28], [30, 16], [12, 18], [28, 25],
[23, 36], [10, 35], [27, 36], [15, 17], [37, 10], [37, 15], [24, 36], [26, 10], [11, 11], [23, 23],
[24, 14], [13, 10], [37, 24], [32, 30], [14, 26], [24, 25], [29, 39], [26, 18], [13, 20], [24, 28],
[11, 22], [16, 16], [27, 35], [16, 14], [15, 12], [17, 28], [25, 19], [33, 16], [24, 27], [32, 20],
[16, 18], [19, 17], [39, 12], [18, 27], [27, 15], [15, 27], [20, 15], [12, 20], [15, 16], [37, 33],
[33, 20], [12, 33], [16, 10], [22, 37], [24, 15], [13, 38], [37, 25], [17, 12], [18, 35], [29, 27],
[29, 24], [32, 13], [13, 31], [16, 39], [20, 14], [32, 38], [25, 17], [35, 15], [28, 21], [23, 39],
[34, 24], [17, 26], [32, 10], [33, 28], [13, 24], [29, 29], [28, 17], [14, 39], [20, 18], [13, 27],
[40, 20], [11, 14], [22, 18], [28, 13], [32, 12], [37, 40], [11, 37], [25, 35], [11, 31], [18, 16],
[19, 24], [29, 37], [34, 31], [26, 19], [34, 11], [37, 29], [20, 37], [24, 38], [35, 32], [30, 26]
]).
rect(X1, Y1, X2, Y2) :-
points(PS),
member([X1, Y1], PS),
member([X1, Y2], PS),
member([X2, Y1], PS),
member([X2, Y2], PS),
X1 < X2,
Y1 < Y2.
rects(RS) :-
findall([[X1, Y1], [X1, Y2], [X2, Y1], [X2, Y2]], rect(X1, Y1, X2, Y2), RS).
main :-
rects(RS),
length(RS, L),
format("~p~n~d~n", [RS, L]).
実行。
$ time gprolog --consult-file rect.pro --entry-goal 'main, halt'
[[[32,14],[32,19],[33,14],[33,19]], ... (略) ... ,[[24,38],[24,39],[32,38],[32,39]]]
450
real 0m0.351s
user 0m0.322s
sys 0m0.023s
すぐに答えが表示されたのには、正直驚きました。
任意の 4 点を取得して、矩形の頂点になるものを選べばよいというのなら、combination で 4 点を選び条件に合うものを選べばよいだろうと、愚直に書き直したものです。
200 個の点は同じ値です。
def points
[
[18, 34], [32, 14], [21, 23], [24, 29], [37, 20], [40, 28], [16, 30], [13, 33], [40, 37], [28, 23],
[30, 38], [23, 37], [29, 20], [34, 14], [25, 26], [12, 27], [10, 19], [30, 18], [13, 26], [18, 13],
[10, 32], [13, 16], [15, 19], [17, 14], [38, 30], [36, 22], [22, 38], [18, 22], [29, 12], [17, 36],
[20, 25], [27, 21], [21, 37], [33, 14], [28, 15], [15, 20], [37, 31], [37, 27], [20, 27], [24, 12],
[18, 21], [32, 19], [33, 19], [27, 18], [32, 39], [10, 36], [37, 19], [28, 16], [32, 32], [31, 12],
[36, 14], [19, 33], [15, 28], [35, 23], [27, 17], [26, 27], [22, 34], [24, 18], [13, 12], [31, 30],
[28, 14], [24, 31], [31, 25], [33, 23], [29, 16], [20, 35], [13, 35], [30, 40], [36, 25], [35, 25],
[11, 19], [26, 17], [37, 28], [10, 25], [20, 22], [35, 31], [20, 17], [31, 32], [33, 33], [35, 40],
[37, 22], [39, 40], [31, 21], [38, 29], [17, 34], [38, 13], [35, 24], [21, 38], [24, 39], [29, 30],
[35, 22], [25, 37], [14, 15], [13, 18], [17, 30], [24, 30], [12, 23], [10, 21], [33, 21], [13, 21],
[32, 28], [26, 31], [27, 31], [23, 11], [14, 21], [33, 34], [12, 28], [30, 16], [12, 18], [28, 25],
[23, 36], [10, 35], [27, 36], [15, 17], [37, 10], [37, 15], [24, 36], [26, 10], [11, 11], [23, 23],
[24, 14], [13, 10], [37, 24], [32, 30], [14, 26], [24, 25], [29, 39], [26, 18], [13, 20], [24, 28],
[11, 22], [16, 16], [27, 35], [16, 14], [15, 12], [17, 28], [25, 19], [33, 16], [24, 27], [32, 20],
[16, 18], [19, 17], [39, 12], [18, 27], [27, 15], [15, 27], [20, 15], [12, 20], [15, 16], [37, 33],
[33, 20], [12, 33], [16, 10], [22, 37], [24, 15], [13, 38], [37, 25], [17, 12], [18, 35], [29, 27],
[29, 24], [32, 13], [13, 31], [16, 39], [20, 14], [32, 38], [25, 17], [35, 15], [28, 21], [23, 39],
[34, 24], [17, 26], [32, 10], [33, 28], [13, 24], [29, 29], [28, 17], [14, 39], [20, 18], [13, 27],
[40, 20], [11, 14], [22, 18], [28, 13], [32, 12], [37, 40], [11, 37], [25, 35], [11, 31], [18, 16],
[19, 24], [29, 37], [34, 31], [26, 19], [34, 11], [37, 29], [20, 37], [24, 38], [35, 32], [30, 26]
]
end
def rects
points.sort.combination(4).select {|p1, p2, p3, p4|
p1[0] == p2[0] && p1[1] == p3[1] && p3[0] == p4[0] && p2[1] == p4[1]
}
end
rs = rects
puts rs.to_s
puts rs.size
実行。
$ time ruby rect1.rb
[[[10, 19], [10, 21], [33, 19], [33, 21]], ... (略) ... , [[37, 20], [37, 28], [40, 20], [40, 28]]]
450
real 0m22.360s
user 0m21.820s
sys 0m0.187s
それほど速くはないだろうと思いつつも、これほど数字になるとは思っていなかったので結構驚きでした。
当然、工夫すれば速くなります。
def points
[
]
end
def rects
points.group_by {|_, y| y }
.map {|y, ps| [y, ps.map(&:first).sort] }
.combination(2)
.map {|(y1, xs1), (y2, xs2)|
(xs1 & xs2).combination(2).map {|x1, x2|
[[x1, y1], [x1, y2], [x2, y1], [x2, y2]]
}
}.reject(&:empty?).flatten(1)
end
rs = rects
puts rs.to_s
puts rs.size
実行。
$ time ruby rect2.rb
[[[17, 34], [17, 14], [33, 34], [33, 14]], ... (略) ... , [[13, 24], [13, 10], [37, 24], [37, 10]]]
450
real 0m0.121s
user 0m0.074s
sys 0m0.041s
ずいぶん速くなります。しかし Prolog で愚直に書いた場合もこれの数倍程度の時間しかかからないということは、やはり驚きです。