W tym wyzwaniu Twoim zadaniem jest zbudowanie niekierowanego wykresu z sekwencji dyrektyw. Istnieje jedna dyrektywa dla każdej nieujemnej liczby całkowitej i każda przekształca dany wykres w nowy.

• Dyrektywa 0: Dodaj nowy odłączony węzeł.
• Dyrektywa 1: Dodaj nowy węzeł i podłącz go do każdego istniejącego węzła.
• Dyrektywa m > 1: Usuń wszystkie węzły, których stopień (liczba sąsiadów) jest podzielny przez m. Zauważ, że 0jest podzielna przez wszystkich m, więc odłączone węzły są zawsze usuwane.

Dyrektywy są stosowane jeden po drugim, od lewej do prawej, zaczynając od pustego wykresu. Na przykład sekwencja [0,1,0,1,0,1,3]jest przetwarzana w następujący sposób, wyjaśniony przy użyciu niesamowitej grafiki ASCII. Zaczynamy od pustego wykresu i dodajemy pojedynczy wierzchołek zgodnie z instrukcjami 0:

a

Następnie dodaj kolejny wierzchołek i połącz go z pierwszym, zgodnie z instrukcjami 1:

a--b

Dodamy kolejny wierzchołek odłączony, a następnie podłączony jeden, zgodnie z zaleceniami 0i 1:

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

Powtarzamy to jeszcze raz, zgodnie z zaleceniami 0i 1:

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

Na koniec usuwamy wierzchołki stopnia-3 ai bzgodnie z instrukcjami 3:

f--e
|\
| c
|/
d

To jest wykres zdefiniowany przez sekwencję [0,1,0,1,0,1,3].

Wejście

Lista nieujemnych liczb całkowitych reprezentujących sekwencję dyrektyw.

Wynik

Liczba węzłów na wykresie określona przez sekwencję.

Przypadki testowe

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

Szczegółowe zasady

Możesz napisać funkcję lub pełny program. Najkrótsza liczba bajtów wygrywa. Standardowe luki są niedozwolone. Proszę wyjaśnić swój algorytm w swojej odpowiedzi.

Minął tydzień, więc zaakceptowałem najkrótszą odpowiedź. Jeśli później pojawi się jeszcze krótszy, zaktualizuję mój wybór. Wyróżnienie należy do odpowiedzi Petera Taylora , na której oparto kilka innych, w tym zwycięzcę.

Pyth , 37 31

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

W tym rozwiązaniu używana jest funkcja zmniejszania ( u) do tworzenia listy, w której każdy wpis odpowiada węzłowi pozostającemu na liście, a wartość wpisu odpowiada temu, czy węzeł został pierwotnie dodany zgodnie z dyrektywą 0 lub 1.

Gjest zmienną akumulatorową w funkcji redukcji i zawiera wyżej wymienioną listę. Jest on inicjowany do pustej listy Y.

Hprzyjmuje wartość każdego elementu Qwejściowego, jeden po drugim. Wynik wyrażenia jest przypisywany Gkażdorazowo, a następny wpis Qjest przypisywany Hi wyrażenie jest ponownie uruchamiane.

Aby Gpoprawnie zaktualizować , istnieją dwie możliwości, jedna dla dyrektywy 0 lub 1 i jedna dla pozostałych dyrektyw. Przypadki te są rozróżniane za pomocą trójskładnika? ... <H2 ...

Jeśli Hma wartość 0 lub 1, to wszystko, co musisz zrobić, to Dołącz Hdo G. +GHosiąga to.

W przeciwnym razie pierwszą rzeczą, którą należy ustalić, jest określenie dla każdego węzła na wykresie liczby sąsiadów. Odbywa się to w dwóch etapach:

Najpierw s>GTzlicza liczbę węzłów w węźle wejściowym lub za nim, które wynoszą 1 s. Wszystkie są podłączone do węzła wejściowego, z tym wyjątkiem, że przeliczy się o 1, jeśli węzeł wejściowy to 1.

Po drugie, potrzebujemy liczby węzłów wcześniej niż węzeł wejściowy, które są z nim połączone. Jest to 0, jeśli węzeł wejściowy to 0, a indeks węzła wejściowego T, jeśli węzeł wejściowy to 1. Ta wartość byłaby podana przez *@GTT. Nadal istnieje jednak przeliczanie z pierwszej sekcji, które należy poprawić. Dlatego *@GTtTzamiast tego obliczamy , czyli o 1 mniej, jeśli węzeł wejściowy to 1. Te wartości są sumowane, aby podać liczbę węzłów podłączonych do węzła wejściowego.

% ... Hda 0 oznacza, że ​​liczba jest podzielna przez H, a zatem powinna zostać usunięta, i nie da 0 w przeciwnym razie.

f ... UGda zatem wskaźniki wejściowe, których nie należy usuwać, ponieważ fjest to filtr, a 0 to fałsz.

m@Gd konwertuje te indeksy na 0 i 1 z odpowiednich węzłów.

Wreszcie, po znalezieniu wynikowej listy węzłów oznaczonych jako 0 i 1, jej długość jest obliczana ( l) i drukowana (niejawna).

Szeroki pomysł dzięki @PeterTaylor.

GolfScript (53 bajty)

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

Demo online

Właściwie to jeszcze nie grałem w golfa, ale odkryłem, że nie jest łatwo wyeliminować zmienne Hi T, więc może to być lokalne minimum.

Pobiera dane wejściowe na standardowe wejście w formacie [0 1 2 3]. Pozostawia wyjście na standardowe wyjście.

Nie golfowany:

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

Rozwiązanie oparte na algorytmie Petera:

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

Rozszerzenie kodu do naśladowania.

Poprzednie rozwiązanie (61 bajtów):

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

Pobiera dane wejściowe ze STDIN, takie jak:

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

Dane wyjściowe to liczba na STDOUT:

8

Algorytm :

• Zachowaj zmienną przyrostową, Uktóra przechowuje identyfikator węzła, który ma zostać dodany.
• Utrzymuj listę, na której każda lista jest węzłem o unikalnym identyfikatorze utworzonym przez pierwszy element listy, a pozostałe elementy są identyfikatorami połączonych węzłów.
• W każdej iteracji (podczas czytania dyrektyw wejściowych)
  • Jeśli dyrektywa jest 0, dodaj [U]do listy
  • Jeśli dyrektywa jest 1, dodaj Udo każdej listy na liście i dodaj kolejną listę składającą się z pierwszego elementu każdej listy iU
  • Aby usunąć dyrektywę, odfiltrowuję wszystkie listy length - 1podzielne przez mi zwracam uwagę na pierwszy element tych list. Po filtrowaniu usuwam cały usunięty identyfikator z pozostałej listy identyfikatorów.

Rozszerzenie kodu :

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

Wypróbuj tutaj

Pyth 88 80 75 znaków

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

Skończyłem. Może ktoś ma jakieś wskazówki dotyczące gry w golfa.

Yjest listą przyległości wykresu. Z powodów golfowych trzymam również węzeł na tej liście, nawet po usunięciu węzła (w przeciwnym razie musiałbym zaktualizować wszystkie indeksy). Każdy węzeł ma siebie jako sąsiada. Lista Jśledzi usunięte węzły.

Pokazuję zmiany listy sąsiedztwa na przykładowym wejściu [0,1,0,1,0,1,3]:

wejście 0: Y = [[0]] J = []
wejście 1: Y = [[0,1], [0,1]] 0 J = []
wejście 0: Y = [[0,1], [0,1], [2]] J = []
wejście 1: Y = [[0,1,3], [0,1,3], [2,3], [0,1,2,3]] J = []
wejście 0: Y = [[0,1,3], [0,1,3], [2,3], [0,1,2,3], [4]] J = []
wkład 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 = []
wejście 3: Y = [[3,5], [3,5], [2,3,5], [2,3,5], [4,5], [2,3,4,5]] J = [0,1]

Algorytm jest wtedy dość prosty: Iteruj po wszystkich danych wejściowych, jeśli dane wejściowe == 0: dodaj nowy węzeł ze sobą jako sąsiadem, jeśli dane wejściowe == 1: dodaj nowy węzeł ze wszystkimi węzłami jako sąsiadami (także usuniętymi) i dodaj ten węzeł do listy sąsiadów wszystkich węzłów, jeśli dane wejściowe> 1: określ węzły za pomocą # sąsiada-1% danych wejściowych == 0 i dodaj je J, w każdym przypadku, zaktualizuj sąsiadów każdego węzła za pomocą J. Na końcu wydrukuj długość Yminus długość (zestawu) 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))

Stosowanie

Wystarczy wywołać skrypt i podać jako dane wejściowe [0,1,0,1,0,1,3]lub inny przypadek testowy.

APL, 71 65 55 znaków

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

Wykres jest reprezentowany jako logiczna macierz przylegania. Wiersze / kolumny są dodawane i usuwane w razie potrzeby.

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)

Każdy węzeł otrzymuje unikalny identyfikator, a identyfikatory sąsiedztwa każdego węzła są rejestrowane. Gdy dyrektywa ma wartość 0, dla nowego węzła dodawana jest pusta lista sąsiadów. Gdy dyrektywa ma wartość 1, identyfikatory wszystkich istniejących węzłów stają się listą sąsiadów dla nowego węzła, a wszystkie inne listy sąsiadów są aktualizowane w celu włączenia nowego identyfikatora węzła. Dla m> 1 węzły z listami sąsiadów, które są wielokrotnością m, są usuwane z listy węzłów i wszystkich list sąsiadów. Dzięki @Optimizer za wykrycie błędu we wcześniejszej wersji.

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

Implementacja jest prosta, odczytując każdy symbol i wykonując odpowiednie działanie.

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

Możesz uruchomić z wiersza poleceń jako f[0 0 1 1 0 0 1 1 2 5 7 0 1].

Ruby 159157 ( wersja 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}

Definiuje funkcję wywoływaną Gza pomocą składni stabby-lambda. Służy G[[0, 1]]do wywoływania go za pomocą poleceń 0i 1.

Implementacja jest dość prosta: istnieje Nodestruktura (nazywana Npowyżej), która zawiera odwołania do wszystkich połączonych węzłów za pośrednictwem lwłaściwości. Gtworzy potrzebne węzły i manipuluje ich łączami. Wersja do odczytu jest dostępna tutaj .

CJam, 99 97 bajtów

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

Jest jeszcze wiele do grania w golfa. Algorytm opiera się na śledzeniu macierzy przylegania, ale reprezentowanie pustej macierzy bez konieczności jej specjalnego traktowania powoduje bóle głowy.

Sprawdź to tutaj.

Dane wejściowe to tablica w stylu 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]

Za pomocą tej uprzęży testowej można uruchomić wszystkie testy:

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

Prawdopodobnie nadal można dużo grać w golfa.

Użyłem słownika gdo przedstawienia wykresu. Węzły są oznaczone liczbami i są odwzorowane na zbiór sąsiednich węzłów. Oznacza to, że każda aktualizacja krawędzi musi zostać wykonana w obu punktach końcowych.

Świeże indeksy węzłów są tworzone przez zliczanie n. Za każdym razem tworzę nowy pusty węzeł n. Na rozkaz 0pozostaje po prostu. Dla polecenia 1jest on połączony ze sobą za pośrednictwem węzła g[i]^={n};g[n]^={i}; przy użyciu xor uczyń go tak, aby węzeł nie był podłączony do siebie. W przypadku poleceń> 1 jest natychmiast usuwany.

Filtrowanie węzłów, których stopień jest wielokrotnością, polega na znalezieniu węzłów, które pozostały ( h), a następnie umieszczeniu andgo na liście węzłów i sąsiadów każdego węzła.

Wreszcie liczba wpisów w słowniku wykresów jest odpowiedzią.

Mathematica, 223 bajty

Wow, okazało się to dłużej niż się spodziewałem.

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

Stosowanie:

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

Oto wyniki z przypadków testowych:

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}

Mniej golfa:

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

Działa to poprzez przedstawienie wykresu jako listy „list sąsiadów”.
Do dyrektywy 0 po prostu dołączam pustą listę.
Do dyrektywy 1 dołączam listę wszystkich poprzednich węzłów i dodam nowy węzeł do wszystkich poprzednich węzłów.
W przypadku dyrektywy > 1 usunąłem określone węzły i zaktualizowałem resztę.