This is the case of noTwos, and we've already dealt with the one case where a 3 can appear, so all the digits are either zero or one. So there's an obvious correspondence between these decimal palindromes and binary palindromes, pairing palindromes whose printable representations in their respective bases are equal.
Of course, n-digit binary numbers map exactly to the elements of the power set of a set of n elements, so we can represent our generated combinations (vide the function choices) as binary numbers. This is pretty tempting as an alternative to a [Int], but I don't want to iterate over all those bits to see which are set. After all, if we're just doing half of the palindrome, and we know the most significant digit has to be 1, that leaves at most three bits on.
Maybe we can use a trick: consider a number n of a type in the Bits class. What can we say about
n .&. (n - 1)?
Well, if n == 0, the result is zero; otherwise, n has some bits set, and one of them is the least-significant bit. n - 1 will have a zero in that position, and the more significant bits will be unchanged. The "and" gets rid of the trailing ones in case the least significant bit of n isn't in the ones position.
So, you can write an lsb function:
import Data.Bits
lsb :: (Bits a) => a -> a
lsb n = n `xor` (n .&. (n - 1))
and then peel the bits off one at a time. To do that, we shouldn't just give back the LSB, because we're generating the next value in the sequence while we're at it, so
bitStrip :: (Bits a) => a -> (a, a)
bitStrip n = (lsb, leftovers)
where leftovers = n .&. (n - 1)
lsb = n `xor` leftovers
and we can pull them off until we end up with zero...but we still have to map over to base 10; that lsb is 2^i for some i. I'm not sure whether the LSB trick will help any.
No comments:
Post a Comment