Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Time to dig up your old trigonometry notes from high school! The challenge is to solve the unknown sides and angles of different triangles. And as is customary in code golf, the smallest working code wins.

This is not a trivial problem; my reference implementation in python is currently down to 838 837 characters, but I'm sure you'll be able to golf solutions far smaller.

Additionally, if you're stuck, this section on Wikipedia should get you going: Triangle: Computing the sides and angles.

Input

The following triangle shows the names of the sides and angles used in this challenge. Note that sides are lowercase and angles are uppercase.

Triangle

Input is given as six space-separated values, either on stdin or as command-line arguments (your choice). The six values correspond to the sides a, b, c and the angles A, B, C. The unknown sides are given as question marks (?). Both input and output angles has to be in radians. You may assume that the input values are correct (you don't have to validate anything). You may also assume that the input triangle is non-degenerate, and that all sides and angles are nonzero.

The following example input tells you that side a is 8, side b is 12 and angle A is 0.5 radians:

8 12 ? 0.5 ? ?

Output

Output is given in the same format as the input - six space-separated numbers on stdout. The only exception is when it is not possible to solve the input triangle - then the string "No solution" must be written to stdout. If two solutions are possible, they are both outputted with a newline between them.

Following is the output for the above input:

8.0 12.0 16.0899264342 0.5 0.802561439714 1.83903121388
8.0 12.0 4.97205505116 0.5 2.33903121388 0.302561439714

Output is not required to have a lot of precision, but at least a couple decimals is required.

Rules

  • Input is read from stdin or command-line arguments
  • Output is written to stdout
  • If two solutions are possible with the given input, output both
  • If there is too little information to get one or two clear solutions, consider it a "No solution" case
  • No built-in or pre-existing code may be used (of course you can use trig functions, but not "solveTriangle" or such)
  • Shortest code wins

Test cases

In   3 4 5 ? ? ?

Out 3.0 4.0 5.0 0.643501108793 0.927295218002 1.57079630572


In   ? 4 ? 0.64 0.92 1.57

Out 3.00248479301 4.0 5.02764025486 0.64 0.92 1.57


In   ? ? 5 ? 0.92 ?

Out No solution


In   ? ? 5 ? 0.92 1.57

Out 3.03226857833 3.97800936148 5.0 0.65159265359 0.92 1.57


In   8 12 ? 0.5 ? ?

Out (two solutions)

8.0 12.0 16.0899264342 0.5 0.802561439714 1.83903121388
8.0 12.0 4.97205505116 0.5 2.33903121388 0.302561439714

In   8 12 ? ? .5 ?

Out 8.0 12.0 18.3912222133 0.325325285223 0.5 2.31626736837

Good luck!

share|improve this question
    
Can we assume that the triangle is non-degenerate, with all lengths and angles positive (in particular, nonzero)? –  boothby Jul 21 '11 at 19:28
    
@boothby Yes, you can. I'll update the OP. –  Håvard Jul 21 '11 at 19:34
1  
Also... if you want us to print all solutions, you need to provide at least one side. Otherwise, y'know, infinite solutions. –  boothby Jul 21 '11 at 20:27
    
@boothby, I was probably too unclear here. What I meant is, if there are two solutions to the input, you have to output both. –  Håvard Jul 21 '11 at 20:59
add comment

3 Answers

up vote 6 down vote accepted

Python, 441 chars

from math import*
V=[map(float,raw_input().replace('?','0').split())+[0]]
for i in' '*9:
 W=[]
 for a,b,c,A,B,C,R in V:
  if B and C:A=A or pi-B-C
  if a:
   if A:R=R or a/sin(A)
   else:
    if b and c:A=acos((b*b+c*c-a*a)/2/b/c)
    elif R:N=asin(a/R);W+=[(b,c,a,B,C,N,R)];A=pi-N
  else:a=R*sin(A)
  W+=[(b,c,a,B,C,A,R)]
 V=W
V=[T for T in V if all(t>0 for t in T)]
if V:
 for T in V:print' '.join(map(str,T[:-1]))
else:print'No solution'

Does your typical trig to compute the answer. The current possible solutions are stored as tuples in V. Any unknown values are recorded as 0. A seventh variable R is the value a/sin(A)==b/sin(B)==c/sin(C).

I use a trick where the a/b/c values are cycled each iteration to avoid lots of redundant logic. The inner loop only needs to compute values of the A side or angle.

share|improve this answer
    
I use a similar trick of cycling the variables, but you sure beat my solution. +1, learnt a couple new tricks from this :) –  Håvard Jul 21 '11 at 20:23
    
By the way, there is a problem with your code: try 8 12 ? ? .5 ?. –  Håvard Jul 21 '11 at 21:05
1  
You can get it to 419 bytes if you shave of the trailing line break and replace the two innermost indentations with one and two tabs, respectively. –  Joey Jul 21 '11 at 23:07
    
Hah, this looks very similar to my solution, too, though I hadn't noticed the "all solutions" until right after you posted this. You can save even more if you replace if a with if not a and flatten down the conditionals to 1 level. –  boothby Jul 22 '11 at 0:10
add comment

Plain C, 565 555 530 chars

C is not the best language for Code Golf, I guess, so it's just for fun.

float t[6],u[6],P=3.1415;x,w,j,k,D,E;
#define y(V) for(V=0;V<6;++V)
#define Y if(p[j]&&p[k]&&
#define A(o,s,a,b,c,A,B,C) z(float*p){y(D)y(E)if(j=D%3,k=E%3,j-k){Y c)w=C=acos((a*a+b*b-c*c)/2/a/b);if(A&&B)w=C=P-A-B;Y C)w=c=sqrt(a*a+b*b-2*a*b*cos(C));if(A&&B&&a)w=b=s(B)*a/s(A);Y A&&!B&&!C)w=B=(x=A<P/2&&a<b&&p==u,1-2*x)*(asin(b*s(A)/a)-x*P);}y(j)k=w&&(p==t||x>0)&&o("%f ",a);o("\n");}main(int l,char*q[]){y(j)sscanf(*++q,"%f",t+j),u[j]=t[j];z(t);z(u);j=w||o("No solution\n");}
A(printf,sin,p[j],p[k],p[3-j-k],p[j+3],p[k+3],p[6-j-k])

Compiled with cc -o trig trig.c -lm. Reads input as command line args.

share|improve this answer
    
This solution also fails for 8 12 ? ? .5 ? - I added it as an additional test case in the OP. –  Håvard Jul 22 '11 at 12:52
1  
Fixed! The length reduced as a side effect :) –  Alexander Bakulin Jul 22 '11 at 14:07
add comment

Perl - 412 chars

As a perl one-liner, based off of Keith Randall's Python Solution:

use Math::Trig;@V=((map{tr/?/0/;$_}@ARGV),0);map{my@W;while(($a,$b,$c,$A,$B,$C,$R)=splice@V,0,7){$A||=pi-$B-$C if($B*$C);if($a){if($A){$R||=$a/sin$A;}else{if($b*$c){$A=acos(($b*$b+$c*$c-$a*$a)/2/$b/$c);}elsif($R){$N=asin($a/$R);push@W,$b,$c,$a,$B,$C,$N,$R;$A=pi-$N;}}}else{$a=$R*sin$A;}push@W,$b,$c,$a,$B,$C,$A,$R if($a*$b*$c>=0);}@V=@W;}(1..9);print($V[0]?join' ',map{(((6-$i++)%7)?$_:"\n")}@V:"No solution\n");

Here in a more readable form:

use Math::Trig;
@V = ( ( map { tr/?/0/; $_ } @ARGV ), 0 );
map {
    my @W;
    while ( ( $a, $b, $c, $A, $B, $C, $R ) = splice @V, 0, 7 ) {
        $A ||= pi- $B - $C
             if ( $B * $C );
        if ($a) {
            if ($A) { $R ||= $a / sin $A; }
            else {
                if ( $b * $c ) {
                    $A = acos(
                        ( $b * $b + $c * $c - $a * $a ) / 2 / $b / $c );
                } elsif ($R) {
                    $N = asin( $a / $R );
                    push @W, $b, $c, $a, $B, $C, $N, $R;
                    $A = pi- $N;
                }
            }
        } else {
            $a = $R * sin $A;
        }
        push @W, $b, $c, $a, $B, $C, $A, $R
            if ( $a * $b * $c >= 0 );
    }
    @V = @W;
} ( 1 .. 9 );

print( $V[0]
         ? join ' ', map { ( ( ( 6 - $i++ ) % 7 ) ? $_ : "\n" ) } @V
         : "No solution\n" );
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.