1 files changed, 35 insertions, 0 deletions
diff --git a/13/b.rb b/13/b.rb
new file mode 100644
index 0000000..71b6a6f
--- /dev/null
+++ b/13/b.rb
@@ -0,0 +1,35 @@
+def extended_gcd(a, b)
+  last_remainder, remainder = a.abs, b.abs
+  x, last_x, y, last_y = 0, 1, 1, 0
+  while remainder != 0
+    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
+    x, last_x = last_x - quotient*x, x
+    y, last_y = last_y - quotient*y, y
+  end
+  return last_remainder, last_x * (a < 0 ? -1 : 1)
+end
+ 
+def invmod(e, et)
+  g, x = extended_gcd(e, et)
+  if g != 1
+    raise 'Multiplicative inverse modulo does not exist!'
+  end
+  x % et
+end
+ 
+def chinese_remainder(mods, remainders)
+  max = mods.inject( :* )  # product of all moduli
+  series = remainders.zip(mods).map{ |r,m| (r * max * invmod(max/m, m) / m) }
+  series.inject( :+ ) % max 
+end
+
+notes = File.readlines('input.txt')[1]
+ids = notes.split(',').each_with_index.filter_map do |id, i|
+  if id != 'x'
+    [id.to_i, -i % id.to_i]
+  end
+end
+
+moduli = ids.map {|m| m[0]}
+remainders = ids.map {|m| m[1]}
+puts chinese_remainder(moduli, remainders)