Você tem uma moeda que produz 0ou 1. Mas você suspeita que a moeda possa estar enviesada , o que significa que a probabilidade de 0(ou 1) não é necessariamente 1/2.

Um procedimento bem conhecido para "transformar" uma moeda tendenciosa em uma moeda justa (ou seja, para obter resultados igualmente prováveis), como proposto por von Neumann, é o seguinte. Produza blocos (sem sobreposição) de dois lançamentos de moedas até que os dois valores de um bloco sejam diferentes; e gera o primeiro valor nesse bloco (o segundo valor também funcionaria, mas, para os propósitos desse desafio, escolhemos o primeiro). Intuitivamente, 1pode ser mais provável que 0, mas 01e 10será igualmente provável.

Por exemplo, a entrada 1110...descartaria o primeiro bloco e produziria um a 1partir do segundo bloco, ...

Esse procedimento é caro , porque vários sorteios são consumidos para gerar um único resultado.

O desafio

Pegue uma sequência finita de zeros e uns, representando lançamentos da moeda original, e produza o número máximo de resultados de acordo com o procedimento acima, até que toda a entrada seja consumida.

O último bloco pode estar incompleto, se o número de valores de entrada for ímpar. Por exemplo, a sequência de entrada 11111não produziria resultado (os dois primeiros blocos têm valores iguais e o terceiro bloco está incompleto).

Regras

A entrada pode ter qualquer número não negativo de valores, não necessariamente positivo ou uniforme.

O formato de entrada pode ser:

• uma matriz de zeros e uns;
• uma sequência de zeros e outros com um separador opcional.

O formato de saída pode ser:

• uma sequência de zeros e uns, com ou sem separadores;
• uma matriz de zeros e uns;
• strings contendo um único zero ou um, separados por novas linhas;
• qualquer formato semelhante e razoável que seja adequado ao seu idioma.

Código de golfe. Menos bytes ganha.

Casos de teste

Entrada e saída são aqui consideradas como seqüências de caracteres.

Input         -->  Output

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

Gelatina, 6 bytes

s2Q€Ṗ€

Experimente online!

Como funciona

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.

Retina , 16 14 bytes

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

Experimente online!

Explicação

Isto é bastante simples. O código define uma única substituição de regex substituindo todas as correspondências (sem sobreposição) de (.)\1|(.)?.qualquer que seja o segundo grupo capturado. Isso combina três casos diferentes em um:

(.)\1 --> <empty>

Se dois dígitos repetidos forem iguais, removemos-os da string (porque o grupo 2 não é utilizado).

(.).  --> $2

Caso contrário, se conseguirmos corresponder dois caracteres, remova o segundo, substituindo os dois pelo primeiro. Se não for esse o caso ?, o grupo será omitido:

.     --> <empty>

Isso só acontece se houver um caractere final não emparelhado, que também será removido.

Labirinto , 21 12 bytes

"(. :
""*$,@

Um exemplo raro de um programa compacto de labirinto que também não possui opcionais. A |versão anterior era completamente desnecessária, e a remoção maciça reduziu o tamanho do programa. De fato, o laboratório está superando a Retina!

Experimente online!

O canto inferior esquerdo "também pode ser um espaço, mas tê-lo lá simplifica bastante a explicação.

Explicação

Este é um pouco mais complicado, por isso é acompanhado por imagens. Mas primeiro, uma cartilha rápida:

• Labirinto é uma linguagem 2D baseada em pilha. A memória consiste em uma pilha principal e uma pilha auxiliar.
• As pilhas do labirinto são sem fundo e preenchidas com zeros, portanto, executar operações em uma pilha vazia não é um erro.
• Em cada junção, onde há dois ou mais caminhos para o ponteiro de instrução seguir, a parte superior da pilha principal é verificada para descobrir para onde seguir. Negativo é virar à esquerda, zero é reto e positivo é virar à direita. Se uma curva falhar, o ponteiro tenta girar na outra direção.

Configuração

O programa inicia no canto superior esquerdo ", o que é um no-op. Então nós executamos:

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

Isso deixa a pilha com um único 0, que é tão bom quanto vazio para os propósitos do Labirinto.

Leitura de entrada e finalização

,lê um char da entrada, retornando 48 ou 49 para 0ou 1respectivamente, e -1 no EOF. Como esse número é diferente de zero, de qualquer maneira nos tornamos o: , o que duplica o topo da pilha.

O processo :está em um beco sem saída, então nos voltamos e executamos ,mais uma vez. Agora, se a última entrada foi EOF, então vire à esquerda e terminar com @, senão viramos à direita, com a pilha parecendo [a a b](onde a, bsão os dois caracteres).

Interpretando o sorteio

Se não terminamos, nosso próximo passo é executar $(bit a bit xor) novamente. Isso gera 0 se os caracteres de entrada forem iguais, 1 caso contrário. Em seguida, multiplicamos aesse resultado, fornecendo 0 ou a. Desde o* está em uma junção, esse valor da pilha superior determina o que acontece a seguir.

No caso 0, seguimos em frente e executamos três "no-ops, antes de executar um (decremento. Como na configuração, isso nos faz girar e executar "*$, deixando-nos prontos para ler mais caracteres.

Caso contrário, no acaso, vire à direita no cruzamento, pois aé positivo (48 ou 49). .gera o caractere, deixando a pilha vazia e (diminui o topo da pilha, transformando um 0 em -1. Mais uma vez, isso nos faz virar à esquerda, executando "*$como na configuração, também nos deixando prontos para ler mais informações.

CJam, 10 8 bytes

l2/{)-}%

Teste aqui.

Explicação

Esta é uma solução muito simples: em cada par, remova todas as instâncias do último caractere. Os dígitos repetidos e os dígitos finais não emparelhados serão removidos, assim como o segundo dígito em qualquer par de dígitos desiguais:

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

Isso deixa apenas os dígitos que estamos procurando. Aqui está como o código calcula isso:

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).
}%

Quando a lista é impressa automaticamente no final do programa, as cadeias vazias são simplesmente omitidas.

Perl, 19 18 17 bytes

A solução @Martin Büttner Retina inspirou um ganho de 2 bytes

Inclui +1 para -p

Corra com a entrada no STDIN, por exemplo perl -p fair.pl <<< 11000110

fair.pl:

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

Não há muito a explicar aqui, pois é uma tradução (indireta) da especificação:

• (.)\1 Se os 2 primeiros dígitos forem iguais, solte-os
• .\K. Caso contrário, os dois primeiros dígitos são diferentes. Mantenha ( \K) o primeiro
• .?\K.Exceto que o primeiro .é opcional. Isso permite uma única correspondência no final da string, que é descartada, pois a parte mantida está vazia

Mathematica, 36 38 bytes

-2 após roubar a função de @ LegionMammal978 para determinar se uma lista de 2 elementos é {0,1} ou {1,0}

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

Espera-se que o argumento seja uma lista de números inteiros.

Hexagonia , 23 21 bytes

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

Desdobrado:

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

Isso termina com um erro, mas a mensagem de erro vai para STDERR.

Experimente online!

A julgar pelo número de espelhos, pode ser possível encaixá-lo no comprimento lateral 3, mas até agora não tive sorte.

Explicação

Aqui está o diagrama usual, gerado com o HexagonyColorer de Timwi :

O programa usa apenas três bordas da memória, rotuladas como A , B e C aqui (diagrama cortesia do EsotericIDE de Timwi ):

A execução começa no caminho azul. O /são apenas espelhos que redirecionam o ponteiro de instrução (IP), o código real é:

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

O ,definirá a borda para, em -1vez do código de caractere, se clicarmos em EOF. Como estamos incrementando as duas entradas, isso não muda se são iguais ou não, mas transforma o EOF em 0.

Usamos o módulo para verificar a igualdade, porque é 1 ou 49(positivo) para caracteres desiguais e 0para caracteres iguais. Também serve como o final do programa, porque quando temos o 0EOF, a tentativa de divisão por zero causará um erro.

Agora o <distingue zeros dos resultados positivos. O mais simples primeiro: se os caracteres forem iguais, o IP seguirá o caminho vermelho. _é um espelho, \também é um espelho, mas é ignorado e >desvia o IP de forma que ele se enrole nas bordas e recomeça a partir do topo. No entanto, nessa iteração, as funções de A , B e C são trocadas ciclicamente ( C agora assume o papel de A e assim por diante).

Se os caracteres forem diferentes, o caminho verde será seguido. Este é um pouco mais confuso. Primeiro, ele pula um no-op com $, depois passa para a /borda esquerda, depois atravessa a penúltima linha da direita para a esquerda e finalmente entra novamente na parte interessante do código-fonte no {. Existe um código essencialmente linear, que explicarei em um segundo, antes $que o IP salte sobre o >para mesclar os dois caminhos novamente.

Aqui está esse trecho de código linear:

{    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.

Observe que, nesse caso, as funções das arestas para a próxima iteração também são trocadas ciclicamente, mas com B assumindo a função de A e assim por diante.

Haskell, 71 44 29 bytes

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

Golfe extremo por nimi .

> <> , 11 bytes

i:i:0(?;-?o

> <> é bastante adequado para desafios de ler um caractere de cada vez :) Experimente online!

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)

Isso tudo acontece em um loop, já que o ponteiro da instrução é contornado quando chega ao final de uma linha.

Python, 42 bytes

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

Diversão com recursão e xor bit a bit. Toma uma lista de 1s e 0s como entrada.

JavaScript (ES6), 33 bytes

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

Como funciona

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.

Prelúdio , 12 bytes

11(-(#!)?^?)

Isso pressupõe um intérprete que lê e imprime caracteres. Você pode tentar online. Mas esse intérprete imprime números inteiros, portanto, para cada0 que você obtém 48e para cada 1um49 (em vez de um avanço de linha).

Explicação

É muito raro você poder escrever um programa não trivial em uma única linha no Prelude (porque o Prelude precisa de mais de uma linha para ter a conclusão de Turing).

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 bytes

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

Byte adicionado para o -nsinalizador.

                /../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

Teste:

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

1



1101001
0
1011101010
1111

Obrigado a @TonHospel por 6 bytes!

Entre 93 , 16 bytes

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

Uma linha para compacidade. Testado usando este intérprete online .

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

A última parte faz uso do fato de que pular de uma pilha vazia do Befunge-93 gera 0 .

Se a != b, realizamos

>                      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

Caso contrário, se a == bexecutarmos:

>                      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

Pitão, 10 9 bytes

jkPM{Mcz2

Algoritmo descaradamente roubado da resposta de Dennis's Jelly .

       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 bytes

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

Experimente online

Obrigado a Dennis e vaultah por apontar coisas que eu perdi

Mathematica, 41 39 bytes

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

Menos complicado e mais curto que a outra resposta. A caixa é um caractere de transposição.

JavaScript (ES6), 33 bytes

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

Porta chata da resposta da Retina.

sed, 34 33 bytes

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

Teste:

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

1



1101001
0
1011101010
1111

Labirinto , 31 bytes

Não tão curto e arrumado quanto a solução do Sp3000, mas pensei em publicar isso de qualquer maneira como uma abordagem diferente:

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

Explicação

O primeiro loop é simplesmente

""
,,

que lê dois caracteres de cada vez ( "não há operações). Após o EOF, ,retornará -1, mas verifique apenas o EOF a cada segundo caractere. Isso significa que, em qualquer caso, o topo da pilha será -1e o valor abaixo será-1 código de caractere com o qual não nos importamos, porque é um lançamento de moeda não emparelhado.

Então )* transforma o -1valor abaixo em um único, do 0qual precisamos: a) livrar-se desses dois valores eb) para inserir o próximo loop corretamente. Esse próximo loop é simplesmente

"}
""

Que muda todos os valores para a pilha auxiliar. Isso é necessário porque queremos começar a processar os pares que lemos primeiro. Agora, o loop final:

:{"
{ $;
)";.

O )apenas incrementa algum valor fictício para garantir que seja positivo e o ponteiro da instrução vire para o norte. {puxa o primeiro dígito do próximo par e: duplica. Agora, quando terminarmos o processamento, isso terá ocorrido 0na parte inferior da pilha auxiliar. Caso contrário, é 48ou 49. No caso de um zero, saímos do loop e terminamos @, caso contrário, o IP vira para o leste.

{encosta o outro dígito do par atual. $leva o XOR entre eles. Se for 0, ou seja, os dois forem iguais, o IP continuará se movendo para o sul, ;descarta o zero e o IP se transforma em oeste na próxima iteração. Se o XOR era 1, ou seja, era diferente, o IP vira para oeste, descarta o 1com ;e imprime o primeiro dígito com ..

MATL , 11 9 8 bytes

`-?6MD]T

Entrada e saída são números separados por novas linhas. Termina com um erro (permitido por padrão) quando todas as entradas foram consumidas.

Experimente online!

`         % 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

Abordagem antiga, 11 bytes

2YCd9L)Xz0<

Entrada é uma sequência. Saída são números separados por novas linhas.

Experimente online!

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

Ruby, 46 bytes

Isso separa l[0], l[1]e l[2..{end}]como a, be c. Em seguida, ele cria uma sequência com aif a!=bou ''não e f[c]se c[0]existe ou ''não.

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

brainfuck, 33 bytes

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

Comparado ao Java, isso é muito compacto, no entanto, eu tenho medo de responder a um jogador que gosta de cérebro. E fique à vontade para mencionar se há algum erro. Supondo que EOF seja 0, a entrada não contém entrada inválida, a célula é inicialmente zero e o intervalo de valores da célula é finito e cíclico. Nenhuma outra suposição está presente.

Explicação:

Mapa da célula de memória

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

Instrução

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

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

Função anônima que insere e gera listas de zeros e uns.

Pitão, 10 bytes

hMf!qFTcz2

Suíte de teste

C, 66 bytes

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

Assumindo sizeof(int) == sizeof(char *)

solução "inteligente" - 84 81 bytes

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

Funciona em máquinas little-endian, assumindo que shortsão 2 bytes. A entrada é passada como argumento. O programa itera sobre pares de caracteres e imprime 0 para 0x3130 e 1 para 0x3031. No big endian, o resultado será revertido (substitua 48|c&1por 49^c&1para corrigir isso).

C, 57 bytes

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

Tentativamente, copiamos um caractere da entrada ppara o resultado r, mas somente avançamos o rponteiro se ele diferir do próximo caractere. Caso contrário, substituí-lo-emos no próximo par não correspondido ou comNUL no final.

Programa de teste:

#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;
}

Saída de teste:

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

Befunge-93 , 40 bytes

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

Você pode tentar aqui . Cole o código no espaço abaixo do botão "show", pressione "show", defina a entrada, pressione "run". Nós usamos o botão "step" para ver como o programa funciona.

Lote DOS / Windows, 201 162 bytes

@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

Entrada é uma sequência separada por espaço, por exemplo 1 0 0 1 1. Comece pelo cmd, caso contrário, a tela sai imediatamente

cera de abelha ,45 35 bytes

Eu poderia dar um golpe de 10 bytes - nada mal.

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

Adotei a leitura de uma abordagem completa de lançamentos de moedas , o que torna o programa bastante grande. A simples leitura de números inteiros um a um tornaria o programa menor - talvez cerca de 22 bytes -, mas também seria muito inconveniente de usar.

Exemplos:

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!

Meu repositório GitHub de cera de abelha.

Meus exemplos de cera de abelha no Código Rosetta.