18
\$\begingroup\$

Task: Given the area of a triangle, find a Heronian triangle with that area. Any Heronian triangle with the specified area is allowed.

A Heronian triangle is a triangle with integer sides and integer area. By Heron's formula, a triangle with sides lengths a,b,c has area

sqrt(s*(s-a)*(s-b)*(s-c))

where s=(a+b+c)/2 is half the perimeter of the triangle. This can also be written as

sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)) / 4

If no such triangle exists, output with a consistent falsey value.

Input: A single, positive integer representing the area of the triangle.

Output: Any three side lengths for such a triangle OR a falsely value.

Examples:

Input -> Output
6 -> 3 4 5
24 -> 4 15 13
114 -> 37 20 19
7 -> error

Standard loopholes apply

This is code golf, shortest answer in bytes wins.

\$\endgroup\$
  • 6
    \$\begingroup\$ Can you write a relatively concise definition of a Heronian triangle in your challenge? \$\endgroup\$ – Okx May 20 '17 at 19:44
  • 1
    \$\begingroup\$ @Okx: Is it not clear that it is a triangle with integer sides and integer area? \$\endgroup\$ – Neil A. May 20 '17 at 19:54
  • \$\begingroup\$ @Okx: That is the idea. All you need to do is find one such example for the given area if it exists. \$\endgroup\$ – Neil A. May 20 '17 at 20:04
  • \$\begingroup\$ From the Wikipedia link: "A Heronian triangle is a triangle that has side lengths and area that are all integers." \$\endgroup\$ – Neil A. May 20 '17 at 20:16
  • 5
    \$\begingroup\$ Could you please explain what is confusing about the definition in the question? \$\endgroup\$ – Neil A. May 20 '17 at 20:20

13 Answers 13

6
\$\begingroup\$

Jelly, 17 16 bytes

-1 byte thanks to Erik the outgolfer (make use of the quick, ¥)

SHð;_P
ṗ3Ç⁼¥Ðf²Ḣ

Brute force application of Heron's formula.

Try it online! (reaches the 60s time out for the 114 tests case. Takes 3m 30s locally - it does check 1143 = 1,481,544 triples)

How?

A true golf solution - given an area a it finds all tuples of three integers between 1 and a (even with repeated triangles and ones of no area), gets their area and filters for those with the desired area (it doesn't even stop as soon as one is found, it ploughs through them all and pops the first result afterwards). Yields 0 if none exists.

SHð;_P - Link 1, get the square of the area of a triangle: list of sides
S      - sum the sides (get the perimeter)
 H     - halve
  ð    - dyadic chain separation (call that p)
    _  - subtraction (vectorises) =    [p-side1,  p-side2,  p-side3]
   ;   - concatenate              = [p, p-side1,  p-side2,  p-side3]
     P - product                  =  p*(p-side1)*(p-side2)*(p-side3)
                                  = the square of Heron's formula = area squared

ṗ3Ç⁼¥Ðf²Ḣ - Main link: number a (area)
ṗ3        - third Cartesian power (all triples of [1,area] : [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2], ... ,[a,a,a]]
       ²  - square a
     Ðf   - filter keep if:
    ¥     -   last two links as a dyad:
  Ç       -     call last link (1) as a monad f(list of sides)
   ⁼      -     left (that result) equals right (square of a)?
        Ḣ - head - get the first one (an empty list yields 0, perfect for the falsey case)
\$\endgroup\$
  • \$\begingroup\$ I figured someone would try to brute force this, nice! \$\endgroup\$ – Neil A. May 20 '17 at 20:25
  • \$\begingroup\$ @NeilA. I imagine most golf submissions will be brute force for this challenge - but some may manage to be golfed while being less ridiculously inefficient than this one. \$\endgroup\$ – Jonathan Allan May 20 '17 at 20:46
  • \$\begingroup\$ You can replace ç with Ç⁼¥ and remove the second line entirely. \$\endgroup\$ – Erik the Outgolfer May 20 '17 at 21:12
  • \$\begingroup\$ @EriktheOutgolfer Oh, thanks, I was wondering how to go about that... \$\endgroup\$ – Jonathan Allan May 20 '17 at 21:13
5
\$\begingroup\$

JavaScript (ES7), 109 102 100 98 bytes

Returns either an array of 3 integers or false. Like the Jelly answer, this is brute forcing Heron's formula.

A=>[...Array(A**3)].some((_,a)=>A*A/(r=[b=a/A%A|0,c=a/A/A|0,a%=A],p=a+b+c>>1)/(p-a)/(p-b)==p-c)&&r

Test cases

let f =

A=>[...Array(A**3)].some((_,a)=>A*A/(r=[b=a/A%A|0,c=a/A/A|0,a%=A],p=a+b+c>>1)/(p-a)/(p-b)==p-c)&&r

console.log(JSON.stringify(f(6)))
console.log(JSON.stringify(f(24)))
console.log(JSON.stringify(f(114)))
console.log(JSON.stringify(f(7)))


Recursive version, 83 bytes

Returns an array of 3 integers or throws a recursion error. Sadly, it only works for small inputs.

f=(A,n)=>A*A/(r=[a=n%A,b=n/A%A|0,c=n/A/A|0],p=a+b+c>>1)/(p-a)/(p-b)==p-c?r:f(A,-~n)

Demo

f=(A,n)=>A*A/(r=[a=n%A,b=n/A%A|0,c=n/A/A|0],p=a+b+c>>1)/(p-a)/(p-b)==p-c?r:f(A,-~n)

console.log(JSON.stringify(f(6)))
console.log(JSON.stringify(f(24)))

\$\endgroup\$
4
\$\begingroup\$

Haskell, 69 bytes

f a=take 1[t|t<-mapM(\_->[1..a])":-)",a*a==product[sum t/2-x|x<-0:t]]

Try it online!

Outputs a singleton of a list of three triangle sides like [[3.0,4.0,5.0]]. Impossible inputs give []. Technically only False is Falsey for Haskell, but because Haskell requires all possible outputs to be of the same type, it can't be used. If an error could be used as Falsey, [...]!!0 would save 3 bytes over take 1[..].

Tries all triples t of possible side lengths each ranging from 1 to the area a. Heron's formula is used to check if the area matches via (s-0)(s-x)(s-y)(s-z)==a*a where s=(x+y+z)/2 is sum t/2. The product (s-0)(s-x)(s-y)(s-z) is expressed as a product with elements taken from 0:t, i.e. the triple as well as 0.

\$\endgroup\$
  • \$\begingroup\$ +1 for smiley face, even if it's sorta a noop \$\endgroup\$ – Julian Wolf May 23 '17 at 0:01
2
\$\begingroup\$

F#, 170 156 152 bytes

let f(a,b,c)=
 let s=(a+b+c)/2.0
 s*(s-a)*(s-b)*(s-c)
let g A=[for a in 1.0..A do for b in a..A do for c in b..A do yield a,b,c]|>List.find(f>>(=)(A*A))

Try it online!

"Ungolfed"

let calculateArea (a, b, c) =
    let s = (a+b+c)/2.0
    s*(s-a)*(s-b)*(s-c)

let getTriangle A =
    [  for a in 1.0..A do
       for b in a..A do
       for c in b..A do yield a,b,c
    ]
    |> List.find(calculateArea>>(=)(A * A))

If there are no results found, the program will fault. If this is not desired, I have to replace List.find with either List.filter (+2 bytes) which will produce an empty list in case nothing is found or List.tryFind (+3 bytes), returning None in case no triangle was found.

I always find that a golfed F# version is still reasonable legible.

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't know F#, but I imagine you could dispense with the System.Math.Sqrt and compare the resulting value to A * A? \$\endgroup\$ – Sean May 20 '17 at 23:20
  • \$\begingroup\$ @Sean Of course! Thanks for the tip :) \$\endgroup\$ – Brunner May 21 '17 at 5:36
  • \$\begingroup\$ Replacing 1.0..A [...] 1.0..A [...] 1.0..A with 1.0..A [...] a..A [..] b..A should save you a couple bytes and speed you up a little (if it works; I have very minimal F# experience). \$\endgroup\$ – CAD97 May 21 '17 at 6:07
  • \$\begingroup\$ @CAD97 It does! Thanks for pointing that out. \$\endgroup\$ – Brunner May 21 '17 at 6:30
2
\$\begingroup\$

Python 2 (PyPy), 131 123 118 bytes

n=input()
t=n*3;r=i=c=0
while c<t:
 i+=1;a,b,c=i%t,i/t%t,i/t/t;s=a+b+c>>1
 if(s-a)*s*(s-b)*(s-c)==n**2:r=a,b,c
print r

Try it online!

While this also works on CPython, PyPy is a lot faster and is able to compute the triangle for 114 in the time limit on TIO.

Timings from my machine:

$ echo 114 | time pypy2 d.py
        0.55 real         0.52 user         0.02 sys
$ echo 114 | time python2 d.py
       52.46 real        51.76 user         0.27 sys
\$\endgroup\$
1
\$\begingroup\$

Pyth - 23 bytes

/mu*G-/sd2Hd/sd2^UQ3^Q2

Which prints a truthy/falsy value, or

fq^Q2u*G-/sT2HT/sT2^UQ3

which prints out all possible solutions, and is horribly slow for large inputs. Put 'h' at the beginning to only print one.

Explanation:

fq^Q2u*G-/sT2HT/sT2^UQ3
                    UQ    # List of numbers from 0 to input-1
                   ^  3   # All triples of these numbers
f                         # Filter this by the following test (on variable T, based on Hero's formula)
     u*G-/sT2HT/sT2       # s*(s-a)*(s-b)*(s-c), where s is the sum of the triple over 2 (calclated as /sT2 )
 q^Q2                     # Test if equal to input ^2

Try it

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 54 bytes

->\a{first {a*a==[*] .sum/2 «-«(0,|$_)},[X] ^a xx 3}

Brute force search of all possibles sides up to one less than a, the input area.

  • ^a is the range of numbers from 0 to a - 1.
  • [X] ^a xx 3 reduces, by cross product, three copies of that range, producing all triplets from (0, 0, 0) to (a - 1, a - 1, a - 1).
  • We look for the first triplet such that the area of the triangle with those sides equals a, using Heron's formula.

Within the code block given to first:

  • $_ is the triplet. Call it (x, y, z) here.
  • (0,|$_) is the same triplet but with 0 prepended: (0, x, y, z).
  • .sum / 2 is half the perimeter (a quantity which is named s in the usual expression of Heron's formula).
  • .sum / 2 «-« (0, |$_) is the subtraction hyperoperator with s on the left and the (0, x, y, z) on the right, giving (s - 0, s - x, s - y, s - z).
  • [*] then reduces that quadruplet with multiplication, giving the square of the area.
  • a * a == looks for a squared area equal to the square of the given area.

If no triplet is found, Nil (which is falsey) is returned.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 76 bytes

f s=[[a,b,c]|a<-[1..s],b<-[1..a],c<-[1..b],a*a*c*c-(a*a+c*c-b*b)^2/4==4*s*s]

This outputs a list of lists containing all possible integral sizes that generate the correct area via brute force (outputting the empty list if there are none). The caveat being it outputs them as doubles because of that division in the middle but their fractional part is always 0.

If you for some reason can't take that,

f s=[[a,b,c]|a<-[1..s],b<-[1..a],c<-[1..b],4*a*a*c*c-(a*a+c*c-b*b)^2==16*s*s]

This will output the answers as a list of integer lists for 89 77 bytes total or 13 1 extra bytes. (Thanks to Neil)

If you need / want only the first element just putting !!0 at the end will give you only the first element if there are numbers that apply and an error if there's none for 3 more bytes and take 1 at the beginning will take the first element without erroring out for 6 more bytes.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ If you want to avoid doubles can't you just multiply the equation by 4 on each side? \$\endgroup\$ – Neil May 22 '17 at 0:04
0
\$\begingroup\$

TI-Basic, 70 69 bytes

Prompt A
For(B,1,A
For(C,1,B
For(D,1,C
(B+C+D)/2
If A2=Ansprod(Ans-{B,C,D
Then
Disp B,C,D
Return
End
End
End
End
/

Displays the three side lengths if there is a triangle, throws a syntax error if there isn't (thanks to the / at the end).

-1 byte thanks to Sean's comment on a different answer

\$\endgroup\$
0
\$\begingroup\$

Mathematica, 77 bytes

with mathematica's Solve

s=(a+b+c)/2;d=Sqrt[s(s-a)(s-b)(s-c)];Solve[d==#&&0<a<b<c<#,{a,b,c},Integers]&

Mathematica, 117 bytes

brute force

s=(a+b+c)/2;l="error";(For[a=1,a<#,a++,For[b=1,b<a,b++,For[c=1,c<b,c++,If[Sqrt[s(s-a)(s-b)(s-c)]==#,l={a,b,c}]]]];l)&
\$\endgroup\$
  • 1
    \$\begingroup\$ Mathematica doesn't have a builtin? Surprising. \$\endgroup\$ – Neil A. May 21 '17 at 0:00
  • \$\begingroup\$ @ovs you can save one byte on that with Area@SSSTriangle[a,b,c] too. \$\endgroup\$ – numbermaniac May 21 '17 at 7:52
0
\$\begingroup\$

Actually, 22 bytes

;╗R3@∙⌠;Σ½;)♀-π*╜²=⌡░F

Try it online!

Explanation:

;╗R3@∙⌠;Σ½;)♀-π*╜²=⌡░F  (implicit input: A)
;╗                      store a copy of A in register 0
  R                     range(1, A+1)
   3@∙                  ternary Cartesian product (all triples with values in [1, A])
      ⌠;Σ½;)♀-π*╜²=⌡░   filter: take triples where function returns truthy
       ;Σ½                make a copy of the triple, compute s = (a+b+c)/2
          ;)              make a copy of s, move it to the bottom of the stack
            ♀-            subtract each value in the triple from s
              π*          product of those values and s (s*(s-a)*(s-b)*(s-c))
                ╜²        A*A
                  =       compare equality (does area of triangle with given dimensions equal input?)
                     F  take first triple that satisfies the filter (or empty list if none)
\$\endgroup\$
0
\$\begingroup\$

Casio Basic, 123 bytes

For 1⇒a To n
For 1⇒b To n
For 1⇒c To n
If(s*(s-a)*(s-b)*(s-c)|s=(a+b+c)/2)=n^2
Then
Print{a,b,c}
Stop
IfEnd
Next:Next:Next

Standard brute force solution. 122 bytes for the code, 1 byte to specify n as a parameter.

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 59 bytes

Solve[Area@SSSTriangle[a,b,c]==#>c>b>a>0,{a,b,c},Integers]&

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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