36
\$\begingroup\$

There is a boy named Peter. Peter is a picky eater and doesn't like to eat the same kind of cookie again on the same day.

Peter gets a present, The present is a box of cookies! The box contains \$K\$ types of cookies. Also, it contains different amount of each type of cookie.

Peter, being the picky eater he is, Wants to eat \$n\$ cookies, on each \$n^{th}\$ day. Also, he does not want to eat more than 1 cookie of the same kind on any given day.

i.e. He eats \$1\$ cookie on the \$1^{st}\$ day, \$2\$ cookies on the \$2^{nd}\$ day and so on.

If there is no possible way for Peter to eat \$n\$ cookies at day \$n\$, he gives up and dumps the box. He also dumps the box if it becomes empty.

Find the maximum number of days that the box will last for Peter.

Input

\$K\$ Positive Integers, specifying the number of cookies for each different kind.

Output

An Integer corresponding to how many days Peter keeps the box.

Test Cases

INPUT -> OUTPUT
1 2 -> 2
1 2 3 -> 3
1 2 3 4 4 -> 4
1 2 3 3 -> 3
2 2 2 -> 3
1 1 1 1 -> 2
11 22 33 44 55 66 77 88 99 -> 9
10 20 30 40 50 60 70 80 -> 8
3 3 3 3 3 3 3 3 3 3 3 -> 7
3 3 3 3 3 3 3 3 3 -> 6
9 5 6 8 7 -> 5
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 -> 35
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 -> 32

Gist for test cases

This is so the shortest code wins.

\$\endgroup\$
9
  • \$\begingroup\$ Should I ever expect negative input? \$\endgroup\$ – Nilster May 19 at 13:10
  • 6
    \$\begingroup\$ @Nilster, i doubt it's possible having negative amount of cookies, So yes, inputs will always be positive \$\endgroup\$ – EliteDaMyth May 19 at 13:13
  • 6
    \$\begingroup\$ Thanks! Perhaps Peter might've received a cookie bill in the box and is now in cookie debt! :) \$\endgroup\$ – Nilster May 19 at 13:22
  • 1
    \$\begingroup\$ @Nilster I have added it to the question too, so no one in the future gets confused if peter would get negative amount of cookies or not \$\endgroup\$ – EliteDaMyth May 19 at 13:23
  • 3
    \$\begingroup\$ Congratulations on 1k rep, by the way. This is a really well-written challenge, and that was how you boosted your rep. I would upvote twice if I could. \$\endgroup\$ – Recursive Co. May 19 at 14:54

19 Answers 19

15
\$\begingroup\$

Perl 5, 79 77 76 75 69 (rip) 68 64 62 bytes

Credit to @Lynn for improving my answer by 4 bytes (68 to 64) and the explanation about the comma operator in scalar context here https://docstore.mik.ua/orelly/perl2/prog/ch03_18.htm

Thanks @Nahuel Fouilleul for the tip using anonymous functions to save 2 bytes (64 to 62) but if it's not allowed I'll revert back

sub{$^=0;++$^while(@_=sort{$b-$a}@_),!grep--$_[$_]<0,0..$^;$^}

Test Cases Here: Try it online!

Expanded:

sub {                       # Declare subroutine
    $^ = 0;                 # Set scalar caret variable to 0 (you can put this variable right next to if statements and for loops etc)
    ++$^ while              # Pre increment caret while the condition below is true
        (                   # Bracket used so that you can declare/reassign values in a conditional
            @_ = sort {     # Sort the default array and store result back to default array
                $b - $a     # Sort from greatest to least (scalar variables a and b are default variables that come with sort)
            }@_             # Add the default array as a parameter for the sort
        ),                  # End of bracket (in scalar context like in this solution it will only grab the right most argument of the array so the while loop is entirely dependent on the condition below)
        !grep               # Only save values if the below statement is true for each item in default array then reverse the boolean (will return false if the size of the array after grep is greater than 0)
            --$_[$_] < 0,   # Check whether the pre decrement of item (default is $_) at the index of default array is less than 0. If the caret is out of range of the array, it will default to undef which is treated as 0 in math operations)
        0 .. $^             # Add an array of range 0 to caret inclusive to the grep
    ;                       # End of the while loop statement modifier
    $^                      # Return caret variable
}                           # End of subroutine
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Welcome to CGCC! Great first answer \$\endgroup\$ – EliteDaMyth May 19 at 15:31
  • 1
    \$\begingroup\$ thank you also great problem \$\endgroup\$ – Hydrazer May 19 at 15:34
  • \$\begingroup\$ Great answer. 66 bytes using a reference to a subroutine tio \$\endgroup\$ – Nahuel Fouilleul May 19 at 18:34
  • \$\begingroup\$ is that allowed? \$\endgroup\$ – Hydrazer May 19 at 18:36
  • \$\begingroup\$ I would say if lamba are allowed, subroutine reference also, unless it's recursive because the name is used \$\endgroup\$ – Nahuel Fouilleul May 19 at 18:46
10
\$\begingroup\$

Python 3, 96 92 91 bytes

f=lambda l,n=1:n<=len(l)and-~f([v-(e<n)for e,v in enumerate(sorted(l)[::-1])if(e<n)-v],n+1)

Try it online!

Simply "eats" \$1\$ each of the \$n\$ cookies with the largest amount each day, starting with \$n=1\$, until we don't have \$n\$ different cookies left. Returns the number of days this was successful.

Explanation

f=lambda l,n=1:                   # function taking the list of  
                                  # cookies l and day n  
  n<=len(l)                       # if don't we have enough cookies for  
                                  # today return False (0)  
           and                    # if we do have enough cookies  
              -~                  # return 1 plus 
                f([...],n+1)      # our function called reclusively for 
                                  # day n+1 with updated list:
         sorted(l)[::-1]          # of cookies sorted from most to least  
       for e,v in enumerate(..)   # over the position and number of the 
                                  # cookies  
v-(e<n)                           # subtract 1 from the n largest 
                                  # amount of cookies  
                        if(e<n)-v # discarding empty amounts  
\$\endgroup\$
1
  • \$\begingroup\$ nice solution :) \$\endgroup\$ – EliteDaMyth May 19 at 13:38
6
\$\begingroup\$

JavaScript (ES6), 70 bytes

f=(a,c=d=0)=>c?d-1:f(a.sort((a,b)=>b-a).map(x=>c*x?x-!!c--:x,c=++d),c)

Try it online!

Commented

f = (                  // f is a recursive function taking:
  a,                   //   a[] = list of cookies
  c =                  //   c   = cookies that were not eaten the day before
  d = 0                //   d   = day counter
) =>                   //
  c ?                  // if we failed to eat all the cookies the day before:
    d - 1              //   stop and return d - 1
  :                    // else:
    f(                 //   do a recursive call:
      a.sort((a, b) => //     sort the list of cookies ...
        b - a          //       ... from highest to lowest
      )                //
      .map(x =>        //     for each value x in the sorted list:
        c * x ?        //       if both c and x are not equal to 0:
          x - !!c--    //         decrement x and c
        :              //       else:
          x,           //         leave x unchanged
        c = ++d        //       start by incrementing d and setting c to d
      ),               //     end of map()
      c                //     pass c
    )                  //   end of recursive call
\$\endgroup\$
2
  • 2
    \$\begingroup\$ you never fail to amaze! \$\endgroup\$ – EliteDaMyth May 19 at 16:15
  • \$\begingroup\$ nice i might add recursion to my solution later \$\endgroup\$ – Hydrazer May 19 at 17:14
6
\$\begingroup\$

Python 2, 82 77 76 bytes

-5 bytes inspired by x1Mike7x's answer. (Adding a 0 to the cookie list at every iteration)
-1 byte thanks to dingledooper!

l=input()
i=0
while l.sort()<l>[0]:i-=1;l[i:]=[x-1for x in[1]+l[i:]]
print~i

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ This seems to work for -1 byte. \$\endgroup\$ – dingledooper May 19 at 18:06
  • \$\begingroup\$ I think while[0]<l>l.sort() saves a space. \$\endgroup\$ – Jonathan Frech May 25 at 23:08
  • \$\begingroup\$ @JonathanFrech That doesn't work because l has to be sorted before being compared to [0]. [1,1,1,1,1,1] is a case where your suggestion would break. \$\endgroup\$ – ovs May 26 at 6:44
5
\$\begingroup\$

Jelly, 15 14 bytes

‘ɼ-€+NÞƲAƑ¿ṛ®’

Try it online!

All testcases

Explanation

‘ɼ-€+NÞƲAƑ¿ṛ®’  Main monadic link
          ¿     While
         Ƒ        invariant under
        A           absolute value
                  (that is, no numbers are negative)
                do
       Ʋ        (
 ɼ                Apply this to the register:
‘                   Increment
   €              Map [over the range 1..register]:
  -                 -1
    +             Add
                    the list
      Þ             sorted by
     N              negation
       Ʋ        )
           ṛ    Replace with
            ®   the register
             ’  Decrement
\$\endgroup\$
5
\$\begingroup\$

Python 3.8, 88 82 81 80 bytes

f=lambda a,n=-1:-1in(a:=sorted([0]+a))and-n-2or f([x-1for x in a[n:]]+a[:n],n-1)

Try it online!

Unwrapped version:

def f(a, n=-1):
    a = sorted([0] + a)
    if -1 in a:
        return -n - 2
    p = [x - 1 for x in a[n:]]
    q = a[:n]
    return f(p + q, n - 1)
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 14 bytes

v{āNÌ‹R-Wds}\O

Try it online! or Try all cases!

Commented:

v          }     # for N in range(len(input))
 {               # sort the current cookie list (initially the input)
  ā              # push the range [1..len(list)]
   NÌ            # push N+2
     ‹           # is each value in the range less than N+2?
                 # this yields a list with N+1 leading ones
      R          # reverse the list of 1's and 0's
       -         # subtract this from the current cookie list
        Wds      # push min(list) >= 0 under the current list

            \    # after the loop: discard the final cookie list
             O   # sum the stack: this counts the number of times
                 #                the cookie counts were non-negative
\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 62 bytes

f=(c,d=0)=>c.sort((x,y)=>y-x)[d]?f(c,++d,c.map(x=>--c[--d])):d

Try it online!

The TIO setup is based on Arnauld's answer.

Seems greedy eating cookies with most copies works, though I don't know how to prove it (but that doesn't matter).

f = (
        c, // cookies (array of integers)
        d = 0 // day (integer)
    ) =>
    c.sort((x, y) => y - x) // sort cookies (desc order)
[d] ? // Is there enough kinds of cookie for today?
f(c, ++d, // Next iteration (day + 1)
    c.map(x => --c[--d]) // Eat 1 per each
    // greedy eat kinds with most copies
): d
\$\endgroup\$
1
  • \$\begingroup\$ Interesting! Really nice solution! \$\endgroup\$ – EliteDaMyth May 20 at 8:26
3
\$\begingroup\$

K (ngn/k), 31 bytes

{#(|/0>)_x{x[y#>x]-:1;x}\1+!#x}

Try it online!

  • x{...}\1+!#x set up a scan, seeded with x (the number of cookies of each type), run over 1..(number of types of cookies + 1) (variable y)
    • y#>x identify the n cookies to eat (i.e., the y indices containing the largest values)
    • {x[...]-:1;x} eat those cookies, feeding the result into the next iteration of the scan
  • (|/0>)_... remove scan iteration results where there was any negative value
  • #... return the count of the filtered results
\$\endgroup\$
2
\$\begingroup\$

Stax, 19 bytes

ⁿ┘ª1µiZ&Xû¢♣◙2╜8æ≥/

Run and debug it

A direct implementation. Takes in golfscript arrays, but normal ones are supported as well.

Explanation

{{No{i|i^<-mcc:@i^>wL%v
{                  w    do-while top of stack is true:
 {No                    sort descending
    {      m            map each element to:
     i|i^<              iteration index <= outer loop iteration index?
          -             subtract that form the element
            cc          copy twice
              :@        count of truthy elements
                i^<     < index+1?
                    L   wrap all arrays in stack
                     %v length decremented
\$\endgroup\$
2
\$\begingroup\$

J, 38 bytes

_1+1#.0*/"1@:<:[(-~\:~)/\.@|.@,(#$1:)\

Try it online!

For 1 2 2:

(#$1:)\
1 0 0
1 1 0
1 1 1

[ … |.@,
1 1 1
1 1 0
1 0 0
1 2 2

   f   /\.    for each suffix, fold from bottom to top with f
(  /:~)       sort the remaining cookies (highest first),
 -~           subtract the needed cookies for the day:
0 0 _1
1 0  1
1 2  1
1 2  2

0*/"1@:<: does the row only contain numbers >= 0?
0 1 1 1

   1#.    count the 1s
_1+       minus one (the initial cookie row)
-> 2
\$\endgroup\$
2
\$\begingroup\$

Pip, 20 bytes

TvNgg:RSNg+:vRL UiDi

Takes inputs as command-line arguments. Try it here!

The equivalent program in Pip Classic is 22 bytes:

TvNgg:RVSNg+:vRL++i--i

Verify all test cases: Try it online!

Explanation

TvNgg:RSNg+:vRL UiDi
                      g is list of cmdline args; v is -1; i is 0 (implicit)
T                     Loop until
 vNg                  there is a -1 in the cookie counts list:
      R                The reverse of
       SNg             the cookie counts list, sorted ascending
                       (in other words: the cookie counts list, sorted descending)
                Ui     Increment i and
            vRL        create a list of that many -1's
          +:           Add those two lists itemwise
    g:                 Assign the result back to g
                  Di  Decrement i and autoprint it

Here are two different approaches, also 20 bytes each:

Wi<#R:SN:FI:gDg@<Uii   Filter 0's out of the list at each step instead of checking for -1
L#gI(g:RSNgi)Dg@<Uii   Loop len(input) times; increment i only if there are enough cookies
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 31 29 bytes

.+
$*
m{O^`^1*
1_
_
}1`1$
_
_

Try it online! Takes a newline-separated list, but link is to test suite that converts from comma-separated list for convenience. Explanation: Performs a slightly different calculation with the same result: on day m he eats up to m cookies, then when all the cookies have run out the desired answer is the most cookies he ate in any given day.

.+
$*

Convert to unary.

m{`
}`

Repeat until all the cookies have been eaten, and also evaluate the script in multiline mode.

O^`^1*

Sort the cookies in descending order.

1_
_

Try to eat the same number of cookies that were eaten the previous day.

1`1$
1_

Try to eat a new different cookie each day.

_

Count the maximum number of cookies eaten on any given day.

\$\endgroup\$
1
  • \$\begingroup\$ nice solution!! \$\endgroup\$ – EliteDaMyth May 19 at 19:03
2
\$\begingroup\$

JavaScript (Node.js), 97 91 88 84 69 63 bytes

f=(n,d=0)=>n.sort((a,b)=>b-a)[d]?f(n.map((e,i)=>e-=d>=i),d+1):d

Try it online!

How it works

Arguments

  • n [init: none] - the array of cookie types
  • d [init: 0] - the day number

Function body

First, we check if there are enough truthy entries to "pick" cookies. If not we simply return the day count.

If there are enough, then from each element of the sorted list (descending) we subtract 1 if the index is low enough and the element is strictly positive. If not, leave the element as it is. Call f with the obtained array and an incremented day number.

I also realized that since 0 is falsey, we do not need to filter. PLEASE don't make the 69 joke, it's getting boring.

-2 bytes thanks to @A username

-6 bytes thanks to @tsh

\$\endgroup\$
9
  • 1
    \$\begingroup\$ nice explanation! \$\endgroup\$ – EliteDaMyth May 19 at 14:45
  • 1
    \$\begingroup\$ @EliteDaMyth well, I was going to use this sort of explanation as a basis for future explanations. \$\endgroup\$ – Recursive Co. May 19 at 14:49
  • \$\begingroup\$ Why did you have i-d>0? \$\endgroup\$ – A username May 20 at 9:08
  • \$\begingroup\$ @Ausername thanks! Combined with another modification, this brings my answer down to 88 bytes. \$\endgroup\$ – Recursive Co. May 20 at 9:13
  • \$\begingroup\$ I just thought of that O_o \$\endgroup\$ – A username May 20 at 9:28
2
\$\begingroup\$

Haskell, 71 bytes

(0?)
n?a=maximum$n:[(n+1)?b|b<-mapM(\x->x:[x-1|x>0])a,sum b+n+1==sum a]

Try it online!

The relevant function is (0?), which takes the list a of cookie quantities and returns the number of days.

Due to Haskell requiring import Data.List for sorting, I think bruteforce is the way to go.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Due to brute force, it times out on tio for the longer tests. \$\endgroup\$ – EliteDaMyth May 20 at 11:31
  • 2
    \$\begingroup\$ @EliteDaMyth Yes it does, but since this is code-golf it shouldn't matter, as long as the algorithm is correct. \$\endgroup\$ – Delfad0r May 20 at 12:49
1
\$\begingroup\$

Charcoal, 42 bytes

≔⁰ζW›Lθζ«≦⊕ζ≔⟦⟧ηW⌈⁻θηF№θκ⊞ηκ≔ΦEη⁻κ‹λζκθ»Iζ

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

≔⁰ζ

Start with n=0.

W›Lθζ«

While there are enough different cookies:

≦⊕ζ

Increment n.

≔⟦⟧ηW⌈⁻θηF№θκ⊞ηκ

Sort the cookies into descending order.

≔ΦEη⁻κ‹λζκθ

Decrement the first n cookies, removing entries that become zero.

»Iζ

Print the final value of n.

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

Core Maude, 257 bytes

fmod P is pr SORTABLE-LIST{Nat<}*(sort List{Nat<}to L). var L : L . var X
N :[L]. op b : L -> Nat . op _,_ : L Nat -> Nat . eq b(L)= L,0 . eq L,N =
d(sort(L),s N),s N . eq X,s N = N[owise]. op d : L Nat ~> L . eq d(L,0)=
L . eq d(L s N,s X)= d(L,X)N . endfm

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Tue May 18 23:37:06 2021
Maude> fmod P is pr SORTABLE-LIST{Nat<}*(sort List{Nat<}to L). var L : L . var X
> N :[L]. op b : L -> Nat . op _,_ : L Nat -> Nat . eq b(L)= L,0 . eq L,N =
> d(sort(L),s N),s N . eq X,s N = N[owise]. op d : L Nat ~> L . eq d(L,0)=
> L . eq d(L s N,s X)= d(L,X)N . endfm
Maude> red b(1 2) .
reduce in P : b(1 2) .
rewrites: 37 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 2
Maude> red b(1 2 3) .
reduce in P : b(1 2 3) .
rewrites: 99 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 3
Maude> red b(2 2 2) .
reduce in P : b(2 2 2) .
rewrites: 96 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 3
Maude> red b(11 22 33 44 55 66 77 88 99) .
reduce in P : b(11 22 33 44 55 66 77 88 99) .
rewrites: 1045 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 9
Maude> red b(1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10) .
reduce in P : b(1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 6 6
    6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10) .
rewrites: 82081 in 27ms cpu (27ms real) (2952129 rewrites/second)
result NzNat: 35

Ungolfed

fmod P is
    pr SORTABLE-LIST{Nat<} * (sort List{Nat<} to L) .

    var L : L .
    var X N : [L] .

    op b : L -> Nat .
    op _,_ : L Nat -> Nat .
    eq b(L) = L, 0 .
    eq L, N = d(sort(L), s N), s N .
    eq X, s N = N [owise] .

    op d : L Nat ~> L .
    eq d(L, 0) = L .
    eq d(L s N, s X) = d(L, X) N .
endfm

This program accepts input via a function b which takes a list of natural numbers. The function d will "eat" cookies for each step, and it the program runs until the list term is no longer a well-formed list of natural numbers, then returns the index of the previous step.

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

R, 86 bytes

function(b){while({b=-sort(-b);b=c(b[1:T]-1,b[-1:-T],0);T<=sum(b|1)&b[T]+1})T=T+1
T-1}

Try it online!

days_peter_keeps_box=
function(b){
  while({                       # Loop for each day peter has the box:
    b=-sort(-b)                 # sort the cookies with most-abundant types first,
    b=c(b[1:T]-1,b[-1:-T],0)    # take out 1 cookie from each of the first T types (initially 1),
    T<=length(b)                # now check: if T is greater than the number of cookie types
      &b[T]>-1                  # or any of the types have less than zero cookies left
                                # then we've gone one day too many... stop the loop;
  })T=T+1                       # otherwise increment T.
T-1}                            # When the loop is finished, output T-1.  
\$\endgroup\$
0
\$\begingroup\$

Haskell, 114 bytes

import Data.List;p i k|i<length(filter(>0)k)=p(i+1).zipWith(-)(sort k)$replicate(length k-i-1)0++repeat 1|0<1=i---

Try it online!


Uses an algorithm of order \$\mathcal O(m\cdot n\ln n)\$ where \$m\$ is the maximum number of cookies of one kind and \$n\$ is the input list's size: On day \$d\$, sort all remaining cookies by their quantity and remove the \$d\$ cookies of whose kinds there are the most, if possible. Else, this day is the one sought after. If on the other hand the removal was successful, go on to day \$d+1\$.

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