1
def debug(m)
2
puts m if ENV["DEBUG"]
3
end
4
5
def order_coords(f, t)
6
[[[f[0], t[0]].min,
7
[f[1], t[1]].min],
8
[[f[0], t[0]].max,
9
[f[1], t[1]].max]]
10
end
11
12
lines = File.readlines('9.input')
13
# lines = DATA.readlines
14
15
coords = lines.map { |l| l.strip.split(",").map(&:to_i) }
16
17
N = coords.length
18
19
combinations = N.times.flat_map do |a|
20
(a + 1).upto(N - 1).map do |b|
21
x1, y1 = coords[a]
22
x2, y2 = coords[b]
23
24
[a, b, ((x2 - x1).abs + 1) * ((y2 - y1).abs + 1)]
25
end
26
end.sort_by { |(_a, _b, size)| -size }
27
28
lines = []
29
N.times do |i|
30
lines << order_coords(coords[i-1], coords[i])
31
end
32
33
hlines, vlines = lines.partition { |f,t| f[1] == t[1] }
34
35
p combinations
36
.lazy
37
.reject { |(a, b, size)|
38
# Pick a point inside and check via raycast that it's actually within the polygon,
39
# then check that none of our connections pass within the coordinates.
40
41
(x1, y1), (x2, y2) = order_coords(coords[a], coords[b])
42
43
debug "Checking #{x1},#{y1} - #{x2},#{y2}"
44
45
mx = (x2 + x1) / 2
46
my = (y2 + y1) / 2
47
48
outside = true
49
50
# Every time we touch a vertical line, we move from inside to outside.
51
debug " Casting ray from 0,#{my} to #{mx},#{my}"
52
0.upto(mx) do |x|
53
if vlines.any? { |f,t| f[0] == x && my >= f[1] && my <= t[1] }
54
outside = !outside
55
debug " Moved #{outside ? "outside" : "inside"} at #{x},#{my}"
56
end
57
end
58
next true if outside
59
60
# The centre of the rectangle is within the polygon; check that it's
61
# uninterrupted by any line in the polygon.
62
63
cursed = false
64
65
hlines.each do |f, t|
66
debug " Checking hline #{f[0]},#{f[1]} - #{t[0]},#{t[1]}"
67
y = f[1]
68
next if y <= y1 || y >= y2
69
(f[0] + 1).upto(t[0] - 1) do |x|
70
if x >= x1 && x <= x2
71
cursed = true
72
break
73
end
74
end
75
break if cursed
76
end
77
78
next true if cursed
79
80
vlines.each do |f, t|
81
debug " Checking vline #{f[0]},#{f[1]} - #{t[0]},#{t[1]}"
82
x = f[0]
83
next if x <= x1 || x >= x2
84
(f[1] + 1).upto(t[1] - 1) do |y|
85
if y >= y1 && y <= y2
86
cursed = true
87
break
88
end
89
end
90
break if cursed
91
end
92
93
next true if cursed
94
95
false
96
}
97
.first
98
.last
99
100
__END__
101
7,1
102
11,1
103
11,7
104
9,7
105
9,5
106
2,5
107
2,3
108
7,3
109
