# Euler Solution 145

### From ProgSoc Wiki

(I don't know what you did when you ran it... :P) |
(→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]] |

## Latest revision as of 12:31, 24 April 2010

## 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 10^{9} (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