day25.rb


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