diff options
Diffstat (limited to 'day25.rb')
-rw-r--r-- | day25.rb | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/day25.rb b/day25.rb new file mode 100644 index 0000000..5b51602 --- /dev/null +++ b/day25.rb @@ -0,0 +1,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 |