Skip to content
August 29, 2011 / oop123

Project Euler #119 – Java

You can see the problem here: Problem #119.

I brute-forced the problem, and my code is very ugly. It contains a loop that search for as, and the loop is pretty much infinite because of the large numbers involve. My code only print out possible a30, so you also need to try the numbers to find the real solution (luckily, for 30, it gives out the solution right away). For large number, my code fails miserably, but it can cope with a small number like 30. I solved the question, so whatever.

final int TOLERABLE_LIMIT = 3; 
List<BigDecimal> a = new ArrayList<BigDecimal>();
int i = 7;

//loop - break condition at the beginning of loop
while (true) {
	i++;

	//break if i * i bigger than the current a[30] - meaning a[30] is for sure the answer
	//it takes so long for this condition to be fulfilled this is pretty much infinite
	if (a.size() >= 30 && a.get(29).compareTo(BigDecimal.valueOf(i * i)) < 0) {
		break;
	}
	
	//just slightly improve performace, and more importantly, take care of infinite loop involving 10, 100, 1000...
	int tempI = i;
	while (tempI % 10 == 0) tempI /= 10;
	if (tempI == 1) continue;

	//loop through the powers of current number, break out of loop if one of the following happens:
	//- if the digit sums exceed the current number three times in a row (a heuristic)
	//- if there is an a[30] and the current power exceeds it, no need to find a's that are bigger than a[30]
	BigDecimal number = BigDecimal.valueOf(tempI);
	BigDecimal currentPow = number.pow(2);
	int numOfFailures = 0;
	while (true) {
		currentPow = currentPow.multiply(number);
		int digitSum = digitSum(currentPow);
		
		if (digitSum == i) {
			if (!a.contains(currentPow)) a.add(currentPow);
			Collections.sort(a);
			
			if (a.size() >= 30) System.out.println(a.get(29));
		} else if (digitSum > i) {
			numOfFailures++;
			if (numOfFailures >= TOLERABLE_LIMIT) break;
		} else {
			numOfFailures = 0;
		}

		if (a.size() >= 30 && currentPow.compareTo(a.get(29)) > 0) break;
	}
}

Runs in <1 millisecond on my computer. The <1 millisecond is the time it took for the answer to be found and printed, and does not involve the huge long (basically infinite) loop. My solution is such a failure, sigh, CU

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: