add rest HEAD master

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