В этой задаче ваша задача состоит в том, чтобы построить неориентированный граф из последовательности директив. Существует одна директива для каждого неотрицательного целого числа, и каждая преобразует данный граф в новый.

• Директива 0: Добавить новый отключенный узел.
• Директива 1: Добавьте новый узел и подключите его к каждому существующему узлу.
• Директива m > 1: Удалите все узлы, чья степень (количество соседей) делится на m. Обратите внимание, что 0это делится на все m, поэтому отключенные узлы всегда удаляются.

Директивы применяются одна за другой слева направо, начиная с пустого графа. Например, последовательность [0,1,0,1,0,1,3]обрабатывается следующим образом, объясненный с использованием удивительной ASCII-графики. Мы начинаем с пустого графа и добавляем одну вершину в соответствии с 0:

a

Затем добавьте еще одну вершину и соедините ее с первой, как указано 1:

a--b

Мы добавляем другую несвязанную вершину, а затем соединенную, как указано 0и 1:

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

Мы повторяем это еще раз, как указано 0и 1:

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

Наконец, мы удаляем вершины степени 3 aи b, как указано 3:

f--e
|\
| c
|/
d

Это график, определенный последовательностью [0,1,0,1,0,1,3].

вход

Список неотрицательных целых чисел, представляющих последовательность директив.

Выход

Количество узлов в графе определяется последовательностью.

Контрольные примеры

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

Подробные правила

Вы можете написать функцию или полную программу. Победит самый короткий счетчик байтов. Стандартные лазейки запрещены. Пожалуйста, объясните свой алгоритм в вашем ответе.

Прошла неделя, поэтому я принял кратчайший ответ. Если позже появится еще более короткий вариант, я обновлю свой выбор. Похвальное упоминание относится к ответу Питера Тейлора , на котором основывалось несколько других, включая победителя.

Пиф , 37 31

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

В этом решении используется функция lower ( u) для создания списка, где каждая запись соответствует узлу, остающемуся в списке, а значение записи соответствует тому, был ли узел первоначально добавлен в соответствии с директивой 0 или 1.

Gявляется переменной-накопителем в функции Reduce и содержит вышеупомянутый список. Инициализируется в пустой список,Y .

Hпринимает значение каждого члена Q, вход, один за другим. Результат выражения присваивается Gкаждому разу, а следующая запись QприсваиваетсяH , и выражение перезапускается.

Обновлять G правильного есть две возможности: одна для директивы 0 или 1, а другая для других директив. Эти дела отличают троичные? ... <H2 ...

Если Hэто 0 или 1, то все , что нам нужно сделать , это Append Hк G. +GHвыполняет это.

В противном случае, первое, что нужно, это определить для каждого узла в графе, сколько у него соседей. Это выполняется в два этапа:

Сначала s>GTподсчитывается количество узлов в или после входного узла, равное 1 с. Все они связаны с входным узлом, за исключением того, что мы будем считать более 1, если входным узлом является 1.

Во-вторых, нам нужно количество узлов, которые раньше, чем входной узел, который подключен к нему. Это 0, если входной узел равен 0, и индекс входного узла T, если входной узел равен 1. Это значение будет задано как *@GTT. Тем не менее, в первом разделе все еще есть перерасчет, который необходимо исправить. Таким образом, *@GTtTвместо этого мы вычисляем , что на 1 меньше, если входной узел равен 1. Эти значения суммируются, чтобы получить количество узлов, подключенных к входному узлу.

% ... Hдаст 0, если число делится на H, и поэтому должно быть удалено, и не даст 0 в противном случае.

f ... UGбудет, таким образом, давать индексы входных данных, которые не должны быть удалены, поскольку fэто фильтр, а 0 - ложь.

m@Gd преобразует эти индексы в 0 и 1 соответствующих узлов.

Наконец, как только найден результирующий список узлов с метками 0 и 1, его длина вычисляется ( l) и печатается (неявно).

Широкая идея благодаря @PeterTaylor.

GolfScript (53 байта)

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

Онлайн демо

На самом деле я еще не играл в гольф, но обнаружил, что устранить переменные Hи Tпеременные не очень легко, так что это может быть локальным минимумом.

Принимает ввод на стандартный ввод в формате [0 1 2 3]. Оставляет вывод на стандартный вывод.

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 байта

Решение на основе алгоритма Питера:

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

Расширение кода, чтобы следовать.

Предыдущее решение (61 байт):

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

Принимает участие от STDIN, как:

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

Вывод числа на STDOUT:

8

Алгоритм :

• Поддерживайте инкрементную переменную, в Uкоторой хранится идентификатор добавляемого узла.
• Вести список списков, в котором каждый список является узлом с уникальным идентификатором, составленным из первого элемента списка, а остальные элементы являются идентификаторами подключенных узлов.
• На каждой итерации (при чтении входных директив)
  • Если директива есть 0, добавьте [U]в список список
  • Если директива есть 1, добавьте Uк каждому списку в списке список и добавьте еще один список, состоящий из первого элемента каждого списка списка иU
  • Чтобы удалить директиву, я отфильтрую все списки, length - 1делимые на, mи продолжаю отмечать первый элемент этих списков. После фильтрации я удаляю все удаленные идентификаторы из оставшегося списка идентификаторов.

Расширение кода :

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

Попробуй здесь

Pyth, 88 80 75 символов

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

Я задолбался. Может быть, у кого-то еще есть советы по игре в гольф.

Yсписок смежности графа По причинам, связанным с игрой в гольф, я также сохраняю узел в этом списке, даже после того, как узел был удален (в противном случае мне пришлось бы обновить все индексы). Каждый узел имеет себя в качестве соседа. Список Jотслеживает удаленные узлы.

Я показываю изменения списка смежности на примере ввода [0,1,0,1,0,1,3]:

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

Алгоритм тогда довольно прост: переберите все входные данные, если input == 0: добавьте новый узел с самим собой в качестве соседа, если input == 1: добавьте новый узел со всеми узлами в качестве соседей (также удаленных) и добавьте этот узел к списку смежности всех узлов, если input> 1: определите узлы с помощью # neighbour-1% input == 0 и добавьте их, чтобы Jв каждом случае обновлять соседей каждого узла, используя J. В конце выведите длину Yминус длина (набор) 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))

использование

Просто вызовите скрипт и передайте в качестве входных данных [0,1,0,1,0,1,3]или другой тестовый пример.

APL, 71 65 55 символов

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

Граф представлен в виде булевой матрицы смежности. Строки / столбцы добавляются и удаляются по мере необходимости.

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)

Каждому узлу присваивается уникальный идентификатор, а идентификаторы соседей каждого узла записываются. Когда директива равна 0, для нового узла добавляется пустой список соседей. Когда директива равна 1, идентификаторы всех существующих узлов становятся списком соседей для нового узла, и все остальные списки соседей обновляются, чтобы включить новый идентификатор узла. При m> 1 узлы со списками соседей, кратными m, удаляются из списка узлов и всех списков соседей. Спасибо @Optimizer за обнаружение ошибки в более ранней версии.

НетЛого, 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

Реализация проста: чтение каждого символа и выполнение соответствующих действий.

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

Вы можете запустить из командной строки как f[0 0 1 1 0 0 1 1 2 5 7 0 1].

Рубин 159 157 ( демо )

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}

Это определяет функцию, вызываемую Gс использованием синтаксиса stabby-lambda. Используйте G[[0, 1]]для вызова с помощью команд 0и 1.

Реализация довольно проста: есть Nodeструктура (называемая Nвыше), которая содержит ссылки на все связанные узлы через lсвойство. Gсоздает узлы по мере необходимости и манипулирует их ссылками. Читаемая версия доступна здесь .

CJam, 99 97 байт

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

В этом еще есть что поиграть в гольф. Алгоритм основан на отслеживании матрицы смежности, но представление пустой матрицы без особого обращения с ней вызывает у меня головную боль.

Проверьте это здесь.

Ввод - это массив в стиле 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]

Вы можете использовать этот тестовый комплект для запуска всех тестов:

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

Это, вероятно, еще можно много играть в гольф.

Я использовал словарь g для представления графика. Узлы помечены номерами, и они отображаются на множество смежных узлов. Это означает, что каждое обновление ребра должно выполняться на обеих его конечных точках.

Свежие индексы узлов создаются путем подсчета n. Каждый раз я создаю новый пустой узел n. Для команды 0это просто остается. По команде 1он подключен друг к другу через узел g[i]^={n};g[n]^={i}; используя xor, сделайте так, чтобы узел не был связан с самим собой. Для команд> 1 он сразу удаляется.

Фильтрация узлов, степень которых кратна, выполняется сначала путем нахождения узлов, которые остаются с ( h), а затем andсо списком узлов и соседей каждого узла.

Наконец, количество записей в графическом словаре является ответом.

Mathematica, 223 байта

Вау, это оказалось дольше, чем я ожидал.

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

Использование:

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

Вот результаты тестовых случаев:

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}

Меньше гольфа:

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

Это работает путем представления графа в виде списка «списков соседей».
Для директивы 0 я просто добавляю пустой список.
Для директивы 1 я добавляю список всех предыдущих узлов и добавляю новый узел ко всем предыдущим узлам.
Для директивы > 1 я удалил указанные узлы и обновил остальные.