programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# apparently creating too many objects

Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
a warning to anyone wanting to solve Euler145 on your own. this is a solution although a slow one.
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:

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
here is the problem statement

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

Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
i am going to try moving the declaration of char c and int t out of the loop that might help

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:

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.

Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Randall Twede wrote:i am going to try moving the declaration of char c and int t out of the loop that might help

It won't. All local variables are allocated at cone, at method entry.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
Jeff, turning them into Strings and using chatAt() and Character.getNumericValue() is where i started at. i have also been thinking about modulo math as a last resort. what i have decided is to take my best effort and let it run long enough to give an answer.(20 minutes+) then i can go to the forum for that question and see how others solved it
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

Winston Gutkowski
Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

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

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
oh crap! i forgot to change the number back from 100,000,00 to 1 billion before i started it
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

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:
There's another good reason to use numbers rather than characters:(assumes that n >= 0 [Edit: and <= 1000000000 ]) and there may well be quicker methods.

Winston

Sheriff
Posts: 3837
66
• 1
• Number of slices to send:
Optional 'thank-you' note:

Winston Gutkowski wrote:... there may well be quicker methods.

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

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
Winston, i can see how that might be better than the way i am doing it. i am going to save that code snippet.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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.

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

Bartender
Posts: 4568
9
• Number of slices to send:
Optional 'thank-you' note:
I suspect you're right. I haven't tried this one yet, but while you can have a solution that takes as long as you like, there's an unofficial one minute target. Specifically, they say:

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.

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

Ranch Hand
Posts: 227
• Number of slices to send:
Optional 'thank-you' note:
I started implementing this after reading the original post. The initial program took close to 104 seconds to generate the answer.

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.

Ranch Hand
Posts: 227
• 3
• Number of slices to send:
Optional 'thank-you' note:
More optimization on the Math level (as opposed to code level), and the time comes down to 5.982 seconds.

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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]

Ranch Hand
Posts: 227
• Number of slices to send:
Optional 'thank-you' note:
Hint for those who are still on it: There won't be any reversible numbers with number of digits as (4*x+1). That means no reversible number would ever have 1-digit, 5-digits and so on...

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

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
i started working on 116. after several days i gave in and cheated by finding a solution on the internet
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:D

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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:D

Winston

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
well using Winston's method didn't seem to help any. i have one less StringBuilder and no Integers(just one StringBuilder now) but it seems no faster. 2 minutes or so for 100,000,000. the answer is the same for 1 billion, it just takes over a half hour instead.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:

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.

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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

 What? What, what, what? What what tiny ad: a bit of art, as a gift, that will fit in a stocking https://gardener-gift.com