Nesse desafio, sua tarefa é construir um gráfico não direcionado a partir de uma sequência de diretivas. Há uma diretiva para cada número inteiro não negativo e cada uma transforma um dado gráfico em um novo.

• Diretiva 0: Adicione um novo nó desconectado.
• Diretiva 1: adicione um novo nó e conecte-o a todos os nós existentes.
• Diretiva m > 1: Remova todos os nós cujo grau (número de vizinhos) é divisível por m. Observe que 0é divisível por todos m, portanto os nós desconectados são sempre removidos.

As diretivas são aplicadas uma a uma, da esquerda para a direita, começando com o gráfico vazio. Por exemplo, a sequência [0,1,0,1,0,1,3]é processada da seguinte maneira, explicada usando a incrível arte ASCII. Começamos com o gráfico vazio e adicionamos um único vértice conforme indicado por 0:

a

Em seguida, adicione outro vértice e conecte-o ao primeiro, conforme indicado por 1:

a--b

Adicionamos outro vértice desconectado e depois um conectado, conforme indicado por 0e 1:

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

Repetimos isso mais uma vez, conforme indicado por 0e 1:

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

Finalmente, removemos os vértices de grau 3 ae b, conforme indicado por 3:

f--e
|\
| c
|/
d

Este é o gráfico definido pela sequência [0,1,0,1,0,1,3].

Entrada

Uma lista de números inteiros não negativos, representando uma sequência de diretivas.

Resultado

O número de nós no gráfico definido pela sequência.

Casos de teste

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

Regras detalhadas

Você pode escrever uma função ou um programa completo. A menor contagem de bytes vence. As brechas padrão não são permitidas. Por favor, explique seu algoritmo na sua resposta.

Já faz uma semana, então aceitei a resposta mais curta. Se um mais curto aparecer mais tarde, atualizarei minha escolha. Uma menção honrosa vai para a resposta de Peter Taylor , na qual várias outras foram baseadas, incluindo o vencedor.

Pyth , 37 31

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

Esta solução usa uma função de redução ( u) para criar uma lista, onde cada entrada corresponde a um nó restante na lista e o valor da entrada correspondente a se o nó foi originalmente adicionado sob a diretiva 0 ou 1.

Gé a variável acumuladora na função reduzir e mantém a lista mencionada acima. É inicializado na lista vazia Y,.

Hpega o valor de cada membro da Qentrada, um por um. O resultado da expressão é atribuído a Gcada vez, e a próxima entrada de Qé atribuída a H, e a expressão é executada novamente.

Para atualizar Gcorretamente, existem duas possibilidades, uma para a diretiva 0 ou 1 e uma para as outras diretivas. Estes casos distinguem-se dos ternários? ... <H2 ...

Se Hé 0 ou 1, então tudo o que precisamos fazer é anexar Ha G. +GHrealiza isso.

Caso contrário, a primeira coisa necessária é determinar, para cada nó no gráfico, quantos vizinhos ele possui. Isso é realizado em duas etapas:

Primeiro, s>GTconta o número de nós no ou após o nó de entrada que são 1s. Todos eles estão conectados ao nó de entrada, exceto que contaremos mais de 1 se o nó de entrada for 1.

Segundo, precisamos do número de nós anteriores ao nó de entrada que está conectado a ele. Este é 0 se o nó de entrada for 0 e o índice do nó de entrada T, se o nó de entrada for 1. Este valor seria fornecido por *@GTT. No entanto, ainda existe a contagem excessiva da primeira seção que precisa ser corrigida. Assim, calculamos em *@GTtTvez disso, que é 1 a menos se o nó de entrada for 1. Esses valores são somados, para fornecer o número de nós conectados ao nó de entrada.

% ... Hdará 0 é que o número é divisível por He, portanto, deve ser removido e não dará 0 caso contrário.

f ... UGassim, fornecerá os índices da entrada que não devem ser removidos, pois fé um filtro e 0 é falso.

m@Gd converte esses índices nos 0s e 1s dos nós correspondentes.

Finalmente, uma vez que a lista resultante de nós rotulados 0 e 1 é encontrada, seu comprimento é calculado ( l) e impresso (implícito).

Grande ideia graças a @PeterTaylor.

GolfScript (53 bytes)

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

Demonstração online

Na verdade, ainda não joguei isso, mas descobri que não é muito fácil eliminar as variáveis He T, portanto, isso pode ser o mínimo local.

Recebe entrada no stdin no formato [0 1 2 3]. Deixa a saída em 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

Solução baseada no algoritmo de Peter:

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

Expansão de código a seguir.

Solução anterior (61 bytes):

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

Recebe entradas do 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]

Saída é o número em STDOUT:

8

Algoritmo :

• Mantenha uma variável de incremento Uque armazena o ID do nó a ser adicionado.
• Mantenha uma lista de lista na qual cada lista é um nó com um ID exclusivo composto pelo primeiro elemento da lista e os demais elementos sendo os IDs dos nós conectados.
• Em cada iteração (ao ler as diretivas de entrada),
  • Se a diretiva for 0, adicione [U]a uma lista de lista
  • Se a diretiva for 1, adicione Ua cada lista da lista de listas e adicione outra lista composta pelo primeiro elemento de cada lista da lista eU
  • Para a diretiva remover, eu filtre todas as listas de length - 1divisíveis por me continuo observando o primeiro elemento dessas listas. Após a filtragem, removo todo o ID removido da lista restante de IDs.

Expansão do 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";

Experimente aqui

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

Terminei. Talvez alguém tenha algumas dicas de golfe.

Yé a lista de adjacência do gráfico. Por motivos de golfe, também mantenho um nó nesta lista, mesmo após a exclusão do nó (caso contrário, eu precisaria atualizar todos os índices). Cada nó tem a si próprio como vizinho. A listaJ mantém o controle dos nós excluídos.

Eu mostro as alterações da lista de adjacências na entrada de exemplo [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]

O algoritmo é bastante simples: itere sobre todas as entradas, se entrada == 0: adicione um novo nó consigo mesmo como vizinho, se entrada == 1: adicione um novo nó com todos os nós como vizinhos (também os excluídos) e adicione este nó à lista de adjacência de todos os nós, se entrada> 1: determine os nós com # neighbour-1% input == 0 e inclua-os J, em cada caso, atualize os vizinhos de cada nó usando J. No final, imprima o comprimento de Ymenos o comprimento de (o 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

Basta chamar o script e fornecer como entrada [0,1,0,1,0,1,3]ou algum outro caso de teste.

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,⍵}

O gráfico é representado como uma matriz de adjacência booleana. Linhas / colunas são adicionadas e removidas conforme necessário.

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)

Cada nó recebe um ID exclusivo e os IDs vizinhos de cada nó são registrados. Quando a diretiva é 0, uma lista de vizinhos vazia é adicionada para o novo nó. Quando a diretiva é 1, os IDs de todos os nós existentes se tornam a lista de vizinhos para o novo nó, e todas as outras listas de vizinhos são atualizadas para incluir o novo ID de nó. Para m> 1, os nós com listas de vizinhos que são um múltiplo de m são removidos da lista de nós e de todas as listas de vizinhos. Agradecemos ao @Optimizer por detectar um bug em uma versão 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

A implementação é simples, lendo cada símbolo e executando a ação apropriada.

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

Você pode executar a partir da linha de comando 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}

Isso define uma função chamada Gusando a sintaxe stabby-lambda. Use G[[0, 1]]para chamá-lo com comandos 0e 1.

A implementação é bem direta: existe uma Nodeestrutura (chamada Nacima) que contém referências a todos os nós vinculados por meio da lpropriedade Gcria nós conforme necessário e manipula seus links. Uma versão legível está disponível aqui .

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

Ainda há muito a ser jogado nisso. O algoritmo baseia-se em acompanhar a matriz de adjacência, mas representar a matriz vazia sem precisar tratá-la especialmente está me dando dores de cabeça.

Teste aqui.

A entrada é uma matriz no 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]

Você pode usar este equipamento de teste para executar todos os testes:

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

Provavelmente ainda pode ser muito praticado.

Eu usei um dicionário g para representar o gráfico. Os nós são rotulados por números e são mapeados para o conjunto de nós adjacentes. Isso significa que cada atualização de uma borda precisa ser executada nos dois pontos de extremidade.

Índices de nós novos são criados pela contagem n. Cada vez, eu crio um novo nó vazio n. Para o comando 0, apenas permanece. Para comando 1, ele é conectado um ao outro nó via g[i]^={n};g[n]^={i}; usando xor faça isso para que o nó não esteja conectado a si mesmo. Para comandos> 1, é excluído imediatamente.

A filtragem de nós cujo grau é um múltiplo é feita localizando primeiro os nós que permanecem ( h) e, em seguida, andinserindo-o na lista de nós e nos vizinhos de cada nó.

Finalmente, o número de entradas no dicionário de gráficos é a resposta.

Mathematica, 223 bytes

Uau, isso acabou mais do que eu esperava.

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}

Aqui estão os resultados dos casos de teste:

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 golfe:

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

A maneira como isso funciona é representando o gráfico como uma lista de "listas de vizinhos".
Para a diretiva 0 , apenas anexo uma lista vazia.
Para a diretiva 1 , anexo uma lista de todos os nós anteriores e adiciono o novo nó a todos os nós anteriores.
Para uma diretiva > 1 , removi os nós especificados e atualizei o restante.