Law of cosines - triples: Difference between revisions
m (→{{header|REXX}}: changed some comments.) |
m (→{{header|REXX}}: added a memoized version, this version also solves the extra credit requirement.) |
||
| Line 377: | Line 377: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===using some optimization=== |
|||
Instead of coding a general purpose subroutine (or function) to solve all of the |
Instead of coding a general purpose subroutine (or function) to solve all of the |
||
task's requirements, it was decided to |
task's requirements, it was decided to |
||
| Line 470: | Line 469: | ||
(13, 13, 13) |
(13, 13, 13) |
||
15 solutions found for 60º (sides up to 13)) |
15 solutions found for 60º (sides up to 13)) |
||
</pre> |
|||
===using memoization=== |
|||
<lang rexx>/*REXX pgm finds integer sided triangles that satisfy Law of cosines for 60º, 90º, 120º.*/ |
|||
parse arg s1 s2 s3 s4 . /*obtain optional arguments from the CL*/ |
|||
if s1=='' | s1=="," then s1= 13 /*Not specified? Then use the default.*/ |
|||
if s2=='' | s2=="," then s2= 13 /* " " " " " " */ |
|||
if s3=='' | s3=="," then s3= 13 /* " " " " " " */ |
|||
if s4=='' | s4=="," then s4= -10000 /* " " " " " " */ |
|||
parse value s1 s2 s3 s4 with os1 os2 os3 os4 . /*obtain the original values for sides.*/ |
|||
s1=abs(s1); s2=abs(s2); s3=abs(s3); s4=abs(s4) /*use absolute values for the # sides. */ |
|||
@.= |
|||
do j=1 for max(s1, s2, s3, s4); @.j = j*j |
|||
end /*j*/ /*build memoization array for squaring.*/ |
|||
if s1>0 then do; call head 120,,os1 /*────120º: a² + b² + ab ≡ c² */ |
|||
do a=1 for s1 |
|||
do b=a+1 to s1; x= @.a + @.b + a*b |
|||
if x>z then iterate a |
|||
do c=b+1 to s1 until @.c>x |
|||
if x==@.c then do; call show; iterate b; end |
|||
end /*c*/ |
|||
end /*b*/ |
|||
end /*a*/ |
|||
call foot s1 |
|||
end |
|||
if s2>0 then do; call head 90,, os2 /*────90º: a² + b² ≡ c² */ |
|||
do a=1 for s2 |
|||
do b=a+1 to s2; x= @.a + @.b |
|||
if x>z then iterate a |
|||
do c=b+1 to s2 until @.c>x |
|||
if x==@.c then do; call show; iterate b; end |
|||
end /*c*/ |
|||
end /*b*/ |
|||
end /*a*/ |
|||
call foot s2 |
|||
end |
|||
if s3>0 then do; call head 60,, os3 /*────60º: a² + b² ─ ab ≡ c² */ |
|||
do a=1 for s3 |
|||
do b=a to s3; x= @.a + @.b - a*b |
|||
if x>z then iterate a |
|||
do c=a to s3 until @.c>x |
|||
if x==@.c then do; call show; iterate b; end |
|||
end /*c*/ |
|||
end /*b*/ |
|||
end /*a*/ |
|||
call foot s3 |
|||
end |
|||
if s4>0 then do; call head 60, 'unique', os4 /*────60º: a² + b² ─ ab ≡ c² */ |
|||
do a=1 for s4 |
|||
do b=a to s4; x= @.a + @.b - a*b |
|||
if x>z then iterate a |
|||
do c=a to s4 until @.c>x |
|||
if x==@.c then do; if a==b&a==c then iterate b |
|||
call show; iterate b |
|||
end |
|||
end /*c*/ |
|||
end /*b*/ |
|||
end /*a*/ |
|||
call foot s4 |
|||
end |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
foot: say right(# ' solutions found for' ang "(sides up to" arg(1)')', 65); say; return |
|||
head: #=0; arg d,,s;z=s*s;w=length(s); ang=' 'd"º " arg(2); say center(ang,65,'═'); return |
|||
show: #= # + 1; if s>0 then say ' ('right(a,w)"," right(b,w)"," right(c,w)')'; return</lang> |
|||
{{out|output|text= when using the inputs of: <tt> 0 0 0 -10000 </tt>}} |
|||
Note that the first three computations are bypassed because of the three zero ('''0''') numbers, the negative ten thousand indicates to find all the triangles with sides up to 10,000, but not list the triangles, it just reports the ''number'' of triangles found. |
|||
<pre> |
|||
══════════════════════════ 60º unique═══════════════════════════ |
|||
18394 solutions found for 60º unique (sides up to 10000) |
|||
</pre> |
</pre> |
||
Revision as of 11:02, 24 September 2018
The Law of cosines states that for an angle γ, (gamma) of any triangle, if the sides adjacent to the angle are A and B and the side opposite is C; then the lengths of the sides are related by this formula:
A2 + B2 - 2ABcos(γ) = C2
- Specific angles
For an angle of of 90º this becomes the more familiar "Pythagoras equation":
A2 + B2 = C2
For an angle of 60º this becomes the less familiar equation:
A2 + B2 - AB = C2
And finally for an angle of 120º this becomes the equation:
A2 + B2 + AB = C2
- Task
- Find all integer solutions (in order) to the three specific cases, distinguishing between each angle being considered.
- Restrain all sides to the integers 1..13 inclusive.
- Show how many results there are for each of the three angles mentioned above.
- Display results on this page.
Note: Triangles with the same length sides but different order are to be treated as the same.
- Optional Extra credit
- How many 60° integer triples are there for sides in the range 1..10_000 where the sides are not all of the same length.
- Related Task
- See also
- Visualising Pythagoras: ultimate proofs and crazy contortions Mathlogger Video
ALGOL 68
<lang algol68>BEGIN
# find all integer sided 90, 60 and 120 degree triangles by finding integer solutions for #
# a^2 + b^2 = c^2, a^2 + b^2 - ab = c^2, a^2 + b^2 + ab = c^2 where a, b, c in 1 .. 13 #
INT max side = 13; # max triangle side to consider #
INT max square = max side * max side; # max triangle side squared to consider #
[ 1 : max square ]INT root; # table of square roots #
FOR s TO UPB root DO root[ s ] := 0 OD;
FOR s TO max side DO root[ s * s ] := s OD;
INT tcount := 0;
[ 1 : max square ]INT ta, tb, tc, tangle;
# prints solutions for the specified angle #
PROC print triangles = ( INT angle )VOID:
BEGIN
INT scount := 0;
FOR t TO tcount DO IF tangle[ t ] = angle THEN scount +:= 1 FI OD;
print( ( whole( scount, -4 ), " ", whole( angle, -3 ), " degree triangles:", newline ) );
FOR t TO tcount DO
IF tangle[ t ] = angle THEN
print( ( " ", whole( ta[ t ], -3 ), whole( tb[ t ], -3 ), whole( tc[ t ], -3 ), newline ) )
FI
OD
END # print triangles # ;
# stores the triangle with sides a, b, root[ c2 ] and the specified angle, #
# if it is a solution #
PROC try triangle = ( INT a, b, c2, angle )VOID:
IF c2 <= max square THEN
# the third side is small enough #
INT c = root[ c2 ];
IF c /= 0 THEN
# the third side is the square of an integer #
tcount +:= 1;
ta[ tcount ] := a; tb[ tcount ] := b; tc[ tcount ] := root[ c2 ];
tangle[ tcount ] := angle
FI
FI # try triangle # ;
# find all triangles #
FOR a TO max side DO
FOR b FROM a TO max side DO
try triangle( a, b, ( a * a ) + ( b * b ) - ( a * b ), 60 );
try triangle( a, b, ( a * a ) + ( b * b ), 90 );
try triangle( a, b, ( a * a ) + ( b * b ) + ( a * b ), 120 )
OD
OD;
# print the solutions #
print triangles( 60 );
print triangles( 90 );
print triangles( 120 )
END</lang>
- Output:
15 60 degree triangles:
1 1 1
2 2 2
3 3 3
3 8 7
4 4 4
5 5 5
5 8 7
6 6 6
7 7 7
8 8 8
9 9 9
10 10 10
11 11 11
12 12 12
13 13 13
3 90 degree triangles:
3 4 5
5 12 13
6 8 10
2 120 degree triangles:
3 5 7
7 8 13
Factor
<lang factor>USING: backtrack formatting kernel locals math math.ranges sequences sets sorting ; IN: rosetta-code.law-of-cosines
- triples ( quot -- seq )
[
V{ } clone :> seen
13 [1,b] dup dup [ amb-lazy ] tri@ :> ( a b c )
a sq b sq + a b quot call( x x x -- x ) c sq =
{ b a c } seen member? not and
must-be-true { a b c } dup seen push
] bag-of ;
- show-solutions ( quot angle -- )
[ triples { } like dup length ] dip rot
"%d solutions for %d degrees:\n%u\n\n" printf ;
[ * + ] 120 [ 2drop 0 - ] 90 [ * - ] 60 [ show-solutions ] 2tri@</lang>
- Output:
2 solutions for 120 degrees:
{ { 3 5 7 } { 7 8 13 } }
3 solutions for 90 degrees:
{ { 3 4 5 } { 5 12 13 } { 6 8 10 } }
15 solutions for 60 degrees:
{
{ 1 1 1 }
{ 2 2 2 }
{ 3 3 3 }
{ 3 8 7 }
{ 4 4 4 }
{ 5 5 5 }
{ 5 8 7 }
{ 6 6 6 }
{ 7 7 7 }
{ 8 8 8 }
{ 9 9 9 }
{ 10 10 10 }
{ 11 11 11 }
{ 12 12 12 }
{ 13 13 13 }
}
Go
<lang go>package main
import "fmt"
type triple struct{ a, b, c int }
var squares13 = make(map[int]int, 13) var squares10000 = make(map[int]int, 10000)
func init() {
for i := 1; i <= 13; i++ {
squares13[i*i] = i
}
for i := 1; i <= 10000; i++ {
squares10000[i*i] = i
}
}
func solve(angle int, maxLen int, allowSame bool) []triple {
var solutions []triple
for a := 1; a <= maxLen; a++ {
for b := a; b <= maxLen; b++ {
lhs := a*a + b*b
if angle != 90 {
switch angle {
case 60:
lhs -= a * b
case 120:
lhs += a * b
default:
panic("Angle must be 60, 90 or 120 degrees")
}
}
switch maxLen {
case 13:
if c, ok := squares13[lhs]; ok && c <= 13 {
if !allowSame && a == b && b == c {
continue
}
solutions = append(solutions, triple{a, b, c})
}
case 10000:
if c, ok := squares10000[lhs]; ok && c <= 10000 {
if !allowSame && a == b && b == c {
continue
}
solutions = append(solutions, triple{a, b, c})
}
default:
panic("Maximum length must be either 13 or 10000")
}
}
}
return solutions
}
func main() {
fmt.Print("For sides in the range [1, 13] ")
fmt.Println("where they can all be of the same length:-\n")
angles := []int{90, 60, 120}
var solutions []triple
for _, angle := range angles {
solutions = solve(angle, 13, true)
fmt.Printf(" For an angle of %d degrees", angle)
fmt.Println(" there are", len(solutions), "solutions, namely:")
fmt.Printf(" %v\n", solutions)
fmt.Println()
}
fmt.Print("For sides in the range [1, 10000] ")
fmt.Println("where they cannot ALL be of the same length:-\n")
solutions = solve(60, 10000, false)
fmt.Print(" For an angle of 60 degrees")
fmt.Println(" there are", len(solutions), "solutions.")
}</lang>
- Output:
For sides in the range [1, 13] where they can all be of the same length:-
For an angle of 90 degrees there are 3 solutions, namely:
[{3 4 5} {5 12 13} {6 8 10}]
For an angle of 60 degrees there are 15 solutions, namely:
[{1 1 1} {2 2 2} {3 3 3} {3 8 7} {4 4 4} {5 5 5} {5 8 7} {6 6 6} {7 7 7} {8 8 8} {9 9 9} {10 10 10} {11 11 11} {12 12 12} {13 13 13}]
For an angle of 120 degrees there are 2 solutions, namely:
[{3 5 7} {7 8 13}]
For sides in the range [1, 10000] where they cannot ALL be of the same length:-
For an angle of 60 degrees there are 18394 solutions.
Haskell
<lang haskell>import Data.List (groupBy, nub, sort, sortBy) import Data.Ord (comparing) import Data.Function (on) import Data.Monoid ((<>)) import Control.Arrow (second)
triplesFound :: Int -> [(Int, [(Int, Int)])] triplesFound n =
let xs = ((,) <*> (^ 2)) <$> [1 .. n] :: [(Int, Int)]
in xs >>=
\x ->
xs >>=
\y ->
xs >>=
\z ->
let d = snd z - (snd x + snd y)
in if 0 == d
then [(90, [x, y, z])]
else if (fst x * fst y) == abs d
then if 0 < d
then [(60, [x, y, z])]
else [(120, [x, y, z])]
else []
showTriples :: [(Int, [(Int, Int)])] -> String showTriples xs =
unlines $
zipWith
(\n vs ->
'\n' :
show (length vs) <> " solutions for " <> show n <> " degrees:\n" <>
show vs)
[120, 90, 60] $
(nub . fmap (sort . snd)) <$>
groupBy (on (==) fst) (second (fmap fst) <$> sortBy (comparing fst) xs)
main :: IO () main = putStrLn $ showTriples (triplesFound 13)</lang>
- Output:
2 solutions for 120 degrees: [[3,5,7],[7,8,13]] 3 solutions for 90 degrees: [[3,4,5],[5,12,13],[6,8,10]] 15 solutions for 60 degrees: [[1,1,1],[2,2,2],[3,3,3],[3,7,8],[4,4,4],[5,5,5],[5,7,8],[6,6,6],[7,7,7],[8,8,8],[9,9,9],[10,10,10],[11,11,11],[12,12,12],[13,13,13]]
Perl 6
Output sorted by number of solutions. Borrowing from Python, Go. <lang perl6>sub triples ($n, @angles) {
my $sq-as-set = set my @squares = 1..$n X**2;
my %triples; my %c2;
for flat @squares X @squares -> $a2, $b2 {
(my $a, my $b) = ($a2,$b2)».sqrt».floor;
my $ab = $a * $b;
%c2{@angles} = $a2 + $b2 X+ 0, -$ab, $ab;
%triples{$_}{~sort $a, $b, %c2{$_}.sqrt}++ if %c2{$_} ∈ $sq-as-set for @angles;
}
%triples
}
use Sort::Naturally;
my $n = 13; say "Integer triangular triples for sides 1..$n:"; my %itt = triples($n, (90, 60, 120)); for %itt.keys.sort: {+%itt{$^a}} -> $angle {
printf "Angle %3d° has %2d solutions: %s\n", $angle, +%itt{$angle}, %itt{$angle}.keys.sort(*.&naturally).join(', ');
}</lang>
- Output:
Integer triangular triples for sides 1..13: Angle 120° has 2 solutions: 3 5 7, 7 8 13 Angle 90° has 3 solutions: 3 4 5, 5 12 13, 6 8 10 Angle 60° has 15 solutions: 1 1 1, 2 2 2, 3 3 3, 3 7 8, 4 4 4, 5 5 5, 5 7 8, 6 6 6, 7 7 7, 8 8 8, 9 9 9, 10 10 10, 11 11 11, 12 12 12, 13 13 13
Python
<lang>N = 13
def method1(N=N):
squares = [x**2 for x in range(0, N+1)]
sqrset = set(squares)
tri90, tri60, tri120 = (set() for _ in range(3))
for a in range(1, N+1):
a2 = squares[a]
for b in range(1, a + 1):
b2 = squares[b]
c2 = a2 + b2
if c2 in sqrset:
tri90.add(tuple(sorted((a, b, int(c2**0.5)))))
continue
ab = a * b
c2 -= ab
if c2 in sqrset:
tri60.add(tuple(sorted((a, b, int(c2**0.5)))))
continue
c2 += 2 * ab
if c2 in sqrset:
tri120.add(tuple(sorted((a, b, int(c2**0.5)))))
return sorted(tri90), sorted(tri60), sorted(tri120)
- %%
if __name__ == '__main__':
print(f'Integer triangular triples for sides 1..{N}:')
for angle, triples in zip([90, 60, 120], method1(N)):
print(f' {angle:3}° has {len(triples)} solutions:\n {triples}')
_, t60, _ = method1(10_000)
notsame = sum(1 for a, b, c in t60 if a != b or b != c)
print('Extra credit:', notsame)</lang>
- Output:
Integer triangular triples for sides 1..13:
90° has 3 solutions:
[(3, 4, 5), (5, 12, 13), (6, 8, 10)]
60° has 15 solutions:
[(1, 1, 1), (2, 2, 2), (3, 3, 3), (3, 7, 8), (4, 4, 4), (5, 5, 5), (5, 7, 8), (6, 6, 6), (7, 7, 7), (8, 8, 8), (9, 9, 9), (10, 10, 10), (11, 11, 11), (12, 12, 12), (13, 13, 13)]
120° has 2 solutions:
[(3, 5, 7), (7, 8, 13)]
Extra credit: 17806
REXX
using some optimization
Instead of coding a general purpose subroutine (or function) to solve all of the
task's requirements, it was decided to
write three very similar do loops (triple nested) to provide the
answers for the three requirements.
Three arguments (from the command line) can be specified which indicates the
maximum length of the triangle sides
(the default is 13, as per the task's requirement) for each of the
three types of angles (60º, 90º, and 120º) for
the triangles. If the maximum length of the triangle's number of
sides is positive, it indicates that the triangle sides are
displayed, as well as a total number of triangles found.
If the maximum length of the triangle sides is negative, only
the number of triangles are
displayed (using the
absolute value of the negative number).
<lang rexx>/*REXX pgm finds integer sided triangles that satisfy Law of cosines for 60º, 90º, 120º.*/
parse arg s1 s2 s3 . /*obtain optional arguments from the CL*/
if s1== | s1=="," then s1= 13 /*Not specified? Then use the default.*/
if s2== | s2=="," then s2= 13 /* " " " " " " */
if s3== | s3=="," then s3= 13 /* " " " " " " */
w= max( length(s1), length(s2), length(s3) ) /*W is used to align the side lengths.*/
if s1>0 then do; call head 120 /*────120º: a² + b² + ab ≡ c² */
do a=1 for s1; aa = a*a
do b=a+1 to s1; x= aa + b*b + a*b
do c=b+1 to s1 until c*c>x
if x==c*c then do; call show; iterate b; end
end /*c*/
end /*b*/
end /*a*/
call foot s1
end
if s2>0 then do; call head 90 /*────90º: a² + b² ≡ c² */
do a=1 for s2; aa = a*a
do b=a+1 to s2; x= aa + b*b
do c=b+1 to s2 until c*c>x
if x==c*c then do; call show; iterate b; end
end /*c*/
end /*b*/
end /*a*/
call foot s2
end
if s3>0 then do; call head 60 /*────60º: a² + b² ─ ab ≡ c² */
do a=1 for s3; aa = a*a
do b=a to s3; x= aa + b*b - a*b
do c=a to s3 until c*c>x
if x==c*c then do; call show; iterate b; end
end /*c*/
end /*b*/
end /*a*/
call foot s3
end
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ foot: say right(# ' solutions found for' angle "(sides up to" arg(1)')', 65); say; return head: #= 0; parse arg deg; angle= ' 'deg"º "; say center(angle, 65, '═'); return show: #= # + 1; say ' ('right(a, w)"," right(b, w)"," right(c, w)')'; return</lang>
- output when using the default number of sides for the input: 13
═════════════════════════════ 120º ══════════════════════════════
( 3, 5, 7)
( 7, 8, 13)
2 solutions found for 120º (sides up to 13)
══════════════════════════════ 90º ══════════════════════════════
( 3, 4, 5)
( 5, 12, 13)
( 6, 8, 10)
3 solutions found for 90º (sides up to 13)
══════════════════════════════ 60º ══════════════════════════════
( 1, 1, 1)
( 2, 2, 2)
( 3, 3, 3)
( 3, 8, 7)
( 4, 4, 4)
( 5, 5, 5)
( 5, 8, 7)
( 6, 6, 6)
( 7, 7, 7)
( 8, 8, 8)
( 9, 9, 9)
(10, 10, 10)
(11, 11, 11)
(12, 12, 12)
(13, 13, 13)
15 solutions found for 60º (sides up to 13))
using memoization
<lang rexx>/*REXX pgm finds integer sided triangles that satisfy Law of cosines for 60º, 90º, 120º.*/ parse arg s1 s2 s3 s4 . /*obtain optional arguments from the CL*/ if s1== | s1=="," then s1= 13 /*Not specified? Then use the default.*/ if s2== | s2=="," then s2= 13 /* " " " " " " */ if s3== | s3=="," then s3= 13 /* " " " " " " */ if s4== | s4=="," then s4= -10000 /* " " " " " " */ parse value s1 s2 s3 s4 with os1 os2 os3 os4 . /*obtain the original values for sides.*/ s1=abs(s1); s2=abs(s2); s3=abs(s3); s4=abs(s4) /*use absolute values for the # sides. */ @.=
do j=1 for max(s1, s2, s3, s4); @.j = j*j
end /*j*/ /*build memoization array for squaring.*/
if s1>0 then do; call head 120,,os1 /*────120º: a² + b² + ab ≡ c² */
do a=1 for s1
do b=a+1 to s1; x= @.a + @.b + a*b
if x>z then iterate a
do c=b+1 to s1 until @.c>x
if x==@.c then do; call show; iterate b; end
end /*c*/
end /*b*/
end /*a*/
call foot s1
end
if s2>0 then do; call head 90,, os2 /*────90º: a² + b² ≡ c² */
do a=1 for s2
do b=a+1 to s2; x= @.a + @.b
if x>z then iterate a
do c=b+1 to s2 until @.c>x
if x==@.c then do; call show; iterate b; end
end /*c*/
end /*b*/
end /*a*/
call foot s2
end
if s3>0 then do; call head 60,, os3 /*────60º: a² + b² ─ ab ≡ c² */
do a=1 for s3
do b=a to s3; x= @.a + @.b - a*b
if x>z then iterate a
do c=a to s3 until @.c>x
if x==@.c then do; call show; iterate b; end
end /*c*/
end /*b*/
end /*a*/
call foot s3
end
if s4>0 then do; call head 60, 'unique', os4 /*────60º: a² + b² ─ ab ≡ c² */
do a=1 for s4
do b=a to s4; x= @.a + @.b - a*b
if x>z then iterate a
do c=a to s4 until @.c>x
if x==@.c then do; if a==b&a==c then iterate b
call show; iterate b
end
end /*c*/
end /*b*/
end /*a*/
call foot s4
end
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ foot: say right(# ' solutions found for' ang "(sides up to" arg(1)')', 65); say; return head: #=0; arg d,,s;z=s*s;w=length(s); ang=' 'd"º " arg(2); say center(ang,65,'═'); return show: #= # + 1; if s>0 then say ' ('right(a,w)"," right(b,w)"," right(c,w)')'; return</lang>
- output when using the inputs of: 0 0 0 -10000
Note that the first three computations are bypassed because of the three zero (0) numbers, the negative ten thousand indicates to find all the triangles with sides up to 10,000, but not list the triangles, it just reports the number of triangles found.
══════════════════════════ 60º unique═══════════════════════════
18394 solutions found for 60º unique (sides up to 10000)