Вызов

Получив список целых чисел, верните список этих целых чисел после многократного удаления всех пар смежных равных элементов.

Обратите внимание, что если у вас есть пробег нечетной длины равных чисел, один из них останется, не будучи частью пары.

Пример:

[0, 0, 0, 1, 2, 4, 4, 2, 1, 1, 0]

Во- первых, вы должны удалить 0, 0, 4, 4и 1, 1получить:

[0, 1, 2, 2, 0]

Теперь вы должны удалить 2, 2:

[0, 1, 0]

И это конечный результат.

Тестовые случаи

[] -> []
[1] -> [1]
[1, 1] -> []
[1, 2] -> [1, 2]
[11, 11, 11] -> [11]
[1, 22, 1] -> [1, 22, 1]
[-31, 46, -31, 46] -> [-31, 46, -31, 46]
[1, 0, 0, 1] -> []
[5, 3, 10, 10, 5] -> [5, 3, 5]
[5, 3, 3, 3, 5] -> [5, 3, 5]
[0, -2, 4, 4, -2, 0] -> []
[0, 2, -14, -14, 2, 0, -1] -> [-1]
[0, 0, 0, 1, 2, 4, 4, 2, 1, 1, 0] -> [0, 1, 0]
[3, 5, 4, 4, 8, 26, 26, 8, 5] -> [3]
[-89, 89, -87, -8, 8, 88] -> [-89, 89, -87, -8, 8, 88]

счет

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

Желе , 10 байт

Œgœ^/€FµÐL

Попробуйте онлайн!

Как это работает

Œgœ^/€FµÐL  Main link. Argument: A (array)

       µ    Combine all links to the left into a chain.
Œg              Group all adjacent equal items.
    /€          Reduce each group by...
  œ^                symmetric multiset difference.
                In each step, this maps ([], n) to [n] and ([n], n) to [], so the
                group is left with a single item if its length is odd, and no items
                at all if its length if even.
      F         Flatten the resulting array of singleton and empty arrays.
        ÐL  Apply the chain until the results are no longer unique. Return the last
            unique result.

Сетчатка ,17 15 байт

+m`^(.+)¶\1$¶?

Попробуйте онлайн!

Сохранено 2 байта благодаря Нейлу и Мартину!

Заменяет каждую пару чисел ничем. Этот процесс повторяется до тех пор, пока не будут внесены изменения.

Mathematica 29 байтов

Это многократно удаляет пары равных соседних элементов, a_,a_пока не останется ни одного.

#//.{b___,a_,a_,c___}:>{b,c}&

Python 2 , 57 байт

r=[]
for x in input():r+=x,;r[-2:]*=r[-2:-1]!=[x]
print r

Попробуйте онлайн!

Итеративно создает список вывода, добавляя следующий элемент, а затем обрезая конец, если добавляемый элемент равен предыдущему. Проверка второго по последнему элементу r[-2:-1]!=[x]оказывается неудобной, поскольку возможно, что список имеет длину только 1.

Желе , 15 байт

Œr;ṪḂ$$€x/€FµÐL

Попробуйте онлайн!

объяснение

Œr;ṪḂ$$€x/€FµÐL  Main Link
Œr               Run-length encode
  ;              Concatenate (?)
       €         For each element
   ṪḂ$$          Is the last element odd?
          €      For each element    // Non-breaking alternative
        x/       Reduce by repeating // for run-length decode
           F     Flatten
            µ    (New monadic link)
             ÐL  Repeat until results are no longer unique

-1 байт благодаря милям и исправлено :)

JavaScript (ES6), 54 53 байта

Сохранено 1 байт благодаря @ThePirateBay

f=a=>1/a.find(q=>q==a[++i],i=-2)?f(a,a.splice(i,2)):a

Наивное рекурсивное решение, может быть ненадежным.

Python 2 , 73 байта

Поскольку у меня недостаточно репутации, чтобы комментировать: я просто изменил ответ @officialaimm, чтобы использовать r! = [] Вместо len (r) для сохранения байта. Очень умное решение для вас, @officialaimm!

r=[]                            # create list that will hold final results. A new list is important because it needs to be removable.
for i in input():               
 if r!=[]and r[-1]==i:r.pop()   # Ensure that we have at least 1 char added to the list (r!=[])... or that the last character of our final result isn't the current character being scanned. If that is, well, remove it from the final list because we do not want it anymore
 else:r+=[i]                    # Shorthand for r.append(i). This adds i to the final result
print r

Попробуйте онлайн!

Опять слишком поздно ... почему я еще не сплю?

Python, 60 58 байт

f=lambda a:a and(a[:1]+f(a[1:]))[2*(a[:1]==f(a[1:])[:1]):]

Попробуйте онлайн!

MATL , 7 байт

t"Y'oY"

Для некоторых тестовых случаев, когда результат пуст, программа завершается с ошибкой, но в любом случае выдает правильный (пустой) вывод.

Попробуйте онлайн! Или проверьте контрольные примеры с непустым выводом .

объяснение

t     % Implicit input. Duplicate
"     % For each (i.e. do as many times as input size)
  Y'  %   Run-length encode. Gives array of values and array of run lengths
  o   %   Parity, element-wise. Reduces run-lengths to either 0 or 1
  Y"  %   Run-length decode. Gives array of values appearing 0 or 1 times;
      %   that is, removes pairs of consecutive values
      % Implicit end. Implicit display

Рассмотрим вход

0 0 0 1 2 4 4 2 1 1 0

Каждая итерация удаляет пары последовательных пар. Первая итерация уменьшает массив до

0 1 2 2 0

Два значения 2, которые теперь являются смежными, не были смежными в исходном массиве. Вот почему необходима вторая итерация, которая дает:

0 1 0

Дальнейшие итерации оставят это без изменений. Количество требуемых итераций ограничено сверху входным размером.

Пустой промежуточный результат приводит Y"к ошибке в функции декодирования длин серий ( ) в текущей версии языка; но выходной сигнал пустой по мере необходимости.

Машинный код x86 (32-битный защищенный режим), 36 байт

52
8B 12
8D 44 91 FC
8B F9
8D 71 04
3B F0
77 10
A7
75 F9
83 EF 04
4A
4A
A5
3B F8
75 FB
97
EB E7
58
89 10
C3

Вышеуказанные байты машинного кода определяют функцию, которая принимает массив в качестве входных данных, сворачивает соседние дубликаты на месте и возвращает вызывающей стороне, не возвращая результат. Из этого следует, __fastcallсоглашение о вызовах , передавая два параметра в ECXи EDXрегистрах, соответственно.

Первый параметр ( ECX) - это указатель на первый элемент в массиве 32-разрядных целых чисел (если массив пуст, он может указывать в любом месте памяти). Второй параметр ( EDX) - это указатель на 32-разрядное целое число, которое содержит длину массива.

Функция при необходимости изменяет элементы массива на месте, а также обновляет длину, чтобы указать новую длину свернутого массива. Это немного необычный метод для ввода и возврата вывода, но у вас действительно нет другого выбора в языке ассемблера. Как и в C, массивы фактически представлены в языке как указатель на первый элемент и длину . Единственное, что немного странно, это взять длину по ссылке , но если бы мы этого не сделали, урезать массив было бы невозможно. Код работал бы нормально, но вывод содержал бы мусор, потому что вызывающая сторона не знала бы, где остановить печать элементов из свернутого массива.

Неуправляемая сборка мнемоники:

; void __fastcall CollapseAdjacentDuplicates(int * ptrArray, int * ptrLength);
; ECX = ptrArray              ; ECX = fixed ptr to first element
; EDX = ptrLength
   push  edx                  ; save pointer to the length
   mov   edx, [edx]           ; EDX = actual length of the array
   lea   eax, [ecx+edx*4-4]   ; EAX = fixed ptr to last element 

FindAdjacentPairs:
   mov   edi, ecx             ; EDI = ptr to element A
   lea   esi, [ecx+4]         ; ESI = ptr to element B
FindNext:
   cmp   esi, eax             ; is ptr to element B at end?
   ja    Finished             ; if we've reached the end, we're finished
   cmpsd                      ; compare DWORDs at ESI and EDI, set flags, and increment both by 4
   jne   FindNext             ; keep looping if this is not a pair

; Found an adjacent pair, so remove it from the array.
   sub   edi, 4               ; undo increment of EDI so it points at element A
   dec   edx                  ; decrease length of the array by 2
   dec   edx                  ;  (two 1-byte DECs are shorter than one 3-byte SUB)
RemoveAdjacentPair:
   movsd                      ; move DWORD at ESI to EDI, and increment both by 4
   cmp   edi, eax             ; have we reached the end?
   jne   RemoveAdjacentPair   ; keep going until we've reached the end
   xchg  eax, edi             ; set new end by updating fixed ptr to last element
   jmp   FindAdjacentPairs    ; restart search for adjacent pairs from beginning

Finished:
   pop   eax                  ; retrieve pointer to the length
   mov   [eax], edx           ; update length for caller
   ret

Реализация была вдохновлена моим ответом на C ++ 11 , но тщательно переписана на ассемблере с оптимизацией по размеру. Сборка - намного лучший язык для игры в гольф. :-)

Примечание. Поскольку этот код использует строковые инструкции, он предполагает, что флаг направления сброшен ( DF== 0). Это разумное допущение в большинстве операционных сред, поскольку ABI обычно требует, чтобы DF был четким. Если это не может быть гарантировано, тогда 1-байтовая CLDинструкция ( 0xFC) должна быть вставлена ​​вверху кода.

Он также, как отмечалось, предполагает 32-битный защищенный режим, в частности, «плоскую» модель памяти, где дополнительный сегмент ( ES) совпадает с сегментом данных ( DS).

Пакет, 133 байта

@set s=.
:l
@if "%1"=="%2" (shift/1)else set s=%s% %1
@shift/1
@if not "%1"=="" goto l
@if not "%s:~2%"=="%*" %0%s:~1%
@echo(%*

Я установил s, .потому что Пакет запутывается, если есть только дубликаты. Я также должен использовать, shift/1чтобы я мог %0%s:~1%установить список аргументов для нового массива и цикла.

Желе , 12 байт

ŒgṁLḂ$$€ẎµÐL

Монадическая ссылка, берущая и возвращающая списки чисел.

Попробуйте онлайн! или посмотрите набор тестов

Как?

ŒgṁLḂ$$€ẎµÐL - Link: list
         µÐL - perform the chain to the left until no changes occur:
Œg           -   group runs (yield a list of lists of non-zero-length equal runs)
      $€     -   last two links as a monad for €ach run:
     $       -     last two links as a monad:
   L         -       length (of the run)
    Ḃ        -       modulo 2 (1 if odd, 0 if even)
  ṁ          -     mould (the run) like (1 or 0) (yields a list of length 1 or 0 lists)
        Ẏ    -   tighten (make the list of lists into a single list)

Japt , 34 байта

ó¥ k_l vîò k_l É}Ãc
ó¥ l ¥Ul ?U:ß

Рекурсивно удаляет пары равных чисел, пока их не существует.

Попробуйте онлайн! с -Qфлагом для форматирования выходного массива.

Запустите все тестовые случаи, используя мой WIP CodePen.

05AB1E , 15 байтов

[γʒgÉ}€нÐγ‚€gË#

Попробуйте онлайн!

объяснение

[γʒgÉ}€нÐγ‚€gË#
[               # Start infinite loop
 γ              # Group Array into consecutive equal elements
  ʒgÉ}          # Keep the subarrays with an uneven amount of elements
      €н        # Keep only the first element of each subarray
        Ð       # Triplicate the result on the stack
         γ      # Group the top element into consecutive equal elements
          ‚     # Wrap the top two items of the stack in an array
           €g   # Get the length of each subarray
             Ë# # Break if they are equal
                # Implicit print          

05AB1E , 13 байтов

[DγʒgÉ}€нDŠQ#

Попробуйте онлайн!

Объяснение:

[DγʒgÉ}€нDŠQ# Implicit input
[             Start infinite loop
 D            Duplicate
  γ           Split into chunks of equal elements
   ʒ  }       Filter by
    g           Length
     É          Odd? (0=falsy 1=truthy)
       €      Foreach command
        н     Head
         D    Duplicate
          Š   Push c, a, b
           Q  Equal? (0=falsy 1=truthy)
            # Break if true (i.e. equal to 1)

Haskell , 33 байта

a!(b:c)|a==b=c
a!b=a:b
foldr(!)[]

Попробуйте онлайн!

Python 2 , 74 70 66 байт

• Спасибо @SteamyRoot за 4 байта: r вместо этого len(r)достаточно проверить пустоту списка / стека.
• Спасибо @ovs за 4 байта: лучше, если условие [i]==r[-1:]

Python 2 , 66 байт

r=[]
for i in input():
 if[i]==r[-1:]:r.pop()
 else:r+=[i]
print r

Попробуйте онлайн!

Clojure, 100 байт

#(loop[i % j[]](if(= i j)i(recur(mapcat(fn[p](repeat(mod(count p)2)(last p)))(partition-by + i))i)))

Не уверен, что это максимально короткий вариант.

Баш, 82 байта

cat>b
while cat b>a
perl -pe 's/(\d+) \1( |$)//g' a>b
! diff a b>c
do :
done
cat a

Вероятно, есть выход из всего этого cat, но я этого не знаю.

Шелуха , 10 байт

ωoṁS↑o%2Lg

Попробуйте онлайн!

объяснение

ωoṁS↑o%2Lg
ω           Repeat until fixed point
 o          the following two functions:
         g   a) group adjacent elements
  ṁ          b) map over groups and concatenate:
        L     length of group
     o%2      mod 2
   S↑         take that many elements of group

PHP, 81 байт

    function f(&$a){for($i=count($a);--$i;)$a[$i]-$a[$i-1]||array_splice($a,$i-1,2);}

функция, позвоните по ссылке или попробуйте онлайн .

сбой для пустого ввода; вставить $i&&или $a&&прежде чем --$iисправить.

V , 10 байт

òͨ.«©î±î*

Попробуйте онлайн!

Сжатый Regex: :%s/\(.\+\)\n\1\n*. Необязательный символ новой строки таков, что он работает и в конце файла. Если я предполагаю, что после конца строки есть новая строка, то это будет 8 байт ... но это кажется натяжкой

постоянный ток , 84 78 байт

[L.ly1-dsy0<A]sA[LtLtS.ly1+sy]sP[dStrdStr!=Pz1<O]sO[0syzdsz1<Oly0<Azlz>M]dsMxf

Попробуйте онлайн!

Немного распаковал его, вышел из строя в какой-то попытке разобраться:

• [0syzdsz1<Olydsx0<Alx1+lz>M]dsMxfОсновной макрос Mсбрасывает счетчик yна 0, извлекает количество элементов в стеке, сохраняет его в регистре z, затем запускает макрос, Oесли в стеке есть хотя бы два элемента. После Oзавершения он загружает счетчик yи копирует его в регистр xперед проверкой, чтобы убедиться, что он не yравен нулю (то есть в стеке .есть данные). Если это так, запускается макрос A. Наконец, он проверяет, больше ли исходный размер стека, чем текущий размер стека, и перезапускает себя, если это так. Как только это закончено, это печатает стек с f.
• [dStrdStr!=Pz1<O]sOМакрос Oвременно сохраняет два верхних элемента в стеке t. Затем он сравнивает два верхних элемента и запускает макрос, Pесли они не равны. Наконец, он проверяет, есть ли в стеке хотя бы два элемента, и запускается сам, если так.
• [LtLtS.ly1+sy]sPМакрос Pберет два элемента из стека t, помещает верхний элемент обратно в основной стек и помещает следующий элемент в стек .. Затем он увеличивает счетчик y.
• [L.ly1-dsy0<A]sAМакрос Aберет стек .и превращает его обратно в основной стек. Он делает это, уменьшая счетчик yдо тех пор, пока больше нечего нажимать.

Отредактированный для объяснения, и для гольфа от 6 байтов, поскольку я без необходимости сохранял размер стека.

C ++ 11, 161 байт

#include<vector>
#include<algorithm>
using V=std::vector<int>;void f(V&v){V::iterator i;while((i=std::adjacent_find(v.begin(),v.end()))!=v.end())v.erase(i,i+2);}

Приведенный выше код определяет функцию, fкоторая принимает std::vector<int>ссылку, модифицирует ее для свертывания смежных дубликатов в соответствии со спецификацией, а затем возвращает.

Попробуйте онлайн!

До того, как я проверил количество байтов, я подумал, что это довольно красивый код. Более 150 байтов, однако, не так хорошо! Либо я не очень хорош в гольфе, либо C ++ не очень хороший язык для игры в гольф ...

Ungolfed:

#include <vector>
#include <algorithm>

using V = std::vector<int>;

void f(V& v)
{
   V::iterator i;

   // Use std::adjacent_find to search the entire vector for adjacent duplicate elements.
   // If an adjacent pair is found, this returns an iterator to the first element of the
   // pair so that we can erase it. Otherwise, it returns v.end(), and we stop.
   while ((i=std::adjacent_find(v.begin(), v.end())) != v.end())
   {
        v.erase(i, i+2);   // erase this adjacent pair
   }
}

PHP, 74 байта

function c(&$a){foreach($a as$k=>$v)$a[$k+1]===$v&&array_splice($a,$k,2);}

Функция c вызывается по ссылке, чтобы уменьшить массив. Попробуйте онлайн .

Интересно, что это работает в Php5.6, но не 7.

R , 57 54 байта

l=rle(scan());while(any(x<-!l$l%%2))l=rle(l$v[!x]);l$v

Попробуйте онлайн!

использует кодирование длин серий для удаления пар.

J , 38 байт

;@(<@($~2|#)/.~0+/\@,}.~:}:)^:(0<#)^:_

Попробуйте онлайн!

GNU sed , 19 + 1 = 20 байт

+1 байт за -rфлаг.

:
s/\b(\S+ )\1//g
t

Попробуйте онлайн!

Pyth, 10 байт

Немного опоздал на вечеринку.

ueMf%hT2r8

Тестирование.