Published
Edited
Dec 13, 2020
1 fork
1 star
Insert cell
Insert cell
lines = input.trim().split('\n')
Insert cell
estimate = +lines[0]
Insert cell
ids = lines[1].split(',').filter(d => d !== 'x').map(Number)
Insert cell
function* times(id, start = 0) {
if (start % id !== 0)
start = Math.floor(start / id) * id
let t = start
while (true) {
yield t += id
}
}
Insert cell
function earliestAfter(estimate, id) {
for (const t of times(id))
if (t > estimate)
return t
}
Insert cell
earliest = ids.map(id => [earliestAfter(estimate, id), id]).sort((a, b) => a[0] - b[0])
Insert cell
part1 = (earliest[0][0] - estimate) * earliest[0][1]
Insert cell
constraints = lines[1].split(',').map(n => n === 'x' ? null : +n)
Insert cell
ordered = constraints
.map((id, i) => [id, i])
.filter(([id, i]) => id)
.sort((a, b) => b[0] - a[0])
Insert cell
part2 = {
const congruences = ordered.map(([id, d]) => [id - d, id])
const a = congruences.map(d => BigInt(d[0]))
const b = congruences.map(d => BigInt(d[1]))
return chineseRemainder(a, b)
}
Insert cell
function check(t) {
for (const [id, d] of ordered)
if ((t + d) % id !== 0)
return false
return true
}
Insert cell
// part2bad = {
// const [largest, d] = ordered[0]
// for (const t of times(largest)) {
// // if (t % 1e6 === 0) yield t
// if (check(t - d))
// return t - d
// }
// }
Insert cell
// From https://raw.githubusercontent.com/pnicorelli/nodejs-chinese-remainder/master/chinese_remainder.js
/**
* Base on http://rosettacode.org/wiki/Chinese_remainder_theorem (python implementation)
* solve a system of linear congruences by applying the Chinese Remainder Theorem
*
* X = a1 (mod n1)
* X = a2 (mod n2)
*
* This function will be called as:
*
* chineseRemainder([a1, a2], [n1, n2])
* @return {integer}
*/
function mul_inv(a, b){
let b0 = b;
let x0 = 0n;
let x1 = 1n;
let q, tmp;
if (b == 1)
return 1

while (a>1){
q = a/b;
tmp = a;
a = b;
b = tmp%b;
tmp = x0;
x0 = x1 - (q * x0);
x1 = tmp;
}
if(x1 <0){
x1 = x1+b0;
}
return x1;
}
Insert cell
function chineseRemainder(as, ns){
let prod = 1n;
for (const n of ns)
prod *= n;

let p = 1n;
let sm = 0n;
for (let i=0; i < ns.length; i++) {
p = prod / ns[i];
sm = sm + (as[i] * mul_inv(p, ns[i]) * p);
}

return sm % prod;
}
Insert cell
chineseRemainder([19n-3n,0n,13n-2n], [19n,17n,13n])
Insert cell
sample = `939
67,x,7,59,61`
Insert cell
input = `1006605
19,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,883,x,x,x,x,x,x,x,23,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,x,x,797,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29`
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more