Skip to content

Instantly share code, notes, and snippets.

@queerviolet
Last active February 27, 2018 20:40
Show Gist options
  • Save queerviolet/ccd7b21e5032ba47f0bf64b4c80866b7 to your computer and use it in GitHub Desktop.
Save queerviolet/ccd7b21e5032ba47f0bf64b4c80866b7 to your computer and use it in GitHub Desktop.
Floyd's cycle finder applied to happy numbers, in JS.
/**
* 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}))
)
// 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}
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