Donation arms race

Question

The barfoos, a hypothetical alien species, go about charity in an interesting way.

Every morning, barfoo Specialists come up with an ordered list of causes to donate to, and for each cause they recommend what quantity of resources should be donated.

That wasn't the weird part. Here's the weird part:

A random civilian barfoo will donate the recommended quantity of resources to the first cause. Another one will likewise donate to the very next cause on the list, and keep going down the list until it has given at least as much as its compatriot, at which point it immediately stops.

This continues, each civilian giving at least as much as the one directly before, until the remaining elements of the Great List of Charitable Causes can no longer satisfy this donation arms race, at which point the Specialists themselves just chip in.

How many civilian barfoos are involved?

Input: a sequence of \$1\leq n\leq100000\$ integers each of value \$1\leq i\leq1000\$, representing the recommended donation sizes for the Great List of Charitable Causes in the order in which it's given to the barfoos.

Output: a single integer representing the number of civilian barfoos who donate something.

Sample 1

Input: 5 2 3 1 3 4 2 5

Output: 3

This may be divided into the buckets 5, 2 3 (sum 5), 1 3 4 (sum 8) and 2 5 (sum 7, cannot satisfy a fourth civilian barfoo).

Sample 2

Input: 4 1 2 3 6 6

Output: 4

This may be divided into the buckets 4, 1 2 3 (sum 6), 6 and 6. (In this case, no Specialists need to involve themselves.)

---

• code-golf; the shortest code in bytes wins.
• The linked rules apply.
• Please explain your code.
• Please link to Try It Online! or another online demo.

---

Credit: 'Nomnomnom' (AIO 2009, Senior)

Answer 1

Python 2, 60 bytes

d=p=t=0
for x in input():
 d-=x
 if d<1:t+=1;p=d=p-d
print t

Try it online!

The code is easier to understand in the below version, which is fairly natural: t tracks the number of barfoos who donate, p tracks the previous donation, and s tracks the sum of the current barfoo's donation.

61 bytes

s=p=t=0
for x in input():
 s+=x
 if s>=p:t+=1;p=s;s=0
print t

Try it online!

The original replaces tracking s with tracking d=p-s, the amount the current barfoo needs to donate to catch up with the previous donation. This lets us replace s>=p with d<1, saving a byte. Note that s/p doesn't work because p starts at 0.

Answer 2

Python 3.8 (pre-release), 59 57 59 58 bytes

Don't mind me, just abusing the walrus

lambda y,p=0,d=0:len([p:=(d:=p-d)for x in y if(d:=d-x)<1])

Surculose Sputum shaved a byte using xnor's idea to keep track of the remaining amount of donation needed instead of the current donation.

Try it online!

Answer 3

JavaScript (ES6), 50 bytes

f=([v,...a],p,s=0)=>v?(s+=v)<p?f(a,p,s):1+f(a,s):0

Try it online!

Commented

f = (            // f is a recursive function taking:
  [ v,           //   v = next entry in the input array
    ...a ],      //   a[] = all remaining entries in the input array
  p,             //   p = previous donation, initially undefined
  s = 0          //   s = current donation
) =>             //
  v ?            // if v is defined:
    (s += v)     //   add v to s
    < p ?        //   if the result is less than the previous donation:
      f(a, p, s) //     do a recursive call with the updated s
    :            //   else:
      1 +        //     increment the final result
      f(a, s)    //     do a recursive call with p = s (and s = 0, implicitly)
  :              // else:
    0            //   stop recursion

Answer 4

Jelly, 8 bytes

ŒṖ§ṢƑƇḢL

A monadic Link accepting a list of numbers which yields a non-negative integer.

Try it online! (not efficient)

How?

ŒṖ§ṢƑƇḢL - Link: list
ŒṖ       - all partitions (order is such that those with shorter sublists at the left appear first)
  §      - sums (sum each part of each partition)
     Ƈ   - filter keep those for which:
    Ƒ    -   is invariant under:
   Ṣ     -     sort
      Ḣ  - head
       L - length

Answer 5

Pyth, 8 bytes

lesDI#./

Try it online!

Form all ordered partitions ./, then filter # for the partitions which are invariant I under sorting D by sum s. Take the last one the survived the filler e, which is also the longest due to the order that ./ outputs partitions, and return its length l.

This is one of the longest string of prefix modifiers (DI#) I've ever used, it's a challenge that fits Pyth quite well.

Answer 6

Python 2, 64 62 bytes

f=lambda l,p=1,c=0:c/p and-~f(l,c)or l>[]and f(l[1:],p,c+l[0])

Try it online!

A recursive function that takes in a list of integers and returns the number of barfoos.

How: p and c keeps track of the previous donation and the current donation. If the current donation is sufficient, moves to a new barfoo. Otherwise, adds another cause to the current donation.

Answer 7

05AB1E, 10 bytes

.œ.ΔOD{Q}g

Try it online!

Answer 8

C (gcc), 56 bytes

Similar to my JS answer, but with \$p\$ and \$s\$ declared in the global scope. They are reset to \$0\$ on the last iteration to make sure that the function is reusable.

Takes a zero-terminated array of integers as input.

p,s;f(int*a){a=!*a?p=s=0:!((s+=*a++)>=p?s-=p=s:1)+f(a);}

Try it online!

Answer 9

C (gcc), 60 bytes

Port of xnor's Python answer.

n;m;s;f(int*l){for(n=m=s=0;*l;s=s<1?++n,m-=s:s)s-=*l++;s=n;}

Try it online!

Inputs a zero-terminated integer array.

Answer 10

PHP, 62 bytes

for(;$a=$argv[++$i];)if(($s+=$a)>=$t){$r++;$t=$s;$s=0;}echo$r;

Try it online!

Pretty straightforward implementation, saying that "s" is for "sum", "t" for "total" and "r" for "result" should be enough ;)

Answer 11

[C#], 108 bytes

f=(i,c,p,s,q)=>{y=c;if(i==L.Length)return;var t=L[i++];p=i==0?t:p;q=s+t>=p;f(i,q?++c:c,q?s+t:p,q?0:s+t,q);};

Try It online!

Very verbose recursion implementation, but I'm proud of this ugly baby. Call function with ever greater sum of donations until donation is equal to or greater then increment a counter, and set sum to 0. Increase index (to loop through donations). Return when index is equal to length of donations.

Answer 12

Charcoal, 41 bytes

≔⁰ηＷΦＥθ…θ⊕묋Σκη«⊞υω≔Σ§ι⁰η≔✂θＬ§ι⁰Ｌθ¹θ»ＩＬυ

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

≔⁰η

Start off with no resources.

ＷΦＥθ…θ⊕묋Σκη«

Find out which prefixes of the remaining list contain as least as many resources as the last donation.

⊞υω

Keep track of how many times a donation was found.

≔Σ§ι⁰η

Calculate the minimum donation for next time.

≔✂θＬ§ι⁰Ｌθ¹θ

Remove the recommendations that were donated.

»ＩＬυ

Print the count of donations.

Answer 13

Io, 72 bytes

Port of xnor's Python solution.

method(I,d :=p :=t :=0;I foreach(x,d=d-x;if(d<1,t=t+1;p=d=p-d))return t)

Try it online!

Answer 14

Perl 5, 35 + 1 bytes

$d-=$_;if($d<1){$\++;$p=$d=$p-$d}}{

Try it online!

I counted one additional byte for replacing the standard command-line switch -e by -pe.

This program reads the list of causes from its standard input, one amount per line. When there is nothing left to read, it prints the number of civilian barfoos who donated something.

This is a port of xnor's Python2 solution with a few Perl golfing tricks thrown in. I use the following variables: $\ tracks the number of barfoos who have successfully donated, $p tracks the previous donation, and $d tracks the amount that the current barfoo still needs to donate to catch up with the previous donation.

Slightly more natural, 36 + 1 bytes

$s+=$_;if($s>=$p){$\++;$p=$s;$s=0}}{

Try it online!

In this version, $s counts the sum of what the current barfoo is trying to donate instead of tracking what is still missing (as done with $d above).

Ungolfed and commented

The implementation is simple but it uses a few well-known Perl golfing tips:

• The -p switch wraps while (<>) { ... ; print } around the program but it does so literally, in a way that allows unmatched curly braces in the code to match those that are added by the wrapper. So perl -p 'foo}{bar' becomes while (<>) { foo } { bar ; print }. In this codegolf entry, I have an empty bar (which is kind of sad, but this is another topic).
• The special variable $\ is the output record separator for the print operator. Using print without arguments would print $_ followed by $\, but $_ is undefined at the end of the while loop, so assigning a value to $\ is a convenient way to print something at the end of the program.
• Incrementing an undefined variable sets its value to 1. $\ is undefined by default.

To make the ungolfed code more readable and to make it easier to understand what is printed, here I use a variable $t for counting the number of successful donations instead of using the output record separator $\. The natural version of the code would look like this:

while (<>) {           # Read all input lines (one amount per line).
  $s += $_;            # Add the amount for the current cause to $s.
  if ($s >= $p) {      # If we can match or exceed the last donation,
    $t++;              # then count it and invite the next barfoo.
    $p = $s;
    $s = 0;
  }
}                      # When we reach the end of the input,
print $t;              # print the number of barfoos who donated.

...and the slightly optimized version would look like this:

while (<>) {           # Read all input lines (one amount per line).
  $d -= $_;            # Subtract the amount from what we need to catch up.
  if ($d < 1) {        # If the difference from the last donation is 0 or lower,
    $t++;              # then count it and invite the next barfoo.
    $d = $p - $d;
    $p = $d;
  }
}                      # When we reach the end of the input,
print $t;              # print the number of barfoos who donated.

Answer 15

MMIX, 52 bytes (13 instrs)

Takes pointer to sequence of 16-bit integers as sole argument, sequence terminated by a 0.

(jelly xxd)

00000000: e301 0000 e302 0000 e303 0000 87ff 0000  ẉ¢¡¡ẉ£¡¡ẉ¤¡¡⁷”¡¡
00000010: 42ff 0008 e700 0002 2002 02ff 5102 fffc  B”¡®ḃ¡¡£ ££”Q£”‘
00000020: 2003 0302 3402 0003 e701 0001 f1ff fff8   ¤¤£4£¡¤ḃ¢¡¢ȯ””ẏ
00000030: f802 0000                                ẏ£¡¡

Disassembly and explanation

charity SETL $1,0       // ndonors = 0
        SETL $2,0       // amtleft = 0
        SETL $3,0       // prevdonor = 0
0H      LDWU $255,$0,0  // loop: amt = *causes (causes is const uint16_t *)
        BZ   $255,0F        // if(!amt) goto end
        INCL $0,2       // causes++
        ADD  $2,$2,$255 // amtleft += amt
        PBN  $2,0B      // iflikely(amtleft < 0) goto loop
        ADD  $3,$3,$2   // prevdonor += amtleft
        NEG  $2,0,$3    // amtleft = -prevdonor
        INCL $1,1       // ndonors++
        JMP  0B         // goto loop
0H      POP  2,0        // end: return ndonors