package puzzle; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; /** * Solves the Triangle Challenge by iterating over all unique point triplets * and print out those where each point pair lies on a different line. * * Use a file with the following content as an input: 11 line1: 0 1 line2: 0 2 4 6 line3: 0 3 7 9 line4: 0 5 8 10 line5: 1 2 3 5 line6: 1 4 7 8 line7: 1 6 9 10 * * @see http://www.frank-buss.de/challenge/index.html * @author Filip Larsen */ public class TriangleCount { public static void main(String[] args) { try { for (int i = 0; i < args.length; i++) { TriangleCount puzzle = new TriangleCount(); puzzle.loadSetup(new FileInputStream(args[i])); System.out.println("Solutions for " + args[i]); puzzle.findSolutions(); System.out.println(puzzle.solutions + " solutions found"); System.out.println(); } } catch (Exception ex) { System.err.println(ex); } } private int n; // number of points private String[][] line; // identifies points on same line private int solutions; // solution count /** * Load setup of puzzle. First line of input is number of points. * The rest of lines, until empty line or end of file, are parsed * as "line-id p1 p2 p3 ..." where the p's are integers in the * range [0;number of points[ identifying the points that lie on * the given line. */ public void loadSetup(InputStream in) throws NumberFormatException, IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(in)); n = Integer.parseInt(reader.readLine()); line = new String[n][]; for (int i = 0; i < n; i++) { line[i] = new String[n]; } String s = reader.readLine(); while (s != null && s.trim().length() > 0) { String[] p = s.split("\\s"); for (int i = 1; i < p.length; i++) { for (int j = i+1; j < p.length; j++) { line[Integer.parseInt(p[i])][Integer.parseInt(p[j])] = p[0]; } } s = reader.readLine(); } } /** * Find solutions by iterating over all unique triplets (p1,p2,p3) and print * out a solution when (p1,p2), (p1,p3) and (p2,p3) all lie on a different * line. */ public void findSolutions() { for (int p1 = 0; p1 < n; p1++) { for (int p2 = p1+1; p2 < n; p2++) { String l1 = line[p1][p2]; if (l1 == null) continue; for (int p3 = p2+1; p3 < n; p3++) { String l2 = line[p1][p3]; String l3 = line[p2][p3]; if (l2 == null || l3 == null || l2 == l1 || l3 == l1 || l2 == l3) continue; System.out.println((++solutions) + ": (P" + p1 + ", P" + p2 + ", P" + p3 + ")"); } } } } }