Notes

The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not.

We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin. Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.

Implementation

Implementing this solution required some somewhat complicated logic to decide which points to draw which lines from and to. I'm not sure how to avoid this. Here are the decisions and the decision criteria involved:

First, determine the "parity" of the triangle - how many points have positive x values, minus how many points have negative x values. If the parity is not 1 or -1, the triangle cannot contain the origin.
One of the endpoints will be used in both lines that we draw. This is the point whose x value has the opposite sign as our parity.
- If the parity of the triangle is positive (meaning there are two endpoints on the positive x side) we should use the negative x endpoint for both of our lines
- If the parity of the triangle is negative (two endpoints are on negative x side) we should use positive x endpoint for both lines
The other two endpoints should each be used once in each of the two lines.

Code

To get this knocked out, I used Java and coded up some useful geometry classes - point, line, and triangle.

Main and test

import java.util.*;
import java.io.*;

public class Triangles {
	public static void main(String[] args) throws FileNotFoundException { 
		solve();
	}

	/** Test things are working ok. */
	public static void test() { 

		String points1 = "-340,495,-153,-910,835,-947";
		Triangle t1 = new Triangle(points1);
		if(t1.containsOrigin()) { 
			System.out.println("Triangle 1 test passed.");
		} else {
			System.out.println("Triangle 1 test failed.");
		}
		
		String points2 = "-175,41,-421,-714,574,-645";
		Triangle t2 = new Triangle(points2);
		if(!t2.containsOrigin()) { 
			System.out.println("Triangle 2 test passed.");
		} else {
			System.out.println("Triangle 2 test failed.");
		}

	}

	/** Solve the actual PE problem. */
	public static void solve() throws FileNotFoundException { 
		// Scan the file to populate list of triangles
		ArrayList<Triangle> ts = new ArrayList<Triangle>();
		Scanner s = new Scanner(new BufferedReader(new FileReader("p102_triangles.txt")));
		while(s.hasNextLine()){
			String line = s.nextLine();
			ts.add(new Triangle(line));
		}

		// Count number of triangles containing origin
		int count = 0;
		for(Triangle t : ts) {
			if(t.containsOrigin()) { 
				count++;
			}
		}

		System.out.println(count);
	}

Triangle, line, and point classes

	/** Triangle class */
	protected static class Triangle {

		/** 
		 * Point class implementation:
		 * this is used to represent an (x,y) 
		 * Cartesian point, particularly the 
		 * endpoint of a triangle.
		 */
		protected static class Point { 
			protected int x;
			protected int y;
			public Point(int x, int y) {
				this.x = x; this.y = y;
			}
			public String toString() { 
				StringBuffer sb = new StringBuffer();
				sb.append("(");
				sb.append(this.x);
				sb.append(",");
				sb.append(this.y);
				sb.append(")");
				return sb.toString();
			}
		}
		
		/** 
		 * Line class implementation:
		 * this is used to go between points, 
		 * slopes, and y-intercepts.
		 */
		protected static class Line {
			boolean p1set, p2set;
			protected Point p1, p2;
			public Line() {}
			public void setPoint1(Point p1) {
				this.p1 = p1;
				this.p1set = true;
			}
			public void setPoint2(Point p2) { 
				this.p2 = p2;
				this.p2set = true;
			}
			public double getSlope() {
				if(p1set!=true) { 
					throw new IllegalStateException("point 1 not set");
				} else if(p2set!=true) { 
					throw new IllegalStateException("point 2 not set");
				}
				return (p1.y-p2.y)/(1.0*(p1.x-p2.x));
			}
			public double getIntercept() { 
				return p1.y - getSlope()*p1.x;
			}
		}


		/** 
		 * Triangle class implementation:
		 * uses the above Point and Line classes
		 * to represent a triangle and determine
		 * if it contains the origin.
		 */

		ArrayList<Point> points;

		/** Constructor turns a line of 6 CSV integers into 3 points. */
		public Triangle(String line) { 
			String[] arr = line.split(",");
			int[] intarr = new int[arr.length];
			for(int i=0; i<arr.length; i++) { 
				intarr[i] = Integer.parseInt(arr[i]);
			}

			// Save the 3 points
			points = new ArrayList<Point>();
			for(int i=0; i<3; i++) { 
				points.add(new Point(intarr[i*2], intarr[i*2+1]));
			}
		}

		/** Turn this triangle into a string. */
		public String toString() {
			StringBuffer sb = new StringBuffer();
			sb.append("< ");
			for(Point p : points) { 
				sb.append(p.toString());
				sb.append(", ");
			}
			sb.append(" > ");
			return sb.toString();
		}

		/** How many endpoints with negative x coordinates does this triangle have? */
		protected int countNegativeX() {
			int negativeCount = 0
			for(Point p : points) { 
				if(p.x<0) { 
					negativeCount++;
				}
			}
			return negativeCount;
		}

		/** How many endpoints with positive x coordinates does this triangle have? */
		protected int countPositiveX() { 
			int positiveCount = 0;
			for(Point p : points) { 
				if(p.x>0) { 
					positiveCount++;
				}
			}
			return positiveCount;
		}

		/** What is the parity (positive minus negative) of x coordinates? */
		protected int parityX() { 
			return countPositiveX() - countNegativeX();
		}

Core functionality - containsOrigin

The last method in the Triangle class checks if this triangle contains the origin. This is the heart of the problem.


		/** Boolean: does this triangle contain the origin? */
		public boolean containsOrigin() { 
			// parity is number of +x points minus number of -x points
			int parity = parityX();

			// If the parity is not 1, there is no way the triangle contains the origin.
			if(Math.abs(parity)==1) { 
				Line l1 = new Line();
				Line l2 = new Line();

				// If the parity is one, we have to figure out if the +x/-x partitions
				// contain one or two points, respectively.
				int whichLine = 1;
				for(Point p : points) { 

					// If x is the same sign as parity, we have two points on this side.
					// In that case, we want this point to be line's second point.
					boolean matchingParity = (parity>0 && p.x>0) || (parity<0 && p.x<0);

					if(matchingParity) { 
						if(whichLine==1) { 
							l1.setPoint2(p);
							whichLine++;
						} else {
							l2.setPoint2(p);
						}

					} else {
						// Otherwise, the sign of this point's x coordinate 
						// is the opposite of the parity of this triangle,
						// so we make i point 1 for both lines.
						l1.setPoint1(p);
						l2.setPoint1(p);

					}
				}
				boolean containsOrigin = (l1.getIntercept()>0 && l2.getIntercept()<0) || (l1.getIntercept()<0 && l2.getIntercept()>0);
				return containsOrigin;

			} else {
				return false;
			}
		}
	}
}

Flags

Project Euler/Problem 102

From charlesreid1

Contents