15
\$\begingroup\$

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 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]
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Mar 22 '18 at 14:19
  • \$\begingroup\$ @LeakyNun Yes, otherwise the condition fails for those N for which N-1 is not present. \$\endgroup\$ – Zgarb Mar 22 '18 at 14:22
  • \$\begingroup\$ @Mr.Xcoder There's [2] too, but such cases should be falsy, yeah. \$\endgroup\$ – Erik the Outgolfer Mar 22 '18 at 14:27
  • \$\begingroup\$ @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. \$\endgroup\$ – Zgarb Mar 22 '18 at 14:35
  • \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Mar 22 '18 at 14:56

10 Answers 10

5
\$\begingroup\$

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.
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Beautiful. I saw the Bag+subset approach but stuck on the thing to compare to. \$\endgroup\$ – Phil H Mar 22 '18 at 21:32
3
\$\begingroup\$

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()
\$\endgroup\$
3
\$\begingroup\$

Perl 5 -p, 49 48 44 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

Jelly, 19 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 17 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ sum(1for ... if x==j!=y) => sum(x==j!=y for ...). \$\endgroup\$ – Mr. Xcoder Mar 22 '18 at 14:56
  • \$\begingroup\$ @Mr.Xcoder oh ofc. thanks! \$\endgroup\$ – HyperNeutrino Mar 22 '18 at 17:51
2
\$\begingroup\$

Japt, 21 bytes

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

Test it online!

\$\endgroup\$
2
\$\begingroup\$

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

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

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!

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