У вас есть монета, которая производит 0или 1. Но вы подозреваете, что монета может быть предвзятой , то есть вероятность 0(или 1) не обязательно равна 1/2.

Хорошо известна процедура «преобразования» Необъективное монету в справедливой монеты (т.е. для получения результатов с равной вероятностью), как это было предложено фон Неймана, состоит в следующем. Производить (не перекрывающиеся) блоки двух бросков монет, пока два значения блока не будут различаться; и вывести первое значение в этом блоке (второе значение также подойдет, но для целей этой задачи мы выбираем первое). Интуитивно, 1может быть, более вероятно, чем 0, но 01и 10будет одинаково вероятным.

Например, входные данные 1110...отбрасывают первый блок, а затем производят 1из второго блока ...

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

Соревнование

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

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

правила

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

Формат ввода может быть:

• массив нулей и единиц;
• строка нулей и единиц с необязательным разделителем.

Выходной формат может быть:

• строка нулей и единиц с разделителями или без них;
• массив нулей и единиц;
• строки, содержащие один ноль или единицу, разделенные символом новой строки;
• любой подобный, разумный формат, который подходит вашему языку.

Код гольф. Побеждает несколько байтов.

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

Вход и выход здесь предполагаются как строки.

Input         -->  Output

'1110'        -->  '1'
'11000110'    -->  '01'
'1100011'     -->  '0'
'00'          -->  ''
'1'           -->  ''
''            -->  ''
'1101001'     -->  '0'
'1011101010'  -->  '1111'

Желе, 6 байт

s2Q€Ṗ€

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

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

s2Q€Ṗ€  Main link. Argument: S (string)

s2      Split the string into pairs of characters.
  Q€    Deduplicate each pair.
        This removes the second character iff it is equal to the first.
    Ṗ€  Pop each; remove the last character of each pair/singleton.

Сетчатка , 16 14 байт

(.)\1|(.)?.
$2

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

объяснение

Это довольно просто. Код определяет одну подстановку регулярных выражений, заменяя все (не перекрывающиеся) совпадения (.)\1|(.)?.чем-либо, что захватила вторая группа. Это объединяет три разных случая в один:

(.)\1 --> <empty>

Если две повторяющиеся цифры равны, мы удаляем их из строки (поскольку группа 2 не используется).

(.).  --> $2

В противном случае, если мы можем сопоставить два символа, удалите второй, заменив оба из них на первый. Если это не так, группа ?пропустит:

.     --> <empty>

Это происходит только в том случае, если есть непарный конечный символ, который также удаляется.

Лабиринт , 21 12 байт

"(. :
""*$,@

Редкий пример компактной программы Лабиринт, которая также не имеет никаких операций. В |предыдущей версии это было совершенно ненужным, и удаление его в значительной степени уменьшило размер программы. На самом деле, лаборатория бьет сетчатку!

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

Нижний левый "угол также может быть пробелом, но наличие его там значительно упрощает объяснение.

объяснение

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

• Лабиринт - это двумерный язык на основе стека. Память состоит из основного стека и вспомогательного стека.
• Стеки лабиринта бездонные и заполнены нулями, поэтому выполнение операций с пустым стеком не является ошибкой.
• В каждом соединении, где есть два или более путей для указателя инструкций, вершина основного стека проверяется, чтобы выяснить, куда идти дальше. Отрицательный - поворот налево, ноль - прямой, а положительный поворот направо. Если поворот не удался, указатель пытается повернуть в другом направлении.

Настроить

Программа начинается в верхнем левом углу ", что является запретом. Затем мы выполняем:

(        Decrement a bottom zero to -1. Since -1 is negative we try to turn 
         left at this junction, fail, and turn right instead.
"        No-op junction, turn left
*        Multiply top of stack (-1) with a 0 at bottom of stack, giving 0.
         This makes us go straight ahead at this junction.
$        Bitwise xor (of 0 and 0)

Таким образом, в стеке остается один ноль, что достаточно для пустых целей в Лабиринте.

Чтение ввода и завершения

,читает символ из ввода, возвращая 48 или 49 для 0или 1соответственно, и -1 в EOF. Поскольку это ненулевое значение, в любом случае мы превращаемся в :, который дублирует вершину стека.

Это :тупик, поэтому мы оборачиваемся и выполняем ,еще раз. Теперь , если последний вход был EOF, то повернуть налево и заканчиваться @, иначе мы повернуть направо, со стеком выглядит как [a a b](где a, bявляются два символа).

Интерпретация броска монеты

Если мы не завершили работу, наш следующий шаг - снова выполнить $(побитовый xor). Это дает 0, если входные символы были одинаковыми, 1 в противном случае. Затем мы умножаем aна этот результат, давая либо 0, либо a. Поскольку *это соединение, это значение верхнего стека определяет, что будет дальше.

В случае 0 мы идем прямо и выполняем три "неоперации перед выполнением (декремента. Подобно настройке, это заставляет нас поворачиваться и выполнять "*$, оставляя нас готовыми читать больше символов.

Иначе, в aслучае, мы поворачиваем направо на соединении, так aкак положительно (48 или 49). .выводит символ, оставляя стек пустым, и (уменьшает вершину стека, поворачивая 0 к -1. Еще раз, это заставляет нас повернуть налево, выполняя "*$как в настройке, также оставляя нас готовыми читать больше ввода.

CJam, 10 8 байт

l2/{)-}%

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

объяснение

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

"0"  --> ""
"1"  --> ""
"00" --> ""
"01" --> "0"
"10" --> "1"
"11" --> ""

Это оставляет только цифры, которые мы ищем. Вот как код вычисляет это:

l     e# Read input.
2/    e# Split into pairs. Odd inputs will yield a single-character string at the end.
{     e# Map this block over the pairs...
  )   e#   Pull the last character off the string.
  -   e#   Remove all occurrences of that character from the remainder (which is either
      e#   an empty string to begin with or a single-digit string).
}%

Когда список автоматически печатается в конце программы, пустые строки просто опускаются.

Perl, 19 18 17 байт

Решение @Martin Büttner Retina обеспечило 2-байтовое усиление

Включает +1 для -p

Запустите с вводом на STDIN, например, perl -p fair.pl <<< 11000110

fair.pl:

s/(.)\1|.?\K.//g

Здесь не так много объяснений, поскольку это (косвенный) перевод спецификации:

• (.)\1 Если первые 2 цифры совпадают, отбросьте их
• .\K. В противном случае первые две цифры отличаются. Keep ( \K) первый
• .?\K.За исключением того, что первое не .является обязательным. Это допускает одно совпадение в конце строки, которое затем отбрасывается, поскольку сохраненная часть пуста

Mathematica, 36 38 байт

-2 после кражи функции @ LegionMammal978 для определения, является ли список из 2 элементов {0,1} или {1,0}

#&@@@Select[#~Partition~2,Tr@#==1&]&

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

Гексагония , 23 21 байт

,){,/;(_\/'%<\{)/>~$>

Развернутая:

    , ) { ,
   / ; ( _ \
  / ' % < \ {
 ) / > ~ $ > .
  . . . . . .
   . . . . .
    . . . .

Это завершается с ошибкой, но сообщение об ошибке отправляется на STDERR.

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

Судя по количеству зеркал, было бы почти возможно установить его в длину стороны 3, но мне пока не повезло.

объяснение

Вот обычная диаграмма, созданная с помощью Timwi HexagonyColorer :

Программа использует только три края памяти, обозначенные здесь как A , B и C (диаграмма любезно предоставлена EsotericIDE Тимви ):

Казнь начинается по синему пути. Это /просто зеркала, которые перенаправляют указатель инструкций (IP), фактический код:

,   Read character from STDIN into memory edge A.
)   Increment.
{   Move to memory edge B.
,   Read character from STDIN into memory edge B.
)   Increment.
'   Move to memory edge C.
%   Compute A mod B in memory edge C.

,Установит край , чтобы -1вместо кода символа , если мы попали EOF. Поскольку мы увеличиваем оба входа, они не меняются, равны они или нет, но превращают EOF в 0.

Мы используем по модулю для проверки на равенство, потому что это либо 1или 49(положительно) для неравных символов и 0для равных символов. Это также служит концом программы, потому что, когда у нас есть 0от EOF, попытка деления на ноль вызовет ошибку.

Теперь <отличает нули от положительных результатов. Сначала просто: если символы равны, IP выбирает красный путь. _является зеркалом, \также является зеркалом, но игнорируется и >отклоняет IP, так что он оборачивается по краям и начинается сверху снова. Однако на этой итерации роли A , B и C меняются местами циклически ( теперь C принимает на себя роль A и т. Д.).

Если символы отличаются, вместо этого берется зеленый путь. Это немного грязнее. Сначала он перепрыгивает через no-op с помощью $, затем оборачивается к /левому краю, затем переходит от второй к последней строке справа налево и, наконец, повторно вводит интересную часть исходного кода в {. Это практически линейный фрагмент кода, который я объясню через секунду, прежде $чем IP заставит IP перепрыгнуть через, чтобы >снова объединить два пути.

Вот этот линейный кусок кода:

{    Move to memory edge A.
(    Decrement to recover the actual character we read.
;    Print the character back to STDOUT.
'    Move to memory edge B.
~    Multiply the value there by -1, making it negative. This is
     necessary to ensure that the path correctly wraps back to the top.

Обратите внимание, что в этом случае роли ребер для следующей итерации также меняются местами циклически, но при этом B принимает роль A и так далее.

Haskell, 71 44 29 байт

p(a:b:r)=[a|a/=b]++p r
p _=[]

Экстремальный гольф от Nimi .

> <> , 11 байт

i:i:0(?;-?o

> <> очень хорошо подходит для таких задач, как «читайте за символ» :) Попробуйте онлайн!

i:            Read char and duplicate
i             Read char
:0(?;         Halt if last char was EOF
-             Subtract
?o            Output first char if the subtraction was non-zero (i.e. not equal)

Все это происходит в цикле, так как указатель инструкции оборачивается, как только достигает конца строки.

Python, 42 байта

f=lambda L:L[1:]and L[:L[0]^L[1]]+f(L[2:])

Веселье с рекурсией и побитовым XOR. Принимает список 1 и 0 в качестве ввода.

JavaScript (ES6), 33 байта

s=>s.filter((c,i)=>++i%2&c!=s[i])

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

s=>s                // Take the input array.
.filter((c,i)=>   ) // Filter to only the chars that are both:
++i%2&              //  on an even index, and
c!=s[i]             //  not equal to the one after them.

Прелюдия , 12 байт

11(-(#!)?^?)

Предполагается, что интерпретатор читает и печатает символы. Вы можете попробовать это онлайн. Но этот интерпретатор печатает целые числа, поэтому для каждого 0вы получите 48и для каждого 1вы получите 49вместо этого (и перевод строки).

объяснение

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

11      Push two 1s. We need something non-zero on the stack to enter the loop, and by
        pushing the same value twice, we make sure that the loop doesn't print anything
        on the first iteration.
(       Main loop...
  -       Subtract the last two values. This will be zero for equal values, and non-zero
          otherwise...
  (       This "loop" is simply used as a conditional: if the last two values were
          were equal, skip the code inside...
    #       Discard the conditional.
    !       Print the value below.
  )       The loop is exited because the value below is always zero.
  ?       Read the first character of the next pair from STDIN.
  ^       Duplicate it, so the lower copy can be printed.
  ?       Read the second character of the pair. This returns 0 at EOF, which
          terminates the loop.
)

Perl, 27 21 байт

say grep$_-chop,/../g

Добавлен байт для -nфлага.

                /../g  match groups of two chars
    grep       ,       select/filter on...
           chop        remove the last character, mutating the string
        $_-            is it different than the remaining char?
                         (subtract it, empty string is falsy)
say                    output if so

Тест:

llama@llama:~$ perl -nE 'say grep$_-chop,/../g'
1110
1
11000110
01
1100011
0
00

1



1101001
0
1011101010
1111

Спасибо @TonHospel за 6 байтов!

Befunge 93 , 16 байт

~:~:0`!#@_->#,_$

Однострочник для компактности. Протестировано с использованием этого онлайн-переводчика .

~:                     Read input char a and dup
  ~                    Read input char b (-1 on EOF)
   :0`!                Push 1 if b <= 0, 0 otherwise
       #@_             Halt if b <= 0 (i.e. EOF)
          -            Subtract to check whether a != b
           >#,_$       Output a if so

Последняя часть использует тот факт, что выталкивание из пустого стека Befunge-93 дает 0 .

Если a != bмы выполняем

>                      Move rightward
#                      Bridge: skip next
_                      Horizontal if - go right if 0, else left. But a != b, so we go left
,                      Output a
#                      Bridge: skip next
-                      Subtract (0 - 0 = 0)
_                      If: go right since 0 is popped
>#                     Go right and skip next
_                      If: go right since 0 is popped
$                      Pop top of stack, stack is now empty

В противном случае, если a == bмы выполняем:

>                      Move rightward
#                      Bridge: skip next
_                      If: go right since a == b (i.e. a-b is 0)
$                      Pop top of stack and discard, keeping stack empty

Pyth, 10 9 байтов

jkPM{Mcz2

Алгоритм беззастенчиво украден из желейного ответа Денниса .

       z    input
      c 2   chunks of 2
    {M      dedup each chunk
  PM        all-but-last element of each chunk
jk          join on empty string; can't use `s' because that gives `0' for []

Python 2, 48 байт

lambda n:[s for s,t in zip(*[iter(n)]*2)if s!=t]

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

Спасибо Деннису и Вольте за указание на вещи, которые я пропустил

Mathematica, 41 39 байт

Select[#~Partition~2,Tr@#==1&][[1]]&

Менее сложный и короче, чем другой ответ. Коробка является транспонированным персонажем.

JavaScript (ES6), 33 байта

s=>s.replace(/(.)\1|(.)?./g,"$2")

Скучный порт Retina ответ.

sed, 34 33 байта

s/../& /g;s/00\|11//g;s/.\b\| //g

Тест:

llama@llama:~$ sed 's/../& /g;s/00\|11//g;s/.\b\| //g'             
1110
1
11000110
01
1100011
0
00

1



1101001
0
1011101010
1111

Лабиринт , 31 байт

Не такой короткий и аккуратный, как решение Sp3000, но я подумал, что все равно опубликую это как другой подход:

"" @
,, :{"
)  { $;
*"})";.
 ""

объяснение

Первый цикл просто

""
,,

который читает по два символа за раз ( "без опций). После EOF ,вернется -1, но проверяет только EOF для каждого второго символа. Это означает, что в любом случае вершина стека будет тогда, -1а значение ниже будет -1или каким- либо символьным кодом, который нас не волнует, потому что это бросок непарной монеты.

Затем )*поворачивает -1и значение ниже , в один , 0который нам нужно) , чтобы избавиться от этих двух значений и б) правильно войти в следующий цикл. Этот следующий цикл просто

"}
""

Который сдвигает все значения во вспомогательный стек. Это необходимо, потому что мы хотим начать обработку пар, которые мы читаем первыми. Теперь последний цикл:

:{"
{ $;
)";.

Значение )Just увеличивает некоторое фиктивное значение, чтобы оно было положительным, а указатель инструкции поворачивался на север. {перетаскивает первую цифру следующей пары и :дублирует ее. Теперь, когда мы закончим обработку, это будет 0из нижней части вспомогательного стека. В противном случае это либо 48или 49. В случае нуля мы выходим из цикла и завершаем работу @, в противном случае IP поворачивается на восток.

{останавливает другую цифру текущей пары. $берет XOR между ними. Если это 0, то есть оба равны, IP просто продолжает двигаться на юг, ;сбрасывает ноль, и IP поворачивает на запад в следующей итерации. Если XOR был 1, то есть они отличались, IP поворачивается на запад, сбрасывает 1с ;и печатает первую цифру с ..

MATL , 11 9 8 байт

`-?6MD]T

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

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

`         % do...while loop
  -       %   take two inputs implicitly. Compute difference
  ?       %   if nonzero
    6M    %     push first of the two most recent inputs again
    D     %     display (and remove from stack)
  ]       %   end if
  T       %   true. Used as loop condition, so the loop is infinite
          % end loop implicitly

Старый подход, 11 байтов

2YCd9L)Xz0<

Ввод - это строка. Выходные данные - числа, разделенные символами новой строки.

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

2YC      % implicitly take input as a string. Generate 2D array of length-2
         % overlapping blocks as columns, padding with a zero if needed.
d        % difference of the two values in each column of that array
9L       % predefined literal [1 2 0]. This corresponds to "1:2:end" indexing
)        % keep only values at indices 1, 3, 5, ... This reduces the set of blocks
         % to non-overlapping, and discards the last (padded) block if the input had
         % odd length
Xz       % keep only nonzero entries, corresponding to blocks that had different values
0<       % 1 if negative, 0 if possitive. Implicitly display

Рубин, 46 байт

Это отделяет l[0], l[1]а l[2..{end}]также a, bи c. Затем он создает строку с aif a!=bили ''иным образом, f[c]если if c[0]существует или ''иным образом.

f=->l{a,b,*c=l;"#{a!=b ?a:''}#{c[0]?f[c]:''}"}

Ungolfed:

def f(l)
  a = l[0]
  b = l[1]
  c = l[2..l.length]
  s = ''
  if a!=b
    s += a.to_s
  end
  if c[0]       # equivalent to !c.empty?
    s += f[c]   # no .to_s because the output will be a string
  end
  puts s
end

брейкфук, 33 байта

,>,[<[->->+<<]>[[-]>.<]>[-]<<,>,]

По сравнению с Java это очень компактно, однако, я боюсь, что ответчик брейнфук-гольфист. И не стесняйтесь упоминать, если есть ошибка. Предполагая, что EOF равно 0, вход не содержит недопустимый ввод, ячейка изначально равна нулю, а диапазон значений ячейки является конечным и циклическим. Никаких других предположений нет.

Объяснение:

Карта памяти

+---------+---------+-----------------+
|1st input|2nd input|copy of 1st input|
+---------+---------+-----------------+

инструкция

,>,                               read two instruction at once | first to first cell |
                                  second to second cell
   [                              Until the input is EOF
    <                             look at first cell
     [->->+<<]                    move the first cell to additional cells while
                                  subtracting the second cell with this at same
                                  time
              >[                  if the second cell is nonzero (it means that first cell and
                                  the second cell is the same)
                [-]>.<            Print the copied first input
                      ]
                       >[-]       clear the first input to prevent it polluting next input
                           <<,>,  continue with next two input
                                ]

Mathematica, 41 байт

Cases[#~Partition~2,a_/;Tr@a==1:>a[[1]]]&

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

Pyth, 10 байт

hMf!qFTcz2

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

C 66 байтов

main(char*p,char**x){for(p=x[1];*p&p[1];p+=2)write(1,p,*p^p[1]);}

Если предположить, sizeof(int) == sizeof(char *)

«умное» решение - 84 81 байт

main(int c,short**x){while(!((c=*x[1]++-12336)&~511))c>>8^c&1&&putchar(48|c&1);}

Работает на машине с прямым порядком байтов, предполагая, что shortэто 2 байта. Ввод передается в качестве аргумента. Программа перебирает пары символов и печатает 0 для 0x3130 и 1 для 0x3031. На big-endian результат будет обратным (замените 48|c&1на, 49^c&1чтобы это исправить).

C 57 байт

f(char*p,char*r){for(;*p*p[1];)*r=*p++,r+=*r!=*p++;*r=0;}

Мы предварительно копируем символ из ввода pв результат r, но передвигаем rуказатель только в том случае, если он отличается от следующего символа. Если нет, то мы перезапишем его в следующей непревзойденной паре или NULв конце.

Тестовая программа:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char **argv) {
    while (*++argv) {
        char *result = malloc(1+strlen(*argv));
        f(*argv, result);
        printf("%s => %s\n", *argv, result);
        free(result);
    }
    return EXIT_SUCCESS;
}

Тестовый вывод:

$ ./74864 1110 11000110 1100011 00 1 "" 1101001 1011101010
1110 => 1
11000110 => 01
1100011 => 0
00 => 
1 => 
 => 
1101001 => 0
1011101010 => 1111

Befunge-93 , 40 байт

v  ,-1<
      | -<
>~1+:~1+:|
^     <  @

Вы можете попробовать это здесь . Вставьте код в поле под кнопкой «показать», нажмите «показать», определите ввод, нажмите «запустить». Мы используем кнопку «шаг», чтобы увидеть, как работает программа.

DOS / Windows Batch, 201 162 байта

@echo off
set/pi=
:a
for /f "tokens=2" %%a in ("%i%") do goto l
exit/b
:l
for /f "tokens=1,2" %%a in ("%i:~0,4%") do if %%a neq %%b echo %%a
set "i=%i:~4%"
goto a

Например, ввод - это строка, разделенная пробелом 1 0 0 1 1. Начните с cmd, иначе экран сразу выйдет

пчелиный воск ,45 35 байт

Я мог бы сыграть в гольф на 10 байтов - неплохо.

pgy~1z;L?gAF1<<?V_
>&?@yg&?~@ KQd{b

Я взял чтение полной цепочки бросков монет , что делает программу довольно большой. Простое чтение по одному целых чисел сделало бы программу меньше - может быть, около 22 байт или около того - но также очень неудобно для использования.

Примеры:

julia> beeswax("FairCoin.bswx")
s1110
1
Program finished!

julia> beeswax("FairCoin.bswx")
s11000110
01
Program finished!

julia> beeswax("FairCoin.bswx")
s1100011
0
Program finished!

julia> beeswax("FairCoin.bswx")
s00

Program finished!

julia> beeswax("FairCoin.bswx")
s10101001010111111100000010011001110100010110101110100001011
1110001010000111100
Program finished!

Мой пчелиный воск GitHub хранилище.

Мои примеры пчелиного воска на Розетте.