A cool way to find out whether a number is palindromic
In this blog entry I proposed a solution to Problem 4 at Project Euler, a crucial element of the problem is to find out whether a number is a palindrome (909 is, 809 isn't), a bit out of laziness and a bit in order to reuse existing methods, I decided to verify the palindrome by converting the number into a char array and then comparing this array with its mirror version, it works but it's not really that mathematical... Dustin Campbell proposed a solution kind of similar to mine (alas, more elegant and, above that, in F#) and using the same trick of converting the number to chars, as he didn't like this part of the solution, in this new blog entry he proposes the detection of a palindrome by mirroring the number one digit at a time. A translation of his F# code to C# 3.0 could be:
1 Func<int, int, int> TailReverseNumber = null;
2 TailReverseNumber = (n, res) => n == 0 ? res : TailReverseNumber(n / 10, 10 * res + n % 10);
3
4 Func<int, bool> IsPalindrome = n => n == TailReverseNumber(n, 0);
TailReverseNumber takes a number n and "mirrors" it, one digit at a time, for example: TailReverseNumber(237, 0) -> TailReverseNumber(23, 7) -> TailReverseNumber(2, 73) -> TailReverseNumber(0, 732), the big trick is that res works as an accumulator that is multiplied by 10, therefore moving its value to the left, and putting in the "hole" that appears at the right the least significant digit of n. As it names implies, TailReverseNumber() uses tail recursion, so that no extra call stack space is used to save any intermediate results, which makes the process pretty efficient. Actually, in my PC it's four times faster than the initial solution. More efficient and more elegant, a smart guy Dustin.