21
\$\begingroup\$

Given an array of integers a which contains n integers, and a single integer x; remove the fewest amount of elements from a to make the sum of a equal to x. If no combinations of a can form x, return a falsy value.

As pointed out in a comment this is the maximum set with a sum of x, excuse my lesser math brain. I forgot a lot of terms since college.


Examples (Truthy):

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

f([2,2,2,2,2,2,2,2,2], 10) = [2,2,2,2,2]

f([2,2,2,2,-2,-2,-2,-4,-2], -8) = [2,2,-2,-2,-2,-4,-2]

f([-2,-4,-2], -6) = [-4,-2] OR [-2,-4]

f([2,2,2,4,2,-2,-2,-2,-4,-2], 0) = [2,2,2,4,2,-2,-2,-2,-4,-2] (Unchanged)

f([], 0) = [] (Unchanged Zero-sum Case)


Examples (Falsy, any consistent non-array value):

Impossible to Make Case: f([-2,4,6,-8], 3) = falsy (E.G. -1)

Zero Sum Case: f([], non-zero number) = falsy (E.G. -1)

  • Note: any value like [-1] cannot be valid for falsy, as it is a potential truthy output.

Rules:

  • Input may be taken in array form, or as a list of arguments, the last or first being x.
  • Output may be any delimited list of integers. E.G. 1\n2\n3\n or [1,2,3].
  • Any value can be used as a falsy indicator, other than an array of integers.
  • Your code must maximize the size of the end array, order does not matter.
    • E.G. For f([3,2,3],5) both [2,3] and [3,2] are equally valid.
    • E.G. For f([1,1,2],2) you can only return [1,1] as [2] is shorter.
  • Both the sum of a and the value of x will be less than 2^32-1 and greater than -2^32-1.
  • This is , lowest byte-count wins.
  • If there are multiple subarrays of the same size that are valid, it is not acceptable to output all of them. You must choose a single one and output that one.

Let me know if this has been posted, I couldn't find it.

Posts I found like this: Related but closed, ...

\$\endgroup\$
  • 1
    \$\begingroup\$ I suppose "Falsy, any consistent non-array value" includes raising an error? \$\endgroup\$ – Jonathan Allan Oct 31 '18 at 20:11
  • \$\begingroup\$ "Any value can be used as a falsy indicator, other than an array of integers." Does that include an empty array? \$\endgroup\$ – Shaggy Nov 1 '18 at 0:09
  • \$\begingroup\$ @shaggy [] is indicative of a potential truthy value, right? Is allowing that meta rule more important than distinct truthy and falsy? \$\endgroup\$ – Magic Octopus Urn Nov 1 '18 at 13:31
  • \$\begingroup\$ @JohnathanAllan if that error cannot be raised in a Truthy scenario- I'd suppose. But I feel this is intentionally attempting to stretch the spec. If i change the wording from indicator to return value is it fine then? \$\endgroup\$ – Magic Octopus Urn Nov 1 '18 at 13:33
  • \$\begingroup\$ I do believe consistent exit values do count as a return value though per meta? \$\endgroup\$ – Magic Octopus Urn Nov 1 '18 at 13:59

15 Answers 15

7
\$\begingroup\$

Brachylog, 8 bytes

h⊇.+~t?∧

Try it online!

Monthly Brachylog answer. Returns false. if it is not possible.

Explanation

h⊇.           The output is a subset of the head of the input
  .+~t?       The sum of the elements of the output must equal the tail of the input
       ∧      (Avoid implicit unification between the output and the input)
\$\endgroup\$
6
\$\begingroup\$

Python 2, 108 104 bytes

lambda a,n:[x for l in range(len(a)+1)for x in combinations(a,l)if sum(x)==n][-1]
from itertools import*

Try it online!

-4 bytes, thanks to Jonathan Allan


Python 2, 108 106 bytes

def f(a,n):
 q=[a]
 while q:
  x=q.pop(0);q+=[x[:i]+x[i+1:]for i in range(len(x))]
  if sum(x)==n:return x

Try it online!

-2 bytes, thanks to Janathan Frech

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 9 bytes

æʒOQ}0ªéθ

Try it online!

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

Japt -h, 11 bytes

à f_x ¥VÃñl

Try it online!

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

Pyth, 8 bytes

  • 8-byter (Try it!) – Outputs only one possible solution. For unsolvable inputs, it doesn't print anything to STDOUT, which is an empty string, which is technically speaking falsey in Pyth, but writes to STDERR. Thanks to FryAmTheEggman for suggesting this (ignoring STDERR and focusing on the STDOUT output only), thus saving 1 byte.

    efqz`sTy    
    
  • 9-byter (Try it!) – Outputs only one possible solution, wrapped in a singleton list as allowed by default (e.g. ([1...10], 10) -> [[1,2,3,4]]; ([], 0) -> [[]]). For unsolvable inputs, it returns [], which is falsey in Pyth.

    >1fqz`sTy
    
  • 10-byter (Try it!) – For a clearer output, without using the singleton-list rule and using 0 rather than [] as a falsy value.

    e+0fqz`sTy
    

Explanation

First, the code computes the powerset of the input list (all possible ordered sub-collections thereof). Then, it only keeps those collections whose sum is equal to the input number. It should be noted that the collections are generated from the shortest to the longest, so we focus on the last one. To obtain it:

  • The 8-byter simply uses the end built-in, which throws an error, but STDERR can be ignored as per our site rules, the output to STDOUT being an empty string, which is falsy.
  • The 9-byter takes the last element, but using the equivalent Python code lst[-1:] in place of lst[-1] to avoid errors from being thrown for unsolvable inputs.
  • The 10-byter prepends a 0 to the list of filtered sub-collections, then takes the end of that collection (last element). If the inputs aren't solvable, then 0 is naturally used instead.
\$\endgroup\$
  • \$\begingroup\$ [] is falsy? Neat. Why does Pyth do that []? \$\endgroup\$ – Magic Octopus Urn Oct 31 '18 at 19:44
  • \$\begingroup\$ @MagicOctopusUrn Pyth inherits that from Python actually: Try it online. \$\endgroup\$ – Mr. Xcoder Oct 31 '18 at 20:29
  • \$\begingroup\$ @FryAmTheEggman wouldn't an empty list be a truthy output in the test case f([], 0) = []? \$\endgroup\$ – Sok Nov 1 '18 at 13:54
  • \$\begingroup\$ @FryAmTheEggman Thanks for your suggestion! I've made the necessary changes :) \$\endgroup\$ – Mr. Xcoder Nov 1 '18 at 17:48
3
\$\begingroup\$

Jelly, 7 bytes

ŒPS⁼¥ƇṪ

Try it online!

Output clarified over TIO.

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

Perl 6, 38 37 bytes

{*.combinations.grep(*.sum==$_).tail}

Try it online!

Curried function.

\$\endgroup\$
  • \$\begingroup\$ Wait, is the ; even necessary? \$\endgroup\$ – Jo King Nov 4 '18 at 10:40
  • \$\begingroup\$ @JoKing It was necessary in an earlier iteration to avoid a "malformed double closure" error. But for some reason it can be omitted now. (I think after I replaced $^x with $_.) \$\endgroup\$ – nwellnhof Nov 4 '18 at 12:04
3
\$\begingroup\$

Brachylog, 4 bytes

⟨⊇+⟩

Try it online!

Just about equivalent to Fatalize's h⊇.+~t?∧, except a lot shorter, thanks to the predicate composition feature which according to the edit history of the reference was a work in progress until January 8, postdating the answer by over two months. ⟨⊇+⟩ is a sandwich, expanding to {[I,J]∧I⊇.+J∧}, where the braces are in this case irrelevant as the sandwich is on its own line anyhow.

                The input
[I,J]           is a list of two elements I and J.
        .       The output,
         +J     which sums to J
           ∧    (which we don't unify with the output),
      I⊇        is a sublist of I
     ∧          (which we don't unify with [I,J]).

A far less dramatic transformation of Fatalize's answer, which uses the same predicates with the same variables but comes out a byte shorter from being organized differently:

Brachylog, 7 bytes

h⊇.&t~+

Try it online!

           The input
h          's first element
 ⊇         is a superlist of
  .        the output,
   &       and the input
    t      's last item
     ~+    is the sum of the elements of
           the output.

(Also, if anyone wants to see something odd, change any of the underscores in the test cases into hyphens.)

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

Pyth, 14 bytes

A.Q|>1fqsTHyG0

Try it online!

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

Clean, 89 bytes

import StdEnv,Data.List,Data.Func
$n=find((==)n o sum)o sortBy(on(>)length)o subsequences

Try it online!

Defines the function $ :: Int -> [Int] -> (Maybe [Int]) returning Nothing if there is no appropriate combination of elements, and (Just [elements...]) otherwise.

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

JavaScript (ES6), 108 bytes

Takes input as (array)(n). Returns either an array or false.

a=>n=>a.reduce((a,x)=>[...a,...a.map(y=>1/r[(y=[...y]).push(x)]||eval(y.join`+`)-n?y:r=y)],[[]],r=!n&&[])&&r

Try it online!

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

This started out cool and small, but edge cases got me. Whatever happens, I'm proud of the work I put into this.

Python 3, 169 161 154 bytes

from itertools import*
def f(a,x):
	if sum(a)==x:return a
	try:return[c for i in range(len(a))for c in combinations(a,i)if sum(c)==x][-1]
	except:return 0

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Remember that this is [code-golf] so you should try to make your byte count as small as possible! You have a leading newline and some other trivial whitespace golfs, and I bet someone else who knows python can golf this down further. \$\endgroup\$ – Giuseppe Oct 31 '18 at 19:47
  • \$\begingroup\$ @Giuseppe Thanks for reminding me of the leading whitespace. I spent some time trying to consolidate some parts of this, but decided to post it in the meantime in case any others can suggest edits. \$\endgroup\$ – Gigaflop Oct 31 '18 at 19:52
  • \$\begingroup\$ Not a problem! It's been like 5 years since I did any Python, but doesn't range(x) generate (0...x-1)? So your range(len(a)) isn't giving you the possibility of leaving the array unchanged? \$\endgroup\$ – Giuseppe Oct 31 '18 at 20:02
  • \$\begingroup\$ @Giuseppe Eureka, that did it. I may have been focusing too much on the new material I was working with. \$\endgroup\$ – Gigaflop Oct 31 '18 at 20:06
  • \$\begingroup\$ Instead of if a==[] and x==0 use if sum(a)==x. Then you can also remove +1 from range. \$\endgroup\$ – Vedant Kandoi Nov 1 '18 at 6:24
2
\$\begingroup\$

R, 100 80 bytes

function(a,x){i[sum(a|1):0,j[combn(a,i,,F),if(sum(j)==x)return(j)]]
F}
`[`=`for`

Try it online!

20 bytes saved thanks to digEmAll

Returns FALSE for impossible criteria.

\$\endgroup\$
  • \$\begingroup\$ And 80 abusing '[' operator :D \$\endgroup\$ – digEmAll Nov 5 '18 at 8:45
  • \$\begingroup\$ @digEmAll I'm certainly glad I didn't get a chance to edit in your 98 byte answer :-) \$\endgroup\$ – Giuseppe Nov 5 '18 at 14:35
  • \$\begingroup\$ eheh forgot to delete it :D \$\endgroup\$ – digEmAll Nov 5 '18 at 15:24
1
\$\begingroup\$

Attache, 28 bytes

${(y&`=@Sum\Radiations@x)@0}

Try it online!

Alternatives

34 bytes: f[x,y]:=({y=Sum@_}\Radiations@x)@0

30 bytes: First@${y&`=@Sum\Radiations@x}

29 bytes: {(_&`=@Sum\_2)@0}#/Radiations

29 bytes: ${({y=Sum@_}\Radiations@x)@0}

29 bytes: `@&0@${y&`=@Sum\Radiations@x}

29 bytes: {_}@@${y&`=@Sum\Radiations@x}

Explanation

${(y&`=@Sum\Radiations@x)@0}
${                         }    function receiving two arguments, x and y
            Radiations@x        calculate the radiations of x
                                (simulates removing all possible subslices of x)
           \                    keep those radiations
        Sum                     ...whose sum...
     `=@                        ...equals...
   y&                           ...y
  (                     )@0     select the first one (always the longest)
\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 65 chars, 130 bytes

{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

↓ is used because the first element of the set of sets would be one void set (here ⍬ Zilde), that one want eliminate because it seems +/⍬ is zero...

For not find, or error it would return ⍬ or in print text:

  o←⎕fmt
  o ⍬
┌0─┐
│ 0│
└~─┘

test:

  z←{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

  o 1 z ,1
┌1─┐
│ 1│
└~─┘
  o 2 z ,1
┌0─┐
│ 0│
└~─┘
  o 10 z 1 2 3 4 5 6 7 8 9 10
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 2,2,2,2,2,2,2,2,2
┌5─────────┐
│ 2 2 2 2 2│
└~─────────┘
  o ¯8 z 2,2,2,2,¯2,¯2,¯2,¯4,¯2
┌7──────────────────┐
│ 2 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~──────────────────┘
  o ¯6 z ¯2,¯4,¯2
┌2─────┐
│ ¯4 ¯2│
└~─────┘
  o 0 z 2,2,2,4,2,¯2,¯2,¯2,¯4,¯2
┌10───────────────────────┐
│ 2 2 2 4 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~────────────────────────┘
  o 10 z 1 2 3 4
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 1 2 3
┌0─┐
│ 0│
└~─┘
  o 0 z ⍬
┌0─┐
│ 0│
└~─┘
  o +/⍬  
0
~
\$\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.