Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 17 of 17

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

  1. #1
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default 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]--;
    				}
    			}
    		}


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    The first problem I see with the code is that are no comments in it that describe the logic it is using to solve the problem.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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();
     
    	}
     
    }

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    The posted code does not compile without errors. There is an import for a 3rd party package and the java.util.Timer class does not have a start() method.


    Suggestion: Change the code to use a variable for the array sizes vs the magic number 1001.
    For testing set that value to a small number like 15 and print out the contents of perims so you can see the data that is being loaded.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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);
    	}

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    What did you see printed out when you tried what I suggested in post #4?
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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();
     
    	}
     
    }

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    Did you print the contents of perims? Do it after the loops where it is loaded.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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.

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    How are you printing the contents of perims? Why does only the line headed by perims: 12: have any numbers on it?
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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

  12. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    Why does only the line headed by perims: 12: have any numbers on it?
    If you don't understand my answer, don't ignore it, ask a question.

  13. #13
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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
    				}
    			}
    		}

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    Glad you found it. I hope you see how using a debug technique like println() can help you find where the code was doing something differently than you expected.

    The code had added the same array over and over with changed contents each time.
    If you don't understand my answer, don't ignore it, ask a question.

  15. The Following User Says Thank You to Norm For This Useful Post:

    aesguitar (January 5th, 2013)

  16. #15
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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.

  17. #16
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,592
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    I haven't run it other than with 15 elements and have no timer.
    If you don't understand my answer, don't ignore it, ask a question.

  18. #17
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    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();
     
     
    	}
     
    }

  19. #18
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Problem getting rid of congruent triangles from a counter.

    Quote Originally Posted by aesguitar View Post
    ... 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

Similar Threads

  1. How to get rid of this?
    By tai8 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: March 12th, 2012, 07:54 PM
  2. Proper way to get rid of breaks.
    By Massaslayer in forum Loops & Control Statements
    Replies: 6
    Last Post: December 23rd, 2011, 06:53 PM
  3. Triangles problem - creating triangle objects
    By sparky5783 in forum What's Wrong With My Code?
    Replies: 6
    Last Post: May 15th, 2011, 12:38 PM
  4. Loop Patterns (triangles) [Beginner]
    By me1010109 in forum Loops & Control Statements
    Replies: 2
    Last Post: October 24th, 2010, 05:13 PM
  5. cant get rid of http connection
    By kartik in forum Java Networking
    Replies: 1
    Last Post: July 21st, 2009, 03:09 AM