En este desafío, su tarea es construir un gráfico no dirigido a partir de una secuencia de directivas. Hay una directiva para cada entero no negativo, y cada uno transforma un gráfico dado en uno nuevo.

• Directiva 0: agregue un nuevo nodo desconectado.
• Directiva 1: agregue un nuevo nodo y conéctelo a cada nodo existente.
• Directiva m > 1: elimine todos los nodos cuyo grado (número de vecinos) es divisible por m. Tenga en cuenta que 0es divisible por todos m, por lo que los nodos desconectados siempre se eliminan.

Las directivas se aplican una por una, de izquierda a derecha, comenzando con el gráfico vacío. Por ejemplo, la secuencia [0,1,0,1,0,1,3]se procesa de la siguiente manera, explicada usando un increíble arte ASCII. Comenzamos con el gráfico vacío y agregamos un vértice único según lo indicado por 0:

a

Luego, agregue otro vértice y conéctelo al primero, como lo indique 1:

a--b

Agregamos otro vértice desconectado y luego uno conectado, como lo indica 0y 1:

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

Repetimos esto una vez más, según las indicaciones 0y 1:

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

Finalmente, eliminamos los vértices de grado 3 ay b, como lo indica 3:

f--e
|\
| c
|/
d

Este es el gráfico definido por la secuencia [0,1,0,1,0,1,3].

Entrada

Una lista de enteros no negativos, que representa una secuencia de directivas.

Salida

El número de nodos en el gráfico definido por la secuencia.

Casos de prueba

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

Reglas detalladas

Puede escribir una función o un programa completo. El conteo de bytes más corto gana. Las lagunas estándar no están permitidas. Por favor explique su algoritmo en su respuesta.

Ha pasado una semana, así que he aceptado la respuesta más corta. Si aparece uno aún más corto más tarde, actualizaré mi elección. Una mención de honor va a la respuesta de Peter Taylor , en la que se basaron varios otros, incluido el ganador.

Pyth , 37 31

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

Esta solución utiliza una función de reducción ( u) para construir una lista, donde cada entrada corresponde a un nodo restante en la lista, y el valor de la entrada correspondiente a si el nodo se agregó originalmente bajo la directiva 0 o 1.

Ges la variable acumuladora en la función reducir y contiene la lista mencionada anteriormente. Se inicializa a la lista vacía, Y.

Htoma el valor de cada miembro de Q, la entrada, uno por uno. El resultado de la expresión se asigna a Gcada vez, y Qse asigna la siguiente entrada de H, y la expresión se vuelve a ejecutar.

Para actualizar Gcorrectamente, hay dos posibilidades, una para la directiva 0 o 1, y otra para las otras directivas. Estos casos se distinguen con el ternario.? ... <H2 ...

Si Hes 0 o 1, entonces todo lo que tenemos que hacer es anexados Ha G. +GHlogra esto.

De lo contrario, lo primero que se necesita es determinar, para cada nodo en el gráfico, cuántos vecinos tiene. Esto se logra en dos pasos:

Primero, s>GTcuenta el número de nodos en o después del nodo de entrada que son 1s. Todos estos están conectados al nodo de entrada, excepto que contaremos de más en 1 si el nodo de entrada es un 1.

En segundo lugar, necesitamos el número de nodos anteriores al nodo de entrada que están conectados a él. Esto es 0 si el nodo de entrada es un 0, y el índice del nodo de entrada T, si el nodo de entrada es un 1. Este valor estaría dado por *@GTT. Sin embargo, todavía existe el conteo excesivo de la primera sección que debe corregirse. Por lo tanto, calculamos en su *@GTtTlugar, que es 1 menos si el nodo de entrada es un 1. Estos valores se suman, para dar el número de nodos conectados al nodo de entrada.

% ... Hdará 0 si ese número es divisible por H, y por lo tanto debe eliminarse, y de lo contrario no dará 0.

f ... UGpor lo tanto, dará los índices de la entrada que no deben eliminarse, ya que fes un filtro y 0 es falso.

m@Gd Convierte estos índices en los 0 y 1 de los nodos correspondientes.

Finalmente, una vez que se encuentra la lista resultante de nodos etiquetados como 0 y 1, se calcula su longitud ( l) y se imprime (implícita).

Amplia idea gracias a @PeterTaylor.

GolfScript (53 bytes)

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

Demostración en línea

En realidad, todavía no he jugado al golf, pero he descubierto que no es muy fácil eliminar las variables Hy T, por lo que podría ser un mínimo local.

Toma entrada en stdin en el formato [0 1 2 3]. Deja la salida en stdout.

Sin golf:

])~{
  :^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

Solución basada en el algoritmo de Peter:

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

Expansión del código a seguir.

Solución anterior (61 bytes):

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

Toma información de STDIN como:

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

La salida es el número en STDOUT:

8

algoritmo :

• Mantener una variable incremental Uque almacena la identificación del nodo que se va a agregar.
• Mantenga una lista de la lista en la cual, cada lista es un nodo con una identificación única compuesta por el primer elemento de la lista y los elementos restantes son los identificadores de los nodos conectados.
• En cada iteración (mientras lee las directivas de entrada),
  • Si la directiva es 0, agregue [U]a una lista de la lista
  • Si la directiva es 1, agregue Ua cada lista en la lista de listas y agregue otra lista compuesta por el primer elemento de cada una de las listas de listas yU
  • Para eliminar la directiva, filtro todas las listas de length - 1divisibles por my sigo notando el primer elemento de esas listas. Después de filtrar, elimino toda la identificación eliminada de la lista restante de identificadores.

Expansión de código :

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";

Pruébalo aquí

Pyth, 88 80 75 caracteres

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

He terminado. Quizás alguien más tenga algunos consejos de golf.

Yes la lista de adyacencia del gráfico. Por razones de golf, también mantengo un nodo en esta lista, incluso después de que el nodo se eliminó (de lo contrario, tendría que actualizar todos los índices). Cada nodo se tiene como vecino. La lista Jrealiza un seguimiento de los nodos eliminados.

Muestro los cambios de la lista de adyacencia en la entrada de ejemplo [0,1,0,1,0,1,3]:

entrada 0: Y = [[0]] J = []
entrada 1: Y = [[0,1], [0,1]] 0 J = []
entrada 0: Y = [[0,1], [0,1], [2]] J = []
entrada 1: Y = [[0,1,3], [0,1,3], [2,3], [0,1,2,3]] J = []
entrada 0: Y = [[0,1,3], [0,1,3], [2,3], [0,1,2,3], [4]] J = []
entrada 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 = []
entrada 3: Y = [[3,5], [3,5], [2,3,5], [2,3,5], [4,5], [2,3,4,5]] J = [0,1]

El algoritmo es bastante simple: iterar sobre todas las entradas, si input == 0: agrega un nuevo nodo consigo mismo como vecino, si input == 1: agrega un nuevo nodo con todos los nodos como vecinos (también los eliminados) y agrega este nodo a la lista de adyacencia de todos los nodos, si input> 1: determine los nodos con # vecino-1% input == 0 y agréguelos a J, en cada caso, actualice los vecinos de cada nodo usando J. Al final imprima la longitud de Ymenos la longitud de (el conjunto de) 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))

Uso

Simplemente llame al script y dé como entrada [0,1,0,1,0,1,3]o algún otro caso de prueba.

APL, 71 65 55 caracteres

{⍬≡⍺:≢⍵⋄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,⍵}

El gráfico se representa como una matriz de adyacencia booleana. Las filas / columnas se agregan y eliminan según sea necesario.

Pitón 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)

Cada nodo recibe una identificación única y se registran las identidades vecinas de cada nodo. Cuando la directiva es 0, se agrega una lista de vecinos vacía para el nuevo nodo. Cuando la directiva es 1, los identificadores de todos los nodos existentes se convierten en la lista de vecinos para el nuevo nodo, y todas las demás listas de vecinos se actualizan para incluir el nuevo ID de nodo. Para m> 1, los nodos con listas de vecinos que son múltiplos de m se eliminan de la lista de nodos y de todas las listas de vecinos. Gracias a @Optimizer por detectar un error en una versión anterior.

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

La implementación es sencilla, lee cada símbolo y realiza la acción adecuada.

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

Puede ejecutar desde la línea de comandos como 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}

Esto define una función llamada Gusando la sintaxis stabby-lambda. Use G[[0, 1]]para llamarlo con comandos 0y 1.

La implementación es bastante sencilla: hay una Nodeestructura (llamada Narriba) que contiene referencias a todos los nodos vinculados a través de la lpropiedad. Gcrea nodos según sea necesario y manipula sus enlaces. Una versión legible está disponible aquí .

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=,

Todavía hay mucho por jugar al golf en esto. El algoritmo se basa en hacer un seguimiento de la matriz de adyacencia, pero representar la matriz vacía sin tener que tratarla especialmente me está dando dolores de cabeza.

Pruébalo aquí.

La entrada es una matriz de estilo CJam:

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

Puede usar este arnés de prueba para ejecutar todas las pruebas:

"[]
[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}/

Pitón 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)

Esto probablemente todavía se puede jugar mucho al golf.

Usé un diccionario g para representar el gráfico. Los nodos están etiquetados por números y se asignan al conjunto de nodos adyacentes. Esto significa que cada actualización de un borde debe ejecutarse en sus dos puntos finales.

Los nuevos índices de nodo se crean contando n. Cada vez, creo un nuevo nodo vacío n. Para el comando 0, solo queda. Para el comando 1, está conectado entre sí a través del nodo g[i]^={n};g[n]^={i}; El uso de xor hace que el nodo no esté conectado a sí mismo. Para los comandos> 1, se elimina inmediatamente.

El filtrado de los nodos cuyo grado es un múltiplo se realiza al encontrar primero los nodos que permanecen ( h), y luego andcon la lista de nodos y los vecinos de cada nodo.

Finalmente, el número de entradas en el diccionario gráfico es la respuesta.

Mathematica, 223 bytes

Wow, esto resultó más de lo que esperaba.

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

Uso:

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

Aquí están los resultados de los casos de prueba:

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}

Menos golfizado:

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

La forma en que esto funciona es representando el gráfico como una lista de "listas de vecinos".
Para la directiva 0 , solo agrego una lista vacía.
Para la directiva 1 , agrego una lista de todos los nodos anteriores y agrego el nuevo nodo a todos los nodos anteriores.
Para una directiva > 1 , eliminé los nodos especificados y actualicé el resto.