## Project Euler – Problem 145

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, $n$, and its reverse, $reverse(n)$ must yield a number with all digits odd, it must be the case that $n$ cannot begin and end with digits of the same parity (i.e. both even or both odd). Hence, a likely candidate must lie in one of these sets $A = \{n : n \,\text{begins with}\, 2, 4, 6, 8 \,\text{and}\, n \,\text{ends with}\, 1, 3, 5, 7, 9\}$ or $B = \{n : n \,\text{begins with}\, 1, 3, 5, 7, 9 \,\text{and}\, n \,\text{ends with}\, 2, 4, 6, 8\}$. Now, $|A| = |B| = (4*5)*10^7 = 200000000$, i.e. 200 million. Furthermore, if a number in $A$ is reversible then its reverse is in $B$ and is obviously reversible as well. This means we only need to generate the elements and count those in $A$ that are reversible. Our final answer must then be multiplied by $2$ to account for those in $B$.

### 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.

Tagged , , , , ,