Skip to content
September 3, 2011 / oop123

Project Euler #159 – Java

You can see the problem here: Problem #159.

This is my 100th question, woot! Now I just need to complete another 50 questions to become level 4. I doubt I can do another 20 questions, let alone 50, but I will try anyway. Now that little “celebration” is over with, let’s get back to the question. This question is pretty easy. The digital root of a number (in base 10) can be found using the following piecewise function (I love google):

f(n) = \begin{cases}    n\ (mod\ 9) & n\ (mod\ 9) \neq 0 \\    9 & n\ (mod\ 9) = 0  \end{cases}

In plain English, for any number n, find the remainder after dividing n by 9. The digital root of n will be the remainder, unless the remainder is 0, in which case the digital root is 9. Kudos for you if you know why this works (it’s not that hard, hint: it’s related to the fact if a number’s digit sum is divisible by 9, then the number itself is divisible by 9).

The maximal Digital Root Sum (MDRS) of each number can be found with dynamic programming since you can start with the MDRS of small numbers and use them to find the MDRS of the bigger numbers. For those of you who can’t google, dynamic programming involves solving complex problem by breaking it down into sub-problems (usually smaller version of the bigger problem) and doing those instead.

final int SIZE = 1000000;
int[] drs = new int[SIZE];
for (int i = 2; i < SIZE; i++) {
	//prime number: mdrs = digital root
	if (drs[i] == 0) {
		drs[i] = i % 9;
		if (drs[i] == 0) drs[i] = 9;
	}
	//a number's digital root can be its mdrs
	else if (drs[i] < 10) {  //a single number's digital root cannot exceed 10
		int candidate = i % 9;
		if (candidate == 0) candidate = 9;
		drs[i] = Math.max(drs[i], candidate);
	}
	
	int currentNum = i;
	for (int factor = 2; factor <= i; factor++) {
		currentNum += i;
		if (currentNum >= SIZE) break;
		drs[currentNum] = Math.max(drs[i] + drs[factor], drs[currentNum]);
	}
}

//find answer
int sum = 0;
for (int num : drs) sum += num;
System.out.println(sum);

Runs in around 225 milliseconds on my computer. CU

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

August 21, 2011 / oop123

Project Euler #102 – Java

You can see the problem here: Problem #102.

I cheated a little and googled for algorithms to solve this problem. Turns out there are many ways to test whether a triangle contains the origin. The algorithm I choose involves finding the triangle’s intersection with the y-axis. It’s based on the fact a triangle contains the origin iff (if and only if) it intersects the y-axis at two points – 1 above the origin and 1 below – OR when one of its vertex is the origin.

public static boolean containsOrigin(int ax, int ay, int bx, int by, int cx, int cy) {
	//one of the three vertex is origin?
	if ((ax == 0 && ay == 0) || (bx == 0 && by == 0) || (cx == 0 && cy == 0)) return false;

	List<Double> intersections = new ArrayList<Double>(2);

	//ax == 0: ay is an intersection
	//otherwise, find the intersection (note how the two conditions remove possibility of counting a vertex that's
	//on the y-axis as an intersection twice)
	if (ax == 0) intersections.add((double) ay);
	else if ((ax < 0 && bx > 0) || (ax > 0 && bx < 0)) {
		double slope = (((double) by) - ay) / (bx - ax);
		intersections.add(-slope * ax + ay);
	}

	//some copy and paste and changing single letters
	if (bx == 0) intersections.add((double) by);
	else if ((bx < 0 && cx > 0) || (bx > 0 && cx < 0)) {
		double slope = (((double) cy) - by) / (cx - bx);
		intersections.add(-slope * bx + by);
	}

	if (cx == 0) intersections.add((double) cy);
	else if ((cx < 0 && ax > 0) || (cx > 0 && ax < 0)) {
		double slope = (((double) ay) - cy) / (ax - cx);
		intersections.add(-slope * cx + cy);
	}
	
	if (intersections.size() < 2) return false;
	return ((intersections.get(0) > 0 && intersections.get(1) < 0) ||
	(intersections.get(0) < 0 && intersections.get(1) > 0));
}

Then we just need to read the text file and pass all the coordinates into the above function.

BufferedReader in = new BufferedReader(new FileReader("triangles.txt"));
int answer = 0;
for (int i = 0; i < 1000; i++) {
	String[] nums = in.readLine().split(",");
	if (containsOrigin(
		Integer.parseInt(nums[0]), Integer.parseInt(nums[1]),
		Integer.parseInt(nums[2]), Integer.parseInt(nums[3]),
		Integer.parseInt(nums[4]), Integer.parseInt(nums[5])))
			answer++;
}
System.out.println(answer);

Runs in around 40 milliseconds on my computer. CU

August 18, 2011 / oop123

Project Euler #91 – Java

You can see the problem here: Problem #91.

This problem is pretty easy.

right triangle with both coordinates at the sidetransformation of the first trianglesecond transformation of first triangle

As you can see from the first pictures, if both coordinates are located at the sides of the grid, we can make a right triangle. That right triangle can also be transformed into two other right triangles, as seen from the remaining two triangles. Since there 50 * 50 = 2500 ways to choose those two coordinates, we already know there are at least 2500 * 3 = 7500 right triangles. Now we just need to figure out a way to find the rest of the triangles.

Let’s say we want to find a right triangle with coordinate P = (1, 2). If we draw a line starting from the origin O to P, the line will have a slope of 2. Then if we draw a line with a slope -1/2, the negative reciprocal of 2, it will be perpendicular to OP. Since the other coordinate Q needs to contain integers, we will find Q by moving P 2 blocks to the right and 1 block down (using slope = -1/2 and definition of slope). See the pictures below for a more visual explanation. The red line has a slope of 2 (1 block right, 2 blocks up) and the blue line has a slope of -1/2 (2 blocks right, 1 block down).
a right triangle with coordinate (1, 2) and (3, 1)
The above right triangle can also be reflected along the line y = x to make another right triangle.
right triangle with coordinates (2, 1) and (1, 3), a y = x reflection of above image
Also, we can extend PQ another 2 blocks to the right and 1 block down and make a different right triangle.
right triangle with coordinates (1, 2) and (5, 0)
There is one last thing to note about. Let’s say the P coordinate is (2, 4), the negative reciprocal of its slope would be -2/4. We need to simplify -2/4 to -1/2 before we can use it in the algorithm, or else we can miss some right triangles. Taken all the above points into account, here is the code (surprisingly short for a Project Euler problems):

final int SIZE = 50;
int answer = SIZE * SIZE * 3;

for (int x = 1; x <= SIZE; x++) {
	for (int y = 1; y <= SIZE; y++) {
		int gcf = EulerMath.GCF(x, y); //bunch of small utility methods I kept in EulerMath
		int dx = x / gcf;
		int dy = y / gcf;
		answer += Math.min(y / dx, (SIZE - x) / dy) * 2;
	}
}

System.out.println(answer);

Runs in ~3 milliseconds on my computer. Note that the problem can also be easily brute force due to its small size, oh well. CU

August 15, 2011 / oop123

Project Euler #88 – Java

You can see the problem here: Problem #88.

This problem is easier than it looks. As you can see from the question, we can add 1s to a list of factor to change its sum but keep its product the same. For example, (2 * 3) = 6, but 2 + 3 only equals 5. We can add 1 to the list of factors [(2 * 3) -> (1 * 2 * 3)] which changes the list’s sum to 6 but keeps its product at 6. Using this observation, we can derive a simple formula that can calculate the k for any list of factors:

k = number_of_factors – sum_of_factors + product_of_factors

So let’s say the list of factors is (2 * 3 * 4), the product_of_factors would be 24, the number_of_factors would be 3, and the sum_of_factors would be 9. Plug those into the above formula, and we get k = 18.

To solve this question, I used a dynamic programming approach again in which I used an array to accumulate all the lists of factors. However, why calculate the lists of factors when we can just keep track of their sum_of_factors and number_of_factors? After I finished the question, I realized the number_of_factors and sum_of_factors can be combined into a single number to be keep track of (number_of_factors – sum_of_factors, see the formula for k), leading to the following (messy) code.

final int SIZE = 12000;
final int RANGE = 24000; //P.S. RANGE can be smaller, down to 12,200

int[] k = new int[SIZE + 1];
List<Set<Integer>> nums = new ArrayList<Set<Integer>>(RANGE + 1);
for (int i = 0; i <= RANGE; i++) nums.add(new HashSet<Integer>());

//dynamically calculate all the k's
for (int i = 2; i <= RANGE / 2; i++) {
	nums.get(i).add(-i + 1);

	for (int num : nums.get(i)) {
		int current = i + i;
		int new_num = num - 1;

		for (int j = 2; j <= i && current <= RANGE; j++) {
			nums.get(current).add(new_num);
			int pk = current + new_num;
			if (pk <= SIZE && (current < k[pk] || k[pk] == 0)) k[pk] = current;
			new_num--;
			current += i;
		}
	}
}

//show the answer
boolean success = true;
for (int i = 2; i < k.length; i++) if (k[i] == 0) success = false;
if (success) {
	k = ArraysUtils.sortAndRemoveDuplicates(k);
	int sum = 0;
	for (int i : k) sum += i;
	System.out.println(sum);
}

Runs in around 500 milliseconds on my computer (200 milliseconds if RANGE = 13000). CU

August 10, 2011 / oop123

Project Euler #95 – Java

You can see the problem here: Problem #95.

Since I am getting stuck on one of Project Euler’s problem (a bug somewhere I can’t find), I decided to find another (an easy) problem to do – voila, problem 95.

Part 1: Getting the number’s sum of divisors

This is very easy: just use a sieve to accumulate the sums.

final int SIZE = 1000000;

//initialize all the sums
int[] sums = new int[SIZE + 1];
Arrays.fill(sums, 1);
for (int i = 2; i <= SIZE / 2; i++) {
	for (int j = i + i; j <= SIZE; j += i) {
		sums[j] += i;
	}
}

Part 2: Solving the problem

A dynamic programming approach to this problem makes solving it a breeze. First, we create an integer array chainNum to store any calculated amicable chain lengths. chainNum can also store -1s to indicate a number cannot form a chain. Then we just loop from 1 to 1,000,000 and attempt to make an amicable chain with each number. If we found a number cannot form an amicable chain, we will update the corresponding index in chainNum with -1. Also, when we found an amicable chain, chainNum will be updated accordingly with the chain’s length.

//***** initalize chainNum *****
//-1 means no chain exists for the number
//0 means we haven't calculated the chainNum yet
int[] chainNum = new int[SIZE + 1];
chainNum[1] = -1;
chainNum[2] = -1;
chainNum[3] = -1;
chainNum[4] = -1;

//***** finding all the chainNum *****
for (int i = 5; i <= SIZE; i++) {
	if (chainNum[i] != 0) continue; //skip numbers that has been tested
	List<Integer> chain = new ArrayList<Integer>();
	chain.add(i);
	int next = sums[i];

	while (true) {
		//if the chain fails, update chainNum
		if (next > SIZE || chainNum[next] != 0) {
			for (Integer n : chain) chainNum[n] = -1;
			break;
		}

		//if the a chain is found, update chainNum
		int index = chain.indexOf(next);
		if (index >= 0) {
			//there may be numbers that leads to the chain but is not actually contain by the chain
			for (int j = 0; j < index; j++) chainNum[chain.get(j)] = -1;
			for (int j = index; j < chain.size(); j++) chainNum[chain.get(j)] = chain.size();
			break;
		}

		chain.add(next);
		next = sums[next];
	}
}

//***** just search for the largest chain number *****
int answer = 0;
int largest = 0;
for (int i = 2; i <= SIZE; i++) {
	if (chainNum[i] > largest) {
		largest = chainNum[i];
		answer = i;
	}
}
System.out.println(answer);

Runs in around 800 milliseconds on my computer. Surprisingly easy. CU

August 3, 2011 / oop123

Project Euler #83 – Java

You can see the problem here: Problem #83.

This is a simple question once I learned the Dijkstra’s algorithm (here’s wikipedia entry on it). The following codes are just an implementation of it, nothing too interesting. I used the same algorithm for question #82 too (just some small changes).

.main(String[] args) body:

final int SIZE = 80;
BufferedReader in = new BufferedReader(new FileReader("matrix.txt"));

//read in all the Nodes
Node[][] nodes = new Node[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
	String[] temp = in.readLine().split(",");
	for (int j = 0; j < SIZE; j++) {
		nodes[i][j] = new Node(Integer.parseInt(temp[j]), i, j);
	}
}

//initialize beginning
PriorityQueue<Node> notVisited = new PriorityQueue<Node>();
nodes[0][0].totalCost = nodes[0][0].travelCost;
notVisited.add(nodes[0][0]);

//algorithm
for (int i = 0; i < SIZE * SIZE - 1; i++) {
	Node node = notVisited.remove();
	node.visited = true;
	int row = node.row;
	int column = node.column;

	if (row == SIZE - 1 && column == SIZE - 1) break;
			
	if (row != 0) {
		update(node, nodes[row - 1][column], notVisited);
	}
	if (row != SIZE - 1) {
		update(node, nodes[row + 1][column], notVisited);
	}
	if (column != SIZE - 1) {
		update(node, nodes[row][column + 1], notVisited);
	}
	if (column != 0) {
		update(node, nodes[row][column - 1], notVisited);
	}
}

System.out.println(nodes[SIZE - 1][SIZE - 1].totalCost);

The Node class and one of the method for the algorithm.

static class Node implements Comparable<Node> {
	public int totalCost = Integer.MAX_VALUE;
	public boolean visited = false;

	public int travelCost;
	public int row;
	public int column;

	public Node(int cost, int row, int column) {
		travelCost = cost;
		this.row = row;
		this.column = column;
	}

	@Override
	public int compareTo(Node node) {
		if (node.totalCost > this.totalCost) {
			return -1;
		} else if (node.totalCost < this.totalCost) {
			return 1;
		}
		return 0;
	}
}

	
static void update(Node start, Node target, PriorityQueue<Node> queue) {
	start.visited = true;
	if (start.totalCost + target.travelCost < target.totalCost) {
		target.totalCost = start.totalCost + target.travelCost;
	}
	if (!target.visited && !queue.contains(target)) {
		queue.add(target);
	}
}

Runs in around 125 milliseconds on my computer. Nothing to this problem if you know (how to google for) path finding algorithms.

Follow

Get every new post delivered to your Inbox.