In dieser Herausforderung besteht Ihre Aufgabe darin, aus einer Folge von Anweisungen ein ungerichtetes Diagramm zu erstellen. Es gibt eine Direktive für jede nichtnegative Ganzzahl und jede transformiert einen gegebenen Graphen in einen neuen.

• Anweisung 0: Fügen Sie einen neuen getrennten Knoten hinzu.
• Anweisung 1: Fügen Sie einen neuen Knoten hinzu und verbinden Sie ihn mit jedem vorhandenen Knoten.
• Richtlinie m > 1: Entfernen Sie alle Knoten, deren Grad (Anzahl der Nachbarn) durch teilbar ist m. Beachten Sie, dass dies 0durch alle teilbar ist m, sodass nicht verbundene Knoten immer entfernt werden.

Die Anweisungen werden nacheinander von links nach rechts angewendet, beginnend mit dem leeren Diagramm. Zum Beispiel wird die Sequenz [0,1,0,1,0,1,3]wie folgt verarbeitet und mit großartiger ASCII-Grafik erklärt. Wir beginnen mit dem leeren Diagramm und fügen einen einzelnen Scheitelpunkt hinzu, wie von 0:

a

Dann wird eine weitere Eckpunkt hinzuzufügen und es an die erste Verbindung, wie angewiesen durch 1:

a--b

Wir fügen einen weiteren getrennten Vertex und dann einen verbundenen hinzu, wie von 0und angewiesen 1:

a--b   c
 \  \ /
  `--d

Wir wiederholen dies noch einmal nach Anweisung von 0und 1:

  ,--f--e
 /  /|\
a--b | c
 \  \|/
  `--d

Zum Schluss entfernen wir die Eckpunkte des 3. Grades aund b, wie von 3:

f--e
|\
| c
|/
d

Dies ist der durch die Sequenz definierte Graph [0,1,0,1,0,1,3].

Eingang

Eine Liste nichtnegativer Ganzzahlen, die eine Folge von Anweisungen darstellen.

Ausgabe

Die Anzahl der durch die Sequenz definierten Knoten im Diagramm.

Testfälle

[] -> 0
[5] -> 0
[0,0,0,11] -> 0
[0,1,0,1,0,1,3] -> 4
[0,0,0,1,1,1] -> 6
[0,0,1,1,0,0,1,1,2,5,7,0,1] -> 6
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2] -> 6
[0,0,1,1,0,0,1,1,5,2,3,0,0,1,1,0,0,1,1,3,4,0,0,1,1,2,1,1] -> 8
[0,0,1,1,0,0,1,1,2,5,7,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,8] -> 14

Detaillierte Regeln

Sie können eine Funktion oder ein vollständiges Programm schreiben. Die kürzeste Byteanzahl gewinnt. Standardlücken sind nicht zulässig. Bitte erläutern Sie Ihren Algorithmus in Ihrer Antwort.

Es ist eine Woche vergangen, deshalb habe ich die kürzeste Antwort akzeptiert. Wenn später eine noch kürzere erscheint, aktualisiere ich meine Auswahl. Eine lobende Erwähnung geht an Peter Taylors Antwort , auf der mehrere andere basierten, einschließlich des Gewinners.

Pyth , 37 31

lu?+GH<H2m@Gdf%+*@GTtTs>GTHUGQY

Diese Lösung verwendet eine Reduktionsfunktion ( u), um eine Liste zu erstellen, wobei jeder Eintrag einem in der Liste verbleibenden Knoten entspricht und der Wert des Eintrags damit übereinstimmt, ob der Knoten ursprünglich unter der Direktive 0 oder 1 hinzugefügt wurde.

Gist die Akkumulatorvariable in der Reduktionsfunktion und enthält die oben genannte Liste. Es wird auf die leere Liste initialisiert Y.

HNimmt den Wert jedes Mitglieds Qder Eingabe nacheinander. Das Ergebnis des Ausdrucks wird Gjedes Mal zugewiesen , und der nächste Eintrag von Qwird zugewiesen H, und der Ausdruck wird erneut ausgeführt.

Für eine Gordnungsgemäße Aktualisierung gibt es zwei Möglichkeiten, eine für Direktive 0 oder 1 und eine für die anderen Direktiven. Diese Fälle unterscheiden sich mit dem ternären? ... <H2 ...

Wenn H0 oder 1 ist, dann werden alle brauchen wir ist append zu tun Hzu G. +GHerreicht dies.

Andernfalls müssen Sie zunächst für jeden Knoten im Diagramm ermitteln, wie viele Nachbarn er hat. Dies erfolgt in zwei Schritten:

Zuerst s>GTzählt die Anzahl der Knoten , an oder nach dem Eingangsknoten , die 1s ist. Diese sind alle mit dem Eingangsknoten verbunden, außer dass wir um 1 überzählen, wenn der Eingangsknoten eine 1 ist.

Zweitens benötigen wir die Anzahl der Knoten, die früher als der damit verbundene Eingangsknoten sind. Dies ist 0, wenn der Eingabeknoten eine 0 ist, und der Index des Eingabeknotens T, wenn der Eingabeknoten eine 1 ist. Dieser Wert würde gegeben sein durch *@GTT. Es gibt jedoch immer noch die Überzählung aus dem ersten Abschnitt, die korrigiert werden muss. Daher berechnen wir *@GTtTstattdessen, was 1 weniger ist, wenn der Eingabeknoten eine 1 ist. Diese Werte werden summiert, um die Anzahl der mit dem Eingabeknoten verbundenen Knoten zu erhalten.

% ... Hwill give 0 ist, dass die Zahl durch teilbar Hist und daher entfernt werden sollte, andernfalls wird sie nicht 0 ergeben.

f ... UGgibt also die Indizes der Eingabe an, die nicht entfernt werden sollten, da fes sich um einen Filter handelt und 0 falsch ist.

m@Gd konvertiert diese Indizes in die Nullen und Einsen der entsprechenden Knoten.

Schließlich wird, sobald die resultierende Liste der mit 0 und 1 bezeichneten Knoten gefunden ist, ihre Länge berechnet ( l) und gedruckt (implizit).

Breite Idee dank @PeterTaylor.

GolfScript (53 Bytes)

])~{:^1>{.-1:H)-,:T;{..H):H*T@-:T+^%!{;}*}%}{^+}if}/,

Online-Demo

Ich habe noch nicht wirklich Golf gespielt, aber ich habe festgestellt, dass es nicht sehr einfach ist, die Variablen Hund zu eliminieren T, so dass dies ein lokales Minimum sein könnte.

Übernimmt die Eingabe von stdin im Format [0 1 2 3]. Lässt die Ausgabe auf stdout.

Ungolfed:

])~{
  :^1>{
    # array of 0s and 1s
    # Each 0 has degree equal to the number of 1s after it
    # Each 1 has degree equal to the number of values before it plus the number of 1s after it
    .-1:H)-,:T;
    {
      # Stack: x
      # T' = T - x is the number of 1s after it
      # H' = H + 1 is the number of values before it
      # Degree is therefore H' * x + T' = H * x + T - x = (H-1)*x + T
      # Keep x unless degree % ^ == 0
      ..H):H*T@-:T+^%!{;}*
    }%
  }{^+}if
}/,

CJam, 129 75 73 68 61 46 42 Bytes

Lösung basierend auf Peters Algorithmus:

Lq~{I+I1>{0:U(<:L{LU<,*LU):U>1b+I%},}*}fI,

Code-Erweiterung folgt.

Vorherige Lösung (61 Bytes):

Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,

Nimmt Eingaben von STDIN wie:

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

Ausgang ist die Nummer auf STDOUT:

8

Algorithmus :

• Pflegen Sie eine inkrementierende Variable, die Udie ID des hinzuzufügenden Knotens speichert.
• Verwalten Sie eine Liste mit Listen, in der jede Liste ein Knoten ist, dessen eindeutige ID aus dem ersten Element der Liste und den verbleibenden Elementen der IDs der verbundenen Knoten besteht.
• In jeder Iteration (beim Lesen der Eingabeanweisungen)
  • Wenn dies der Fall ist 0, fügen Sie [U]eine Liste mit Listen hinzu
  • Wenn dies der Fall ist 1, fügen Sie Uzu jeder Liste in der Liste der Listen eine weitere Liste hinzu, die aus dem ersten Element jeder Liste der Listen und bestehtU
  • Damit die Direktive entfernt werden kann, filtere ich alle durch length - 1teilbaren Listen heraus mund notiere weiterhin das erste Element dieser Listen. Nach dem Filtern entferne ich alle entfernten IDs aus der verbleibenden Liste der IDs.

Code-Erweiterung :

Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,
L                                            "Put an empty array on stack";
 q~                                          "Evaluate the input";
   {                                }/       "For each directive";
    :N                                       "Store the directive in N";
      2<{     ...    }{    ...    }?         "If directive is 0 or 1, run the first";
                                             "block, else second";
{U):UaN{f+U1$0f=+}*a+}
 U):U                                        "Increment and update U (initially 0)";
     a                                       "Wrap it in an array";
      N{         }*                          "Run this block if directive is 1";
        f+                                   "Add U to each list in list of list";
          U1$                                "Put U and list of lists on stack";
             0f=                             "Get first element of each list";
                +                            "Prepend U to the above array";
                   a+                        "Wrap in array and append to list of list";
{{:X,(N%_!{X0=L+:L;}*},Lf-}
 {                   },                      "Filter the list of list on this block";
  :X,(                                       "Get number of connections of this node";
      N%_                                    "mod with directive and copy the result";
         !{        }*                        "If the mod is 0, run this block";
           X0=                               "Get the id of this node";
              L+:L;                          "Add to variable L and update L";
                       Lf-                   "Remove all the filtered out ids from the";
                                             "remaining nodes";
,                                            "After the whole process is completed for"
                                             "all directives, take length of remaining ";
                                             "nodes in the list of list";

Probieren Sie es hier aus

Pyth, 88 80 75 Zeichen

JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J

Ich bin fertig. Vielleicht hat jemand anderes ein paar Golftipps.

Yist die Adjazenzliste des Graphen. Aus Golfgründen behalte ich auch nach dem Löschen des Knotens einen Knoten in dieser Liste (ansonsten müsste ich alle Indizes aktualisieren). Jeder Knoten hat sich als Nachbarn. Die Liste Jverfolgt die gelöschten Knoten.

Ich zeige die Änderungen der Adjazenzliste an der Beispieleingabe [0,1,0,1,0,1,3]:

Eingabe 0: Y = [[0]] J = []
Eingabe 1: Y = [[0,1], [0,1]] 0 J = []
Eingabe 0: Y = [[0,1], [0,1], [2]] J = []
Eingabe 1: Y = [[0,1,3], [0,1,3], [2,3], [0,1,2,3]] J = []
Eingabe 0: Y = [[0,1,3], [0,1,3], [2,3], [0,1,2,3], [4]] J = []
Eingabe 1: Y = [[0,1,3,5], [0,1,3,5], [2,3,5], [0,1,2,3,5], [4,5 ], [0,1,2,3,4,5]] J = []
Eingabe 3: Y = [[3,5], [3,5], [2,3,5], [2,3,5], [4,5], [2,3,4,5] J = [0,1]

Der Algorithmus ist dann ziemlich einfach: Iteriere über alle Eingaben, wenn Eingabe == 0: füge einen neuen Knoten mit sich selbst als Nachbarn hinzu, wenn Eingabe == 1: füge einen neuen Knoten mit allen Knoten als Nachbarn hinzu (auch die gelöschten) und füge hinzu dieser Knoten zur Adjazenzliste aller Knoten, wenn Eingabe> 1: Ermitteln Sie die Knoten mit # Nachbar-1% Eingabe == 0 und fügen Sie sie hinzu J, um jeweils die Nachbarn jedes Knotens mit zu aktualisieren J. Am Ende drucken Sie die Länge von Yminus der Länge von (der Menge von) J.

JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J
JY                      set J=[]
  FHQ                   for H in: input()
I!H      )                if H==0:
   ~Y]]lY                   Y.append([len(Y)])
IqH1              )       if H==1:
    =Y+                     Y=                 +
       m+dlYY                 old nodes updated
             ]UhlY                              new node with all neighbors
VY                )       for N in range(len(Q)):
  I&Hq%l@YNH1    )          if H>0 and len(Y[N])%H==1:
             ~J]N             J.append(N) //this node gets deleted
=Ym           Y           Y=[           for k in Y]
   f!}TJ@YkUlY               k-filtered  //all items of J are removed
;                       end input for loop
-lYl{J                  print len(Y) - len(set(J))

Verwendung

Rufen Sie einfach das Skript auf und geben Sie eine Eingabe [0,1,0,1,0,1,3]oder einen anderen Testfall ein.

APL, 71 65 55 Zeichen

{⍬≡⍺:≢⍵⋄r←1↓⍺⋄1<c←⊃⍺:r∇i⌿⍵/⍨i←0≠c|+/⍵⋄c:r∇∨⌿↑a(⍉a←⍵,1)⋄r∇0,0⍪⍵}∘(0 0⍴0)

{⍺←0 0⍴0⋄⍬≡⍵:≢⍺⋄(⍺{1<⍵:i⌿⍺/⍨i←×⍵|+/⍺⋄⍵:-⌿↑(1,1⍪⍺)1⋄0,0⍪⍺}⊃⍵)∇1↓⍵}

{g←0 0⍴0⋄(≢g)⊣{1<⍵:g⌿⍨←g/⍨←×⍵|+/g⋄(⊃g)-←g⍪⍨←g,⍨←⍵}¨2,⍵}

Das Diagramm wird als boolesche Adjazenzmatrix dargestellt. Zeilen / Spalten werden nach Bedarf hinzugefügt und entfernt.

Python 2, 296

s=input();e=[];n=[];c=0
for t in s:
    if t<2:e=e+[[]]if t==0 else [x+[c]for x in e]+[n[:]];n+=[c];c+=1
    else:
        M=zip(*[(i,n[i])for i,x in enumerate(e)if not len(x)%t])
        if M:e=[list(set(z)-set(M[1]))for j,z in enumerate(e)if j not in M[0]];n=list(set(n)-set(M[1]))
print len(n)

Jeder Knoten erhält eine eindeutige ID und die Nachbar-IDs jedes Knotens werden aufgezeichnet. Wenn die Direktive 0 ist, wird eine leere Nachbarliste für den neuen Knoten hinzugefügt. Wenn die Direktive 1 ist, werden die IDs aller vorhandenen Knoten zur Nachbarliste für den neuen Knoten, und alle anderen Nachbarlisten werden aktualisiert, um die neue Knoten-ID aufzunehmen. Für m> 1 werden Knoten mit Nachbarlisten, die ein Vielfaches von m sind, aus der Knotenliste und allen Nachbarlisten entfernt. Vielen Dank an @Optimizer für das Erkennen eines Fehlers in einer früheren Version.

NetLogo, 160

to f[t]foreach t[if ? = 0[crt 1]if ? = 1[crt 1[create-links-with other turtles]]if ? > 1[ask turtles with[count my-links mod ? = 0][die]]]show count turtles
end

Die Implementierung ist unkompliziert, da jedes Symbol gelesen und die entsprechende Aktion ausgeführt wird.

to f[t]
  foreach t [
    if ? = 0 [
      crt 1
    ]
    if ? = 1 [
      crt 1 [create-links-with other turtles]
    ]
    if ? > 1 [
      ask turtles with [count my-links mod ? = 0] [die]
    ]
  ]
  show count turtles
end

Sie können von der Befehlszeile aus als ausführen f[0 0 1 1 0 0 1 1 2 5 7 0 1].

Ruby 159 157 ( Demo )

N=Struct.new:l
G=->c{n=[]
c.map{|m|m<1?n<<N.new([]):m<2?(w=N.new([])
n.map{|x|x.l<<w;w.l<<x}
n<<w):(n-=r=n.select{|x|x.l.size%m<1}
n.map{|x|x.l-=r})}
n.size}

Dies definiert eine Funktion, die Gmit der Stabby-Lambda-Syntax aufgerufen wird . Verwenden Sie G[[0, 1]], um es mit den Befehlen 0und aufzurufen 1.

Die Implementierung ist ziemlich einfach: Es gibt eine NodeStruktur ( Noben genannt), die über die lEigenschaft Verweise auf alle verknüpften Knoten enthält .GErstellt Knoten nach Bedarf und bearbeitet deren Verknüpfungen. Eine lesbare Version finden Sie hier .

CJam, 99 97 Bytes

Lal~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,

Hier gibt es noch viel zu golfen. Der Algorithmus basiert auf dem Verfolgen der Adjazenzmatrix, aber das Darstellen der leeren Matrix, ohne sie speziell behandeln zu müssen, bereitet mir Kopfschmerzen.

Teste es hier.

Die Eingabe ist ein Array im CJam-Stil:

[0 0 1 1 0 0 1 1 2 5 7 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 8]

Mit diesem Testgeschirr können Sie alle Tests ausführen:

"[]
[5]
[0,0,0,11]
[0,1,0,1,0,1,3]
[0,0,0,1,1,1]
[0,0,1,1,0,0,1,1,2,5,7,0,1]
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2]
[0,0,1,1,0,0,1,1,5,2,3,0,0,1,1,0,0,1,1,3,4,0,0,1,1,2,1,1]
[0,0,1,1,0,0,1,1,2,5,7,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,8]"

","SerN/{
La\~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,
N}/

Python 2, 174

l=input()
g={}
n=0
for x in l:
 n+=1;g[n]=set()
 if x>1:h={i for i in g if len(g[i])%x};g={i:g[i]&h for i in set(g)&h}
 if x==1:
  for i in g:g[i]^={n};g[n]^={i}
print len(g)

Damit kann wohl noch viel gespielt werden.

Ich habe ein Wörterbuch benutzt g , um die Grafik darzustellen. Die Knoten sind durch Zahlen gekennzeichnet und werden der Menge benachbarter Knoten zugeordnet. Dies bedeutet, dass jede Aktualisierung einer Kante an beiden Endpunkten ausgeführt werden muss.

Neue Knotenindizes werden durch Hochzählen erstellt n. Jedes Mal erstelle ich einen neuen leeren Knoten n. Für das Kommando 0bleibt es nur. Für den Befehl 1ist er über mit dem anderen Knoten verbunden g[i]^={n};g[n]^={i}. Verwenden von xoder machen es so, dass der Knoten nicht mit sich selbst verbunden ist. Bei Befehlen> 1 wird es sofort gelöscht.

Das Filtern von Knoten, deren Grad ein Vielfaches ist, wird durchgeführt, indem zuerst Knoten gefunden werden, die übrig bleiben ( h), dannand die Liste der Knoten und die Nachbarn jedes Knotens ermittelt werden.

Schließlich ist die Anzahl der Einträge im Diagrammwörterbuch die Antwort.

Mathematica, 223 Bytes

Wow, das war länger als ich erwartet hatte.

f=(g={};t=Append;l=Length;m=ListQ;h=Flatten;k=Position;o=If;(d=#;o[d==0,g=g~t~{},o[d==1,g=o[m@#,t[#,l@g+1],#]&/@g;g=t[g,h@k[g,_?m,1]],g=o[l@#~Mod~d==0,0,#]&/@g;p=h@k[g,0];(c=#;g=#~DeleteCases~c&/@g)&/@p]])&/@#;g~Count~_?m)&

Verwendung:

f@{0, 1, 0, 1, 0, 1, 3}

Hier sind die Ergebnisse aus den Testfällen:

f /@ {
  {},
  {5},
  {0, 0, 0, 11},
  {0, 1, 0, 1, 0, 1, 3},
  {0, 0, 0, 1, 1, 1},
  {0, 0, 1, 1, 0, 0, 1, 1, 2, 5, 7, 0, 1},
  {0, 0, 1, 1, 1, 1, 5, 1, 4, 3, 1, 0, 0, 0, 1, 2},
  {0, 0, 1, 1, 0, 0, 1, 1, 5, 2, 3, 0, 0, 1, 1, 0, 0, 1, 1, 3, 4, 0, 0, 1, 1, 2, 1, 1},
  {0, 0, 1, 1, 0, 0, 1, 1, 2, 5, 7, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 8}
}

Out: {0, 0, 0, 4, 6, 6, 6, 8, 14}

Weniger golfen:

f = (
   a = #;
   g = {};
   Table[
    If[a[[n]] == 0,
     AppendTo[g, {}],
     If[a[[n]] == 1,
      g = If[ListQ@#, Append[#, Length@g + 1], #] & /@ g; 
      g = Append[g, Flatten@Position[g, _?ListQ, 1]],
      If[a[[n]] > 1,
       g = If[Mod[Length@#, a[[n]]] == 0, 0, #] & /@ g;
       p = Flatten@Position[g, 0];
       (c = #; g = DeleteCases[#, c] & /@ g) & /@ p
       ]
      ]
     ],
    {n, Length@a}];
   Count[g, _?ListQ]
   ) &

Die Art und Weise, wie dies funktioniert, ist die Darstellung des Diagramms als Liste von "Listen von Nachbarn".
Für die 0- Direktive füge ich einfach eine leere Liste an.
Für die Direktive 1 hänge ich eine Liste aller vorherigen Knoten an und füge den neuen Knoten allen vorherigen Knoten hinzu.
Bei einer Direktive > 1 habe ich die angegebenen Knoten entfernt und den Rest aktualisiert.