Tarea

Codifique una cadena que consista completamente en alfabetos en mayúscula ( A-Z) usando solo ceros y unos, usando su propio esquema favorito. ¡Pero la regla no es tan simple!

Reglas

1. Su programa / función debe manejar correctamente cualquier cadena de entrada válida de longitud 8 .
2. Los resultados deben tener la misma longitud para todas las entradas.
3. Los resultados deben ser distintos para entradas distintas.
4. Los resultados deben ser lo más cortos posible.
5. Los resultados deben ser cero-uno equilibrado (tener un número similar a los de ceros). No tienen que ser iguales (es decir, perfectamente equilibrados), pero su puntaje será penalizado por eso.

No tiene que proporcionar un programa / función que decodifique su codificación.

Entrada y salida

• Puede decidir aceptar cualquier conjunto de 26 caracteres ASCII imprimibles distintos en lugar de A-Z.
• Puede decidir generar cualquier par de caracteres ASCII imprimibles distintos en lugar de 0y 1.
• No puede generar un número entero en lugar de una cadena de bits, ya que puede tener ceros a la izquierda y no está claro si realmente cumplió con la regla 2.
• Si decide desviarse del valor predeterminado ( A-Zentrada y 01salida), debe especificar los conjuntos de caracteres de entrada / salida en su envío.

Puntuación

• Puntaje base: tamaño del código, o 1 si su programa está vacío.
• Sanciones
  • Penalidad por longitud: multiplicar 1.5 ** (encoded length - 42)
  • No hay bonificación por ser más bajo; 42 es la longitud mínima para una codificación perfectamente equilibrada de cadenas de 8 longitudes con un tamaño de alfabeto 26.
  • Penalización por estar desequilibrado: multiplica 2 ** max(abs(ones - zeros) for every valid input of length 8), donde onesy zerosson los recuentos de 1 y 0 en cada salida, respectivamente.
  • Su envío debe mostrar el peor de los casos (entrada / salida) o una explicación teórica sobre el valor de la penalización.
• El puntaje más bajo gana.

Presentación de ejemplo

Esolang hipotético, 0 bytes, puntuación 74733.8906

Aquí hay un hipotético esolang, donde un programa vacío imprime todos los códigos ASCII de los caracteres de entrada en binario.

Por ejemplo, si da AAAAAAAAcomo entrada, el programa imprimirá 10000018 veces seguidas, es decir 10000011000001100000110000011000001100000110000011000001.

El alfabeto de entrada se elige para ser CEFGIJKLMNQRSTUVXYZabcdefh. De esta manera, todos los caracteres se convierten a siete dígitos en binario, y los recuentos de cero uno difieren solo en uno por carácter (todos tienen tres 1 y cuatro 0 o viceversa cuando se convierten en binario).

La longitud de salida siempre es 56, y el desequilibrio en el peor de los casos ocurre en las entradas como CCCCCCCC, donde los ceros aparecen 8 veces más que unos.

Por lo tanto, el puntaje de esta presentación es 1.5 ** (56 - 42) * 2 ** 8 == 74733.8906.

Stax , 11 bytes, 0 penalización, Puntuación 11

Este programa utiliza [0-9A-P]para entrada y [01]salida.

ö■▄←·ï↨≡⌐╠H

Ejecútelo y depúrelo en línea : haga clic en el botón Ejecutar para comenzar. Los primeros cuatro casos de prueba se ejecutan en milisegundos. El quinto en segundos. El sexto en milenios.

La representación ascii correspondiente de este programa es la siguiente.

A$21*,26|bD|N

Se apoya fuertemente en las |Ninstrucciones, que obtienen la permutación posterior de una matriz.

A$21*           "10" repeated 21 times
     ,26|b      get input and decode it as a base 26 number
          D|N    ... that many times get the next lexicographic permutation

Todas las salidas son permutaciones de la cadena inicial. Tiene 21 ceros y 21 unos. Por lo tanto, todas las salidas tienen 42 caracteres y están perfectamente equilibradas.

Jalea , 19 bytes

O_65ḅ26ị2Ḷ¤x21¤Œ!Q¤

Pruébalo en línea!

Explicación

O_65ḅ26ị2Ḷ¤x21¤Œ!Q¤  Main Link
O                    Take the character code of each character
 _65                 Subtract 65 (the code of "A")
    ḅ26              Convert to base 26
       ị             Get the <left-arg>th element of:
        2Ḷ¤x21¤Œ!Q¤  All balanced strings of length 42:
        2Ḷ           range(2) == [0, 1]
           x21       stretch 21 ([0, 0, ..., 0, 1, 1, ..., 1])
               Œ!    all permutations
                 Q   deduplicate

Pyth, 20 19 14 bytes, Diferencia máxima: 0, Longitud: 64, Puntuación: 149636.5528 142154.7251 104745.5869

sm@S.{.p*`T4xG

Pruébalo en línea!

Utiliza el alfabeto en minúsculas ( [a-z]) en lugar de mayúsculas. Puede usar mayúsculas reemplazando Gpor rG1, a un costo de 2 bytes.

Podría haber traducido la respuesta Python 3 de HyperNeutrino para obtener una mejor puntuación, pero, francamente, quiero una respuesta que realmente funcione.

Python 2 , 779 645 bytes, Máx. (Dif.) = 0, Longitud = 48, Puntuación = 7346.95

def f(s):
 a,b=0,""
 for i in s:a=a*26+ord(i)-65
 a+=56*252**4
 for i in range(5):b=bin((int("4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33",36)>>a%252*10)&1023)[2:].rjust(10,"0")+b;a/=252
 return b[2:]

Pruébalo en línea!

El número mágico 4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33(en base 36), o su equivalente decimal 382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271, codifica las 252 permutaciones de 5 0sy 5 1s.

Los primeros convertidos algoritmo A-Zen 0-25y tratan como un número en base 26, a continuación, añadir 56*252**4.

Luego, el número se convierte en un número base-252 de 5 dígitos, y se sustituye con la permutación correspondiente de 5 0sy 5 1s.

Después de eso, elimine los primeros 2 bits, lo que está garantizado 01. Luego hemos codificado la cadena en una cadena de 48 bits, que consta de exactamente 24 0sy 24 1s.

JavaScript (ES8), puntaje 22186.623779296875

f=
s=>s.replace(/./g,(c,i)=>(i%2*127^c.charCodeAt()).toString(2).padStart(7,0))

<input oninput=o.textContent=f(this.value)><pre id=o>

Para una entrada de longitud uniforme, siempre genera 3.5 * de ceros y unos, por lo que solo paga la penalización de 1.5 ** 14. Caracteres soportados: '+-.3569:<GKMNSUVYZ\cefijlqrtx.

Jalea , 16 bytes

42ɠO%ḅ26ịœcH$ạ‘Ṭ

Utiliza +,-./0123456789:;<=>?@ABCDpara entrada y devuelve una lista de unos y ceros.

Esto intenta crear una lista de 538,257,874,440 combinaciones en la memoria, por lo que necesitará una gran cantidad de RAM para ejecutarla como está ...

Pruébalo en línea! (comprobable; longitud de entrada 3, longitud de salida 18)

Cómo funciona

42ɠO%ḅ26ịœcH$ạ‘Ṭ  Main link. No arguments.

42                Set the argument and the return value to 42.
  ɠ               Read one line from STDIN.
   O              Ordinal; map ['+', ..., 'D'] to [43, ..., 69].
    %             Take the code points modulo 42, mapping [43, ..., 69] to
                  [1, ..., 26].
     ḅ26          Convert the result from base 26 to integer.
            $     Combine the two links to the left into a monadic chain.
           H          Halve; yield 21.
         œc           Generate all 21-combinations of [1, ..., 42].
                  There are 538,257,874,440 of these combinations. The first
                  269,128,937,220 begin with a 1.
        ị         Retrieve the combination at the index to the left.
                  [26, 26, 26, 26, 26, 26, 26, 26] in bijective base 26 equals
                  217,180,147,158 in decimal, so the retrieved combination will
                  begin with a 1.
              ‘   Increment; yield 43.
             ạ    Absolute difference; map [1, ..., 42] to [42, ..., 1].
                  The combination now begins with a 42.
               Ṭ  Untruth; turn the combination into a Boolean list, with 1's
                  at the specified indices and 0's elsewhere.
                  Since the maximum of the combination is 42, this list will have
                  exactly 42 items, 21 of which will be 1's.

Python 3 , 985135 bytes, Diferencia máxima 0, Longitud 42, puntaje 135

lambda s:C(int(s,26),21,20)
B=lambda x,y:y<1or-~x*B(x+1,y-1)//y
def C(n,o,z):p=B(o,z);x=n>=p;return z+1and[x]+C(n-p*x,o-x,z-1+x)or[1]*o

Pruébalo en línea!

Cortesía de Bubbler.

Código sin golf:

import math

def binomial(x, y):
    return math.factorial(x) // math.factorial(y) // math.factorial(x - y)

def string_to_int(input_str):
    result = 0
    for i in range(0,8):
        result += (ord(input_str[i])-65)%26 * pow(26,i)
    return result

def counting_function(target, ones, zeros):
    if zeros > 0:
        position = binomial(ones+zeros-1,zeros-1)
    else:
        position = 1
    if target > position:
        if ones > 0:
            print("1", end='')
            ones -= 1
            counting_function(target-position,ones,zeros)
    else:
        if zeros > 0:
            print("0", end='')
            zeros -= 1
            counting_function(target,ones,zeros)
        elif ones > 0:
            print("1", end='')
            ones -= 1
            counting_function(target,ones,zeros)

input_str = input("Input string (A-Z): ")
input_int = string_to_int(input_str)+1
target = input_int
ones = 21
zeros = 21
counting_function(target, ones, zeros)
print("")

Dado que otros enfoques parecen bastante ineficientes, he tratado de hacer un tiempo óptimo. Es claramente O (N) en N bits de codificación, lo cual es óptimo para Big-O.

Sugerencia: trate de pensar en el triángulo de Pascal para este ( este diagrama lo revela)

Resultados de muestra:

Input:  AAAAAAAA
Output: 000000000000000000000111111111111111111111

Input:  ZZZZZZZZ
Output: 011001000000011010011000111010110110111110

Tiempo de ejecución: <0.013 s (aproximadamente constante para todas las entradas)

Perl 5 , 55 bytes, diferencia máxima 0, longitud 42, puntaje 56 55

Esto funciona, pero tomará un tiempo largo pero factible ( ZZZZZZZZtomó 2.5 días en mi computadora). La memoria no es problema.

Se usa A-Zcomo entrada 1y Acomo caracteres de codificación. Siempre están perfectamente equilibrados. Omite las primeras 26^7 = 8031810176combinaciones equilibradas que representan cadenas de menos de 8 caracteres, pero está bien, ya que están 538257874440disponibles y uso 208827064575y 208827064575 + 8031810176 < 538257874440.

Sin embargo, en realidad "cuenta" hasta la combinación objetivo, lo que llevará mucho tiempo. Es por eso que en el enlace TIO solo usé una cadena de entrada demasiado corta (que también son compatibles) para demostrar que la salida es correcta. Funcionará un poco más que AAAAAAantes del tiempo de espera de TIO. ZZZZZZZZdebería ser aproximadamente 26^3 = 17576más lento.

#!/usr/bin/perl -ap
$_=1x21 .($i=A)x21;s/(A*)(1*)1A/$2$1A1/ until"@F"eq$i++

Pruébalo en línea!

El decodificador es casi el mismo:

#!/usr/bin/perl -ap
$_=1x21 .($\=A)x21;s/(A*)(1*)1A/$2$1A1/,$\++until"@F"eq$_}{

Pruébalo en línea!

> <> , 75 bytes, Diferencia máxima 0, Longitud 42, puntaje 75

0i:0(?v'A'-$dd+*+!
.")1+.\1+:0$:2%:}:@-2,@+$bl"
[ab+-?\$:?vv~3
~~]>n<v$-1<>

Pruébalo en línea!

Advertencia justa, esto llevará mucho, mucho, mucho tiempo en completarse incluso para el AAAAAAAAcaso trivial . Corre a través de cada representación binaria de un contador hasta que 1se alcanza el número binario (base 26 de la entrada) con 21 s. Si quiere probar el programa de alguna manera, puede reemplazar el ab+en la tercera línea con la 1que devolverá el enésimo número binario con solo uno 1, ¡ Pruébelo en línea!

Python 3 , 75 bytes, Diferencia máxima 0, Longitud 42, Puntuación 112

lambda s:sorted({*permutations("01"*21)})[int(s,26)]
from itertools import*

Pruébalo en línea!

Esto solo funciona en teoría debido a restricciones de memoria. Existen 538257874440distintas cadenas equilibradas de cero uno de longitud 42 y 208827064575posibles entradas, por lo que algunas de las posibles salidas no se utilizarán.

-37 bytes gracias a @recursive

C ++, 146 bytes, longitud máxima 42, 0 desequilibrio, puntaje 146

#include<algorithm>
long long i,s;int f(char*I,char*O){for(O[i=42]=s=0;i--;i<8?s=s*26+I[i]:0)O[i]=i%2|48;for(;s--;)std::next_permutation(O,O+42);}

Funciona para cualquier char 26 continuo, pero advirtiendo que se ejecuta un tiempo inaceptable