Selbstlimitierende Listen

Stellen Sie sich eine nicht leere Liste L vor, die nichtnegative ganze Zahlen enthält. Ein Lauf in L ist eine zusammenhängende Unterliste gleicher Elemente, die nicht länger gemacht werden kann. Zum Beispiel können die Läufe von [0,0,1,1,3,3,3,2,1,1] sind [0,0], [1,1], [3,3,3], [2 ], [1,1] . Die Liste L ist selbstlimitierend, wenn für jede ganze Zahl N ≥ 1 die Anzahl der Vorkommen von N kleiner oder gleich der Anzahl der Durchläufe von N-1 ist . Die obige Liste ist nicht selbstlimitierend, da es 4 Vorkommen von 1 gibt , sondern nur einen Lauf von 0 s.

Hier ist ein Beispiel einer selbstlimitierenden Liste: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,1,0] . Es hat

• 5 Läufe von 0 und 5 Vorkommen von 1 ,
• 4 Läufe von 1 und 2 Vorkommen von 2 ,
• 2 Läufe von 2 und 1 Auftreten von 3 ,
• 1 Lauf von 3 und 1 Auftreten von 4 ,
• 1 Lauf von 4 und keine Vorkommen von 5 ,
• keine Vorkommen von anderen ganzen Zahlen.

Die Aufgabe

Ihre Aufgabe ist es, zu entscheiden, ob eine Liste selbstlimitierend ist. Insbesondere soll Ihre Eingabe eine nicht leere Liste nichtnegativer Ganzzahlen sein. Wenn sich die Liste selbst einschränkt, ist Ihre Ausgabe wahrheitsgetreu. sonst ist es falsch. Eingabe und Ausgabe können in jedem vernünftigen Format erfolgen.

Die niedrigste Byteanzahl in jeder Programmiersprache ist der Gewinner. Standard Code-Golf .

Testfälle

Wahrheitsinstanzen:

[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]

Falsche Instanzen:

[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]

Perl 6 , 29 Bytes

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

Probieren Sie es online!

Sehr schöne Herausforderung für Perl 6. Verwendet den Teilmengenoperator für Taschen (ganzzahlige Mengen). Erläuterung:

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

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

Probieren Sie es online!

Wie?

Das Array c [] wird verwendet, um sowohl die Anzahl der Durchläufe als auch die Anzahl der ganzzahligen Vorkommen zu speichern. Läufe werden auf nicht-negative Indizes gespeichert und integer Vorkommen an 1's-Komplement Indizes gespeichert ( c [-1] = Anzahl von 0 's, c [-2] = Anzahl der 1 ist, etc.).

Negative Indizes werden tatsächlich als Eigenschaften des zugrunde liegenden Array-Objekts gespeichert, und .some () durchläuft sie nicht.

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 , 49 48 44 Bytes

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

Probieren Sie es online!

Gelee , 10 Bytes

œ-ŒgḢ€‘ƊS¬

Probieren Sie es online!

Wie es funktioniert

œ-Œ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$$Ẹ

Probieren Sie es online!

Gelee , 17 Bytes

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

Probieren Sie es 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)))

Probieren Sie es online!

Japt , 21 Bytes

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

Online testen!

Stax , 13 9 Bytes

Dennis fand einen viel besseren Algorithmus . Ich habe es schamlos auf stax portiert.

ä╨²@┬↕OR♣

Führen Sie es online aus und debuggen Sie es

Ausgepackt, ungolfed und kommentiert, so sieht es aus.

c   copy input
:g  get run elements
{^m increment each
|-  multiset-subtract from original input
|M! get maximum from result, and apply logical not

Führen Sie dieses aus

Alte Antwort:

║Ä|╤#╫∩▼cëózü

Führen Sie es aus und debuggen Sie es

Es durchläuft die Eingabe und überprüft die Bedingungen:

• Ist das Element > 0?
• Ist occurrences(element) >= runs(element - 1)?

Wenn eine dieser Bedingungen für ein Element zutrifft, ist dieses Element konform. Wenn alle Elemente kompatibel sind, ist das Ergebnis 1.

Hier ist die entpackte, ungolfierte, kommentierte Darstellung desselben Programms.

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

Führen Sie dieses aus

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]

Probieren Sie es online!