Tâche

Encodez une chaîne entièrement composée d'alphabets majuscules ( A-Z) utilisant uniquement des zéros et des uns, en utilisant votre propre schéma préféré. Mais la règle n'est pas si simple!

Règles

1. Votre programme / fonction doit gérer correctement toute chaîne d'entrée valide de longueur 8 .
2. Les résultats doivent avoir la même longueur pour toutes les entrées.
3. Les résultats doivent être distincts pour des entrées distinctes.
4. Les résultats doivent être aussi courts que possible.
5. Les résultats doivent être équilibrés à zéro (avoir un nombre similaire à celui des zéros). Ils ne doivent pas nécessairement être égaux (c'est-à-dire parfaitement équilibrés), mais votre score sera pénalisé pour cela.

Vous n'êtes pas obligé de fournir un programme / une fonction qui décode votre encodage.

Entrée et sortie

• Vous pouvez décider d'accepter tout ensemble de 26 caractères ASCII imprimables distincts au lieu de A-Z.
• Vous pouvez décider de sortir n'importe quelle paire de caractères ASCII imprimables distincts au lieu de 0et 1.
• Vous n'êtes pas autorisé à générer un entier au lieu d'une chaîne de bits, car il peut avoir des zéros non significatifs et il n'est pas clair si vous avez réellement respecté la règle 2.
• Si vous décidez de vous écarter de la valeur par défaut ( A-Zentrée et 01sortie), vous devez spécifier les jeux de caractères d'entrée / sortie dans votre soumission.

Notation

• Score de base: taille du code, ou 1 si votre programme est vide.
• Sanctions
  • Pénalité pour la durée: multiplier 1.5 ** (encoded length - 42)
  • Il n'y a aucun bonus pour être plus court; 42 est la longueur minimale pour un encodage parfaitement équilibré de chaînes de 8 longueurs avec une taille d'alphabet 26.
  • Pénalité pour déséquilibre: multipliez 2 ** max(abs(ones - zeros) for every valid input of length 8), où oneset zerossont les comptes de 1 et 0 dans chaque sortie, respectivement.
  • Votre soumission doit montrer un exemple du pire des cas (entrée / sortie) ou une explication théorique sur la valeur de la pénalité.
• Le score le plus bas l'emporte.

Exemple de soumission

Esolang hypothétique, 0 octet, score 74733.8906

Voici un esolang hypothétique, où un programme vide imprime tous les codes ASCII des caractères d'entrée en binaire.

Par exemple, si vous donnez AAAAAAAAen entrée, le programme imprimera 10000018 fois de suite, c'est-à-dire 10000011000001100000110000011000001100000110000011000001.

L'alphabet saisi est choisi pour être CEFGIJKLMNQRSTUVXYZabcdefh. De cette façon, tous les caractères sont convertis en sept chiffres en binaire, et le nombre de zéro ne diffère que d'un par caractère (ils ont tous trois 1 et quatre 0 ou vice versa lorsqu'ils sont convertis en binaire).

La longueur de sortie est toujours de 56 et le pire déséquilibre se produit sur les entrées comme CCCCCCCC, où les zéros apparaissent 8 fois plus que les uns.

Par conséquent, le score de cette soumission est 1.5 ** (56 - 42) * 2 ** 8 == 74733.8906.

Stax , 11 octets, 0 pénalité, Score 11

Ce programme utilise [0-9A-P]pour l'entrée et [01]pour la sortie.

ö■▄←·ï↨≡⌐╠H

Exécutez-le et déboguez-le en ligne - cliquez sur le bouton Exécuter pour commencer. Les quatre premiers cas de test s'exécutent en millisecondes. Le cinquième en quelques secondes. Le sixième en millénaires.

La représentation ascii correspondante de ce programme est la suivante.

A$21*,26|bD|N

Il s'appuie fortement sur l' |Ninstruction, qui obtient la permutation ultérieure d'un tableau.

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

Toutes les sorties sont des permutations de la chaîne initiale. Il a 21 zéros et 21 uns. Par conséquent, toutes les sorties sont de 42 caractères et parfaitement équilibrées.

Gelée , 19 octets

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

Essayez-le en ligne!

Explication

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 octets, Diff Max: 0, Longueur: 64, Score: 149636.5528 142154.7251 104745.5869

sm@S.{.p*`T4xG

Essayez-le en ligne!

Utilise l'alphabet en minuscules ( [a-z]) au lieu de majuscules. Peut utiliser des majuscules en les remplaçant Gpar rG1, au prix de 2 octets.

J'aurais pu traduire la réponse Python 3 d' HyperNeutrino pour un meilleur score, mais franchement, je veux une réponse qui fonctionne réellement.

Python 2 , 779 645 octets, Max (Diff) = 0, Longueur = 48, Score = 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:]

Essayez-le en ligne!

Le nombre magique 4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33(en base 36), ou son équivalent décimal 382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271, code les 252 permutations de 5 0s et 5 1s.

L'algorithme se convertit d'abord A-Zen 0-25et le traite comme un nombre en base 26, puis ajoute 56*252**4.

Ensuite, le nombre est converti en un nombre à 25 chiffres en base 252 et remplacé par la permutation correspondante de 5 0s et 5 1s.

Après cela, supprimez les 2 premiers bits, ce qui est garanti 01. Ensuite, nous avons codé la chaîne en une chaîne de 48 bits, qui se compose exactement de 24 0s et 24 1s.

JavaScript (ES8), score 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>

Pour une entrée de longueur égale, émet toujours 3,5 * de zéros et de uns, donc il ne paie que la pénalité de 1,5 ** 14. Caractères pris en charge: '+-.3569:<GKMNSUVYZ\cefijlqrtx.

Gelée , 16 octets

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

Utilise la +,-./0123456789:;<=>?@ABCDsaisie et renvoie une liste de uns et de zéros.

Cela tente de créer une liste de 538 257 874 440 combinaisons en mémoire, vous aurez donc besoin d'une grande quantité de RAM pour l'exécuter telle quelle ...

Essayez-le en ligne! (testable; longueur d'entrée 3, longueur de sortie 18)

Comment ça fonctionne

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 , 985 135 octets, Max Diff 0, Longueur 42, score 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

Essayez-le en ligne!

Gracieuseté de Bubbler

Code non 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("")

Étant donné que d'autres approches semblent assez inefficaces, j'ai essayé d'en faire une optimale dans le temps. Il s'agit clairement de O (N) en N bits de codage, ce qui est optimal en big-O.

Astuce: essayez de penser au triangle de Pascal pour celui-ci ( ce diagramme le révèle)

Exemples de sorties:

Input:  AAAAAAAA
Output: 000000000000000000000111111111111111111111

Input:  ZZZZZZZZ
Output: 011001000000011010011000111010110110111110

Temps d'exécution: <0,013 s (à peu près constant pour toutes les entrées)

Perl 5 , 55 octets, max diff 0, longueur 42, score 56 55

Cela fonctionne mais prendra un temps long mais réalisable (a ZZZZZZZZpris 2,5 jours sur mon ordinateur). La mémoire n'est pas un problème.

Utilise A-Zcomme entrée et 1et Acomme caractères d'encodage. Ils sont toujours parfaitement équilibrés. Saute les premières 26^7 = 8031810176combinaisons équilibrées représentant une chaîne de moins de 8 caractères, mais c'est OK car il y en a 538257874440et j'utilise 208827064575et 208827064575 + 8031810176 < 538257874440.

Cependant, il "compte" jusqu'à la combinaison cible qui prendra très longtemps. C'est pourquoi dans le lien TIO, j'ai uniquement utilisé une chaîne d'entrée trop courte (qui est également prise en charge) pour démontrer que la sortie est correcte. Fonctionne jusqu'à un peu plus AAAAAAqu'avant l'expiration de TIO. ZZZZZZZZdevrait être environ 26^3 = 17576plus lent.

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

Essayez-le en ligne!

Le décodeur est presque le même:

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

Essayez-le en ligne!

> <> , 75 octets, Max Diff 0, Longueur 42, score 75

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

Essayez-le en ligne!

Juste avertissement, cela prendra très très très longtemps, même pour le AAAAAAAAcas trivial . Parcourt chaque représentation binaire d'un compteur jusqu'à ce que le (nombre 26 de base de l'entrée) du e nombre binaire avec 21 1s soit atteint. Si vous voulez tester un peu le programme, vous pouvez remplacer le ab+sur la troisième ligne par 1laquelle retournera le nième nombre binaire avec un seul 1, essayez-le en ligne!

Python 3 , 75 octets, Diff Max 0, Longueur 42, Score 112

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

Essayez-le en ligne!

Cela ne fonctionne qu'en théorie à cause des contraintes de mémoire. Il existe 538257874440des chaînes nulles et équilibrées distinctes de longueur 42 et 208827064575des entrées possibles, de sorte que certaines des sorties possibles ne seront pas utilisées.

-37 octets grâce à @recursive

C ++, 146 octets, 42 maxlength, 0 déséquilibre, score 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);}

Fonctionne pour tout caractère continu de 26 caractères, mais avertissement qu'il s'exécute un temps inacceptable