The Wandering Comets of Ulverholm
The star-readers of Ulverholm Observatory have posted a commission. Several comets cross the sky above the observatory, and each one returns on a fixed rhythm. The Guild of the Brass Astrolabe will pay a bounty to whoever names the first night on which every one of these comets burns overhead together, so that the great lens can be turned on all of them at once.
The comets are described by two lists of the same length:
periods[i]is a positive integer, the rhythm of cometi.offsets[i]is an integer with0 <= offsets[i] < periods[i].
Comet i is visible on night n exactly when the remainder of n divided by periods[i] equals offsets[i].
Nights are numbered from 1. Night 0 is never considered. limit is a non-negative integer, the last night the star-readers are willing to wait for.
Write firstConjunction(periods, offsets, limit). It returns the smallest integer n with 1 <= n <= limit on which every comet is visible. If no such night exists in that range, it returns -1.
There is always at least one comet, and the two lists always have the same length.
examples
- case 1
periods of [3, 5], offsets of [2, 4], limit of 10014, since 14 leaves remainder 2 when divided by 3 and remainder 4 when divided by 5, and no earlier night does both - case 2
periods of [4], offsets of [0], limit of 104, because night 0 is never counted - case 3
periods of [4, 6], offsets of [1, 2], limit of 100-1, because the first comet only shows on odd nights and the second only on even ones
- reward
- 220 XP
- signature
firstConjunction
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- two comets meet on night 14
- limit one short of the meeting
- limit exactly on the meeting night is inclusive
- offset zero skips night zero
- comets that can never align
- period one is visible every night
- limit of zero
- three comets
- all offsets zero
- periods sharing a factor