# Euler Solution 145

(Difference between revisions)
 Revision as of 06:27, 19 April 2009 (view source) (I don't know what you did when you ran it... :P)← Older edit Latest revision as of 12:31, 24 April 2010 (view source)Althalus (Talk | contribs) (→Solutions for Problem 145) Line 74: Line 74: 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. 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 + [[Category: Euler]] [[Category: Euler]]

# 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)?

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
```