Heronian triangles: Difference between revisions
(Better D entry) |
(→{{header|Perl 6}}: better integer test) |
||
| Line 198: | Line 198: | ||
sub heronian-area($a, $b, $c) { |
sub heronian-area($a, $b, $c) { |
||
given hero |
$_ when Int given hero($a, $b, $c).narrow; |
||
} |
} |
||
Revision as of 17:26, 3 January 2015
You are encouraged to solve this task according to the task description, using any language you may know.
Hero's formula for the area of a triangle given the length of its three sides a, b, and c is given by:
where s is half the perimeter of the triangle; that is,
Heronian triangles are triangles whose sides and area are all integers.
- An example is the triangle with sides 3, 4, 5 whose area is 6 (and whose perimeter is 12).
Note that any triangle whose sides are all an integer multiple of 3,4,5; such as 6,8,10, will also be a heronian triangle.
Define a Primitive Heronian triangle as a heronian triangle where the greatest common divisor of all three sides is 1. this will exclude, for example triangle 6,8,10
The task is to:
- Create a named function/method/proceedure/... that implements Hero's formula.
- Use the function to generate all the primitive heronian triangles with sides <= 200.
- Show the count of how many triangles are found.
- Order the triangles by first increasing area, then by increasing perimeter, then by increasing maximum side lengths
- Show the first ten ordered triangles in a table of sides, perimeter, and area.
- Show a similar ordered table for those triangles with area = 210
Show all output here.
Note: when generating triangles it may help to restrict
D
<lang d>import std.stdio, std.math, std.range, std.algorithm, std.numeric, std.traits, std.typecons;
double hero(in uint a, in uint b, in uint c) pure nothrow @safe @nogc {
immutable s = (a + b + c) / 2.0; immutable a2 = s * (s - a) * (s - b) * (s - c); return (a2 > 0) ? a2.sqrt : 0.0;
}
bool isHeronian(in uint a, in uint b, in uint c) pure nothrow @safe @nogc {
immutable h = hero(a, b, c); return h > 0 && h.floor == h.ceil;
}
T gcd3(T)(in T x, in T y, in T z) pure nothrow @safe @nogc {
return gcd(gcd(x, y), z);
}
void main() /*@safe*/ {
enum uint maxSide = 200;
// Sort by increasing area, perimeter, then sides.
//auto h = cartesianProduct!3(iota(1, maxSide + 1))
auto r = iota(1, maxSide + 1);
const h = cartesianProduct(r, r, r)
//.filter!({a, b, c} => ...
.filter!(t => t[0] <= t[1] && t[1] <= t[2] &&
t[0] + t[1] > t[2] &&
t[].gcd3 == 1 && t[].isHeronian)
.array
.schwartzSort!(t => tuple(t[].hero, t[].only.sum, t.reverse))
.release;
static void showTriangles(R)(R ts) @safe {
"Area Perimeter Sides".writeln;
foreach (immutable t; ts)
writefln("%3s %8d %3dx%dx%d", t[].hero, t[].only.sum, t[]);
}
writefln("Primitive Heronian triangles with sides up to %d: %d", maxSide, h.length);
"\nFirst ten when ordered by increasing area, then perimeter,then maximum sides:".writeln;
showTriangles(h.take(10));
"\nAll with area 210 subject to the previous ordering:".writeln; showTriangles(h.filter!(t => t[].hero == 210));
}</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517 First ten when ordered by increasing area, then perimeter,then maximum sides: Area Perimeter Sides 6 12 3x4x5 12 16 5x5x6 12 18 5x5x8 24 32 4x13x15 30 30 5x12x13 36 36 9x10x17 36 54 3x25x26 42 42 7x15x20 60 36 10x13x13 60 40 8x15x17 All with area 210 subject to the previous ordering: Area Perimeter Sides 210 70 17x25x28 210 70 20x21x29 210 84 12x35x37 210 84 17x28x39 210 140 7x65x68 210 300 3x148x149
Perl
<lang perl>use strict; use warnings; use List::Util qw(max);
sub gcd { $_[1] == 0 ? $_[0] : gcd($_[1], $_[0] % $_[1]) }
sub hero {
my ($a, $b, $c) = @_[0,1,2]; my $s = ($a + $b + $c) / 2; sqrt $s*($s - $a)*($s - $b)*($s - $c);
}
sub heronian_area {
my $hero = hero my ($a, $b, $c) = @_[0,1,2];
sprintf("%.0f", $hero) eq $hero ? $hero : 0
}
sub primitive_heronian_area {
my ($a, $b, $c) = @_[0,1,2]; heronian_area($a, $b, $c) if 1 == gcd $a, gcd $b, $c;
}
sub show {
print " Area Perimeter Sides\n";
for (@_) {
my ($area, $perim, $c, $b, $a) = @$_;
printf "%7d %9d %d×%d×%d\n", $area, $perim, $a, $b, $c;
}
}
sub main {
my $maxside = shift // 200;
my $first = shift // 10;
my $witharea = shift // 210;
my @h;
for my $c (1 .. $maxside) {
for my $b (1 .. $c) { for my $a ($c - $b + 1 .. $b) { if (my $area = primitive_heronian_area $a, $b, $c) { push @h, [$area, $a+$b+$c, $c, $b, $a]; } } }
}
@h = sort {
$a->[0] <=> $b->[0] or $a->[1] <=> $b->[1] or max(@$a[2,3,4]) <=> max(@$b[2,3,4])
} @h;
printf "Primitive Heronian triangles with sides up to %d: %d\n",
$maxside,
scalar @h;
print "First:\n";
show @h[0 .. $first - 1];
print "Area $witharea:\n";
show grep { $_->[0] == $witharea } @h;
}
&main();</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517
First:
Area Perimeter Sides
6 12 3×4×5
12 16 5×5×6
12 18 5×5×8
24 32 4×13×15
30 30 5×12×13
36 36 9×10×17
36 54 3×25×26
42 42 7×15×20
60 36 10×13×13
60 40 8×15×17
Area 210:
Area Perimeter Sides
210 70 17×25×28
210 70 20×21×29
210 84 12×35×37
210 84 17×28×39
210 140 7×65×68
210 300 3×148×149
Perl 6
<lang perl6>sub hero($a, $b, $c) {
my $s = ($a + $b + $c) / 2; my $a2 = $s * ($s - $a) * ($s - $b) * ($s - $c); $a2.sqrt;
}
sub heronian-area($a, $b, $c) {
$_ when Int given hero($a, $b, $c).narrow;
}
sub primitive-heronian-area($a, $b, $c) {
heronian-area $a, $b, $c
if 1 == [gcd] $a, $b, $c;
}
sub show {
say " Area Perimeter Sides";
for @_ -> [$area, $perim, $c, $b, $a] {
printf "%6d %6d %12s\n", $area, $perim, "$a×$b×$c";
}
}
sub MAIN ($maxside = 200, $first = 10, $witharea = 210) {
my \h = sort gather
for 1 .. $maxside -> $c {
for 1 .. $c -> $b {
for $c - $b + 1 .. $b -> $a {
if primitive-heronian-area($a,$b,$c) -> $area {
take [$area, $a+$b+$c, $c, $b, $a];
}
}
}
}
say "Primitive Heronian triangles with sides up to $maxside: ", +h;
say "\nFirst $first:"; show h[^$first];
say "\nArea $witharea:"; show h.grep: *[0] == $witharea;
}</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517
First 10:
Area Perimeter Sides
6 12 3×4×5
12 16 5×5×6
12 18 5×5×8
24 32 4×13×15
30 30 5×12×13
36 36 9×10×17
36 54 3×25×26
42 42 7×15×20
60 36 10×13×13
60 40 8×15×17
Area 210:
Area Perimeter Sides
210 70 17×25×28
210 70 20×21×29
210 84 12×35×37
210 84 17×28×39
210 140 7×65×68
210 300 3×148×149
Python
<lang python>from math import sqrt from fractions import gcd from itertools import product
def hero(a, b, c):
s = (a + b + c) / 2 a2 = s*(s-a)*(s-b)*(s-c) return sqrt(a2) if a2 > 0 else 0
def is_heronian(a, b, c):
a = hero(a, b, c) return a > 0 and a.is_integer()
def gcd3(x, y, z):
return gcd(gcd(x, y), z)
if __name__ == '__main__':
maxside = 200
h = [(a, b, c) for a,b,c in product(range(1, maxside + 1), repeat=3)
if a <= b <= c and a + b > c and gcd3(a, b, c) == 1 and is_heronian(a, b, c)]
h.sort(key = lambda x: (hero(*x), sum(x), x[::-1])) # By increasing area, perimeter, then sides
print('Primitive Heronian triangles with sides up to %i:' % maxside, len(h))
print('\nFirst ten when ordered by increasing area, then perimeter,then maximum sides:')
print('\n'.join(' %14r perim: %3i area: %i'
% (sides, sum(sides), hero(*sides)) for sides in h[:10]))
print('\nAll with area 210 subject to the previous ordering:')
print('\n'.join(' %14r perim: %3i area: %i'
% (sides, sum(sides), hero(*sides)) for sides in h
if hero(*sides) == 210))</lang>
- Output:
Primitive Heronian triangles with sides up to 200: 517
First ten when ordered by increasing area, then perimeter,then maximum sides:
(3, 4, 5) perim: 12 area: 6
(5, 5, 6) perim: 16 area: 12
(5, 5, 8) perim: 18 area: 12
(4, 13, 15) perim: 32 area: 24
(5, 12, 13) perim: 30 area: 30
(9, 10, 17) perim: 36 area: 36
(3, 25, 26) perim: 54 area: 36
(7, 15, 20) perim: 42 area: 42
(10, 13, 13) perim: 36 area: 60
(8, 15, 17) perim: 40 area: 60
All with area 210 subject to the previous ordering:
(17, 25, 28) perim: 70 area: 210
(20, 21, 29) perim: 70 area: 210
(12, 35, 37) perim: 84 area: 210
(17, 28, 39) perim: 84 area: 210
(7, 65, 68) perim: 140 area: 210
(3, 148, 149) perim: 300 area: 210