1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#!/usr/bin/env ruby
input = $stdin.readlines.map(&:strip).map(&:chars)
.map{ |l| l.map{ |c| c == "#" } }
H = input.length
W = input[0].length
def count(grid, x, y, angles)
c = 0
angles.each do |dx, dy|
tx = x
ty = y
loop do
tx += dx
ty += dy
break if tx < 0 || tx >= W
break if ty < 0 || ty >= H
if grid[ty][tx] then
c += 1
break
end
end
end
c
end
def rotate(n, arr)
arr.map do |x, y|
case n
when 1
[-y, x]
when 2
[-x, -y]
when 3
[y, -x]
end
end
end
def coords_of(n, grid, x, y, angles)
c = 0
loop do
tx = x
ty = y
angles.each do |dx, dy|
s = 1
loop do
tx = x + s*dx
ty = y + s*dy
break if tx < 0 || tx >= W
break if ty < 0 || ty >= H
if grid[ty][tx] then
c += 1
return [tx, ty] if c == 200
break
else
s += 1
end
end
end
end
end
angles = []
(0...W).each do |x|
(0...H).each do |y|
angles << [x, -y] if x.gcd(y) == 1
end
end
angles.sort! do |a,b|
b[0].to_f/b[1] <=> a[0].to_f/a[1]
end
angles.shift
angles = angles +
rotate(1, angles) +
rotate(2, angles) +
rotate(3, angles)
maxcount = 0
stationx = nil
stationy = nil
(0...H).each do |y|
(0...W).each do |x|
if input[y][x] then
c = count(input, x, y, angles)
if c > maxcount
maxcount = c
stationx = x
stationy = y
end
end
end
end
asteroid200 = coords_of(200, input, stationx, stationy, angles)
puts (100 * asteroid200[0]) + asteroid200[1]
|
