The problem: Problem 145
Analysis
Suprisingly enough the brute-force solution works. It takes a couple of minutes but it gets the job done. Suppose we have a function called is_reversible then the following algorithm can be used to count all the reversible numbers below one-billion.
count = 0 for i = 1 upto 1000000000 do if (is_reversible(i)) then count++ endfor output count
Implementation
Uses the OCaml programming language.
(* a left fold over the digits of a positive integer *)
let rec nfoldl f v = function
0 -> v
| n -> nfoldl f (f v (n mod 10)) (n / 10)
let reverse = nfoldl (fun n d -> (n * 10) + d) 0
let odd n = n mod 2 = 1
let allodd = nfoldl (fun b d -> b && odd d) true
let is_reversible n =
n mod 10 <> 0 && allodd (n + reverse n)
let naive_count n =
let cnt = ref 0 in
for i = 1 to n-1 do
if is_reversible i then incr cnt;
done;
!cnt
The above code is elegant and it solves the problem but I’m not satisfied with its speed. In that regard I decided to improve on the algorithm a bit.
More Analysis
Notice that since the sum of a number, 
A Better Implementation
Uses the Haskell programming language. I switched languages when I realised that the list code I needed for this to work was not implemented using tail-recursion in the OCaml standard library. I did rewrite those pieces using tail recursion but in the end I still decided to switch languages just for the fun of it. Actually, the Haskell version below isn’t much better. Its still slow. But very elegant :D. At least I can use it for testing correctness on small cases since the solution is so simple and easy to read.
nfoldl _ v 0 = v
nfoldl f v n = nfoldl f (f v (n `mod` 10)) (n `div` 10)
nreverse = nfoldl (\n d -> (n * 10) + d) 0
allodd = nfoldl (\b d -> b && odd d) True
isReversible n = n `mod` 10 /= 0 && allodd (n + nreverse n)
countDigits = (+1) . floor . logBase 10 . fromIntegral
genCandidates n =
let gen m i len = if i > len then
if m >= n then [] else [m]
else
if i == 1 then
concatMap (\d -> gen (m*10+d) (i+1) len) [1,3,5,7,9]
else if i == len then
concatMap (\d -> gen (m*10+d) (i+1) len) [2,4,6,8]
else
concatMap (\d -> gen (m*10+d) (i+1) len) [0..9]
in concatMap (gen 0 1) [1..countDigits n]
betterCount = (*2) . length . (filter isReversible) . genCandidates
Finally, I bit my tongue and decided to code up a solution in everyone’s favorite system programming language, C.
#include <stdio.h>
#include <math.h>
#define FALSE 0
#define TRUE 1
#define even(n) ((n)%2==0)
int reverse(int n) {
int m = 0;
while (n > 0) { m = m*10 + (n%10); n /= 10; }
return m;
}
int allodd(int n) {
while (n > 0) {
if (even(n%10)) return FALSE;
n /= 10;
}
return TRUE;
}
#define is_reversible(n) ((n)%10>0 && allodd((n) + reverse(n)))
#define count_digits(n) ((int)(floor(log10(n) + 1)))
int __count;
void __better_count(int m, int i, int len, int n) {
int j;
if (i > len) {
if (m < n && is_reversible(m)) __count += 2;
} else {
if (i == 1) {
for (j = 1; j <= 9; j+=2) __better_count(m*10+j, i+1, len, n);
} else if (i == len) {
for (j = 2; j <= 8; j+=2) __better_count(m*10+j, i+1, len, n);
} else {
for (j = 0; j <= 9; j++) __better_count(m*10+j, i+1, len, n);
}
}
}
int better_count(int n) {
int len;
__count = 0;
for (len = 2; len <= count_digits(n); len++) __better_count(0, 1, len, n);
return __count;
}
int main(void) {
printf("%d\n", better_count(1000000000));
return 0;
}
In the end, the problem was easy and I had a lot of fun playing around with the various languages. I learned quite a lot, so it certainly wasn’t a waste of time.
