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.
Code :
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.
Code java:
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]--;
}
}
}
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.
Re: Problem getting rid of congruent triangles from a counter.
Code with comments:
Code java:
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();
}
}
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.
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.
Code java:
/**
* 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);
}
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?
Re: Problem getting rid of congruent triangles from a counter.
Code :
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:
Code java:
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();
}
}
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.
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.
Code :
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.
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?
Re: Problem getting rid of congruent triangles from a counter.
This is the code I'm using to print out perims.
Code java:
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();
}
Quote:
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.
Code java:
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
Re: Problem getting rid of congruent triangles from a counter.
Why does only the line headed by perims: 12: have any numbers on it?
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:
Code :
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.
Code java:
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
}
}
}
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.
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.
Re: Problem getting rid of congruent triangles from a counter.
I haven't run it other than with 15 elements and have no timer.
Re: Problem getting rid of congruent triangles from a counter.
Run this. I'll give you my Timer.
Code java:
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.
Code java:
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();
}
}
Re: Problem getting rid of congruent triangles from a counter.
Quote:
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
Code java:
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
