Created
April 4, 2020 14:30
-
-
Save Driim/23b5584e6f7158eb9716d38c81281fb3 to your computer and use it in GitHub Desktop.
The solution of the numbers problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const fs = require('fs'); | |
| const readline = require('readline'); | |
| const PRECISION = 60; | |
| /* see https://en.wikipedia.org/wiki/Parasitic_number */ | |
| function getSmallestParasiticNumber(n, k) { | |
| if (n > k) { | |
| return '0'; | |
| } | |
| if (n > 9 || k > 9) { | |
| throw new Error('Args should be smaller then or equal 9'); | |
| } | |
| const number = 10 * Number(n) - 1; | |
| const primes = primeFactors(number); | |
| for (const prime of primes) { | |
| if (prime !== 2 && prime !== 5) { | |
| return getNumber(k, number); | |
| } | |
| } | |
| } | |
| function isPrime(num) { | |
| for (let i = 2; i <= Math.sqrt(num); i++) { | |
| return num % i !== 0 ? true : false; | |
| } | |
| } | |
| function primeFactors(num) { | |
| const result = new Set(); | |
| for (let i = 2; i <= num; i++) { | |
| while (isPrime(i) && num % i === 0) { | |
| result.add(i); // using set, so no duplicates | |
| num = Math.floor(num / i); | |
| } | |
| } | |
| return result; | |
| } | |
| function getNumber(k, d) { | |
| const number = []; | |
| const storage = new Map(); | |
| let n = k; | |
| for (var i = 0; i < PRECISION; i++) { | |
| if (storage.has(n)) { | |
| return number.slice(storage.get(n)).join(''); | |
| } | |
| storage.set(n, i); | |
| number.push(Math.floor(n / d)); | |
| n = n % d * 10; | |
| } | |
| } | |
| function run() { | |
| const args = process.argv.slice(2); | |
| switch (args[0]) { | |
| case 'file': { | |
| const file = args[1]; | |
| if (!file) { | |
| throw new Error('need file'); | |
| } | |
| const fileStream = fs.createReadStream(file); | |
| const lines = readline.createInterface({ | |
| input: fileStream, | |
| crlfDelay: Infinity | |
| }); | |
| let skipFirst = true; | |
| lines.on('line', (line) => { | |
| if (skipFirst) { | |
| skipFirst = false; | |
| return; | |
| } | |
| const nums = line.split(' '); | |
| if (nums.length !== 2) { | |
| throw new Error('Each line must contain 2 numbers'); | |
| } | |
| console.log(getSmallestParasiticNumber(parseInt(nums[0]), parseInt(nums[1]))); | |
| }); | |
| break; | |
| } | |
| case 'test': { | |
| /* | |
| * I decided not to use assert, instead I made the tests more visual. | |
| */ | |
| console.log(`getSmallestParasiticNumber(1, 0) = ${getSmallestParasiticNumber(1, 0)} should be 0`); | |
| console.log(`getSmallestParasiticNumber(1, 1) = ${getSmallestParasiticNumber(1, 1)} should be 1`); | |
| console.log(`getSmallestParasiticNumber(2, 2) = ${getSmallestParasiticNumber(2, 2)} should be 105263157894736842`); | |
| console.log(`getSmallestParasiticNumber(6, 6) = ${getSmallestParasiticNumber(6, 6)} should be 1016949152542372881355932203389830508474576271186440677966`); | |
| console.log(`getSmallestParasiticNumber(4, 5) = ${getSmallestParasiticNumber(9, 9)} should be 10112359550561797752808988764044943820224719`); | |
| break; | |
| } | |
| default: { | |
| throw new Error('You should call: "node number.js test" or "node number.js file <filename>"'); | |
| } | |
| } | |
| } | |
| run(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment