blob: 5b5160215b432341cd9d313cd5874c41a96dc243 (
plain) (
blame)
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
|
d = File.readlines("day25").map { |x| x.split(",").map(&:to_i) }
class DSU
def initialize(x)
@array = Array.new(x) {|i| i }
end
def find(x)
return x if @array[x] == x
@array[x] = find(@array[x])
end
def union(a, b)
@array[find(a)] = @array[find(b)]
end
def sets
@array.collect{ |i| find(i) }.uniq.length
end
end
dsu = DSU.new(d.size)
(0...d.size).each { |i|
(i+1...d.size).each { |j|
if d[i].zip(d[j]).map { |(a,b)| (a-b).abs }.sum <= 3
dsu.union(i, j)
end
}
}
p dsu.sets
|