16
\$\begingroup\$

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.
\$\endgroup\$
  • 6
    \$\begingroup\$ 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). \$\endgroup\$ – Lynn Nov 14 at 16:43
  • 1
    \$\begingroup\$ @Lynn Thank you a lot for your contributions. \$\endgroup\$ – chau giang Nov 14 at 23:53

14 Answers 14

9
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – manatwork Nov 14 at 10:02
  • \$\begingroup\$ You are right. Fixed now. \$\endgroup\$ – G B Nov 14 at 10:37
  • \$\begingroup\$ Yepp, that was the easy fix. But handling negative numbers like in test case B [1, 0, -1] may be harder. ☹ \$\endgroup\$ – manatwork Nov 14 at 10:55
  • \$\begingroup\$ Oops. Fixed again. \$\endgroup\$ – G B Nov 14 at 11:05
8
\$\begingroup\$

05AB1E, 11 10 9 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).

Try it online or verify all test cases.

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 
\$\endgroup\$
  • 1
    \$\begingroup\$ xsOå can also be œÆP>. Same byte-count, but more stylish. \$\endgroup\$ – Grimmy Nov 14 at 13:55
  • 1
    \$\begingroup\$ @Grimmy The Æ was also in my 9-byter. :) I've added it (with 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. :) \$\endgroup\$ – Kevin Cruijssen Nov 14 at 14:03
6
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ [2,2,4] shouldn't be a magic triplet. I think you can fix by replacing the sort by distinct. \$\endgroup\$ – Kroppeb Nov 15 at 16:27
  • \$\begingroup\$ 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. \$\endgroup\$ – Unrelated String Nov 15 at 22:40
  • \$\begingroup\$ by bad, I didn't read the question properly. \$\endgroup\$ – Kroppeb Nov 16 at 11:58
5
\$\begingroup\$

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

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Flooring the halved sum adds (0 0 1) to the new last test case ([0,0,0,0,1]). \$\endgroup\$ – Unrelated String Nov 14 at 7:51
  • 1
    \$\begingroup\$ ...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. \$\endgroup\$ – Unrelated String Nov 14 at 8:01
  • 1
    \$\begingroup\$ @UnrelatedString Rolled back to a previous version. That test case was modified later (OP added the second 40), so I had the old version. \$\endgroup\$ – Jo King Nov 14 at 8:04
  • \$\begingroup\$ Ah, makes sense. \$\endgroup\$ – Unrelated String Nov 14 at 8:25
4
\$\begingroup\$

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()
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 78 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

K (oK), 38 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 66 bytes

FLθFLθFLθF¬⌈⟦⁼ικ⁼ιλ⁼κ뛧θι§θꛧθκ§θλ⟧«≔E⟦ικλ⟧§θνη¿∧№η⊘Ση¬№υη⊞υη»Iυ

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

FLθFLθFLθF¬⌈⟦

Loop through all triples of indices...

⁼ικ⁼ιλ⁼κλ

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

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

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

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

... 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.

»Iυ

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

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

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
        r.add(Arrays.toString(t));}
                          //     Then convert this array to a String,
                          //     and add it to the result-TreeSet
  return r;}              //  After the nested loop: return the result-TreeSet
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Unrelated String Nov 16 at 9:21

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.