37
\$\begingroup\$

Introduction:

A few days ago I read this post with the same title when I came across it in the HNQ. In this question it is being discussed if the claim of president-candidate Bernie Sanders, who claimed the following:

Today the world's richest 26 billionaires, 26, now own as much wealth as the poorest 3.8 billion people on the planet, half of the world's population.
Link to video

is true or not. Please go to the question itself for answers and discussions there.

As for the actual challenge based on this claim:

Challenge:

Two inputs: a descending sorted number-list \$L\$ and a number \$n\$ (where \$n\$ is \$1\leq n\lt \text{length of }L\$).
Output: the longest possible suffix sub-list of \$L\$ for which the total sum is \$\leq\$ the sum of the first \$n\$ values in list \$L\$.

Example:

Inputs: \$L\$ = [500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3] and \$n=2\$.
Output: [125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3]

Why?

The first \$n=2\$ values of the list \$L\$ ([500,200]) sum to 700. If we take all suffixes of the remaining numbers, as well as their sums:

Suffix:                                                                  Sum:

[-3]                                                                     -3
[-2,-3]                                                                  -5
[0,-2,-3]                                                                -5
[1,0,-2,-3]                                                              -4
[2,1,0,-2,-3]                                                            -2
[2,2,1,0,-2,-3]                                                          0
[3,2,2,1,0,-2,-3]                                                        3
[5,3,2,2,1,0,-2,-3]                                                      8
[5,5,3,2,2,1,0,-2,-3]                                                    13
[5,5,5,3,2,2,1,0,-2,-3]                                                  18
[5,5,5,5,3,2,2,1,0,-2,-3]                                                23
[10,5,5,5,5,3,2,2,1,0,-2,-3]                                             33
[10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                          43
[20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                       63
[30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                    93
[30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                                 123
[40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                              163
[50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                           213
[55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                        268
[75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                     343
[75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]                  418
[100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]              518
[125,100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]          643
[150,125,100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]      793
[150,150,125,100,75,75,55,50,40,30,30,20,10,10,5,5,5,5,3,2,2,1,0,-2,-3]  943

The longest suffix which has a sum lower than or equal to 700 is [125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3] with a sum of 643, so that is our result.

Challenge rules:

  • Values in the first \$n\$ prefix aren't counted towards the output-suffix. I.e. inputs \$L\$ = [10,5,5,3] and \$n=2\$ would result in [5,3], and not [5,5,3].
  • I/O is flexible. You can input \$L\$ as a list/stream/array of integers/decimals/strings, a single delimited string, one by one through STDIN, etc. You can output as a list/stream/array of integers/decimals/strings as well, print/return a delimited string, print a number on each newline, etc. Your call.
  • The output is guarantees to be non-empty. So you won't have to deal with test cases like \$L\$ = [-5,-10,-13] and \$n=2\$ resulting in [].
  • Both (or either) the input and/or output may also be in ascending order instead of descending order if you choose to.

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Test cases:

Inputs: L=[500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3], n=2
Output: [125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3]

Inputs: L=[10,5,5,3], n=2
Output: [5,3]

Inputs: L=[7,2,1,-2,-4,-5,-10,-12], n=7
Output: [-12]

Inputs: L=[30,20,10,0,-10,-20,-30], n=1
Output: [20,10,0,-10,-20,-30]

Inputs: L=[100,35,25,15,5,5,5,5,5,5,5,5,5,5,5,5,5], n=1
Output: [15,5,5,5,5,5,5,5,5,5,5,5,5,5]

Inputs: L=[0,-5,-10,-15], n=2
Output: [-10,-15]

Inputs: L=[1000,999,998,900,800,766,525,525,400,340,120,110,80,77,33,12,0,-15,-45,-250], n=2
Output: [525,525,400,340,120,110,80,77,33,12,0,-15,-45,-250]

Inputs: L=[10,5,5], n=1
Output: [5,5]
\$\endgroup\$
  • \$\begingroup\$ Can I write an answer that only works with positive (or maybe nonnegative; I haven't written it yet) integers due to the lack of an integer type in the language? \$\endgroup\$ – Neil Jul 1 at 8:38
  • 3
    \$\begingroup\$ @Neil I assume you're talking about Retina here? But sure, you can assume all the values are non-negative in that case. Although, do you best to also have a second version that works for negative values, because I have the feeling that might actually be achievable (with a huge increase in byte-count and some work-arounds); which is more of a general feeling than actual fact, not sure if it is indeed possible to work-around the negative values part). \$\endgroup\$ – Kevin Cruijssen Jul 1 at 8:41
  • 6
    \$\begingroup\$ The real test case would look like that: [131000000000, 96500000000, 82500000000, 76000000000, (7.7 billion more entries)] :p \$\endgroup\$ – Arnauld Jul 1 at 10:06
  • 2
    \$\begingroup\$ What about the scenario where none of the values meet the criteria: [1,2,3] n = 1? What do you want for output? \$\endgroup\$ – ouflak Jul 1 at 12:48
  • \$\begingroup\$ @ouflak See the third challenge rule: "The output is guarantees to be non-empty. So you won't have to deal with test cases like L = [-5,-10,-13] and n=2 resulting in []." Also, the input-list is guaranteed to be sorted descending (or ascending if you choose to), so [1,2,3] isn't a valid input-list to begin with (unless you choose ascending input, in which case [1,2] would be the result). \$\endgroup\$ – Kevin Cruijssen Jul 1 at 12:49

31 Answers 31

17
\$\begingroup\$

C# (Visual C# Interactive Compiler), 88 81 69 68 63 bytes

-4 bytes thanks to LiefdeWen

a=>b=>a.Skip(b).Where((x,i)=>a.Skip(i+b).Sum()<a.Take(b).Sum())

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I'm thinking you could shave off two more by eliminating +b in the Skip call; it's redundant to check the first n list, but I think it's still correct. \$\endgroup\$ – TheRubberDuck Jul 2 at 16:43
  • 3
    \$\begingroup\$ @TheRubberDuck nope, had to add it in for the case where the prefix and suffix overlap. I.e [10,5,5,3], n = 2 \$\endgroup\$ – Expired Data Jul 2 at 16:45
  • \$\begingroup\$ 64 bytes \$\endgroup\$ – LiefdeWen Jul 4 at 9:44
  • \$\begingroup\$ @LiefdeWen nice! it's actually less too if we use a curried function \$\endgroup\$ – Expired Data Jul 4 at 9:46
  • \$\begingroup\$ @ExpiredData Oh yeah, forgot I removed it. \$\endgroup\$ – LiefdeWen Jul 4 at 9:47
12
\$\begingroup\$

EXAPUNKS (2 EXAs, 30 Instructions, 594-byte solution file)

I've wanted to try a code golf challenge in EXAPUNKS for a while, and you looked like the best fit I could find, so, congrats!

Input via files 200 and 201, for L and n respectively. Output via a new file. L and the output are in ascending order.

Basically, XA sums the last n values in L, then sends it to XB. It then seeks to the beginning of L and sends each value one-by-one to XB. XB first receives the total from XA and stores it in register X. It then receives values one-by-one from XA, deducting the new value from X, and writing those values to the output file until X < 0.

XA

GRAB 201
SUBI T F T
DROP
GRAB 200
SEEK 9999
SEEK T
MARK FIRST_SUM
ADDI F X X
ADDI T 1 T
SEEK -1
VOID F
TJMP FIRST_SUM
COPY X M
SEEK -9999
MARK SECOND_SUM
COPY F M
TEST EOF
FJMP SECOND_SUM
KILL

XB

MAKE
COPY M X
MARK LOOP
COPY M T
COPY T F
SUBI X T X
TEST X > 0
TJMP LOOP
SEEK -1
VOID F
KILL

JavaScript for the level here

\$\endgroup\$
  • \$\begingroup\$ IIRC doesn't exapunks have a way to save solutions? If so you should use byte count rather than in game instructions. \$\endgroup\$ – Wheat Wizard Jul 1 at 20:04
  • 1
    \$\begingroup\$ @SriotchilismO'Zaic, yep, I didn't think the files were supposed to be easily-accessible, but I've just found them. I'll add the size-on-disk. A bunch of metadata that I didn't write gets stored alongside it, but I guess this is the best way to actually get a single "byte count" out of this game. \$\endgroup\$ – ymbirtt Jul 1 at 20:51
  • \$\begingroup\$ I'd love to take the time to look at these files and see if there is a way to sort of golf the metadata down. I also wonder if some instructions take more memory than others. \$\endgroup\$ – Wheat Wizard Jul 1 at 23:01
  • \$\begingroup\$ @SriotchilismO'Zaic, they actually do. All the instructions get stored as plaintext, so for a start we can turn all the marks to single-letter identifiers. The name of your solution is in there, so we can remove a few bytes by calling the solution 'a'. Some parts of it also seem related to the virtual network you created for the EXA, though. Honestly, I think the "fairest" way to score EXAPUNKS solutions is to either use the byte count of the actual code, or the number of instructions. This might be worth a meta post... \$\endgroup\$ – ymbirtt Jul 2 at 5:56
  • 2
    \$\begingroup\$ @ymbirtt I suppose the question then comes down to could you write an interpreter which will look at the instructions and convert into the saved data? Well trivially yes, just write a program which inputs for you from the source.. it would count as a different language though. \$\endgroup\$ – Expired Data Jul 2 at 7:02
11
\$\begingroup\$

Python 2, 60 bytes

l,n=input()
s=sum(l[:n])
while sum(l[n:])>s:n+=1
print l[n:]

Try it online!


Explanation:

First takes the sum of the first n items.

Then the sum of each sublist is compared to this sum. As soon as one is not larger, we stop.

Then the resulting (longest) sublist is printed.

\$\endgroup\$
  • 2
    \$\begingroup\$ actually the most readable one +1 \$\endgroup\$ – Kryštof Řeháček Jul 2 at 10:46
10
\$\begingroup\$

05AB1E, 14 12 bytes

Saved 2 bytes thanks to Grimy

.$ΔDOI¹£O›.$

Try it online!

Explanation

.$               # drop the first n entries of the list
  Δ              # repeat the following code until the result doesn't change
   DO            # duplicate and sum the copy
     I¹£O        # calculate the sum of the first n items of the input
         ›.$     # if the current sum is greater than the sum of the first n items
                 # remove the first item of the current list
\$\endgroup\$
  • 2
    \$\begingroup\$ 'Exactly' the same as what I had prepared as solution. And by 'exactly' I mean mine was .$.sʒO²¹£O>‹}θ. :) \$\endgroup\$ – Kevin Cruijssen Jul 1 at 11:45
  • 2
    \$\begingroup\$ @KevinCruijssen here's 12 \$\endgroup\$ – Grimmy Jul 1 at 14:26
  • 1
    \$\begingroup\$ ASCII-only 12 (using a different input method). \$\endgroup\$ – Grimmy Jul 1 at 14:45
  • 1
    \$\begingroup\$ @Grimy: Huh. I never knew | overwrote the last-input, interesting. \$\endgroup\$ – Emigna Jul 1 at 14:50
  • 2
    \$\begingroup\$ @Grimy: See this vs this. Normally when all inputs are consumed, the last input is implicitly used for all instances of next input. Using | here makes the result of | become the last input instead of what was actually the last input. \$\endgroup\$ – Emigna Jul 1 at 14:59
7
\$\begingroup\$

J, 18 bytes

}.#~+/@{.>:+/\.@}.

Try it online!

Explanation:

A dyadic verb, taking n as its left argument and L - as its right argument.

                }.  drop the first n items from L 
               @    and
             \.     for each suffix (starting from the longest)
           +/       find its sum
         >.         is this sum smaller or equal than (results in a boolean vector)
    +/              the sum 
      @             of
       {.           the first n items of L
  #~                use the 1s in the boolean vector to copy the respective
}.                  elements of L (without the first n)
\$\endgroup\$
7
\$\begingroup\$

Ruby, 47 43 bytes

Takes an ascending list as input. Removes \$n\$ items from the end of the array to get the initial sum, then continue removing items until the remaining elements' sum is less than the initial sum.

-4 bytes by reading the spec more closely.

->a,n{s=a.pop(n).sum;a.pop while a.sum>s;a}

Try it online!

\$\endgroup\$
7
\$\begingroup\$

R, 53 55 bytes

@Giuseppe saved me 2 bytes changing the way remove was done

function(n,L,Y=rev(L[0:-n]))Y[cumsum(Y)<=sum(L[1:n])]

Try it online! Takes the input as descending and outputs in ascending as allowed by rule 4.

  • Y is the rev of L with 1:n removed using 0:-n
  • returns from Y where cumulative sum is less then equal to the sum of L[X]
\$\endgroup\$
  • \$\begingroup\$ @Giuseppe as always thanks. Tried removing the X using -(1:n) but of course that was the same size, so left it \$\endgroup\$ – MickyT Jul 1 at 22:55
6
\$\begingroup\$

JavaScript (ES6), 66 bytes

Takes input as (a)(n) with the list in ascending order.

a=>n=>(g=s=>n?g(s+a.pop(n--)):eval(a.join`+`)>s?g(s,a.pop()):a)(0)

Try it online!

Commented

a => n =>               // a[] = list, n = number of richest guys
  ( g = s =>            // g is a recursive function taking a sum s
    n ?                 // if n is not equal to 0:
      g(s + a.pop(n--)) //   recursive call: add the last entry to s and decrement n
    :                   // else:
      eval(a.join`+`)   //   if the sum of the remaining entries
      > s ?             //   is greater than s:
        g(s, a.pop())   //     recursive call with the last entry removed
      :                 //   else:
        a               //     stop recursion and return a[]
  )(0)                  // initial call to g with s = 0
\$\endgroup\$
  • 1
    \$\begingroup\$ @KevinCruijssen Seems like I misread the requirement. Should be fixed now. \$\endgroup\$ – Arnauld Jul 1 at 12:32
  • \$\begingroup\$ And unlike some other answers that had fixed the same issue, without an increase in byte-count. :) (And partially my bad, should have included a test case for \$\leq\$ to begin with..) \$\endgroup\$ – Kevin Cruijssen Jul 1 at 12:32
5
\$\begingroup\$

Python 2, 59 bytes

Also compatible with Python 3

f=lambda l,n:l[n:]*(sum(l)/2>=l.pop(n)+sum(l[n:]))or f(l,n)

Try it online!


Explanation

The sum of the suffix is compared to half of the sum of the whole list. If the sum of the suffix is smaller or equal, the suffix is returned. If not, the function is called recursively with the first item of the suffix popped out.

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

Pyth, 16 15 bytes

efgs>vzQsT._<vz

Try it online!

The input list is expected to be sorted in ascending order, rather than descending as is used in the examples.

It's at times like this when I really wish Pyth had a single token operator to access the second input more than once (E evaluates the next line of input, but repeated calls discard the previous value read).

efgs>vzQsT._<vzQ   Implicit: Q=eval(input()), z=input() - that is, Q is list, z is string n
                   Trailing Q inferred
             vz    Evaluate z as integer
            <  Q   Remove the above number of elements from the end of Q
          ._       Generate a list of all prefixes of the above
 f                 Filter keep elements of the above, as T, where:
    >vzQ             Take the last z elements of Q
   s                 Sum
  g                  Is the above greater than or equal to...
        sT           ... the sum of T?
e                  Take the last remaining element, implicit print

Edit: saved 1 byte thanks to MrXcoder

\$\endgroup\$
  • \$\begingroup\$ @Mr.Xcoder Good grief, what an obvious save! Thanks 👍 \$\endgroup\$ – Sok Jul 1 at 13:05
4
\$\begingroup\$

JavaScript, 64 bytes

f=(a,n,s=0,[h,...t]=a)=>n<1?f(a)>s?f(t,0,s):a:1/h?f(t,n-1,s+h):s

Try it online!

f=(
  a,               // remaining array
  n,               // if n >= 0: we try to find suffix <= s + a[0..n]
                   // if n is NaN (or undefined): we calculate sum(a) + s
  s = 0,           // previous sum
  [h, ...t] = a    // split array (a) into head (h) and tail (t)
) => (n < 1 ?      // if n == 0
  f(a) > s ?       //   if sum(a) > s
    f(t,0,s) :     //     drop head and test tail again
    a :            //   otherwise, a is the answer
  1 / h ?          // if a is not empty
    f(t,n-1,s+h) : //   add head to sum and recurse
    s              //   we only reach here if n is NaN, return the sum
)
\$\endgroup\$
4
\$\begingroup\$

Stax, 12 bytes

îo╧╫Σ↑>'qµΣº

Run and debug it at staxlang.xyz!

Nicer version

Unpacked (14 bytes) and explanation:

:/|]{|+n|+>!}j
:/                Split array at index.
  |]              Suffixes. The bit after the split (the poor) is on top for this.
    {       }j    First item in array that yields truthy under the block:
     |+             Sum array (collective wealth of the many).
       n            Copy second item to top of stack.
        |+          Sum again. Wasted computation, but this location saves a byte.
          >!        Second item on stack less than or equal to first?

By consensus, I can leave this result on the stack. Stax will attempt an implicit print, which might fail, but appending an m to the unpacked program lets you see the output nicely.

Looks like { ... }j is the same as { ... fh. Huh. Edit: That's not quite the case; the only the former will stop when it gets a truthy result, possibly avoiding side effects or a fatal error later on.

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

APL+WIN, 27 bytes

Prompts for input of L then n.

⌽((+/n↑v)≥+\m)/m←⌽(n←⎕)↓v←⎕

Try it online! Courtesy of Dyalog Classic

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

Japt, 16 bytes

£sV+YÃæ_x §U¯V x

Try it

£sV+YÃæ_x §U¯V x     :Implicit input of U=L and V=n
£                    :Map U, with Y being the 0-based indices
 sV+Y                :  Slice U from index V+Y
     Ã               :End map
      æ              :First element that returns true
       _             :When passed through the following function
        x            :  Reduce by addition
          §          :  Less than or equal to
           U¯V       :    Slice U to index V
               x     :    Reduce by addition
\$\endgroup\$
3
\$\begingroup\$

Jelly, 13 12 bytes

ṫḊÐƤS>¥ÞḣS¥Ḣ

Try it online!

Thanks to @JonathanAllan for saving a byte!

A dyadic link taking the list of values \$L\$ as left argument and the number \$n\$ as right.

Explanation

ṫ            | Tail: take all values of L from the nth onwards (which is actually one too many; dealt with below)
 ḊÐƤ         | Take all suffixes, removing the first value from each. This will yield a list of all possible suffixes of L that exclude the first n values
       Þ     | Sort by:
    S>¥ ḣS¥  | - The sum is greater than the sum of the first n values of L
           Ḣ | Take the first resulting list and return from link (implicitly output when called as a full program)
\$\endgroup\$
  • \$\begingroup\$ You can save a byte by sorting instead of filtering: ṫḊÐƤS>¥ÞḣS¥Ḣ \$\endgroup\$ – Jonathan Allan Jul 1 at 17:12
3
\$\begingroup\$

Gaia, 12 bytes

eSe¤Σ¤┅⟪Σ⊃⟫∇

Try it online!

I think there's a byte I can golf if I get the stack just right.

e	| eval first input as Gaia code
S	| Split into a list of ["first n elements" "rest of elements"]
e	| dump onto stack
¤Σ	| swap and take the sum (sum of first n elements)
¤┅	| swap and take suffixes
⟪  ⟫∇	| return the first element of suffixes where:
 Σ⊃	| the sum(first n elements) ≥ sum(suffix)
\$\endgroup\$
3
\$\begingroup\$

Haskell, 46 bytes

Displeased with how this looks; hope I’m just missing some obvious golfs.

n#l=until(((sum$take n l)>=).sum)tail$drop n l

Try it online!

I tried getting the prefix and suffix using splitAt and pattern matching in a guard, but that turned out to be 3 bytes more. Planning on trying to convert to a recursive function with guards later to see if that lowers the byte count.

Explanation

n # l = until (((sum $ take n l) >= ) . sum) tail $ drop n l
n # l =                                                        -- define infix operator
n                                                              --  the number of elements
    l                                                          --  the list
        until                                                  -- until
                                        sum                    --  the sum of the suffix
               ((sum $ take n l) >=)                           --  is <= the sum of the prefix
                                             tail              --  remove the first element
                                                    drop n l   -- the suffix

What I refer to as "the prefix" is the first n elements and "the suffix" is the rest of the list.

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

APL (Dyalog Unicode), 23 21 bytesSBCS

Anonymous prefix lambda, taking \$n\$ as left argument and \$L\$ as right argument.

{⍵↓⍨⍺⌈⊥⍨(+/⍺↑⍵)<+\⌽⍵}

Try it online!

{} "dfn"; \$n\$ is (leftmost Greek letter) and \$L\$ is (rightmost Greek letter):

⌽⍵ reverse \$L\$

+\ prefix sums of that

()< Boolean mask where less than:

  ⍺↑⍵ take the first \$n\$ elements of \$L\$

  +/ sum those

⊥⍨count trailing truths

⍺⌈ the maximum of \$n\$ and that

⍵↓⍨ drop that many elements from the front of \$L\$

\$\endgroup\$
  • 1
    \$\begingroup\$ @KevinCruijssen Nicely spotted. Fixed. \$\endgroup\$ – Adám Jul 2 at 6:44
3
\$\begingroup\$

MATL, 13 12 bytes

1 byte saved thanks to @Giuseppe, based on the answer by @MickyT.

:&)PtYsbs>~)

Output is in ascending order.

Try it online! Or verify all test cases.

Explanation

Consider inputs 2 and [500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,-2,-3].

:      % Implicit input: n. Push [1 2 ... n]
       % STACK: [1 2]
&)     % Implicit input: array. Two-output indexing: pushes the subarray
       % indexed by [1 2 ... n] and the remaining subarray
       % STACK: [500 200], [150 150 125 ... -2 -3]
P      % Flip
       % STACK: [500 200], [-3 -2 ... 125 150 150]
t      % Duplicate top of the stack
       % STACK: [500 200], [-3 -2 ... 125 150 150], [-3 -2 ... 125 150 150]
Ys     % Cumulative sum
       % STACK: [500 200], [-3 -2 ... 125 150 150], [-3 -5 ...646 796 946]
b      % Bubble up in the stack
       % STACK: [-3 -2 ... 125 150 150], [-3 -5 ...646 796 946], [500 200]
s      % Sum
       % STACK: [-3 -2 ... 125 150 150], [-3 -5 ...646 796 946], 7
>~     % Greater than, negate; element-wise
       % STACK: [-3 -2 ... 125 150 150], [1 1 ... 1 0 0]
)      % Index. Implicit display
       % STACK: [-3 -2 ... 125]
\$\endgroup\$
3
\$\begingroup\$

PowerShell, 99 97 bytes

param($n,$l)do{$a+=$l[$i++]}until($a-gt($l[-1..-$n]-join'+'|iex)-or$i-gt$l.count-$n)$l[($i-2)..0]

Try it online!

Takes list in ascending order, output is descending (because it was easier to compare to the test cases :^))

Goes through the list backwards forwards, comparing the accumulator to the last n entries added together (via gluing them together with +s and passing the resulting string to invoke-expression). The Until loop needed additional logic to handle going into the Rich Neighborhood because it wouldn't stop if we're still not richer than the Rich Guys until we churn through the entire list.

Unrolled:

param($n,$list)
do{
  $acc+=$list[$i++]
}until($acc -gt ($list[-1..-$n] -join '+'|invoke-expression) -or ($i -eq $list.count-$n))
$list[($i-2)..0]
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 99 bytes

\d+
$*
^
;,
+`;,(1+)(,.*)1$
$1;$2
,
;$'¶$`,
;.*(;.*)
$1$1
T`,`_`.*;
1G`(1+);\1;
.*;

(1*),
$.1,
,$

Try it online! Link only includes some test cases; I could get it to work in some cases with negative numbers at a cost of 12 bytes (in particular the first n entries in L still need to be positive; theoretically I could probably only require the sum of the first n entries to be positive). Explanation:

\d+
$*

Convert to unary.

^
;,

Insert a marker at the start of L.

+`;,(1+)(,.*)1$
$1;$2

Move it down the list n times, summing as we go. This deletes n but its comma remains.

,
;$'¶$`,

Create an entry for each suffix of L.

;.*(;.*)
$1$1

Replace the middle with a copy of the suffix.

T`,`_`.*;

Sum the copy of the suffix.

1G`(1+);\1;

Take the first entry where the suffix sum does not exceed the prefix sum.

.*;

Delete the sums.

(1*),
$.1,

Convert to decimal.

.,$

Delete the trailing comma that came before n.

\$\endgroup\$
  • \$\begingroup\$ Nice answer. :) Could you perhaps add a TIO link to the version that's 12 bytes longer containing negative numbers. And np that it doesn't work when the first \$n\$ numbers sum to a negative value. As long as it works with positive integers it's still fine. Well done. \$\endgroup\$ – Kevin Cruijssen Jul 2 at 6:46
  • 1
    \$\begingroup\$ @KevinCruijssen My negative number version turned out to be prohibitively slow, but I managed to fix that by using the r option, so I've now linked it in with some test cases. \$\endgroup\$ – Neil Jul 4 at 22:51
2
\$\begingroup\$

Charcoal, 17 bytes

IΦθ¬∨‹κη‹Σ…θηΣ✂θκ

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

  θ                 Input `L`
 Φ ¬                Filter out elements where
      κ             Current index
     ‹              Is less than
       η            Input `n`
    ∨               Logical Or
           θ        Input `L`
          … η       First `n` terms
         Σ          Summed
        ‹           Is less than
              ✂θκ   Remainder of `L`
             Σ      Summed
I                   Cast to string
                    Implicitly print on separate lines
\$\endgroup\$
2
\$\begingroup\$

Red, 63 bytes

func[L n][s: sum take/part L n forall L[if s >= sum L[break]]L]

Try it online!

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

PowerShell, 86 bytes

param($n,$l)$l|?{$k++-ge$n}|?{(&{$l|%{$s+=($_,0,-$_)[($n-le$i)+(++$i-ge$k)]};$s})-ge0}

Try it online!

Unrolled:

param($n,$list)
$list|?{$k++-ge$n}|?{                               # tail elements after $n only
    $sumLeftSegmentMinusSumRightSgement = &{        # calc in a new scope to reinit variables $s, $i
        $l|%{$s+=($_,0,-$_)[($n-le$i)+(++$i-ge$k)]} # sum(list[0..n-1]) - sum(list[k-1..list.Count-1])
        $s                                          # output sum to the outer scope
    }
    $sumLeftSegmentMinusSumRightSgement -ge 0       # output elements where sum >= 0
}
\$\endgroup\$
2
\$\begingroup\$

MathGolf, 13 bytes

(‼≥≤Σ\æ╞`Σ≥▼Þ

Try it online!

Explanation

Takes input as n L

(               pops n and decrements (TOS is n-1)
 ‼              apply next two operators to stack simultaneously
  ≥             slice L[n-1:] (gets all elements with index >= n-1)
   ≤            slice L[:n] (gets all elements with index <= n-1)
    Σ           get sum of topmost list (this is the sum of n largest elements)
     \          swap top elements
      æ    ▼    do while false with pop using block of length 4
       ╞        discard from left of string/array
        `       duplicate the top two items on the stack
         Σ      sum the list which is on top
          ≥     is the sum of the partial list >= the desired sum?
            Þ   discard everything but TOS

The reason why this works is that in the first step, we actually divide the list into two overlapping parts. As an example, L = [4, 3, 2, 1], n = 2 will split up the list as [3, 2, 1] and [4, 3]. The reason for having an extra element in the first list is that in the loop, the first thing that happens is a discard. If an extra element was not prepended, the cases where the output should be the entire rest of the list would fail.

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

Wolfram Language (Mathematica), 40 bytes

Drop@##//.{a_,b__}/;a+b>Tr@Take@##:>{b}&

Try it online!

Drop@##                     (*don't include the first n values*)
 //.{a_,b__}/;a+b>Tr@Take@##(*while the remaining values sum to greater than the sum of the first n*)
     :>{b}&                 (*drop the first element*)
\$\endgroup\$
1
\$\begingroup\$

Clojure, 66 75 bytes

#(loop[v(drop %2 %)](if(>(apply + v)(apply +(take %2 %)))(recur(rest v))v))

Sadly there doesn't seem to be a shorter idiom for the total sum of a sequence.

Edit: Oh when adding examples to the Try it online! link I noticed that the original answer gave wrong results when many negative numbers were present.

The doseq uses "keys" destructuring so it should be somewhat clear which data ends up in which symbol. #(...) is an anonymous function, here I'm binding it to the symbol f:

(def f #(loop[v(drop %2 %)](if(>(apply + v)(apply +(take %2 %)))(recur(rest v))v)))


(doseq [{:keys [L n]} [{:L [10,5,5,3] :n 2}
                       {:L [7,2,1,-2,-4,-5,-10,-12] :n 7}
                       {:L [30,20,10,0,-10,-20,-30] :n 1}]]
  (println (f L n)))

Output:

(5 3)
(-12)
(20 10 0 -10 -20 -30)
\$\endgroup\$
  • 1
    \$\begingroup\$ Would you mind adding a TIO with test code (I see Clojure in the list)? If it isn't possible somehow (version mismatch, or using builtins that aren't available on TIO), could you include a screenshot with some of the test cases as verification that it works? \$\endgroup\$ – Kevin Cruijssen Jul 1 at 12:21
1
\$\begingroup\$

APL(NARS), 32 chars, 64 bytes

{v/⍨(+/⍺↑⍵)≥+/¨{⍵↓v}¨¯1+⍳≢v←⍺↓⍵}

test and comments:

  q←{v/⍨(+/⍺↑⍵)≥+/¨{⍵↓v}¨¯1+⍳≢v←⍺↓⍵}
  2 q 500,200,150,150,125,100,75,75,55,50,40,30,30,20,10,10,8,5,5,5,3,2,2,1,0,¯2,¯3
125 100 75 75 55 50 40 30 30 20 10 10 8 5 5 5 3 2 2 1 0 ¯2 ¯3 
  2 q 10,5,5,3
5 3 
  ⎕fmt  7 q 7,2,1,¯2,¯4,¯5,¯10,¯12
┌1───┐
│ ¯12│
└~───┘
  2 q 0,¯5,¯10,¯15
¯10 ¯15 
  ⎕fmt 1 q 100,35,25,15,5,5,5,5,5,5,5,5,5,5,5,5,5
┌14───────────────────────────┐
│ 15 5 5 5 5 5 5 5 5 5 5 5 5 5│
└~────────────────────────────┘
  2 q 1000,999,998,900,800,766,525,525,400,340,120,110,80,77,33,12,0,¯15,¯45,¯250
525 525 400 340 120 110 80 77 33 12 0 ¯15 ¯45 ¯250 
  1 q 10,5,5
5 5 
  ⎕fmt  2 q ¯5,¯10,¯13
┌0─┐
│ 0│
└~─┘
  ⎕fmt  1 q 30,20,10,0,¯10,¯20,¯30
┌6───────────────────┐
│ 20 10 0 ¯10 ¯20 ¯30│
└~───────────────────┘


   {v/⍨(+/⍺↑⍵)≥+/¨{⍵↓v}¨¯1+⍳≢v←⍺↓⍵}
                             v←⍺↓⍵   v is ⍵[(⍺+1)..≢⍵] 
                  {⍵↓v}¨¯1+⍳≢v        build the array of array cut v of 0..((≢v)-1) elements
               +/¨                   sum each of these element of array above
      (+/⍺↑⍵)≥                       compare ≥ with the sum of ⍵[1..⍺] obtain one bolean array
                                     has the same lenght of v
   v/⍨                               return the element of v that are 1 of the boolean array above

I reported wrongly the byte length...

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

MS SQL Server 2017, 271 bytes

create function f(@L nvarchar(max),@ int)returns table return
select v
from(select*,sum(iif(n<=@,v,0))over()r,sum(v)over(order by v)p
from(select row_number()over(order by-v)n,v
from STRING_SPLIT(@L,',')cross apply(select
try_parse(value as int)v)t)t)t
where p<=r and @<n

I know that using a more relation-like table to store the input data can make the code more concise, but using the character data type to store the numeric list and the STRING_SPLIT function, I get shorter the Build Schema part :)

More readable version:

CREATE FUNCTION f(@L NVARCHAR(MAX), @n INT)
  RETURNS TABLE AS RETURN (
    SELECT
      v
    FROM (
      SELECT
        *,
        SUM(IIF(n<=@n, v, 0)) OVER() AS r,
        SUM(v) OVER(ORDER BY v) AS p
      FROM(
        SELECT ROW_NUMBER() OVER(ORDER BY -v) AS n, v
        FROM STRING_SPLIT(@L, ',')
        CROSS APPLY(
          SELECT TRY_PARSE(value AS INT) AS v
        ) AS t
      ) AS t
    ) AS t
    WHERE p <= r AND @n < n
  );

Try it on SQL Fiddle!

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

Python 3.8 (pre-release), 59 bytes

Output is in ascending Order

def f(l,n):
 s=sum(l[:n])
 while(w:=l.pop())<s:yield w;s-=w

Try it online!

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