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.
Programming Praxis 
[…] Question is from here: […]
Java solution here.
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 anglesOne 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.
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)))[…] Pages: 1 2 […]
A python solution:
It looks that the correct definition of the cross product has a “-” instead of a “+” in the middle:
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.
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);
}
/**
*
instructionThis 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);
}
}
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