Thread: Problem getting rid of congruent triangles from a counter.

I've been trying to solve this problem of Project euler: Problem 39 - Project Euler

I've run into a problem with sorting out triangle sides that are already used like {3,4,5} and {4,3,5} and so one. I tried building an array list of array lists of int arrays. Each int array contains the sides of the triangle like so.

sides[0] = a;
sides[1] = b;
sides[2] = c;

It adds the sides array to the ArrayList contained in the ArrayList at a+b+c. Thus sorting each possible right triangle based on perimeter. Then it goes through with another ArrayList c that contains all the 'c' values (sides[2]) in. If c doesn't contain that value, then it adds it; else if it does, it subtracts 1 from the count of triangles with that have that c value.

It isn't working correctly and I can't figure out why.

int[] triangles = new int[1001];
		ArrayList<ArrayList<int[]>> perims = new ArrayList<ArrayList<int[]>>(1001);
		for(int i = 0; i < 1001; i++)
		{
			perims.add(new ArrayList<int[]>());
		}
		int[] sides = new int[3];
 
		for(int a = 1; a < 335; a++)
		{
			for(int b = 1;  b<335 && a+b+Math.sqrt(a*a+b*b)<=1000 ; b++)
			{
				double c =  Math.sqrt(a*a+b*b);
				if(Algorithms.isInt(c))
				{
					System.out.println("Perimeter: " + (a+b+ (int)c) + " ; Sides: {" + a + ", " + b + ", " + (int)c + "}");
					triangles[a+b+(int)c]++;
					sides[0] = a;
					sides[1] = b;
					sides[2] = (int)c;
					perims.get((int) (a+b+c)).add(sides);
				}
			}
		}
 
		for(int i = 1; i < perims.size(); i++)
		{
			ArrayList<Integer> c = new ArrayList<Integer>();
			for(int j = 0; j < perims.get(i).size(); j++)
			{
				if(!c.contains(perims.get(i).get(j)[2]))
				{
					c.add(perims.get(i).get(j)[2]);
				}
				else if(c.contains(perims.get(i).get(j)[2]))
				{
					triangles[i]--;
				}
			}
		}

Code with comments:

package tools;
 
import java.util.*;
 
import org.jscience.mathematics.number.LargeInteger;
 
public class Tester {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Timer time = new Timer();
		time.start();
 
		int[] triangles = new int[1001];//create an array of 1001 (0-1000) to count every right triangle with a perimeter <=1000
		ArrayList<ArrayList<int[]>> perims = new ArrayList<ArrayList<int[]>>(1001);//create an ArrayList of ArrayLists that contain int arrays. There will be one ArrayList for every perimeter >= 1000. Chose to use ArrayLists for ease. Can be changed to an array if necessary
		for(int i = 0; i < 1001; i++)
		{
			perims.add(new ArrayList<int[]>());//initialize the arrays in perims
		}
		int[] sides = new int[3];//side length array for use with the perims ArrayList
 
		//loop through all possible right triangles with perimeter >= 1000
		for(int a = 1; a < 1000; a++)//iterate the a variable
		{
			for(int b = 1;  b<1000 && a+b+Math.sqrt(a*a+b*b)<=1000 ; b++)//iterate the b variable and check that the perimeter <=1000
			{
				double c =  Math.sqrt(a*a+b*b);//calculate c based of the Pythagorean thereom
				if(Algorithms.isInt(c))//checks that c is an integer as prescribed in the problem
				{
					System.out.println("Perimeter: " + (a+b+ (int)c) + " ; Sides: {" + a + ", " + b + ", " + (int)c + "}");//shows the perimeter and side lengths
					triangles[a+b+(int)c]++;//adds one to that perimeter's value in the counter array
					sides[0] = a;//set the values in the sides array
					sides[1] = b;
					sides[2] = (int)c;
					perims.get((int) (a+b+c)).add(sides);//add the triangle to the perims ArrayList
				}
			}
		}
//-------------------Problem Code--------------------------\\
		//loop through everything in the perims array to attempt to get rid of duplicate arrays
		for(int i = 1; i < perims.size(); i++)
		{
			ArrayList<Integer> c = new ArrayList<Integer>();//creates a c-variable arraylist to check for duplicated triangles.
			for(int j = 0; j < perims.get(i).size(); j++)//loop through the arraylists in perims
			{
				if(!c.contains(perims.get(i).get(j)[2]))//if c doesn't contain that sides[2] equivalent value, then add it to c
				{
					c.add(perims.get(i).get(j)[2]);
				}
				else if(c.contains(perims.get(i).get(j)[2]))//otherwise, subtract one from that perimeter's count.
				{
					triangles[i]--;
				}
			}
		}
//---------------------------------------------------------\\
 
			System.out.println("triangles["+Algorithms.indexOfMaximum(triangles)+"] = " + Algorithms.maximum(triangles));//print the results.
 
				time.end();
				time.printElapsedTimeSeconds();
 
	}
 
}

Ignore timer. That's my own class. I use it for timing the amount of time it takes. Neither of the imports are used in this program. This is my 'general use' class. These are the Algorithms.* methods.

/**
	 * Uses the Pythagorean Thereom to prove that triangle ABC is a right triangle.
	 * @param a - length of side a.
	 * @param b - length of side b.
	 * @param c - length of side c.
	 * @return true if a^2 + b^2 = c^2; false otherwise
	 */
	public static boolean isRightTriange(double a, double b, double c)
	{
		return a*a+b*b==c*c;
	}
 
	/**
	 * Find the maximum value in an array.
	 * @param arr - the array to look through
	 * @return The highest values in the array.
	 */
	public static int maximum(int[] arr)
	{
		int max = 0;
		for(int i : arr)
		{
			if(i>max)
				max=i;
		}
 
		return max;
	}
 
	/**
	 * Finds the index of the highest value.
	 * @param arr - array to search through.
	 * @return the index of the highest value.
	 */
	public static int indexOfMaximum(int[] arr)
	{
		int max = maximum(arr);
		for(int i = 0; i<arr.length; i++)
		{
			if(max==arr[i])
				return i;
		}
		return 0;
	}
 
/**
	 * Checks to see if the given double value is an integer
	 * @param val - value to check
	 * @return true - if, when val is cast to an int, is equal to the original val. False if not.
	 */
	public static boolean isInt(double val)
	{
		return ((int)val==val);
	}
 
	public static boolean isInt(double val)
	{
		return ((int)val==val);
	}

Perimeter: 12 ; Sides: {3, 4, 5}
Perimeter: 12 ; Sides: {4, 3, 5}
triangles[12] = 1
Elapsed time: 0.001 sec.

This is what was printed out. I used 15 as the size. Code edited to use a variable to change size on the fly:

package tools;
 
import java.util.*;
 
import org.jscience.mathematics.number.LargeInteger;
 
public class Tester {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Timer time = new Timer();
		time.start();
 
		int size = 15;
		int[] triangles = new int[size];//create an array of size (0-size-1) to count every right triangle with a perimeter <=size-1
		ArrayList<ArrayList<int[]>> perims = new ArrayList<ArrayList<int[]>>(size);//create an ArrayList of ArrayLists that contain int arrays. There will be one ArrayList for every perimeter >= size-1. Chose to use ArrayLists for ease. Can be changed to an array if necessary
		for(int i = 0; i < size; i++)
		{
			perims.add(new ArrayList<int[]>());//initialize the arrays in perims
		}
		int[] sides = new int[3];//side length array for use with the perims ArrayList
 
		//loop through all possible right triangles with perimeter >= size-1
		for(int a = 1; a < size-1; a++)//iterate the a variable
		{
			for(int b = 1;  b<size-1 && a+b+Math.sqrt(a*a+b*b)<=size-1 ; b++)//iterate the b variable and check that the perimeter <=size-1
			{
				double c =  Math.sqrt(a*a+b*b);//calculate c based of the Pythagorean thereom
				if(Algorithms.isInt(c))//checks that c is an integer as prescribed in the problem
				{
					System.out.println("Perimeter: " + (a+b+ (int)c) + " ; Sides: {" + a + ", " + b + ", " + (int)c + "}");//shows the perimeter and side lengths
					triangles[a+b+(int)c]++;//adds one to that perimeter's value in the counter array
					sides[0] = a;//set the values in the sides array
					sides[1] = b;
					sides[2] = (int)c;
					perims.get((int) (a+b+c)).add(sides);//add the triangle to the perims ArrayList
				}
			}
		}
//-------------------Problem Code--------------------------\\
		//loop through everything in the perims array to attempt to get rid of duplicate arrays
		for(int i = 1; i < perims.size(); i++)
		{
			ArrayList<Integer> c = new ArrayList<Integer>();//creates a c-variable arraylist to check for duplicated triangles.
			for(int j = 0; j < perims.get(i).size(); j++)//loop through the arraylists in perims
			{
				if(!c.contains(perims.get(i).get(j)[2]))//if c doesn't contain that sides[2] equivalent value, then add it to c
				{
					c.add(perims.get(i).get(j)[2]);
				}
				else if(c.contains(perims.get(i).get(j)[2]))//otherwise, subtract one from that perimeter's count.
				{
					triangles[i]--;
				}
			}
		}
//---------------------------------------------------------\\
 
			System.out.println("triangles["+Algorithms.indexOfMaximum(triangles)+"] = " + Algorithms.maximum(triangles));//print the results.
 
				time.end();
				time.printElapsedTimeSeconds();
 
	}
 
}

This is what I get when I print perims after everything is added together, before anything else happens.

Perimeter: 12 ; Sides: {3, 4, 5}
Perimeter: 12 ; Sides: {4, 3, 5}
perims:0: 
perims:1: 
perims:2: 
perims:3: 
perims:4: 
perims:5: 
perims:6: 
perims:7: 
perims:8: 
perims:9: 
perims:10: 
perims:11: 
perims:12: [4, 3, 5] [4, 3, 5] 
perims:13: 
perims:14: 
triangles[12] = 1
Elapsed time: 0.003 sec.

It appears that the array isn't adding correctly.

This is the code I'm using to print out perims.

for(int i = 0; i < perims.size(); i++)
		{
			System.out.print("perims:" + i +": ");
			for(int[] j : perims.get(i))
			{
				System.out.print(Arrays.toString(j)+" ");
			}
			System.out.println();
		}

Why does only the line headed by perims: 12: have any numbers on it?

That is the only line with anything in it because with a perimeter limit of 15, the only right triangles that were found were {3,4,5} and {4,3,5}. They were added to the perims (short for perimeters) in the arraylist at index=12. It happens at these lines.

sides[0] = a;//set the values in the sides array
					sides[1] = b;
					sides[2] = (int)c;
					perims.get((int) (a+b+c)).add(sides);//add the triangle to the perims ArrayList

Because right triangles with perimeter 12 were the only ones found. The sides array was supposed to be added twice to perims.get(12) on two separate occasions. Which it was, but something apparently went wrong. it should read:

perims:12: [3,4,5] [4,3,5]
 
not
 
perims:12: [4,3,5] [4,3,5]

I don't understand why that's wrong. the perims arraylist is really an arraylist of arraylists of int arrays. the int arrays contain side lengths. Each index in the perims arraylist represents a seperate perimeter length. Each arraylist at each unique perimeter (the indexes of perims) contains all the right triangle side lengths of that perimeter. So, in this example, there were two triangles that were found with a perimeter of 12.

--- Update ---

I changed the line where it adds into the perims madness. the arrays are added correctly now because it creates a new array everytime.

for(int a = 1; a < size-1; a++)//iterate the a variable
		{
			for(int b = 1;  b<size-1 && a+b+Math.sqrt(a*a+b*b)<=size-1 ; b++)//iterate the b variable and check that the perimeter <=size-1
			{
				double c =  Math.sqrt(a*a+b*b);//calculate c based of the Pythagorean thereom
				if(Algorithms.isInt(c))//checks that c is an integer as prescribed in the problem
				{
					System.out.println("Perimeter: " + (a+b+ (int)c) + " ; Sides: {" + a + ", " + b + ", " + (int)c + "}");//shows the perimeter and side lengths
					triangles[a+b+(int)c]++;//adds one to that perimeter's value in the counter array
					/*sides[0] = a;//set the values in the sides array
					sides[1] = b;
					sides[2] = (int)c;*/
					perims.get((int) (a+b+c)).add(new int[] {a, b, (int)c});//add the triangle to the perims ArrayList
				}
			}
		}

That solved it. How fast does this algorithm run for you? I have a new computer with a very fast i7 in it. Does it run in about 10ms for you with out the debug printing? Just want to see how efficient it is.

Run this. I'll give you my Timer.

public class Tester {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Timer time = new Timer();
		time.start();
 
		int size = 1001;
		int[] triangles = new int[size];//create an array of size (0-size-1) to count every right triangle with a perimeter <=size-1
		ArrayList<ArrayList<int[]>> perims = new ArrayList<ArrayList<int[]>>(size);//create an ArrayList of ArrayLists that contain int arrays. There will be one ArrayList for every perimeter >= size-1. Chose to use ArrayLists for ease. Can be changed to an array if necessary
		for(int i = 0; i < size; i++)
		{
			perims.add(new ArrayList<int[]>());//initialize the arrays in perims
		}
		//int[] sides = new int[3];//side length array for use with the perims ArrayList
 
		//loop through all possible right triangles with perimeter >= size-1
		for(int a = 1; a < size-1; a++)//iterate the a variable
		{
			for(int b = 1;  b<size-1 && a+b+Math.sqrt(a*a+b*b)<=size-1 ; b++)//iterate the b variable and check that the perimeter <=size-1
			{
				double c =  Math.sqrt(a*a+b*b);//calculate c based of the Pythagorean thereom
				if(Algorithms.isInt(c))//checks that c is an integer as prescribed in the problem
				{
					//System.out.println("Perimeter: " + (a+b+ (int)c) + " ; Sides: {" + a + ", " + b + ", " + (int)c + "}");//shows the perimeter and side lengths
					triangles[a+b+(int)c]++;//adds one to that perimeter's value in the counter array
					/*sides[0] = a;//set the values in the sides array
					sides[1] = b;
					sides[2] = (int)c;*/
					perims.get((int) (a+b+c)).add(new int[] {a, b, (int)c});//add the triangle to the perims ArrayList
				}
			}
		}
 
		/*for(int i = 0; i < perims.size(); i++)
		{
			System.out.print("perims:" + i +": ");
			for(int[] j : perims.get(i))
			{
				System.out.print(Arrays.toString(j)+" ");
			}
			System.out.println();
		}*/
//-------------------Problem Code--------------------------\\
		//loop through everything in the perims array to attempt to get rid of duplicate arrays
		for(int i = 1; i < perims.size(); i++)
		{
			ArrayList<Integer> c = new ArrayList<Integer>();//creates a c-variable arraylist to check for duplicated triangles.
			for(int j = 0; j < perims.get(i).size(); j++)//loop through the arraylists in perims
			{
				if(!c.contains(perims.get(i).get(j)[2]))//if c doesn't contain that sides[2] equivalent value, then add it to c
				{
					c.add(perims.get(i).get(j)[2]);
				}
				else if(c.contains(perims.get(i).get(j)[2]))//otherwise, subtract one from that perimeter's count.
				{
					triangles[i]--;
				}
			}
		}
//---------------------------------------------------------\\
 
			System.out.println("triangles["+Algorithms.indexOfMaximum(triangles)+"] = " + Algorithms.maximum(triangles));//print the results.
 
				time.end();
				time.printElapsedTimeSeconds();
 
	}
 
}

A useful timer class I built.

package tools;
 
public class Timer {
 
	private long start = 0, end = 0, startNanos = 0, endNanos = 0;
 
	public Timer(){};
 
	public void start()
	{
		start = System.nanoTime()/1000000;
	}
 
	public void end()
	{
		end = System.nanoTime()/1000000;
	}
 
	public void startNanos()
	{
		startNanos = System.nanoTime();
	}
 
	public void endNanos()
	{
		endNanos = System.nanoTime();
	}
 
	public long getElapsedTime()
	{
		if(start==0)
		{
			throw new RuntimeException("Failed to start timer.");
		}
 
		if(end==0)
		{
			return System.currentTimeMillis()-start;
		}
 
		return end-start;
	}
 
	public long getElapsedTimeNanos()
	{
		if(startNanos==0)
		{
			throw new RuntimeException("Failed to start timer.");
		}
 
		if(endNanos == 0)
		{
			return System.nanoTime() - startNanos;
		}
 
		return endNanos - startNanos;
	}
 
	public double getElapsedTimeSeconds()
	{
		return (double)getElapsedTime()/1000.0;
	}
 
	public double getElapsedTimeMinutes()
	{
		return (double)getElapsedTimeSeconds()/60.0;
	}
 
	public void printElapsedTimeNanos()
	{
		System.out.println("Elapsed time: " + formatThousands(getElapsedTimeNanos()) + " ns.");
	}
 
	public void printElapsedTime()
	{
		System.out.println("Elapsed time: " + formatThousands(getElapsedTime()) + " ms.");
	}
 
	public void printElapsedTimeSeconds()
	{
		System.out.println("Elapsed time: " + getElapsedTimeSeconds() + " sec.");
	}
 
	public void printElapsedTimeMinutes()
	{
 
		System.out.println("Elapsed time: " + (int)getElapsedTimeMinutes() + ": " + getElapsedTimeSeconds()%60 + " min.");
	}
 
	public void printAll()
	{
		if(startNanos!=0)
		{
			printElapsedTimeNanos();
		}
 
		if(start!=0)
		{
			printElapsedTime();
			printElapsedTimeSeconds();
			printElapsedTimeMinutes();
		}
	}
 
	public void pause(long millis)
	{
		long start = System.currentTimeMillis();
 
		if(millis<0)
		{
			throw new IllegalArgumentException("Negative time in argument: millis");
		}
 
		while((System.currentTimeMillis()-start)!=millis){}
	}
 
	private String formatThousands(Long val)
	{
		String str = "";
 
		if(val.toString().length()<4)
		{
			return val.toString();
		}
		else
		{
			int index = val.toString().length();
			String valS = val.toString();
 
			while(index-3>0)
			{
				str+="," + valS.substring(index-3, index);
				index-=3;
			}
 
			return valS.substring(0, index).concat(str);
		}
 
	}
 
 
	public static void main(String[] args) {
 
		Timer time = new Timer();
 
		time.start();
		time.pause(1523);
		time.end();
 
		time.printAll();
 
 
	}
 
}

Originally Posted by aesguitar

... efficient...

I think the most important thing is to have something that works. (Which you apparently do.)

Now, thinking about efficiency without basically changing your approach, I have a couple of observations:

First of all, the way that you are doing it, at the end of your discovery loop, each entry in your triangles array will have a value equal to two times the number of triangles with that perimeter. That is because, for each side set (a, b, c) in the ArrayList for that perimeter, there will be an entry (b, a, c), corresponding to a congruent triangle. (Note that there are no integer right triangles that have two equal sides.)

Therefore, the index of largest element value in your triangles array already indicates the answer to the problem as stated. In fact, unless you want to print out the side sets for a given perimeter, you don't actually need any ArrayLists at all. (Ability to print out solutions is a nice touch, but not really part of the problem assignment.)

Secondly, you can calculate the triangles array element values (and create the ArrayLists if you want to) with no duplicates by changing your discovery loops to something like

        for(int a = 1; whatever...)
        {
            for(int b = a+1;  whatever...)
            {

So, not only is the corrective loop (to remove duplicates) no longer necessary, but the discovery loop runs faster. You can still create the ArrayLists if you want to print the side sets, and you don't have to worry about duplicates at all.


There may be other ways to improve performance, as you can see by referring to the Project Euler list of comments for that problem, which you can access after you have submitted the correct answer. In my opinion, that's the real value of Project Euler: Seeing how others approach the problem.


Cheers!

Z