One of my friend sent me below image as puzzle to count the triangles. I started counting them and first got to 15, then again recounted and reached to 19.
But I was not sure whether I was right or not. So I thought of writing a simple program to find out the total number of triangles. I used below algorithm to find out the number of triangles.
- Any triangle has three distinct points.
- Any triangle consists of three different lines.
Now counting lines with points is easy, from below image we can easily see that it contains 7 lines.
Below is the program to find out the total number of triangles in these scenarios.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
package com.journaldev.utils; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set; public class FindTriangles { public static void main(String[] args) { // Scanner scanner = new Scanner(System.in); // System.out.println("Please enter number of lines"); // int count = Integer.parseInt(scanner.nextLine()); // // List<String> lines = new ArrayList<String>(); // for(int i=0; i<count; i++){ // System.out.println("Please enter line "+(i+1)); // lines.add(scanner.nextLine()); // } // scanner.close(); // System.out.println("Lines are::"+lines.toString()); findTriangles(Arrays.asList(new String[] { "ABC", "CDEF", "AIF", "BGHI", "CKJI", "AGKD", "AHJE" })); findTriangles(Arrays.asList(new String[] { "AB","BC","CA"})); } // Logic to find triangles public static void findTriangles(List<String> lines) { int count=0; // Find total distinct points using Set Set<String> points = new HashSet<String>(); for (String line : lines) { char[] pointArray = line.toCharArray(); for (char c : pointArray) points.add(c + ""); } System.out.println("Points are::" + points.toString()); //Create Array from Set String[] pointsArray = new String[points.size()]; pointsArray = points.toArray(pointsArray); System.out.println(Arrays.toString(pointsArray)); //Create distinct points set by looping for(int i=0; i< pointsArray.length-2; i++){ for(int j=i+1; j< pointsArray.length-1; j++){ for(int k=j+1; k< pointsArray.length; k++){ // Triangle has 3 distinct points and 3 different lines String triangleOption = pointsArray[i]+pointsArray[j]+pointsArray[k]; //if all 3 points are in single line, its not a triangle // also 2 points should be part of a line boolean b1 = false; boolean b2 = false; boolean b3 = false; for( String line : lines){ if(line.contains(pointsArray[i]) && line.contains(pointsArray[j]) && !line.contains(pointsArray[k])){ b1=true; } if(line.contains(pointsArray[i]) && line.contains(pointsArray[k]) && !line.contains(pointsArray[j])){ b2=true; } if(line.contains(pointsArray[j]) && line.contains(pointsArray[k]) && !line.contains(pointsArray[i])){ b3=true; } } if(b1 && b2 && b3){ count++; System.out.println(triangleOption); } } } } System.out.println("Total Triangles="+count); } } |
Below is the output of the above program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
Points are::[D, E, F, G, A, B, C, H, I, J, K] [D, E, F, G, A, B, C, H, I, J, K] DEA DFA DAC DCK EFA EAC ECJ FAC FCI GAB GAH GAI GIK ABH ABI ACI ACJ ACK AHI AIJ AIK AJK BCI HIJ Total Triangles=24 Points are::[A, B, C] [A, B, C] ABC Total Triangles=1 |
So the total number of triangles is 24, well I missed a lot in counting them. But now I have an easy way to do it, I hope it will help someone too for these kind of problems.