m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2020-12-25 15:29:50 +0100
committerMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2020-12-25 15:29:50 +0100
commit8c33b12b21f30724c6a6e3cc357facb7b0cc1b85 (patch)
treec8c041f16da4df5da34c791c527358537fba38fa
parent13d928de6e5fb1bbc6a7e2daa10d28ecee982689 (diff)
Add day 13
-rw-r--r--13/a.rb19
-rw-r--r--13/b.rb35
-rw-r--r--13/input.txt2
3 files changed, 56 insertions, 0 deletions
diff --git a/13/a.rb b/13/a.rb
new file mode 100644
index 0000000..ebadaf0
--- /dev/null
+++ b/13/a.rb
@@ -0,0 +1,19 @@
+earliest, notes = File.readlines('input.txt')
+earliest = earliest.to_i
+ids = notes.split(',').filter_map do |id|
+ if id != 'x'
+ id.to_i
+ end
+end
+
+best_wait = ids.max + 1
+best_id = 0
+ids.each do |id|
+ wait = id - (earliest % id)
+ if wait < best_wait
+ best_wait = wait
+ best_id = id
+ end
+end
+
+puts best_wait * best_id
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)
diff --git a/13/input.txt b/13/input.txt
new file mode 100644
index 0000000..096e2cc
--- /dev/null
+++ b/13/input.txt
@@ -0,0 +1,2 @@
+1002618
+19,x,x,x,x,x,x,x,x,41,x,x,x,37,x,x,x,x,x,367,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,373,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,23