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, , and its reverse, must yield a number with all digits odd, it must be the case that 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 or . Now, , i.e. 200 million. Furthermore, if a number in is reversible then its reverse is in and is obviously reversible as well. This means we only need to generate the elements and count those in that are reversible. Our final answer must then be multiplied by to account for those in .

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.