# Count Until Overflow

### The challenge:

Assuming you have $$\ X \$$ collections, each collection $$\ C_i \$$ has a name $$\ N_i \$$ and a capacity $$\ N_i \$$ of elements - Determine which collection will be overflowed first while counting the occurrences of the names in a cyclic list. Also print how many cycles of the list occurred.

Example:

4 Collections are available:

• Name: "cat", Capacity: 3
• Name: "dog", Capacity: 4
• Name: "parrot", Capacity: 1
• Name: "otter", Capacity: 5

Given the list: ["dog","cat","parrot","otter","otter","cat","parrot","cat","cat","dog"], "parrot" collection will be overflowed first, since we've counted two "parrot"s to the "parrot" collection which has a capacity of 1. At the point of the overflow, there were only 1 dog, 2 cats, 2 otters - these collection are still capable to get more elements. 0 cycles occurred in that case.

Another example that demonstrate the cyclic property:

For the same collections, given the list: ["dog","cat","cat","parrot","otter"], "cat" collection will be overflowed first, since after reading the last element "otter", we continue reading the list again from the start ("dog"), and we are reaching 4 cats before any other collection reaches the capacity. 1 cycle occurred in that case.

### Assumptions:

• Collections with $$\ C_i = 0\$$ are possible.
• In case there will never be an overflow, the program should print falsely value.
• It is possible to meet elements in the list that has no collection to be counted into, although you can assume all elements in the list contains [A-Za-z] characters only.
• Name of a collection contains [A-Za-z] characters only.
• Names of collections and elements are case sensitive.
• It is possible to get no collections or an empty list as an input.

### Input:

• A list of collections, each collection has a name and capacity. (You can pass the names and the capacities in two different arguments that keep the relative order).
• A list of elements, each element.

You can pass the input in any sensible way. Possible options:

[[["cat",3],["dog",4],["parrot",1],["otter",5]],["dog","cat","parrot","otter","otter","cat","parrot","cat","cat","dog"]]

[["cat",3,"dog",4,"parrot",1,"otter",5],["dog","cat","parrot","otter","otter","cat","parrot","cat","cat","dog"]]

["cat","dog","parrot","otter"],[3,4,1,5],["dog","cat","parrot","otter","otter","cat","parrot","cat","cat","dog"]]

cat,3
dog,4
parrot,1
otter,5
dog,cat,parrot,otter,otter,cat,parrot,cat,cat,dog


### Output:

• The name of the collection that will overflow first.
• The amount of reading cycles on the list.

or falsely if no collection will ever be overflowed.

### Scoring:

Since this is , lowest bytes wins.

### Test Cases:

[[["cat",3],["dog",4],["parrot",1],["otter",5]],["dog","cat","parrot","otter","otter","cat","parrot","cat","cat","dog"]] --> "parrot",0

[[["cat",3],["dog",4],["parrot",1],["otter",5]],["dog","cat","cat","parrot","otter"]] --> "cat",1

[[["cat",7],["dog",8]],["dog","cat"]] --> "cat",7

[[["cat",7],["dog",8]],["woof","meow"]] --> False

[[["cat",7],["dog",8]],["Cat","Dog"]] --> False

[[["cat",1],["dog",0]],[]] --> False

[[["cat",0],["dog",0],["parrot",1],["otter",5]],["otter","otter","otter","otter","otter","parrot","dog"]] --> "dog",0

[[],["dog","cat"]] --> False

• By sorted/sorting do you mean something more like moved/moving or matched/matching? If so you should use a different word as using sorted/sorting is confusing. Commented Aug 20, 2020 at 13:48
• @Noodle9 I think the right word is sorting, although it is not sorting the list in place, but more like literally taking elements and sorting them to their right collections one by one. I can see why it may be confusing programming-wise, but I still think it is the right word for it. Commented Aug 20, 2020 at 13:56
• @petStorm Unfortunately no. The program must halt and give an output. Commented Aug 20, 2020 at 13:57
• @SomoKRoceS I think counting would be a more accurate word Commented Aug 20, 2020 at 13:58
• Or classifying? Commented Aug 20, 2020 at 15:33

# JavaScript (ES6), 63 bytes

Expects (c)(a), where c is an object holding the collections (keys = names, values = capacities), and a is the list of items.

Returns either [name, count] or 0.

(c,e=n=0)=>g=a=>a.every(s=>~--c[e|=c[s],v=s])?e&&g(a,n++):[v,n]


Try it online!

### Commented

( c,               // c = object describing the collections
e =              // e = flag to detect whether at least one item requested in the
//     list has a non-zero capacity
n = 0            // n = cycling counter
) =>               //
g = a =>         // g is a recursive function taking the list of items a[]
a.every(s =>   // for each value s in a[]:
~--c[        //   try to decrement c[s] and apply a bitwise NOT on the result
e |= c[s], //   set e if c[s] is non-zero (before being decremented)
v = s      //   set v to s
]            //   this yields 0 if and only if c[s] is defined and was set to 0
//   (if c[s] is undefined, --c[s] is NaN and ~--c[s] is -1)
) ?            // end of every(); if truthy:
e &&         //   abort if e = 0, so that we don't loop forever
g(a, n++)    //   otherwise, increment n and do a recursive call
:              // else:
[v, n]       //   return the result pair


# Io, 157 153 bytes

method(~,\,(if(X := ~values max,X,0)* ~size)repeat(i,if(~hasKey(x := \at(i% \size)asString)and~atPut(x,~at(x)-1)at(x)<1,return list(x,(i/ \size)round))))


Try it online!

## Explanation (Ungolfed)

method(a, b,                                    // Take inputs a & b.
(if(X := a values max, X, 0)                // The max of an empty list is nil, so we gotta return 0 if max is nil.
* a size) repeat(i,                         // Repeat max of capacities * dict size:
if(a hasKey(x :=b at(i%b size)asString) //     If the dict a has (x := b's current cyclic index)
and a atPut(x,a at(x) - 1)at(x) < 1, //     And decrementing that index results in 0:
return list(x,(i/b size)round)      //         Return [x, iteration # / size of list]
)
)                                           // After the Repeat: If nothing is returned from the if expression,
)                                               // a falsy value will be returned by default.


# R, 99 bytes

function(e,k)(which(sapply(rep(e,sum(unlist(k))),function(y)k[[y]]<<-k[[y]]-1)<0)[1]-1)%/%length(e)


Try it online!

Accepts 'elements' as a character vector and 'collections' as a named list of capacities.
Returns the element name and the number of full cycles at overflow, or NA if overflow never happens.

How?

overflow=o=
function(e,k)               # e=elements, k=collections
(which( ... )[1]           # get the first index of...
sapply(                  # a loop over...
rep(e,sum(unlist(k))),  # ...lots of repeats of the elements...
function(y)            # ...at each loop returning...
k[[y]]<<-k[[y]]-1     # ...the number of free spots left in the collection,
)<0                     # that is less than zero,
-1)%/%length(e)           # minus 1, DIV the number of elements
)                          # (so it's the number of complete loops,
# rather than the loop-in-progress)

• you might be able to shorten things by taking k as a named vector, and swapping k[[y]] with k[y]. I'm not sure why it's outputting name.name, though... Try it Online! Commented Aug 20, 2020 at 15:34
• Yeah, I thought so, too, and tried that. Unfortunately you need to use the USE.NAMES=F option to sapply to prevent the name.name labelling, and it ended up at the same bytes... Commented Aug 20, 2020 at 15:51
• (er, that is, same bytes once the extra () are removed...) Commented Aug 20, 2020 at 16:00
• I suspect that some iterative or recursive approach might be shorter, but I couldn't resist the chance to use <<- to modify k out-of-scope, in what must be a howler of bad 'R' programming style... Commented Aug 20, 2020 at 16:39
• Probably iterative; sapply is pretty long compared to a for loop if you have to define a function. Commented Aug 20, 2020 at 16:45

# Charcoal, 62 46 bytes

¿Φθ№η§ι¹«Ｗ¬Φυ№θκＦη⊞υ⟦№Ｅυ§λ¹κκ⟧⟦⊟§Φυ№θι⁰Ｉ⊖÷ＬυＬη


Try it online! Link is to verbose version of code. Takes input as an array of [capacity, name] pairs and an array of elements. Explanation:

¿Φθ№η§ι¹«


If there are no collections with an element, do nothing (falsy value), otherwise:

Ｗ¬Φυ№θκ


Repeat until an element causes the collection to overflow...

Ｆη⊞υ⟦№Ｅυ§λ¹κκ⟧


... for each element in the input, push its previous appearance count and the element to the predefined empty list. If the pair appears in the collection, this means that we had already exhausted it and this element now makes the collection overflow.

⟦⊟§Φυ№θι⁰Ｉ⊖÷ＬυＬη


Get the first element to overflow, plus calculate the number of iterations of the above loop and decrement it, which gives the number of whole cycles.

# Python 3.8, 95 bytes

Input is a dictionary and a list. This outputs an empty set if no collection overflows, a tuple otherwise.

f=lambda c,l,n=0:{*c}&{*l}and(c[(x:=l.pop(0))]and f({**c,x:c[x]-1},l+[x],n+1)or(x,n//-~len(l)))


Try it online!

In Python 3.9 this will be 2 bytes shorter as {**c,x:c[x]-1} can be replaced by c|{x:c[x]-1} due to this change.

# 05AB1E, 29 bytes

åài¹ÞvÐyk>©è<D0‹iyN¹g÷‚që®ǝë0


First input is the list of names, second is a flattened list of collections.

Try it online.

Explanation:

å                         # Check for each string in the first (implicit) input-list if
# it's in the second (implicit) input-list
ài                       # If any is truthy:
¹                      #  Push the first input-list again
Þ                     #  Cycle it indefinitely
v                    #  Loop over each name y:
Ð                   #   Triplicate the collection list (which will use the implicit
#   second input-list in the first iteration)
yk                 #   Get the index of name y in this list
>                #   Increase this index by 1
©               #   Store it in variable ® (without popping)
è              #   Use this index+1 to index into the collection-list again
<             #   Decrease this integer by 1
D0‹i         #   If this count is now negative:
N       #    Push the loop-index N
¹g     #    Push the length of the first input-list
÷    #    Integer-divide the index by this length
y    ‚   #    Pair it with name y
q  #    And exit the program
#    (after which this pair is output implicitly as result)
ë         #   Else (the count is still 0 or positive):
®        #    Push the index from variable ®
ǝ       #    And insert the new count back into the collection-list at
#    this index
ë                       #  Else (none of the names is in the collection-list)
0                      #   Push a 0
#   (after which it is output implicitly as falsey result)


NOTE: We could omit the final ë0 so it will implicitly output the second input as falsey result, since only 1 is truthy in 05AB1E. But this might cause confusion if the second input-list is a single pair, which we might confuse as a truthy pair result instead.

# PHP, 106104 102 bytes

function($a,$b){for(;$b;++$i)foreach($b as$x)if(!isset($a[$x]))$b=0;elseif(!$a[$x]--)return[$x,$i|0];}  Try it online! More verbosity: function($a, $b ) { for( ;$b; ++$i ) { // loop infinitely if original list is not empty // (and +1 cycle counter) foreach($b as $x ) { // start/restart cycling of list if( ! isset($a[$x] ) ) { // if item on list is not in collection...$b = 0;                 //   empty the list to return Falsey above
} elseif( ! $a[$x]-- )      // or if item collection has reached 0...
return [ $x,$i | 0 ];  //   return the set of item and cycle counter
}
}
}
}


# Husk, 27 bytes

?ȯsM÷L⁰▼øfo€⁰→mGλ←Vḣ¢²o>⁰#


Try it online!

Takes two arguments: a list of strings in the format ["dog","dog","cat"] and a list of number-string pairs in the format [(2,"dog"),(3,"cat")]. Prints a number-string pair or nothing. I have checked all test cases and the program passes them. Note that the interpreter doesn't like extra spaces in inputs.

If the second input is an empty list, its type needs to be specified or the interpreter can't deduce it and gives a type error. An empty list of number-string pairs is given as []:LPNLC. Apparently the first input can be empty without any issues.

## Explanation

Two arguments, one explicit (list of string, accessed through ⁰ by default, ² inside a lambda),
one implicit (list of pairs).

mGλ←Vḣ¢²o>⁰#   For each pair (n,x), replace n by index of first overflow.
m               Map over list of pairs:
G              Replace pair (n,x) by (f n x,x) where f is
λ             an anonymous function:
f takes two arguments, one explicit (n, accessed through ⁰) and one implicit (x)
²        First program input.
¢         Cycle infinitely
ḣ          and take prefixes.
V           1-based index of first prefix that satisfies:
#     Number of occurrences of x
o>⁰      is greater than n.
←            Decrement to get 0-based index.

fo€⁰→   Remove pairs whose string never occurs in the list:
f       Filter by
→   right part
o€     is an element of
⁰    first input.
Because Husk is lazy, the index calculation is never performed for the removed pairs.

?ȯsM÷L⁰▼ø   Produce output.
?           If the filtered list is empty,
ø   return the empty string.
ȯsM÷L⁰▼    Otherwise return this:
▼    take lexicographic minimum,
M        apply on its left part:
÷        integer division by
L⁰      length of first input
ȯs         cast to string (to keep types consistent).


I could save a few bytes by returning (0,"") as the falsy value instead of using strings, but it's also a valid "truthy" output and thus ambiguous. Since Husk is strongly typed, I can't return a pair for some inputs and a non-pair for others.

# Haskell, 274 235 228 bytes

a!e=[(x,y-sum[1|x==e])|(x,y)<-a]
u(h:t)
|and[b>=0|(a,b)<-h]=h:u t
|1>0=h:[]
s((a,b):t)
|b<0=a
|1>0=s t
c#l=let o=u$scanl(!)c$cycle l in(s$last o,length odivlength l) c&l |or[xeleml|(x,y)<-c]=print$c#l
|1>0=print"False"


Try it online!

• Saved 45 bytes thanks to @Zgarb !

& If there's any valid entry prints result, otherwise prints False.

# produces a list of all steps and returns a tuple of :

• element overflowed(s) of last iteration ,
• iterations length / list length

u stops infinite list when overflow happens.

! decremnts corresponding entry of list cycled

• Some hints: 1) foldl(&&)True can be and, foldl(||)False can be or 2) The condition on the first line can be (x,y-sum[1|x==e]) 3) You don't need parentheses around the arguments to div 4) Binary functions are usually shorter to define as infix, like a!e=… instead of h a e=…` Commented Aug 31, 2020 at 12:13
• Thanks @Zgarb ! I'm new to Haskell and I really like it Commented Sep 2, 2020 at 0:16
• Be sure to check the tips question! Commented Sep 2, 2020 at 10:08