i tried changing from String to StringBuilder, but it is still very slow. any help or observation appreciated.

line 23 looks especially suspect, but i don't see any other way.

the new code:

the previous code:

SCJP

Visit my download page

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (109)?

SCJP

Visit my download page

Randall Twede wrote:i tried changing from String to StringBuilder, but it is still very slow. any help or observation appreciated.

Personally, I wouldn't use either. What about breaking up each number into a List (or array) of

`int`digits?

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

SCJP

Visit my download page

Personally, I wouldn't use either. What about breaking up each number into a List (or array) of int digits?

that sounds good to me i didn't like changing back and forth in the first place. i have no idea how though

primitives don't have a charAt() method. i could get rid of strings by using Integer class i guess.

SCJP

Visit my download page

Randall Twede wrote:

Personally, I wouldn't use either. What about breaking up each number into a List (or array) of int digits?

that sounds good to me i didn't like changing back and forth in the first place. i have no idea how though

primitives don't have a charAt() method.

They can bet turned into Strings though, and String has a charAt() method. And there are ways to turn that char into an int.

There's also division and modulo math to extract digits.

i found i had a lot of fat to trim. my latest has only 2 StringBuilders, and 1 Integer. a small improvement anyway

it takes about 2 minutes to find answer for 100,000,000 1 billion will hopefully only take 10 times as long.

i am going to start it now since i can only stay at McDonalds for sooo long

SCJP

Visit my download page

- 1

Randall Twede wrote:i have also been thinking about modulo math as a last resort.

Why as a last resort? For one thing, it breaks your number up into

*numeric*digits rather than characters; for another, it naturally delivers those digits

*in reverse order*.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

a= x % 10

b = x % 100

c = x % 1000

d = x % 10000

e = x % 100000

f = x % 1000000

g = x % 10000000

h = x % 100000000

SCJP

Visit my download page

i cant stay at McDonalds for another half hour or more

oh even worse. i did change it. the answer looked like the same from 100,000,000 so i closed it and assumed i made a mistake

im gonna go drink a beer now and run my battery into the ground getting the answer again

SCJP

Visit my download page

Randall Twede wrote:could you imagine...

a= x % 10

b = x % 100

c = x % 1000

d = x % 10000

e = x % 100000

f = x % 1000000

g = x % 10000000

h = x % 100000000

I can, but I'd rather imagine an array or a List and repeated multiplication and/or division.

When there's such as obvious pattern as that, it cries out for a loop, rather than repeating the same code over and over.

__and__<= 1000000000 ]) and there may well be quicker methods.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Martin Vajsar wrote:What about creating a lookup table for numbers below 1000 and doing it three digits at a time?

Not sure about the lookup, but I

*do*like the idea of tackling the digits in groups of 3. Gold star from me.

Winston

Articles by Winston can be found here

SCJP

Visit my download page

SCJP

Visit my download page

Randall Twede wrote:i finally let it run long enough and got the correct answer. i am still keeping in mind what Winston wrote and am going to see how others solved it.

How long did it take in the end? After a bit of tweaking (ie, coupling), I got mine down to 550 seconds on my clunky old Dell using brute force; but I have a strong feeling that there may be ways of eliminating more than just numbers ending in 0.

For example: If the first and last digits added together are even, the number can be eliminated; which I think eliminates about 50% of all possibles with only one extra divide.

I also suspect that there are properties of

`n + reverse(n)`that we (or at least I) are missing.

Winston

Articles by Winston can be found here

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Randall Twede wrote:i finally let it run long enough and got the correct answer. i am still keeping in mind what Winston wrote and am going to see how others solved it.

Just FYI, I went off on a geek hunt and found the following two algorithms at Hacker's Delight:

`mod10()`runs about 6 times as fast as '

`n % 10`' on my computer (only works on positive values though);

`div10()`runs about 3 times as fast as '

`n / 10`'.

Now THAT'S micro-optimizing. Don't do this at home.

I also suspect it won't come close to bringing my program in under 1 minute.

Winston

Articles by Winston can be found here

After applying the incredibly geeky optimization as mentioned above, thanks to Winston Gutkowski, it came down to 61.101 seconds.

So close!

P.S.: And yes, no String business at all. Just positive integers bliss.

Aditya Jha wrote:More optimization on the Math level (as opposed to code level), and the time comes down to 5.982 seconds.

Got mine down from 550 to 120, but I know I'm missing something obvious.

Winston

[Edit: Got mine down to 12 seconds now, and I suspect the same trick will work for n < 10^13 too; but I still don't know why ]

[Edit 2: GOT IT!!! Thanks Aditya]

Articles by Winston can be found here

Though, I recommend first proving this theorem for yourself, and then using the technique in code.

Aditya Jha wrote:Though, I recommend first proving this theorem for yourself, and then using the technique in code.

Absolutely. When I said "Got it!", I actually didn't quite. Took me about another half hour to work out the proof; but it's a long time since A-Level Maths for me.

I'm now having a look at the Darts checkout one (#109).

Winston

Articles by Winston can be found here

after looking through the forum after my crime, i found similarities in some of the other solutions to what i was trying. i will still try to work it out but with help now. some solutions were awesome! like the first one i found. i couldn't imagine it could be so simple. several used what they call memoization and dynamic programming. i intend to read some more about both of those subjects. Winston, i am still going to use your method to see how much it helps my solution to 145, i just got distracted

SCJP

Visit my download page

Randall Twede wrote:Winston, i am still going to use your method to see how much it helps my solution to 145, i just got distracted

The biggest help will be to follow Aditya's advice.

Winston

Articles by Winston can be found here

SCJP

Visit my download page

this is similar to what i have been reading about concerning memoization. however a lookup table is compile time while memoization is done at runtime. i am still reading about this and dynamic programming. it will be worth it if i can understand it all. i have trouble with recursion to begin with.

SCJP

Visit my download page

Randall Twede wrote:i have trouble with recursion to begin with.

Well you know what they say:

To understand recursion, you must first understand recursion.

Winston

Articles by Winston can be found here