diff options
author | Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com> | 2020-12-25 15:29:50 +0100 |
---|---|---|
committer | Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com> | 2020-12-25 15:29:50 +0100 |
commit | 8c33b12b21f30724c6a6e3cc357facb7b0cc1b85 (patch) | |
tree | c8c041f16da4df5da34c791c527358537fba38fa /13/b.rb | |
parent | 13d928de6e5fb1bbc6a7e2daa10d28ecee982689 (diff) |
Add day 13
Diffstat (limited to '13/b.rb')
-rw-r--r-- | 13/b.rb | 35 |
1 files changed, 35 insertions, 0 deletions
@@ -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) |