Limit your numbers by your runs

Question

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.

The task

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 code-golf 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]

Answer 1

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

Answer 2

Perl 5 -p, 49 48 44 bytes

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

Try it online!

Answer 3

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

Answer 4

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.

Answer 5

Jelly, 19 bytes

ŒgḢ€ċЀṀḶ$<ċЀṀR$$Ẹ

Try it online!

Answer 6

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!

Answer 7

Jelly, 17 bytes

ŒgḢ€ċ’}<ċ
çЀx⁸ẸṆ

Try it online!

Answer 8

Japt, 21 bytes

x o e@ó¥ mÌè¥X ¨Uè¥XÄ

Test it online!

Answer 9

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

Answer 10

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!