20
\$\begingroup\$

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.)


  • ; 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)

\$\endgroup\$
  • \$\begingroup\$ I appreciate how you're rewriting from the olympiad and linking them to give credit. \$\endgroup\$ – xnor Apr 27 at 6:07
  • \$\begingroup\$ For some reason, all three rules links are getting redirected to random code golf answers. Is that a bug? \$\endgroup\$ – Kale_Surfer_Dude Apr 27 at 6:36
  • 1
    \$\begingroup\$ @Kale_Surfer_Dude The problem was that they were supposed to point to Codegolf Meta. \$\endgroup\$ – lightlyheld Apr 27 at 7:18

14 Answers 14

8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ out of curiosity, what's the reason you (and many others) golf in python2 rather than python3? is it just familiarity or did python3 changes make it somehow less golfy? \$\endgroup\$ – Jonah Apr 27 at 17:00
  • 1
    \$\begingroup\$ @Jonah One reason for me is because in Python 2, input() evaluates the input string and can returns any type of object, as oppose to Python 3 where input() always returns a string. Also, print, exec, and integer division in Python 2 is shorter. \$\endgroup\$ – Surculose Sputum Apr 27 at 18:11
  • 1
    \$\begingroup\$ @Jonah Though I do sometimes strategically pick between Python 2 and 3 depending on which on is shorter for the problem at hand, I also do have a sentimental bias for Python 2, which is what I first started golfing in. And, for instance, Python 3.6's f-strings make some ASCII art challenges too straightforward in my mind, so I like golfing those in Python 2 where more tricks are needed. \$\endgroup\$ – xnor Apr 28 at 4:00
  • \$\begingroup\$ What is the input format for this? I tried passing in 5 2 3 1 3 4 2 5, it errors out with invalid syntax on the first "2". EDIT: Oh, just saw the TIO link, it's accepting list. \$\endgroup\$ – justhalf Apr 28 at 5:26
5
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 10 bytes

.œ.ΔOD{Q}g

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Not bad, but even when I input an array of only 1,000 integers, runtime goes above 60 s. Of course, I didn't say anything about time in the question... \$\endgroup\$ – lightlyheld Apr 27 at 8:11
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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 ;)

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

[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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 41 bytes

≔⁰ηWΦEθ…θ⊕묋Σκη«⊞υω≔Σ§ι⁰η≔✂θL§ι⁰Lθ¹θ»ILυ

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

≔⁰η

Start off with no resources.

WΦEθ…θ⊕묋Σκη«

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.

≔✂θL§ι⁰Lθ¹θ

Remove the recommendations that were donated.

»ILυ

Print the count of donations.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.
| improve this answer | |
\$\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.