apparently creating too many objects

[Randall Twede]

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:

class Euler145 implements Problem
{
	public String solve()
	{
		StringBuilder forward = new StringBuilder();
		StringBuilder reverse = new StringBuilder();
		StringBuilder sum = new StringBuilder();
		Integer r;
		int s;
		int answer = 0;
		boolean odd = true;
		
		for(int i = 11; i <1000000000; i++)
		{
			odd = true;
			forward.delete(0, forward.length());
			reverse.delete(0, reverse.length());
			sum.delete(0, sum.length());
			if(i % 10 != 0)
			{
				forward.append(i);
				reverse = forward.reverse();
				r = new Integer(reverse.toString());
				s = i + r;
				sum.append(s);
				for(int k = 0; k < sum.length(); k++)
				{
					char c = sum.charAt(k);
					int t = Character.getNumericValue(c);
					if(t % 2 == 0)
					{
						odd = false;
					}
				}
				if(odd == true)
				{
					answer++;
				}
			}
		}
		return Integer.toString(answer);
	}
	
	public String getMessage()
	{
		return "How many reversible numbers are there below one-billion (10^9)?";
	}
}

the previous code:

class Euler145 implements Problem
{
	public String solve()
	{
		String forward = "";
		String reverse = "";
		String sum = "";
		Integer f;
		Integer r;
		int s;
		int answer = 0;
		boolean odd = true;
		
		for(int i = 11; i <1000000000; i++)
		{
			odd = true;
			reverse = "";
			if(i % 10 != 0)
			{
				forward = Integer.toString(i);
				for(int j = forward.length() - 1; j >= 0; j--)
				{
					reverse = reverse + forward.charAt(j);
				}
				f = new Integer(forward);
				r = new Integer(reverse);
				s = f.intValue() + r.intValue();
				sum = Integer.toString(s);
				for(int k = 0; k < sum.length(); k++)
				{
					char c = sum.charAt(k);
					int t = Character.getNumericValue(c);
					if(t % 2 == 0)
					{
						odd = false;
					}
				}
				if(odd == true)
				{
					answer++;
					//System.out.println(s);
					//System.out.println(forward + " + " + reverse + " = " + sum);
				}
			}
		}
		return Integer.toString(answer);
	}
	
	public String getMessage()
	{
		return "How many reversible numbers are there below one-billion (10^9)?";
	}
}

[Randall Twede]

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

[Winston Gutkowski]

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]

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

[Randall Twede]

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.

[Jeff Verdegan]

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]

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]

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

class Euler145 implements Problem
{
	public String solve()
	{
		StringBuilder number = new StringBuilder();
		StringBuilder sum = new StringBuilder();
		Integer reverse;
		int s;
		int answer = 0;
		boolean odd = true;
		char c;
		int t;
		
		for(int i = 11; i <1000000; i++)
		{
			odd = true;
			number.delete(0, number.length());
			sum.delete(0, sum.length());
			if(i % 10 != 0)
			{
				number.append(i);
				number = number.reverse();
				reverse = Integer.decode(number.toString());
				s = i + reverse;
				sum.append(s);
				for(int k = 0; k < sum.length(); k++)
				{
					c = sum.charAt(k);
					t = Character.getNumericValue(c);
					if(t % 2 == 0)
					{
						odd = false;
					}
				}
				if(odd == true)
				{
					answer++;
				}
			}
		}
		return Integer.toString(answer);
	}
	
	public String getMessage()
	{
		return "How many reversible numbers are there below one-billion (10^9)?";
	}
}

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]

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]

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]

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]

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]

There's another good reason to use numbers rather than characters:

public int reverse(int n) {
   int result = 0;
   while (n >= 10) {
      result = (result * 10) + (n % 10);
      n /= 10;
   }
   return (result * 10) + n;
}

(assumes that n >= 0 [Edit: and <= 1000000000 ]) and there may well be quicker methods.

Winston

[Martin Vashko]

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]

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]

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]

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]

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

[Matthew Brown]

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]

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:

private static final int[] mod10table = { 0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0 };

public static final int mod10(int n) {
   return mod10table[((0x19999999 * n) + (n >> 1) + (n >> 3)) >>> 28];
}

public static final int div10(int n) {
   return ((int) ((n * 0x66666667L) >> 34)) + (n >>> 31);
}

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

[Aditya Jha]

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.

[Aditya Jha]

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

[Winston Gutkowski]

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]

[Aditya Jha]

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]

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]

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]

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

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

Winston

[Randall Twede]

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.

class Euler145 implements Problem
{
	public String solve()
	{
		//StringBuilder number = new StringBuilder();
		StringBuilder sum = new StringBuilder();
		//Integer reverse;
		int s;
		int answer = 0;
		boolean odd = true;
		char c;
		int t;
		
		for(int i = 11; i <100000000; i++)
		{
			odd = true;
			//number.delete(0, number.length());
			sum.delete(0, sum.length());
			if(i % 10 != 0)
			{
				//number.append(i);
				//number = number.reverse();
				//reverse = Integer.decode(number.toString());
				//s = i + reverse;
				s = i + reverse(i);
				sum.append(s);
				//System.out.println(sum);
				for(int k = 0; k < sum.length(); k++)
				{
					c = sum.charAt(k);
					t = Character.getNumericValue(c);
					if(t % 2 == 0)
					{
						odd = false;
					}
				}
				if(odd == true)
				{
					answer++;
				}
			}
		}
		return Integer.toString(answer);//608720
	}
	
    private int reverse(int n)
	{  
       int result = 0;  
       while (n >= 10)
	   {  
          result = (result * 10) + (n % 10);  
          n /= 10;  
       }  
       return (result * 10) + n;  
    }
	
	public String getMessage()
	{
		return "How many reversible numbers are there below one-billion (10^9)?";
	}
}

[Randall Twede]

private static final int[] mod10table = { 0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0 };  
  
public static final int mod10(int n) {  
   return mod10table[((0x19999999 * n) + (n >> 1) + (n >> 3)) >>> 28];  
}

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]

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