Triangle Trilemma

January 18, 2013

Today’s exercise is Problem A from the Google Code Jam Beta 2008. The problem is to accept three points as input, determine if they form a triangle, and, if they do, classify it at equilateral (all three sides the same), isoceles (two sides the same, the other different), or scalene (all three sides different), and also classify it as acute (all three angles less than 90 degrees), obtuse (one angle greater than 90 degrees) or right (one angle equal 90 degrees).

Your task is to write the triangle classifier. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

10 Responses to “Triangle Trilemma”

  1. Jussi Piitulainen said

    Someone posted complex-arithmetic solutions to an earlier problem where there were four points. I found that interesting. Here is an attempt to determine the three angles, in increasing order, that works by translating and rotating the triangle with complex arithmetic so that each point in turn is at the origin, one side extends to the right, and then the angle is the angle of the polar form of the remaining point.

    (define (ang x y z) (abs (angle (/ (- x y) (- x z))))) ;angle at point x        
    (define (med a b c) (max (min a b) (min a c) (min b c))) ;median of three       
    
    (define (angles x y z) ;points as complex numbers                               
      (let ((a (ang x y z)) (b (ang y x z)) (c (ang z y x))) ;angles                
        (list (min a b c) (med a b c) (max a b c)))) ;increasing angles
    

    One could then compare the angles (all within epsilon of each other, or first two, or last two, or not), or compare the third angle to a straight angle (within epsilon, more than epsilon smaller, or larger), to arrive at the requested classifications.

  2. Jussi Piitulainen said

    Here’s what I used to test my code: construct various known triangles in different positions and compute their angles. The code appeared to work. The errors, where not 0, were on the order of 10 to the power -16, which is what floating point does. (Complex division was buggy in an ancient, year 2003, version of Guile; a newer Guile worked beautifully.) (I paid little attention to non-triangles. These would either crash arithmetically or produce zero or straight angles.)

    ;;; Expected results e<k> for <k> = 1, ..., 6                                   
    (define tau (* 2 (angle -1))) ;right angle = tau/4                              
    (define e1 (list (/ tau 8) (/ tau 8) (/ tau 4)))
    (define e2 (list (/ tau 6) (/ tau 6) (/ tau 6)))
    (define e3 (list (/ tau 12) (/ tau 6) (/ tau 4)))
    (define e4 (list (/ tau 8) (/ tau 6) (* tau (+ 1/12 1/8))))
    (define e5 (list (/ tau 12) (/ tau 12) (/ tau 3)))
    (define e6 (list (/ tau 12) (/ tau 8) (* tau (+ 1/6 1/8))))
    
    ;;; Expect (apply angles t<k>) = e<k>                                           
    (define t1 (list 0+0i 3+0i 0+3i))
    (define t2 (list -1+0i 1+0i (make-rectangular 0 (sqrt 3))))
    (define t3 (list -1+0i 0+0i (make-rectangular 0 (sqrt 3))))
    (define t4 (list -1+0i (make-rectangular 0 (sqrt 3))
                     (make-rectangular (sqrt 3) 0)))
    (define t5 (list (make-rectangular 0 (sqrt 3))
                     (make-rectangular 0 (- (sqrt 3))) -1+0i))
    (define t6 (list (make-rectangular (- (sqrt 3)) -1) 0+0i 1-1i))
    
    ;;; Expect (apply angles u<k>) = (apply angles t<k>) = e<k>                     
    (define (move u w) (lambda (x) (/ (- x u) (/ w (magnitude w)))))
    (define u1 (map (move 3-i 4-i) t1))
    (define u2 (map (move 3-i 4-i) t2))
    (define u3 (map (move 3-i 4-i) t3))
    (define u4 (map (move 3-i 4-i) t4))
    (define u5 (map (move 3-i 4-i) t5))
    (define u6 (map (move 3-i 4-i) t6))
    
    ;;; Expect (diff e<k> t<k>) = (list 0.0 0.0 0.0) +- small error                 
    (define (diff e t) (map - e (apply angles t)))
    
  3. cosmin said

    A python solution:

    def dist(A, B):
    	return (A[0] - B[0])**2 + (A[1] - B[1])**2
    
    def dot_prod(A, B, C):
    	return (A[0] - B[0])*(C[0] - B[0]) + (A[1] - B[1])*(C[1] - B[1])
    
    def cross_prod(A, B, C):
    	return (A[0] - B[0])*(C[1] - B[1]) + (A[1] - B[1])*(C[0] - B[0])
    
    def classify_triangle(A, B, C):
    	s = sorted([cross_prod(A, B, C), cross_prod(B, C, A), cross_prod(C, A, B)])
    	if s[0] == 0:
    		return "not a triangle"
    	res = ""
    	d = sorted([dist(A, B), dist(B, C), dist(C, A)])
    	if d[0] == d[2]:
    		res = "equilateral "
    	elif d[0] == d[1] or d[1] == d[2]:
    		res = "isosceles "
    	else:
    		res = "scalene "
    	p = sorted([dot_prod(A, B, C), dot_prod(B, C, A), dot_prod(C, A, B)])
    	if p[0] < 0:
    		res += "obtuse "
    	elif p[0] == 0:
    		res += "right "
    	else:
    		res += "acute "
    	return res + "triangle"
    
    print classify_triangle((0, 0), (0, 4), (1, 2))
    print classify_triangle((1, 1), (1, 4), (3, 2))
    print classify_triangle((2, 2), (2, 4), (4, 3))
    print classify_triangle((3, 3), (3, 4), (5, 3))
    print classify_triangle((4, 4), (4, 5), (5, 6))
    print classify_triangle((5, 5), (5, 6), (6, 5))
    print classify_triangle((6, 6), (6, 7), (6, 8))
    print classify_triangle((7, 7), (7, 7), (7, 7))
    
  4. cosmin said

    It looks that the correct definition of the cross product has a “-” instead of a “+” in the middle:

    def cross_prod(A, B, C):
    	return (A[0] - B[0])*(C[1] - B[1]) - (A[1] - B[1])*(C[0] - B[0])
    
  5. jpv said

    Here’s my take in Racket: Triangle Trilemma

    It’s a bit longer than I expected, but I think it’s pretty solid. If anyone has any counter examples (like there were with the squares problem), I’d love to hear them.

  6. Here is whole solution in Java with self explanatory doc

    package in.kumarpallav.triangle;

    import java.util.Arrays;
    import java.util.Scanner;

    /**
    * The problem is to accept three points as input, determine if they form a
    * triangle, and, if they do, classify it at equilateral (all three sides the
    * same), isoceles (two sides the same, the other different), or scalene (all
    * three sides different), and also classify it as acute (all three angles less
    * than 90 degrees), obtuse (one angle greater than 90 degrees) or right (one
    * angle equal 90 degrees).
    *
    * Following are conditions
    * 1. Any three point on a plane can make a triangle if
    * and only if all three are not on same line i.e. they don’t make a straight
    * line
    * 2. To be a equilateral triangle all three sides should mesure same, All equilateral triangle are always
    * of 60 degree with each of the angle all three sides are less than 90
    * 3. If two sides are of same length two it is an right angle triangle
    * 4. Obviously if 1 side is greater than 90 degree it’s obtuse
    * # Modularity
    *
    *
    * @author Kumar Pallav
    *
    */
    public class Main {
    private static String userInput=””;
    private static Scanner scanner;
    private static String typeOfTriangle;
    public static void main (String args[]){
    //Lets Print Instruction to user to enter command line input
    instruction();
    //Lets Take User Input from console
    while(true){
    try{
    scanner = new Scanner(System.in);
    userInput=scanner.nextLine();
    //Validate user input
    if(isUserInputValid(userInput.split(” “))){//This will ensure that user input are valid then only we need to proceed further
    //Lets validate if the input are line forms a triangle
    isTrianglePossible(userInput.split(” “));

    }

    }catch (Exception e){
    System.out.println(“\n Something has gone wrong , we appologise”);

    }

    }
    }
    /**
    * The method below will check if it is possible to make a triangle and is Yes it should proceed for
    * @param userInput
    */
    private static void isTrianglePossible(String coordinates[]) {
    //Only case where there could be no triangle when all provided coordinates are on same plane
    //i.e. either all x or y coordinates are same
    double xCords[]=new double[3];
    double yCords[]=new double[3];
    String split[]=null;
    for (int i=0;i90 degree. There can be one and only one obtuse angle , it comes as 90 degree
    //certainly we have right angle triangle else we have acute angle triangle
    //Step 1: Calculate all the distance
    double d1,d2,d3;//All Sides of coordinates
    d1=calculateDistance(xCords[0],yCords[0],xCords[1],yCords[1]);
    d2=calculateDistance(xCords[0],yCords[0],xCords[2],yCords[2]);
    d3=calculateDistance(xCords[1],yCords[1],xCords[2],yCords[2]);
    if((xCords[0]==xCords[1])&&(xCords[1]==xCords[2])&&(xCords[0]==xCords[2])||
    (yCords[0]==yCords[1])&&(yCords[1]==yCords[2])&&(yCords[0]==yCords[2])){
    System.out.println(“Provided cordinates make a staight line, No triangle possible”);
    }else
    if(d1==0&&d2==0&&d3==0){

    System.out.println(“No triangle possible,It is a point”);
    }else if(d1==0||d2==0||d3==0){

    System.out.println(“No triangle possible,Two coordinates are same”);
    }
    else if(d1==d2&&d2==d3&&d1==d3){
    typeOfTriangle=”Equilateral”;
    System.out.println(“Equilateral Triangle “);
    }else{
    //Find Largest of three provided d1, d2 and d3, the easiest is to sort so that highest one comes in beginning
    if(d1==d2||d2==d3||d3==d1){
    typeOfTriangle=”isosceles”;
    }else{

    typeOfTriangle=”scalene”;
    }
    double sortedDistance[]={d1,d2,d3};
    Arrays.sort(sortedDistance);
    //With Sorted
    findAnglesAndDecide(sortedDistance);
    }

    }

    private static void findAnglesAndDecide(double[] sortedDistance) {
    //find cosine of angle largest in java
    double num=(Math.pow(sortedDistance[0], 2))+(Math.pow(sortedDistance[1],2))-(Math.pow(sortedDistance[2],2));
    double den=2*sortedDistance[0]*sortedDistance[1];
    double cos=num/den;
    //System.out.println(“Cos :”+cos);
    double degree = Math.acos(cos) * 180/Math.PI;
    if(degree>90){
    System.out.println(typeOfTriangle+ ” obtuse triangle”);
    }else if(degree==90){

    System.out.println(typeOfTriangle+” right angle triangle”);
    }else{
    System.out.println(typeOfTriangle+” acute triangle”);
    }

    }
    /**
    *
    * @param x1 :x1 cord
    * @param y1 :y1 cord
    * @param x2 :x2 cord
    * @param y2 :y2 cord
    * @return
    */
    private static double calculateDistance(double x1, double y1, double x2,
    double y2) {
    return Math.sqrt(Math.pow((x2-x1),2)+Math.pow((y2-y1),2));
    }
    /**
    * The code below checks the user input and validates the cordinates
    * if Proper it returns true else value
    * @param args
    * @return
    */
    public static boolean isUserInputValid(String args[]){
    boolean isInputValid=true;
    switch (args.length) {
    case 3:
    //iterate over input and find if they are in order and proper
    String cords[]=null;
    for(String a:args){
    cords =a.split(“,”);
    if(cords.length!=2){
    System.out.println(“Provided cordinates are not valid”);
    break;

    }//If there are two coordinates per input lets verify if we they are in floating point else coordinates are not proper
    else{
    try{
    for(String cord: cords){
    validateCordinates(cord);
    }
    }catch(NumberFormatException nfe){
    System.out.println(“Provided cordinates are not valid”);
    isInputValid=false;//If number format exception happens provided inputs are not valid
    break;
    }
    }

    }
    break;

    default:
    System.out.println(“Input provided is not valid”);
    break;
    }
    return isInputValid;
    }
    /**
    * @param a
    * @throws NumberFormatException
    */
    private static void validateCordinates(String a) throws NumberFormatException {
    double d=Double.parseDouble(a);

    }
    /**
    * instruction This will print instruction
    * @author Kumar Pallav
    */
    public static void instruction(){
    String instruction=”****Welcome to triangle program*****\n” +
    “To find the if the provided co-orodinates makes a triangle , Please enter input as ” +
    “\n x,y x,y x,y \n\t where x and y are co-ordinated ” +
    “\n To Quit enter exit”;
    System.out.println(instruction);
    }

    }

  7. Ali said

    Hello, I am a bignner in python. I really need codes of prime and kruskal which will works on python runner. I was wondering if you could help me and send me the codes or give me precise info about these two codes. my email address is elfetop2012@yahoo.com. best wishes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 647 other followers

%d bloggers like this: