Euler Solution 145

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 145

Define lr(n) to be the lexigraphical reversal of a number n, e.g. ln(135) = 531. A number n is reversible if n + lr(n) consists entirely of odd digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313.

How many reversible natural numbers are there below 109 (not counting leading zeros)?

Haskell by SanguineV

Runtime: niflheim is broken, but probably a lot.

{- Returns true if an integer is all odd digits -}
oddDigs :: Integer -> Bool
oddDigs n | n < 10 = mod n 2 == 1
oddDigs n = (mod (mod n 10) 2) == 1 && oddDigs (div n 10)

{- Takes a number and reverses it lexigraphically -}
rev :: Integer -> Integer -> Integer
rev n acc | n < 10 = n + (10 * acc)
rev n acc = rev (div n 10) ((mod n 10) + (10 * acc))

{- Returns true if a number is "reversible".
 - Note the special case to avoid potential leading 0's -}
isRev :: Integer -> Bool
isRev n | mod n 10 == 0 = False
isRev n = oddDigs (n + (rev n 0))

{- Start at 1000 and add 120 as this information is already
 - known and provided by the problem. -}
main = print (120 + length (filter isRev [1000..1000000000]))

C by SanguineV

Runtime: 58.85 seconds (on aglaope)

#include <stdio.h>

// Returns 1 if all the digits are odd (true in C speak).
int oddDecDig(unsigned long n) {
  int res = 1;
  while (res && n > 0) {
    res = (n%10)%2;
    n = n / 10;
  }
  return res;
}

// Do the lexigraphical reversal.
unsigned long lexRev(unsigned long n) {
  unsigned long res;
  res = n%10;
  n = n/10;
  while (n != 0) {
    res = (n%10) + (10 * res);
    n = n / 10;
  }
  return res;
}

int main(void) {
  // Initialise at known values
  unsigned long num = 1001;
  unsigned long count = 120;
  while(num < 1000000000) {
    // If the number does not end in 0 and is reversible then
    // increment the counter.
    if (num%10 != 0 && (oddDecDig(num + lexRev(num)))) {
      count++;
    }
    num++;
  }
  printf("Found %u reversible numbers\n",count);
  return 0;
}

Should be orders of magnitude faster than the Haskell solution above. There is also a mathematical solution that doesn't use brute force that will be orders of magnitude more efficient again.

Python by Althalus

Runtime: 184 minutes. After finding out that this gives the correct answer, I then implemented the equivalent of Thomas's C code in python - It was actually slower than this painful snail. I am well aware that C is much faster, but this is the first time I've seen that huge a discrepency between functionally identical code...

from time import time
start = time()

import re
regex = re.compile("^[13579]+$");

count = 0 
for x in xrange(1,10**9):
    if x % 100000 == 0: print x
    xs = str(x)
    if xs[-1] == "0": continue
    res = str(x+int(xs[::-1]))
    if regex.match(res):
            count += 1

print count
print time() - start
Personal tools