Tuesday, April 14, 2015

Counting Triangles

Problem: Count the number of triangles shown in the following figure.


Solution: Label all the vertices as 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 from top to bottom, left to right. 


There are 7 lines, each line with a few vertices on it.

  Line 1: {0, 1, 7},
    Line 2:     {0, 2, 6, 8},
    Line 3: {0, 3, 5, 9},
    Line 4:     {0, 4, 10},
    Line 5:     {1, 2, 3, 4},
    Line 6:     {4, 5, 6, 7},
    Line 7:     {7, 8, 9, 10}.   

We examine all triples, and check whether three vertices form a valid triangle:
  • These vertices cannot all lie on the same line.
  • Each pair of these vertices should lie on the same line.

Output of the following Java code: 

Triangle 1: (0, 1, 2)
Triangle 2: (0, 1, 3)
Triangle 3: (0, 1, 4)
Triangle 4: (0, 2, 3)
Triangle 5: (0, 2, 4)
Triangle 6: (0, 3, 4)
Triangle 7: (0, 4, 5)
Triangle 8: (0, 4, 6)
Triangle 9: (0, 4, 7)
Triangle 10: (0, 5, 6)
Triangle 11: (0, 5, 7)
Triangle 12: (0, 6, 7)
Triangle 13: (0, 7, 8)
Triangle 14: (0, 7, 9)
Triangle 15: (0, 7, 10)
Triangle 16: (0, 8, 9)
Triangle 17: (0, 8, 10)
Triangle 18: (0, 9, 10)
Triangle 19: (1, 4, 7)
Triangle 20: (2, 4, 6)
Triangle 21: (3, 4, 5)
Triangle 22: (4, 7, 10)
Triangle 23: (5, 7, 9)
Triangle 24: (6, 7, 8)

Code in Java: (still need to figure out the best way to paste code here)

    public void countTriangles() {
     int[][] linesAdjArray = new int[][] {
      {0, 1, 7},
      {0, 2, 6, 8},
      {0, 3, 5, 9},
      {0, 4, 10},
      {1, 2, 3, 4},
      {4, 5, 6, 7},
      {7, 8, 9, 10},        
     };
     int numTriangles = 0;
     int numVectices = 11;
     for (int i = 0; i < numVectices - 2; i++) {
      for (int j = i + 1; j < numVectices - 1; j++) {
       for (int k = j + 1; k < numVectices; k++) {
        if (
         !isCollinear(linesAdjArray, i, j, k) &&
         isConnected(linesAdjArray, i, j) &&
         isConnected(linesAdjArray, i, k) &&
         isConnected(linesAdjArray, j, k)
        ) {
         numTriangles++;
         String triangleInfo = 
           "Triangle " + numTriangles + ": " +
           "("  + i + ", " + j + ", " + k + ")";
         System.out.println(triangleInfo);
        } 
       }
      }
     }
     return;
    }
    
    public boolean isCollinear(
     int[][] linesAdjArray, 
     int a, 
     int b, 
     int c
    ) {
     for (int[] lineAdjArray : linesAdjArray) {
      if (
       Arrays.binarySearch(lineAdjArray, a) >= 0 &&
       Arrays.binarySearch(lineAdjArray, b) >= 0 &&      
       Arrays.binarySearch(lineAdjArray, c) >= 0
      ) {
       return true;
      }
     }
     return false;
    }
    
    public boolean isConnected(
     int[][] linesAdjArray, 
     int a, 
     int b
    ) {
     for (int[] lineAdjArray : linesAdjArray) {
      if (
       Arrays.binarySearch(lineAdjArray, a) >= 0 &&
       Arrays.binarySearch(lineAdjArray, b) >= 0      
      ) {
       return true;
      }
     }
     return false;
    }

No comments:

Post a Comment