Last active
February 27, 2018 20:40
-
-
Save queerviolet/ccd7b21e5032ba47f0bf64b4c80866b7 to your computer and use it in GitHub Desktop.
Floyd's cycle finder applied to happy numbers, in JS.
This file contains 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
/** | |
* Exports an Object like {1: 1, 7: 7, 10: 10, ...}, | |
* containing happy numbers up to 1000. | |
* | |
* This makes it easy for the test to check whether a given | |
* number is happy. | |
*/ | |
module.exports = Object.assign( | |
...[ | |
1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, 103, 109, 129, 130, 133, 139, 167, 176, 188, 190, 192, 193, 203, 208, 219, 226, 230, 236, 239, 262, 263, 280, 291, 293, 301, 302, 310, 313, 319, 320, 326, 329, 331, 338, 356, 362, 365, 367, 368, 376, 379, 383, 386, 391, 392, 397, 404, 409, 440, 446, 464, 469, 478, 487, 490, 496, 536, 556, 563, 565, 566, 608, 617, 622, 623, 632, 635, 637, 638, 644, 649, 653, 655, 656, 665, 671, 673, 680, 683, 694, 700, 709, 716, 736, 739, 748, 761, 763, 784, 790, 793, 802, 806, 818, 820, 833, 836, 847, 860, 863, 874, 881, 888, 899, 901, 904, 907, 910, 912, 913, 921, 923, 931, 932, 937, 940, 946, 964, 970, 973, 989, 998, 1000 | |
].map(n => ({[n]: n})) | |
) |
This file contains 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
// Floyd's cycle finder, applied to happy numbers. | |
const isHappy = t => { | |
let h = t // 🐢 and 🐇 start at the same place | |
while (h !== 1) { | |
t = tickle(t) // 🐢 moves 1 | |
h = tickle(tickle(h)) // 🐇 hops 2 | |
// If they're in the same place, and that place | |
// isn't the end, we've found a cycle. | |
if (t !== 1 && t === h) | |
return false | |
} | |
return true | |
} | |
// Split e.g. 154 into ['1', '5', '4'] by | |
// spreading the string into an array. | |
const tickle = n => [...String(n)] | |
// Reduce to the sum of the digits, squared. | |
// (this works because in JS, '2' * '2' = 4). | |
.reduce((next, n) => next + n * n, 0) | |
module.exports = {isHappy, tickle} |
This file contains 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 {isHappy, tickle} = require('./happy') | |
const assert = require('assert') | |
// Check that tickle generates the sequence for 19. | |
const seq = [19, 82, 68, 100, 1, 1] | |
for (let i = 0; i < seq.length - 1; ++i) { | |
assert.equal(tickle(seq[i]), seq[i + 1]) | |
} | |
const happy = require('./happy-numbers') | |
for (let n = 0; n <= 1000; ++n) { | |
assert.equal(isHappy(n), !!happy[n]) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment