Tienes una moneda que produce 0
o 1
. Pero sospecha que la moneda puede estar sesgada , lo que significa que la probabilidad de 0
(o 1
) no es necesariamente 1/2.
Un procedimiento bien conocido para "transformar" una moneda sesgada en una moneda justa (es decir, para obtener resultados igualmente probables), como lo propone von Neumann, es el siguiente. Produzca bloques (no superpuestos) de dos lanzamientos de monedas hasta que los dos valores de un bloque difieran; y generar el primer valor en ese bloque (el segundo valor también funcionaría, pero para los propósitos de este desafío, elegimos el primero). Intuitivamente, 1
puede ser más probable que 0
, sin embargo 01
, y 10
será igualmente probable.
Por ejemplo, la entrada 1110...
descartaría el primer bloque, luego produciría un 1
del segundo bloque, ...
Este procedimiento es costoso , porque se consumen varios lanzamientos de monedas para generar un solo resultado.
El reto
Tome una secuencia finita de ceros y unos, que representan lanzamientos de la moneda original, y produzca el número máximo de resultados de acuerdo con el procedimiento anterior, hasta que se consuma toda la entrada.
El último bloque puede estar incompleto, si el número de valores de entrada es impar. Por ejemplo, la secuencia de entrada 11111
no produciría ningún resultado (los dos primeros bloques tienen valores iguales y el tercer bloque está incompleto).
Reglas
La entrada puede tener cualquier número de valores no negativos, no necesariamente positivos o pares.
El formato de entrada puede ser:
- una serie de ceros y unos;
- Una cadena de ceros y unos con un separador opcional.
El formato de salida puede ser:
- una cadena de ceros y unos, con o sin separadores;
- una serie de ceros y unos;
- cadenas que contienen un solo cero o uno, separados por nuevas líneas;
- cualquier formato similar y razonable que se adapte a su idioma.
Código de golf. Pocos bytes ganan.
Casos de prueba
Aquí se supone que la entrada y la salida son cadenas.
Input --> Output
'1110' --> '1'
'11000110' --> '01'
'1100011' --> '0'
'00' --> ''
'1' --> ''
'' --> ''
'1101001' --> '0'
'1011101010' --> '1111'
Respuestas:
Jalea, 6 bytes
Pruébalo en línea!
Cómo funciona
fuente
Retina ,
1614 bytesPruébalo en línea!
Explicación
Esto es bastante simple. El código define una única sustitución de expresiones regulares que reemplaza todas las coincidencias (no superpuestas) de
(.)\1|(.)?.
lo que sea que haya capturado el segundo grupo. Esto combina tres casos diferentes en uno:Si dos dígitos repetidos son iguales, los eliminamos de la cadena (porque el grupo 2 no está en uso).
De lo contrario, si podemos unir dos caracteres, elimine el segundo, reemplazándolos por el primero. Si ese no es el caso
?
, omitirá el grupo:Esto solo sucede si hay un carácter final no emparejado, que también se elimina.
fuente
Laberinto ,
2112 bytesUn raro ejemplo de un programa compacto de Labyrinth que tampoco tiene no-ops.La|
versión anterior era completamente innecesaria, y su eliminación redujo enormemente el tamaño del programa. De hecho, ¡Lab está superando a Retina!Pruébalo en línea!
La esquina inferior izquierda
"
también puede ser un espacio, pero tenerla allí simplifica enormemente la explicación.Explicación
Este es un poco más complicado, por lo que va acompañado de imágenes. Pero primero, una introducción rápida:
Preparar
El programa comienza en la esquina superior izquierda
"
, que no funciona. Luego realizamos:Esto deja a la pila con un solo 0, que es tan bueno como vacío para los propósitos de Labyrinth.
Lectura de entrada y terminación
,
lee un carácter de entrada, devolviendo 48 o 49 para0
o1
respectivamente, y -1 en EOF. Como esto no es cero, de cualquier manera nos convertimos en:
, que duplica la parte superior de la pila.El
:
está en un callejón sin salida, por lo que damos la vuelta y ejecutamos,
una vez más. Ahora bien, si la última entrada fue EOF, a continuación, giramos a la izquierda y terminar con el@
, de lo giramos a la derecha, con la pila que parece[a a b]
(dondea
,b
son los dos caracteres).Interpretando el lanzamiento de la moneda
Si no terminamos, nuestro próximo movimiento es ejecutar
$
(bitor xor) nuevamente. Esto produce 0 si los caracteres de entrada son los mismos, 1 de lo contrario. Luego multiplicamosa
con este resultado, dando 0 oa
. Como*
está en una unión, este valor de la pila superior determina lo que sucede a continuación.En el caso 0, seguimos adelante y ejecutamos tres
"
no-ops, antes de realizar una(
disminución. Al igual que la configuración, esto nos hace girar y ejecutar"*$
, dejándonos listos para leer más caracteres.De lo contrario, en el
a
caso, giramos a la derecha en el cruce ya quea
es positivo (48 o 49)..
genera el carácter, dejando la pila vacía y(
disminuye la parte superior de la pila, convirtiendo un 0 en -1. Una vez más, esto nos hace girar a la izquierda, ejecutar"*$
como en la configuración, y también nos deja listos para leer más entradas.fuente
(
y.
genera char 255 (-1 módulo 256). Así que ya está mal comenzar desde allí, desafortunadamente: PCJam,
108 bytesPruébalo aquí.
Explicación
Esta es una solución muy simple: en cada par, elimine todas las instancias del último carácter. Los dígitos repetidos y los dígitos finales no apareados se eliminarán, al igual que el segundo dígito en cualquier par de dígitos desiguales:
Esto deja solo los dígitos que estamos buscando. Así es como el código calcula esto:
Cuando la lista se imprime automáticamente al final del programa, las cadenas vacías simplemente se omiten.
fuente
Perl,
191817 bytesLa solución Retina @Martin Büttner inspiró una ganancia de 2 bytes
Incluye +1 para
-p
Ejecutar con la entrada en STDIN, p. Ej.
perl -p fair.pl <<< 11000110
fair.pl
:No hay mucho que explicar aquí, ya que es una traducción (indirecta) de la especificación:
(.)\1
Si los primeros 2 dígitos son iguales, suéltelos.\K.
De lo contrario, los dos primeros dígitos son diferentes. Mantener (\K
) el primero.?\K.
Excepto que el primero.
es opcional. Esto permite una sola coincidencia al final de la cadena que luego se descarta ya que la parte guardada está vacíafuente
Mathematica, 36
38bytes-2 después de robar la función de @ LegionMammal978 para determinar si una lista de 2 elementos es {0,1} o {1,0}
Se espera que el argumento sea una lista de enteros.
fuente
Hexagonía ,
2321 bytesDesplegado:
Esto termina con un error, pero el mensaje de error va a STDERR.
Pruébalo en línea!
A juzgar por la cantidad de espejos, podría ser posible encajarlo en la longitud lateral 3, pero hasta ahora no he tenido suerte.
Explicación
Aquí está el diagrama habitual, generado con el HexagonyColorer de Timwi :
El programa utiliza sólo tres bordes de memoria, marcado con A , B , y C aquí (diagrama de cortesía de de Timwi EsotericIDE ):
La ejecución comienza en el camino azul. El
/
son sólo espejos que redirigen el puntero de instrucción (IP), el código real es:El
,
establecerá el borde a-1
en lugar del código de caracteres, si hemos golpeado EOF. Dado que estamos incrementando ambas entradas que no cambian si son iguales o no, pero convierte EOF en0
.Usamos módulo para verificar la igualdad, porque es
1
o49
(positivo) para caracteres desiguales y0
para caracteres iguales. También sirve como el final del programa, porque cuando tenemos el0
de EOF, el intento de división por cero causará un error.Ahora el
<
distingue los ceros de los resultados positivos. El simple primero: si los caracteres son iguales, la IP toma el camino rojo._
es un espejo,\
también es un espejo, pero se ignora y>
desvía la IP de modo que se enrolla en los bordes y comienza desde la parte superior nuevamente. Sin embargo, en esta iteración, los roles de A , B y C se intercambian cíclicamente ( C ahora toma el rol de A y así sucesivamente).Si los caracteres son diferentes, se toma el camino verde en su lugar. Este es un poco más desordenado. Primero salta sobre un no-op con
$
, luego se envuelve hacia el/
borde izquierdo, luego atraviesa la penúltima fila de derecha a izquierda y finalmente vuelve a ingresar la parte interesante del código fuente en el{
. Hay un bit de código esencialmente lineal, que explicaré en un segundo, antes de$
que la IP salte sobre el>
para fusionar las dos rutas nuevamente.Aquí está ese código lineal:
Tenga en cuenta que en este caso, los roles de los bordes para la próxima iteración también se intercambian cíclicamente, pero con B tomando el rol de A y así sucesivamente.
fuente
Haskell,
714429 bytesGolf extremo por nimi .
fuente
> <> , 11 bytes
> <> se adapta bastante bien a desafíos de leer un char-at-a-time como este :) ¡ Pruébelo en línea!
Todo esto sucede en un bucle ya que el puntero de instrucción se ajusta una vez que llega al final de una línea.
fuente
>
o<
Python, 42 bytes
Diversión con recursividad y bitor xor. Toma una lista de 1s y 0s como entrada.
fuente
JavaScript (ES6), 33 bytes
Cómo funciona
fuente
Preludio , 12 bytes
Esto supone un intérprete que lee e imprime caracteres. Puede intentarlo en línea. Pero ese intérprete imprime enteros, así que para cada
0
uno obtendrá48
y para cada1
uno obtendrá en su49
lugar (y un salto de línea).Explicación
Es muy raro que pueda escribir un programa no trivial en una sola línea en Prelude (porque Prelude necesita más de una línea para completar Turing).
fuente
Perl,
2721 bytesByte agregado para la
-n
bandera.Prueba:
¡Gracias a @TonHospel por 6 bytes!
fuente
say grep$_-chop,/../g
Befunge 93 , 16 bytes
Una línea para la compacidad. Probado con este intérprete en línea .
La última parte hace uso del hecho de que saltar de una pila Befunge-93 vacía produce 0 .
Si
a != b
, realizamosDe lo contrario, si
a == b
, realizamos:fuente
Pyth,
109 bytesAlgoritmo robado descaradamente de la respuesta de Dennis's Jelly .
fuente
Python 2, 48 bytes
Pruébalo en línea
Gracias a Dennis y Vaultah por señalar cosas que me perdí
fuente
zip(*[iter(n)]*2)
Mathematica,
4139 bytesMenos complicado y más corto que la otra respuesta. El cuadro es un carácter de transposición.
fuente
JavaScript (ES6), 33 bytes
Aburrido puerto de la Retina respuesta.
fuente
sed,
3433 bytesPrueba:
fuente
fold(1)
comando para dividirme en pares. ¡Eso también salió a los 34!fold -s2|sed 's+01+0+p;s+10+1+p;d'
fold -s2
es equivalente afold -2
, haciendo esos 33 bytes ... que es a lo que acabo de jugar la solución sed pura, también. : Ps/../& /g;s/00\|11\|.\b\| //g
Laberinto , 31 bytes
No es tan corto y ordenado como la solución de Sp3000, pero pensé en publicar esto de todos modos como un enfoque diferente:
Explicación
El primer bucle es simplemente
que se lee en dos caracteres a la vez (el
"
son no-ops). Después de EOF,,
volverá-1
, pero solo verificará si hay EOF en cada segundo personaje. Eso significa que, en cualquier caso, la parte superior de la pila será entonces-1
y el valor a continuación es-1
o algún código de caracteres que no nos importa, porque es un lanzamiento de moneda no emparejado.Luego
)*
convierte el-1
y el valor a continuación en uno solo0
que necesitamos a) para deshacernos de esos dos valores yb) para ingresar el siguiente ciclo correctamente. El siguiente ciclo es simplementeLo que desplaza todos los valores a la pila auxiliar. Esto es necesario porque queremos comenzar a procesar los pares que leemos primero. Ahora el bucle final:
El
)
solo incrementa un valor ficticio para asegurar que sea positivo y el puntero de instrucción gire hacia el norte.{
detiene el primer dígito del siguiente par y lo:
duplica. Ahora, cuando terminemos de procesar, esto habrá sido un0
desde la parte inferior de la pila auxiliar. De lo contrario, es48
o49
. En caso de cero, salimos del bucle y terminamos@
, de lo contrario, la IP gira hacia el este.{
detiene el otro dígito del par actual.$
toma el XOR entre ellos. Si eso es 0, es decir, los dos son iguales, la IP simplemente continúa moviéndose hacia el sur,;
descarta el cero y la IP gira hacia el oeste en la siguiente iteración. Si el XOR era1
, es decir, eran diferentes, la IP gira hacia el oeste, descarta el1
con;
e imprime el primer dígito con.
.fuente
MATL ,
1198 bytesEntrada y salida son números separados por nuevas líneas. Finaliza con un error (permitido de manera predeterminada) cuando se han consumido todas las entradas.
Pruébalo en línea!
Enfoque antiguo, 11 bytes
La entrada es una cadena. La salida es números separados por nuevas líneas.
Pruébalo en línea!
fuente
Ruby, 46 bytes
Esto separa
l[0]
,l[1]
yl[2..{end}]
comoa
,b
yc
. Luego crea una cadena cona
sia!=b
o de lo''
contrario yf[c]
sic[0]
existe o de lo''
contrario.Sin golf:
fuente
brainfuck, 33 bytes
En comparación con Java, esto es muy compacto, sin embargo, me temo que responda al golfista mental. Y siéntase libre de mencionar si hay un error. Suponiendo que EOF es 0, la entrada no contiene una entrada no válida, la celda es inicialmente cero y el rango de valores de la celda es finito y cíclico. Ninguna otra suposición está presente.
Explicación:
Mapa de celdas de memoria
Instrucción
fuente
Mathematica, 41 bytes
Función anónima que ingresa y emite listas de ceros y unos.
fuente
#&@@a
es 1 byte más corto quea[[1]]
.RuleDelayed
.Transpose
:(Pyth, 10 bytes
Banco de pruebas
fuente
!q
porn
y luego el filtrofnFT
pornF#
. (hMnF#cz2
; esto fue lo que pensé cuando vi el desafío, pero el tuyo está lo suficientemente cerca para que no lo publique por separado)1
C, 66 bytes
Asumiendo
sizeof(int) == sizeof(char *)
solución "inteligente" -
8481 bytesFunciona en máquinas little-endian suponiendo que
short
sea de 2 bytes. La entrada se pasa como argumento. El programa itera sobre pares de caracteres e imprime 0 para 0x3130 y 1 para 0x3031. En big-endian, el resultado se invertirá (reemplace48|c&1
con49^c&1
para arreglar esto).fuente
C, 57 bytes
Copiamos tentativamente un carácter de la entrada
p
al resultador
, pero solo avanzamos elr
puntero si difiere del siguiente carácter. De lo contrario, lo sobrescribiremos en el siguiente par no coincidente, o conNUL
al final.Programa de prueba:
Prueba de salida:
fuente
Befunge-93 , 40 bytes
Puedes probarlo aquí . Pegue el código en el espacio debajo del botón "mostrar", presione "mostrar", defina la entrada, presione "ejecutar". Usamos el botón "paso" para ver cómo funciona el programa.
fuente
Lote DOS / Windows,
201162 bytesLa entrada es una cadena separada por espacios, por ejemplo
1 0 0 1 1
. Comience desde cmd, de lo contrario la pantalla se cerrará inmediatamentefuente
cera de abejas ,
4535 bytesPodría jugar golf por 10 bytes, no está mal.
Tomé la lectura como un enfoque completo de lanzamiento de monedas , lo que hace que el programa sea bastante grande. Solo leer enteros individuales uno por uno haría que el programa fuera más pequeño, tal vez alrededor de 22 bytes más o menos, pero también sería muy inconveniente de usar.
Ejemplos:
Mi repositorio GitHub de cera de abejas.
Mis ejemplos de cera de abejas en el código de Rosetta.
fuente