Unique magic triplets

Description

Your input is a list of integers $$\[a_1, \dots, a_n]\$$.

A magic triplet is a triplet $$\(a_i, a_j, a_k)\$$ of values from this list, such that

• the indices $$\\{i, j, k\}\$$ are all distinct,
• the values are in ascending order ($$\a_i \leq a_j \leq a_k\$$), and
• the sum of two of the values equals the third.

Your task is to output all unique magic triplets, in any order.

Rules

1. Each number in the input list is guaranteed to be in the range $$\-2^{32} \leq a < 2^{32}\$$.
2. The input list's length is guaranteed to be at most 1000.
3. The input list's length may be less than 3 (even 0). In this case, there are no magic triplets, and your program should produce an empty result.
4. The shortest answer in bytes wins.

Test cases

[1,2,3,2,4] -> [[1,2,3], [1,3,4], [2,2,4]]
[0,0,0,0] -> [[0,0,0]]
[1,0,-1] -> [[-1,0,1]]
[1,2] -> []
[1,2,4,8,99] -> []
[33,90,7,24,60,32,80,43,15,40,36,90,65,12,91,33,88,1,96,33,40] -> [[7,33,40], [32,33,65], [1,32,33], [1,90,91], [7,36,43], [24,36,60], [12,24,36], [36,60,96], [15,65,80], [40,40,80]]


Notes

• In the second test case, [[0,0,0], [0,0,0]] is not a valid answer. No triplet may be listed twice in the output.
• Remember that your program may order the triplets differently. For example, [[2,2,4], [1,2,3], [1,3,4]] is also a valid output for the first test case.
• Nonetheless, [[4,2,2], …] is invalid: each triplet itself must be in ascending order.
• Hey @chaugiang, I rewrote your question for clarity, and to be a bit more in the codegolf.SE “style”. If you disagree with my rewrite, feel free to roll it back (or fix what you dislike about it).
– Lynn
Nov 14 '19 at 16:43
• @Lynn Thank you a lot for your contributions. Nov 14 '19 at 23:53

Ruby, 46 51 58 bytes

->l{l.permutation(3).select{|a,b,c|a+b==c}.map(&:sort)|[]}


Try it online!

Ok, not so straightforward, but now seems to work.

• I'm afraid this works only for input array already sorted ascending, which is not guaranteed by the challenge. For example from test case E it finds only 5 sets while 10 are expected. Nov 14 '19 at 10:02
• You are right. Fixed now.
– G B
Nov 14 '19 at 10:37
• Yepp, that was the easy fix. But handling negative numbers like in test case B [1, 0, -1] may be harder. ☹ Nov 14 '19 at 10:55
• Oops. Fixed again.
– G B
Nov 14 '19 at 11:05

05AB1E, 11109 10 bytes

{æ3ùêʒxsOå


+1 byte as bugfix for test cases like [1,0,-1] → [[-1,0,1]] (-1+1=0) and [-1,-2,-3] → [[-3,-2,-1]] (-1+-2=-3).

Explanation:

{           # Sort the (implicit) input-list from lowest to highest value
æ          # Take the powerset of this sorted list
3ù        # Only keep inner lists of length 3
ê       # (Sort and) uniquify this entire list of triplets
ʒ      # Filter this list of (individually sorted) triplets by:
x     #  Double each value in the triplet (without popping the triplet itself)
s    #  Swap to get the original triplet
O   #  Take the sum of this triplet
å  #  And check whether this value is in the doubled list
# (after which the filtered list is output implicitly as result)


The last four bytes could alternatively be œÆ0å (given by @Grimy): Try it online or verify all test cases.

      œ     #  Get all possible permutations of the triplet
Æ    #  Reduce each by subtracting: [a,b,c] → a-b-c
0å  #  And check if there are any 0s among the reduced permutations

• xsOå can also be œÆP>. Same byte-count, but more stylish. Nov 14 '19 at 13:55
• @Grimmy The Æ was also in my 9-byter. :) I've added it (with 0å instead of P>, since it's a bit more logical to me what's being checked). PS: It might be more stylish, but I think that permutations builtin would decrease the performance slightly, though. :) Nov 14 '19 at 14:03

Jelly, 10 bytes

Ṣœc3ḤiSƊƇQ


Try it online!

Ṣ             Sort the input,
œc3          find all length-3 subsequences,
Ƈ     filter to only the sets for which
S       the sum of all three elements
i        is an element of
Ḥ  Ɗ      the set with all elements doubled,
Q    and uniquify.


Brachylog, 11 bytes

{o⊇Ṫ.+/₂∈}ᵘ


Try it online!

Takes input through the input variable and outputs through the output variable.

{        }ᵘ    Output every unique output from:
.          the output is
⊇            a subsequence
Ṫ           of length 3
{              of the input
o             sorted
+         the sum of which
/₂       divided by 2
∈      is an element of
}     the output.

• [2,2,4] shouldn't be a magic triplet. I think you can fix by replacing the sort by distinct. Nov 15 '19 at 16:27
• The challenge spec only requires that the indices are distinct, and that the values within the triplet are non-decreasing (although it uses the word "increasing"). Note that the first test case contains two 2s and expects [2,2,4] to be output, and the fifth test case only contains one 2, so expects [2,2,4] to not be output. Nov 15 '19 at 22:40
• by bad, I didn't read the question properly. Nov 16 '19 at 11:58

Japt, 13 11 bytes

á3 k_r-ÃmÍâ


Try it

á3 k_r-ÃmÍâ // input as arrays
á3            // all unique permutations
k_          // save list that..
r-Ã       // reduced by - from first element
mÍ   // ==mn   => sort all
â // remove duplicates


Thanks to @Shaggy and @Embodiment of Ignorance for saving 2

• 12 bytes: petershaggynoble.github.io/Japt-Interpreter/…. Using r- is very clever! Nov 14 '19 at 15:34
• 11 bytes Nov 14 '19 at 16:17
• @Embodiment of Ignorance thanks, it's been a while since I wanted to use it ! Forgot that sort can be just mn! Nov 14 '19 at 16:53
• Very nicely done, by the way. I took a quick, uncaffeinated stab at this this morning and ended up around 15 bytes. Nov 14 '19 at 23:21
• @Shaggy thanks for all the help given! Nov 15 '19 at 5:21

Perl 6, 65 64 bytes

*.combinations(3)>>.sort.grep({@$_.sum==2*.any}).unique(:as(~*))  Try it online! *.combinations(3) # All the combinations of length 3 >>.sort # Sorted .grep({ }) # Filtered by {@$_.sum==         # The sum is equal to
2*.any   # Double any element
.unique(:as(~*))  # And take the unique lists

• Flooring the halved sum adds (0 0 1) to the new last test case ([0,0,0,0,1]). Nov 14 '19 at 7:51
• ...actually it adds a bunch of stuff to several test cases. I thought this might work as a fixed version, but 1. I don't actually know Perl and 2. it's missing (40 40 80) from the [33, 90, 7, 24, 60, 32, 80, 43, 15, 40, 36, 90, 65, 12, 91, 33, 88, 1, 96, 33, 40] case. Nov 14 '19 at 8:01
• @UnrelatedString Rolled back to a previous version. That test case was modified later (OP added the second 40), so I had the old version.
– Jo King
Nov 14 '19 at 8:04
• Ah, makes sense. Nov 14 '19 at 8:25

JavaScript (Node.js),  118 116  115 bytes

Returns a set.

a=>new Set(a.flatMap((x,i)=>a.flatMap((y,j)=>j-i&&~(k=a.indexOf(x+y))&&k-i&&k-j?[x,y,x+y].sort((a,b)=>a-b)+'':[])))


Try it online!

Commented

a =>                             // a[] = input array
new Set(                       // create a set:
a.flatMap((x, i) =>          //   for each value x at position i in a[]:
a.flatMap((y, j) =>        //     for each value y at position j in a[]:
j - i &&                 //       if j is not equal to i
~(                       //       and the position k
k = a.indexOf(x + y)   //       of x + y in a[]
) &&                     //       is not equal to -1
k - i &&                 //       and k is not equal to i
k - j ?                  //       and k is not equal to j:
[x, y, x + y]          //         build the triplet (x, y, x + y)
.sort((a, b) => a - b) //         sort it in ascending order
+ ''                   //         and coerce it to a string
:                        //       else:
[]                     //         yield an empty array
)                          //     end of inner flatMap()
)                            //   end of outer flatMap()
)                              // end of Set()


Python 3, 94, 89, 88, 85 bytes

One byte saved thanks to frank.

lambda l:{p for p in combinations(sorted(l),3)if sum(p)/2in p}
from itertools import*


Try it online!

import Data.List
f x=nub[y|y@[a,b,c]<-subsequences\$sort x,or[2*z==sum y|z<-y]]


Try it online!

K (oK), 38 bytes

{?{x@<x}'({z=x+y}.)#x@/:{x~?x}#+!3##x}


Try it online!

Charcoal, 66 bytes

ＦＬθＦＬθＦＬθＦ¬⌈⟦⁼ικ⁼ιλ⁼κλ›§θι§θκ›§θκ§θλ⟧«≔Ｅ⟦ικλ⟧§θνη¿∧№η⊘Ση¬№υη⊞υη»Ｉυ


Try it online! Link is to verbose version of code. Explanation:

ＦＬθＦＬθＦＬθＦ¬⌈⟦


Loop through all triples of indices...

⁼ικ⁼ιλ⁼κλ


... checking whether the indices are distinct...

›§θι§θκ›§θκ§θλ


... and that the triplet is in ascending order...

⟧«≔Ｅ⟦ικλ⟧§θνη


... if so then save the triplet in a variable...

¿∧№η⊘Ση¬№υη⊞υη


... and if it contains its halved sum and is unique then remember it in a list.

»Ｉυ


After checking all triplets output the unique magic triplets double-spaced with each triplet member on its own line.

Java 10, 225 bytes

import java.util.*;L->{var r=new TreeSet();for(int j,k,a,b,t[],i=L.size();i-->0;)for(j=i;j-->0;)if((k=L.indexOf((a=L.get(i))+(b=L.get(j))))>=0&k!=i&k!=j){Arrays.sort(t=new int[]{a,b,a+b});r.add(Arrays.toString(t));}return r;}


Port of @Arnauld's JavaScript answer, just twice as long.. >.>

Try it online.

Explanation:

import java.util.*;       // Required import for the TreeSet and both Arrays
L->{                      // Method with integer-List as parameter & sorted Set as return
var r=new TreeSet();    //  Result-set, starting uninitialized
//  A Set will automatically remove duplicates
//  (and a TreeSet will automatically sort, which is irrelevant,
//   but it's the same size as a regular HashSet anyway)
for(int j,k,a,b,t[],    //  Temp integers
i=L.sisze();i-->0;) //  Loop i in the range (input-length, 0]:
for(j=i;j-->0;)       //   Inner loop j in the range (i, 0]:
if((k=L.indexOf((a=L.get(i))
//    Set a to the i'th value in the list
+(b=L.get(j))   //    Set b to the j'th value in the list
//    And add a and b together
))               //    Set k to the index of this sum
>=0            //    If the index k is NOT -1
&k!=i&k!=j){     //    And k is also NOT i nor j:
Arrays.sort(t=new int[]{a,b,a+b});
//     Create an array t with items [a,b,a+b],
//     and sort the values of this triplet
//     Then convert this array to a String,
//     and add it to the result-TreeSet
return r;}              //  After the nested loop: return the result-TreeSet


Pyth, 13 bytes

{f}csT2T.cSQ3


Try it online!

Port of the solution thats been floating around.

How it works

{f}csT2T.cSQ3
.c  3  - All combinations length 3 of...
SQ   - The sorted input
f             - Filtered such that...
csT2        - Half the sum of each combination...
}    T       - Is an element of the original combination
{              - Remove duplicates


Pyth, 15 bytes

{mSdfqsPTeT.PQ3


Try it online!

Less sophisticated solution. Posting it because I think it can be golfed more

How it works

{mSdfqsPTeT.PQ3
.PQ3 - All 3 element permutations of the input
f           - Filtered such that
sPT       - The sum of the first 2 inputs...
q   eT     - Is equal to the last input
mSd            - Sort all elements
{               - Remove duplicates


JULIA

A solution w/o external package:

F(l)=(n=length(sort!(l));a=Set();
for i=1:n,j=1:n,k=1:n i<j<k&&(v=l[[i,j,k]];sum(v) in 2v)&&push!(a,v)end;
[a...])


Not a nice one 115 bytes of code (with 2 extra newlines for readability).

A solution using the non-core package Combinatorics:

using Combinatorics
H(l)=[Set(v for v in combinations(sort(l),3) if sum(v) in 2v)...]


Length 85 bytes (or 84 if you omit the space before the '''if''')
You can REPLIT online.

• Welcome to CG&CC! I tried running your solution online, but the Combinatorics package doesn't seem to be installed on TIO. I don't think there's any problem with using non-standard libraries so long as you mention them in the language header, but it might be a good idea to also write a solution that can be more easily verified. Nov 16 '19 at 9:21