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 '21 at 7:02
  • \$\begingroup\$ So this is some kind of an approximation to "1/3 * max number"? \$\endgroup\$ Dec 30 '21 at 0:33

16 Answers 16

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 '21 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 '21 at 11:47
  • \$\begingroup\$ @DominicvanEssen Wow! First R answer here! Thanks. \$\endgroup\$ Dec 28 '21 at 11:50
  • 1
    \$\begingroup\$ I've deleted my longer straightforward boring answer after seeing yours. \$\endgroup\$
    – pajonk
    Dec 28 '21 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 '21 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 '21 at 5:37
  • 1
    \$\begingroup\$ @tsh Woo, why didn't I think of that! Edited my answer. \$\endgroup\$ Dec 28 '21 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 '21 at 5:43
  • \$\begingroup\$ @tsh Edited, wow!! \$\endgroup\$ Dec 28 '21 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\$
3
  • 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 '21 at 13:53
  • \$\begingroup\$ Unfortunately, Jonathan's trick fails for [1,2,5,7,11] \$\endgroup\$ Dec 30 '21 at 13:35
  • \$\begingroup\$ thanks, reverted \$\endgroup\$
    – Natte
    Dec 30 '21 at 21:28
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\$
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 '21 at 13:21
  • \$\begingroup\$ 74 bytes \$\endgroup\$
    – Wheat Wizard
    Dec 29 '21 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 '21 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 '21 at 13:58
1
\$\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\$
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 '21 at 15:27
  • \$\begingroup\$ @DominicvanEssen Reverted back to my original solution - thanks! :D \$\endgroup\$
    – Noodle9
    Dec 29 '21 at 18:04

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.