function rev(x) { local r = 0; while (x > 0) { r = r*10 + x%10; x /= 10; } return r; } function digits(x) { local arr = []; while (x > 0) { arr.append(x % 10); x /= 10; } return arr; } function isPalindrome(x) { local digs = digits(x); for (local i = 0; i < (digs.len() + 1) / 2; ++i) { if (digs[i] != digs[digs.len() - i - 1]) { return false; } } return true; } function isLycherel(x) { for (local i = 0; i < 50; ++i) { x += rev(x); if (x < 0) { return true; } if (isPalindrome(x)) { return false; } } return true; } local ans = 0; for (local i = 1; i < 10000; ++i) { if (isLycherel(i)) { ++ans; } } print(ans + "\n");
Thursday, October 17, 2013
Problem 55 - Squirrel
I have been using Squirrel a lot recently...it is a nice language, and it just happens that I seem to always use it in places where I choose to replace it very quickly. Anywhere, here is my latest squirrel problem. Problem 55 involves finding candidate lychrel numbers: A lychrel number is one which, if you repeatedly add the reverse of a number to itself, yields a palindrome. Now, no one has proved that any number is actually lychrel in base 10, however, there are many numbers which all the world's computing power has never been able to prove non-lychrel. This problem tasks one to find all such numbers under 10000, given that it will not take more than 50 iterations to reach a palindrome. Attempting to do this in Squirrel led to overflow in the 64-bit integers available....luckily, assuming that any number that could cause integer overflow was lychrel led to the correct result. Here is my code, runs in ~.166ms.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment