8
\$\begingroup\$

Let's say I've got a list (or array) of:

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

I want to get the third Cartesian power of the above list, where we take every possible triple of elements from l.

Then I want to filter and only keep the sublists where the sum of that sublist equal to the maximum value of the list.

Then I only want one sublist, which is the sublist where the difference of the three numbers that add up to the maximum value is the smallest.

The algorithm to see the smallest difference could be something like (in Python):

max(v1,v2,v3) - min(v1,v2,v3)

So the expected output for this case would be:

(3, 3, 4)

The order of the elements within the output could be in any order.

Test cases:

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
-> (3, 3, 4)

l = [1, 2, 3, 4, 5]
-> (1, 2, 2)

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
-> (33, 33, 34)

l = [1, 4, 5, 2, 3, 9, 8, 7, 10, 6]
-> (3, 3, 4)

l = [1, 4, 8, 12, 13, 16, 20, 24, 27]
-> (1, 13, 13)

This is tagged with , so the shortest code in bytes wins!

There will always be an output, never would be a case where no 3 elements would add up to the maximum value.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ suggest [1, 3, 6, 7, 13] -> (3, 3, 7) \$\endgroup\$
    – att
    Dec 28, 2021 at 7:02
  • \$\begingroup\$ So this is some kind of an approximation to "1/3 * max number"? \$\endgroup\$ Dec 30, 2021 at 0:33

17 Answers 17

4
\$\begingroup\$

Factor + math.combinatorics math.unicode, 83 bytes

[ dup supremum swap 3 selections [ Σ = ] with filter [ minmax - abs ] infimum-by ]

Try it online!

Explanation

                            ! { 1 2 3 4 5 }
dup                         ! { 1 2 3 4 5 } { 1 2 3 4 5 }
supremum                    ! { 1 2 3 4 5 } 5
swap                        ! 5 { 1 2 3 4 5 }
3 selections                ! 5 { { 1 1 1 } { 1 1 2 } ... }
[ Σ = ] with filter         ! { { 1 1 3 } { 1 2 2 } ... }
[ minmax - abs ] infimum-by ! { 1 2 2 }
\$\endgroup\$
0
4
\$\begingroup\$

Wolfram Language (Mathematica), 39 55 bytes

l#&@@SortBy[l~Tuples~3,Abs[Max@l-Tr@#]|Max@#-Min@#&]

Try it online!

Slow for larger input lists.

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

R, 105 96 bytes

(or 89 bytes in R≥4.1 by using \ for function)

Edit: -9 bytes thanks to pajonk

function(l,a=expand.grid(l,l,l),b=apply(a[rowSums(a)==max(l),],1,sort))b[,order(b[3,]-b[1,])[1]]

Try it online!

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Try expand.grid without rep! \$\endgroup\$
    – pajonk
    Dec 28, 2021 at 11:46
  • 1
    \$\begingroup\$ @pajonk - I saw it in your answer, and was just editing it in, but it seemed sneaky... \$\endgroup\$ Dec 28, 2021 at 11:47
  • \$\begingroup\$ @DominicvanEssen Wow! First R answer here! Thanks. \$\endgroup\$ Dec 28, 2021 at 11:50
  • 1
    \$\begingroup\$ I've deleted my longer straightforward boring answer after seeing yours. \$\endgroup\$
    – pajonk
    Dec 28, 2021 at 11:50
  • 1
    \$\begingroup\$ @U12-Forward - I'll edit to mention it. Generally, though, I don't use it where it doesn't achieve better than the trivial 7-byte saving (especially because it's convenient to be able to directly compare answers on 'Try it online', which doesn't support R version 4.1). \$\endgroup\$ Dec 28, 2021 at 12:01
3
\$\begingroup\$

Vyxal, 18 bytes

3ÞẊ'∑?G=;µ÷Ȯε^ε+;h

Try it Online!

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

Vyxal, 16 bytes

3ÞẊ'∑?G=;µ₌Gg-;h

Try it Online!

-2 thanks to Bubbler's insight.

3ÞẊ              # Combinations of input of length 3
   '    ;        # Filter by...
    ∑  =         # Sum equals
     ?G          # Maximum of input
         µ    ;h # Minimum by...
          ₌Gg-   # Difference of min + max
\$\endgroup\$
3
\$\begingroup\$

Python 3.8, 130 115 99 85 80 bytes:

-14 Thanks to @tsh
-5 Thanks again to @tsh

lambda l:max([((z:=max(l)-x-y)in l,x<=y<=z,x-z,x,y,z)for x in l for y in l])[3:]

Try it Online!

Get's the Cartesian Product by looping the list 3 times, and summing it up.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ 85: lambda l:min([(x>y,y>z,x+y+z!=max(l),z-x,x,y,z)for x in l for y in l for z in l])[4:] \$\endgroup\$
    – tsh
    Dec 28, 2021 at 5:37
  • 1
    \$\begingroup\$ @tsh Woo, why didn't I think of that! Edited my answer. \$\endgroup\$ Dec 28, 2021 at 5:39
  • 2
    \$\begingroup\$ 80: lambda l:max([((z:=max(l)-x-y)in l,x<=y<=z,x-z,x,y,z)for x in l for y in l])[3:] \$\endgroup\$
    – tsh
    Dec 28, 2021 at 5:43
  • \$\begingroup\$ @tsh Edited, wow!! \$\endgroup\$ Dec 28, 2021 at 5:46
3
\$\begingroup\$

Jelly (fork), 11 bytes

ṗ3SƘṀṀ_ṂƊÞḢ

Try it online! (this is the equivalent in normal Jelly)

This uses my fork of Jelly which includes the Ƙ (keep-like) quick to replace the commonly used <link>⁼¥Ƈ pattern. You can see this in the TIO link.

How it works

ṗ3SƘṀṀ_ṂƊÞḢ - Main link. Takes a list L on the left
ṗ3          - Cartesian Cube
    Ṁ       - Maximum of L
   Ƙ        - Keep triples whose     is like the maximum
  S         -                    sum
        ƊÞ  - Sort the remaining triples by:
     Ṁ      -   maximum
      _     -   minus
       Ṃ    -   minimum
          Ḣ - Take the first
\$\endgroup\$
0
3
\$\begingroup\$

Husk, 14 13 bytes

-1 byte thanks to Dominic van Essen

◄§-▼▲fo=▲¹Σπ3

Try it online!

Explanation

◄§-▼▲fo=▲¹Σπ3
           π3     cartesian product of 3 * input
     fo          filter by composed function
       =▲¹Σ      max of input equals sum
◄§               min by composed binary function
  -▼▲            max - min
\$\endgroup\$
2
  • 1
    \$\begingroup\$ -1 byte by changing ΠR3 (cartesian product of 3 copies of input) to π3 (cartesian power of 3 of input) \$\endgroup\$ Dec 28, 2021 at 13:53
  • \$\begingroup\$ Unfortunately, Jonathan's trick fails for [1,2,5,7,11] \$\endgroup\$ Dec 30, 2021 at 13:35
2
\$\begingroup\$

APL+WIN, 53 bytes

Prompts for list

↑((⌊/m)=m←(⌈/¨l)-⌊/¨l)/l←((⌈/i)=+/¨l)/l←,i∘.,,i∘.,i←⎕

Try it online! Thanks to Dyalog Classic

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

Python/NumPy, 77 bytes

lambda l:min(l[argwhere(sum(ix_(l,l,l))==max(l))],key=ptp)
from numpy import*

Attempt This Online!

Takes and returns numpy arrays. Approach is straightforward. ix_(l,l,l) is essentially the cartesian product. This is then summed over coordinates and compared to the maximum. argwhere extracts the coordinates where the comparison succeeds and these are used to index back into l. It remains to select a triplet that minimises the spread (difference between min and max). Rather conveniently, numpy has a function for the spread: ptp

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

Ruby, 73 72 68 61 bytes

->l{l.product(l,l).min_by{|x|[(l.max-x.sum)**2,x.max-x.min]}}

Try it online!

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

MATL, 28 25 bytes

3Z^!tsGX>=Z)ttX<-X>&S1)Z)

Try it online!

3Z^     % Third Cartesian power 

!ts     % Sum of each sublist

GX> =   % See which ones' sums equal input's maximum

Z)      % Filter to keep only those

ttX<-   % Subtract from each sublist its Minimum  

X>      % Maximum of each. Effectively this is (Max - Min)

&S      % Get the indices that would sort this result

1)      % Get the first index of those i.e. the argmin

Z)      % Extract the sublist at that index

(Equivalently, perhaps slightly more clearly, 3Z^!tsGX>=Z)tX>yX<-&S1)Z) - instead of "effectively" doing max - min, just explicitly does max - min.)

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

Charcoal, 38 bytes

FθFθFθ⊞υ⟦ικλ⟧≔Φυ⁼Σι⌈θυ≔Eυ⁻⌈ι⌊ιθI§υ⌕θ⌊θ

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

FθFθFθ⊞υ⟦ικλ⟧

Create the Cartesian product of three copies of the list.

≔Φυ⁼Σι⌈θυ

Extract those triples that sum to the maximum of the original list.

≔Eυ⁻⌈ι⌊ιθ

For each triple, find the difference between its largest and smallest entries.

I§υ⌕θ⌊θ

Output the first triple with the smallest difference.

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

Perl 5 List::Util, 140 bytes

sub{$"=',';my$m;($d=max(@$_)-min@$_)<($m//9e9)and($m,@r)=($d,@$_)for grep max(@_)==sum(@$_),map[split$"],glob"{@_},{@_},{@_}";sort{$a-$b}@r}

Try it online!

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

Scala, 85 bytes

a=>(for{x<-a;y<-a;z<-a if x+y+z==a.max}yield Seq(x,y,z)).minBy(l=>l.max-l.min).sorted

Try it online!

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

Haskell, 97 bytes

import Data.List
f x=head$sortOn(\t->m t-minimum t)$filter((==m x).sum)$sequence[x,x,x]
m=maximum

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ 92 bytes \$\endgroup\$
    – Wheat Wizard
    Dec 29, 2021 at 13:21
  • \$\begingroup\$ 74 bytes \$\endgroup\$
    – Wheat Wizard
    Dec 29, 2021 at 13:27
  • \$\begingroup\$ a Wizard you are indeed. I knew my solution was clunky, I didn't know it was that clunky \$\endgroup\$ Dec 29, 2021 at 13:51
  • 1
    \$\begingroup\$ The main issue is just the import really. If you weren't burdened by it all 3 versions would be roughly comparable. \$\endgroup\$
    – Wheat Wizard
    Dec 29, 2021 at 13:58
1
\$\begingroup\$

C++ (gcc), 280 \$\cdots\$ 211 210 bytes

#import<regex>
#define S(v)std::sort(&v[0],&*end(v))
using V=std::vector<int>;int f(V&v){V r=v,x;S(v);int m=v.back(),n=m,t;for(int a:r)for(int b:r)for(int c:r)x={a,b,c},S(x),t=x[2]-x[0],v=t<m&a+b+c==n?m=t,x:v;}

Try it online!

Saved 3 4 bytes thanks to ceilingcat!!!

Inputs a vector of integers.
Replaces the input vector with the cartesian product of 3 elements of the input vector that add up to the maximum of the input vector and that have the minimum difference between the smallest and the largest element from all of the cartesian products.

\$\endgroup\$
2
  • \$\begingroup\$ See att's comment on Jonathan's (now deleted) answer: [1,2,5,7,11] should output [1,5,5] (difference 4), not [2,7,7] (difference 5). \$\endgroup\$ Dec 29, 2021 at 15:27
  • \$\begingroup\$ @DominicvanEssen Reverted back to my original solution - thanks! :D \$\endgroup\$
    – Noodle9
    Dec 29, 2021 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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