## Self-limiting lists

Consider a nonempty list L containing nonnegative integers. A run in L is a contiguous sublist of equal elements, which cannot be made longer. For example, the runs of [0,0,1,1,3,3,3,2,1,1] are [0,0], [1,1], [3,3,3], [2], [1,1]. The list L is self-limiting if for each integer N ≥ 1, the number of occurrences of N is less than or equal to the number of runs of N-1. The above list is not self-limiting, because there are 4 occurrences of 1, but only one run of 0s.

Here's an example of a self-limiting list: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,1,0]. It has

• 5 runs of 0 and 5 occurrences of 1,
• 4 runs of 1 and 2 occurrences of 2,
• 2 runs of 2 and 1 occurrence of 3,
• 1 run of 3 and 1 occurrence of 4,
• 1 run of 4 and no occurrences of 5,
• no occurrences of other integers.

Your task is to decide whether a list is self-limiting. More explicitly, your input shall be a nonempty list of nonnegative integers. If the list is self-limiting, your output shall be truthy; otherwise, it shall be falsy. Input and output can be in any reasonable format.

The lowest byte count in each programming language is the winner. Standard rules apply.

## Test cases

Truthy instances:

[0]
[1,0]
[0,1,1,0,2]
[3,1,1,0,0,2,0,0]
[5,0,4,1,3,0,2,2,0,1,1,1,0]
[0,0,1,1,0,0,1,1,0,0,2,2,0,0]
[6,0,0,0,2,2,1,0,5,0,3,4,0,1,1,1]
[5,0,1,0,0,0,0,4,0,3,1,1,1,2,2,0,0,0,0,0]
[4,5,1,3,2,0,5,2,0,3,0,1,0,1,0,0,0,1,0,0,1,0,3,4,4,0,2,6,0,2,6]
[0,4,1,3,10,6,0,1,3,7,9,5,5,0,7,4,2,2,5,0,1,3,8,8,11,0,0,6,2,1,1,2,0,4]


Falsy instances:

[2]
[1,1,0]
[0,0,1,1,1,0,0,2]
[0,1,0,1,1,2,2,3,0,0,4,6]
[1,1,2,1,2,0,2,0,3,0,0,2,2,1,2,3,2,0,1,1,1,0,0,3,3,0]
[3,4,1,0,0,0,5,5,0,2,2,0,0,0,0,0,2,0,1,1,0,4,3,5,4,3]
[1,0,0,0,2,5,3,1,1,0,3,3,1,3,5,4,0,4,0,0,2,0,2,1,1,5,0,0,2,4,4,0,2,0,1,4,4,2,3,3,5,3,4,0,2,0,5]
[4,3,1,0,0,4,6,6,1,0,1,2,1,3,0,1,0,2,0,3,4,0,2,1,1,3,0,2,2,2,0,5,5,0,5,2,5,5,0,4,3,2,3,1,1,3,5,1,4,1,6,2,6,2,4,0,4,0,4,5,3,3,0,0,6,1,0,0,0,6,2,1,0,1,2,6,2,4]
[5,1,1,1,0,2,0,6,1,0,2,1,2,2,5,3,1,0,0,0,3,2,3,0,1,1,0,1,0,1,1,2,0,6,4,1,2,1,1,6,4,1,2,2,4,0,1,2,2,1,3,0,1,2,0,0,0,2,0,2,2,0,1,0,0,1,3,0,0,0,6,2,0,1,0,1,2,1,1,1,0,4,0,0,5,2,0,0,0,4,1,2,2,2,2,0,5,3,2,4,5,0,5]

• Not to be a bother, but please consider using one of the approaches from this meta discussion instead of truthy/falsy, as truthiness isn't a property of more than a couple languages used here often. Mar 22, 2018 at 14:19
• @LeakyNun Yes, otherwise the condition fails for those N for which N-1 is not present. Mar 22, 2018 at 14:22
• @Mr.Xcoder There's [2] too, but such cases should be falsy, yeah. Mar 22, 2018 at 14:27
• @FryAmTheEggman I hadn't seen that discussion, thanks for linking it. I'll keep this challenge as it is though, because I want to process the approaches discussed there for a while. Mar 22, 2018 at 14:35
• Sure, but I would like to keep the comment there, since I feel like a lot of people have missed it. It matters quite a lot, at least for me, in posting in languages like Retina. Mar 22, 2018 at 14:56

# Perl 6, 29 bytes

{bag(.grep(?*)X-1)⊆.squish}


Try it online!

Very nice challenge for Perl 6. Uses the subset operator on Bags (integer-weighted sets). Explanation:

{
bag(           # Create bag of
.grep(?*)  # non-zero elements,
X- 1       # decremented by one.
)
⊆              # Subset test.
.squish        # "squish" removes repeated elements in each run.
# The result is implicitly converted to a bag
# counting the number of runs.
}

• Beautiful. I saw the Bag+subset approach but stuck on the thing to compare to. Mar 22, 2018 at 21:32

# JavaScript (ES6), 92 89 bytes

a=>a.map(n=>g(~n,n!=p&&g(p=n)),c=[j=0],p=g=n=>c[n]=-~c[n])&&!c.some((n,i)=>i-j++|n<c[~j])


Try it online!

### How?

The array c[ ] is used to store both the number of runs and the number of integer occurrences. Runs are stored at non-negative indices and integer occurrences are stored at 1's-complement indices (c[-1] = number of 0's, c[-2] = number of 1's, etc.).

Negative indices are actually saved as properties of the underlying array object and .some() does not iterate over them.

a =>                        // given the input array a[]
a.map(n =>                // for each value n in a[]:
g(                      //   update c[]:
~n,                   //     increment c[~n] (# of integer occurrences)
n != p && g(p = n)    //     if n != p, set p to n and increment c[n] (# of runs)
),                      //   end of c[] update
c = [j = 0],            //   start with c = [0] and j = 0 (used later)
p =                     //   initialize p to a non-numeric value
g = n => c[n] = -~c[n]  //   g = helper function to increment c[n]
)                         // end of map()
&& !c.some((n, i) =>      // for each value n at position i in c[]:
i - j++ |               //   make sure that i == j++
n < c[~j]               //   and n is greater than or equal to c[~j]
)                         // end of some()


# Perl 5-p, 4948 44 bytes

#!/usr/bin/perl -p
$z[$_+1]+=!/^$o$/;$z[$o=$_]--}{$_="@z"!~/.-/


Try it online!

# Jelly, 10 bytes

œ-ŒgḢ€‘ƊS¬


Try it online!

### How it works

œ-ŒgḢ€‘ƊS¬  Main link. Argument: A (array)

Ɗ    Drei; group the three links to the left into a monadic chain.
Œg          Group consecutive, identical elements of A into subarrays.
Ḣ€        Head each; pop the first element of each run.
‘       Increment the extracted integers.
The resulting array contains n repeated once for each run of (n-1)'s.
œ-          Perform multiset subtraction, removing one occurrence of n for each
run of (n-1)'s.
S    Take the sum. If only 0's remain, the sum will be 0.
¬   Take the logical NOT, mapping 0 to 1 and positive integers to 0.


# Jelly, 19 bytes

ŒgḢ€ċÐ€ṀḶ$<ċÐ€ṀR$$Ẹ  Try it online! # Jelly, 17 bytes ŒgḢ€ċ’}<ċ çÐ€x⁸ẸṆ  Try it online! # Python 3, 94 bytes lambda a:all(sum(1for x,y in zip(a,a[1:]+[-1])if x==j!=y)>=a.count(j+1)for j in range(max(a)))  Try it online! • sum(1for ... if x==j!=y) => sum(x==j!=y for ...). Mar 22, 2018 at 14:56 • @Mr.Xcoder oh ofc. thanks! Mar 22, 2018 at 17:51 # Japt, 21 bytes x o e@ó¥ mÌè¥X ¨Uè¥XÄ  Test it online! # Stax, 13 9 bytes Dennis found a much better algorithm. I've shamelessly ported it to stax. ä╨²@┬↕OR♣  Run and debug it online Unpacked, ungolfed, and commented, this is what it looks like. c copy input :g get run elements {^m increment each |- multiset-subtract from original input |M! get maximum from result, and apply logical not  Run this one Old Answer: ║Ä|╤#╫∩▼cëózü  Run and debug it It iterates over the input and checks the conditions: • Is the element > 0? • Is occurrences(element) >= runs(element - 1)? If either of these conditions are true for an element, then that element is compliant. Iff all elements are compliant, the result is 1. Here's the unpacked, ungolfed, commented representation of the same program. O push 1 under the input F iterate over the input using the rest of program |c skip this iteration of the value is 0 x# number of occurrences of this value in input (a) x:g _v# number of runs of (current-1) in input (b) >! not (a > b); this will be truthy iff this element is compliant * multiply with running result  Run this one ## Haskell, 80 bytes import Data.List o#l=[1|x<-l,x==o] f x=and[(i-1)#(head<$>group x)>=i#x|i<-x,i>0]


Try it online!