Ausgeglichene Null-Eins-Kodierung

12

Aufgabe

Codieren Sie eine Zeichenfolge, die ausschließlich aus Großbuchstaben ( A-Z) besteht , und verwenden Sie dabei nur Nullen und Einsen. Verwenden Sie dabei Ihr eigenes Lieblingsschema. Aber die Regel ist nicht so einfach!

Regeln

  1. Ihr Programm / Ihre Funktion muss eine gültige Eingabezeichenfolge der Länge 8 korrekt verarbeiten .
  2. Die Ergebnisse müssen für alle Eingaben gleich lang sein.
  3. Die Ergebnisse müssen für unterschiedliche Eingaben unterschiedlich sein.
  4. Die Ergebnisse müssen so kurz wie möglich sein.
  5. Die Ergebnisse müssen eins zu null ausbalanciert sein (eine Anzahl von Einsen ähnlich der von Nullen). Sie müssen nicht gleich sein (dh perfekt ausbalanciert sein), aber Ihre Punktzahl wird dafür bestraft.

Sie müssen kein Programm / keine Funktion bereitstellen, die Ihre Codierung decodiert.

Ein- und Ausgang

  • Sie können eine beliebige Menge von 26 verschieden zu akzeptieren entscheiden druckbaren ASCII - Zeichen statt A-Z.
  • Sie können festlegen, dass anstelle von und ein Paar eindeutiger druckbarer ASCII-Zeichen ausgegeben werden soll .01
  • Sie dürfen anstelle einer Bitfolge keine Ganzzahl ausgeben , da diese möglicherweise führende Nullen enthält und es unklar ist, ob Sie die Regel 2 tatsächlich erfüllt haben.
  • Wenn Sie von der Standardeinstellung ( A-ZEingabe und 01Ausgabe) abweichen möchten , müssen Sie die Eingabe- / Ausgabe-Zeichensätze in Ihrer Übermittlung angeben.

Wertung

  • Basisbewertung: Codegröße oder 1, wenn Ihr Programm leer ist.
  • Strafen
    • Strafe für Länge: multiplizieren 1.5 ** (encoded length - 42)
    • Es gibt keinen Bonus dafür, kürzer zu sein. 42 ist die Mindestlänge für eine perfekt ausbalancierte Kodierung von 8-fachen Zeichenfolgen mit der Alphabetgröße 26.
    • Strafe für Unausgeglichenheit: Multiplizieren Sie 2 ** max(abs(ones - zeros) for every valid input of length 8), wo onesund zerossind die Zählungen von 1 und 0 in jedem Ausgang.
    • Ihr Beitrag muss entweder ein Worst-Case-Beispiel (Eingabe / Ausgabe) oder eine theoretische Erklärung zum Strafwert enthalten.
  • Die niedrigste Punktzahl gewinnt.

Beispiel Einsendung

Hypothetisches esolang, 0 Bytes, Kerbe 74733.8906

Hier ist ein hypothetischer Esolang, bei dem ein leeres Programm alle ASCII-Codes der eingegebenen Zeichen binär ausgibt.

 

Wenn Sie AAAAAAAAbeispielsweise eine Eingabe machen, druckt das Programm 10000018 Mal hintereinander, d 10000011000001100000110000011000001100000110000011000001. H.

Das eingegebene Alphabet wird als gewählt CEFGIJKLMNQRSTUVXYZabcdefh. Auf diese Weise werden alle Zeichen in Binärform in sieben Ziffern umgewandelt, und die Null-Eins-Zählungen unterscheiden sich nur um eins pro Zeichen (bei der Umwandlung in Binärform haben alle drei Einsen und vier Nullen oder umgekehrt).

Die Ausgabelänge beträgt immer 56, und der ungünstigste Fall tritt bei den Eingängen auf CCCCCCCC, bei denen Nullen 8-mal häufiger auftreten als Einsen.

Daher ist der Punktestand dieser Einreichung 1.5 ** (56 - 42) * 2 ** 8 == 74733.8906.

Bubbler
quelle
Kann ich meinen hypothetischen Esolang verwenden, bei dem das leere Programm eine Zahl N in 26-stelliger Buchstabenkodierung akzeptiert und die N-te mögliche 42-Bit-Folge von Summe 21 ausgibt?
ngn
@ngn - Entspricht Ihre hypothetische Sprache unseren akzeptierten Kriterien ? - EDIT ah Eingabe ist immer [AZ] - Ich denke, das ist einfach genug ... :)
Jonathan Allan
1
Können wir eine Liste von Einsen und Nullen ausgeben oder muss es eine Zeichenkette sein?
Dennis
1
Die ganze Frage ist Blei in „nicht Unwucht haben müssen, müssen in 42 - stellig sein, die Pflegezeit Echt läuft“
l4m2

Antworten:

4

Stax , 11 Bytes, 0 Strafe, 11 Punkte

Dieses Programm verwendet [0-9A-P]für die Eingabe und [01]für die Ausgabe.

ö■▄←·ï↨≡⌐╠H

Führen Sie es online aus und debuggen Sie es - klicken Sie zum Starten auf die Schaltfläche Ausführen. Die ersten vier Testfälle werden in Millisekunden ausgeführt. Der fünfte in Sekunden. Der sechste in Jahrtausenden.

Die entsprechende ASCII-Darstellung dieses Programms ist dies.

A$21*,26|bD|N

Es stützt sich stark auf die |NAnweisung, die die nachfolgende Permutation eines Arrays erhält.

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

Alle Ausgaben sind Permutationen der Anfangszeichenfolge. Es hat 21 Nullen und 21 Einsen. Daher sind alle Ausgaben 42 Zeichen und perfekt ausbalanciert.

rekursiv
quelle
3

Jelly , 19 Bytes

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

Probieren Sie es online!

Erläuterung

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
HyperNeutrino
quelle
E x p l a n a t i o n?
Esolanging Fruit
@EsolangingFruit hinzugefügt
HyperNeutrino
3

Pyth, 20 - 19 - 14 Byte, maximaler Diff: 0, Länge: 64, Ergebnis: 149636.5528 142154.7251 104745.5869

sm@S.{.p*`T4xG

Probieren Sie es online!

Verwendet das Kleinbuchstaben ( [a-z]) anstelle von Großbuchstaben. Verwenden Groß kann durch das Ersetzen Gmit rG1auf Kosten von 2 Byte.

Ich hätte HyperNeutrinos Python 3-Antwort für eine bessere Punktzahl übersetzen können, aber ehrlich gesagt möchte ich eine Antwort, die tatsächlich funktioniert.

hakr14
quelle
2

Python 2 , 779 645 Bytes, Max (Diff) = 0, Länge = 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:]

Probieren Sie es online!

Die magische Zahl 4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33(in Basis 36) oder ihr Dezimaläquivalent 382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271codiert alle 252 Permutationen von 5 0s und 5 1s.

Der Algorithmus wandelt zuerst A-Zin 0-25und behandle es als Basis-26 - Zahl, dann fügen 56*252**4.

Dann wird die Zahl in eine 5-stellige Basis-252-Zahl umgewandelt und durch die entsprechende Permutation von 5 0s und 5 1s ersetzt.

Danach löschen Sie die ersten 2 Bits, was garantiert ist 01. Dann haben wir den String in einen 48-Bit-String kodiert, der genau aus 24 0s und 24 1s besteht.

Shieru Asakoto
quelle
Ziemlich sicher, dass die Strafen multipliziert werden müssen (das heißt, Ihre Punktzahl ist 7346.953125).
HyperNeutrino
@HyperNeutrino Oh, ich denke, es ist eine Ergänzung; P Bearbeitet
Shieru Asakoto
2

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

Bei Eingabe mit gerader Länge werden immer 3,5 * Nullen und Einsen ausgegeben, sodass nur die Strafe von 1,5 ** 14 bezahlt wird. Unterstützte Zeichen: '+-.3569:<GKMNSUVYZ\cefijlqrtx.

Neil
quelle
2

Gelee , 16 Bytes

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

Verwendet +,-./0123456789:;<=>?@ABCDfür die Eingabe und gibt eine Liste von Einsen und Nullen zurück.

Auf diese Weise wird versucht, eine Liste mit 538.257.874.440 Kombinationen im Speicher zu erstellen. Sie benötigen also eine große Menge an RAM, um die Liste wie sie ist auszuführen.

Probieren Sie es online! (prüfbar; Eingangslänge 3, Ausgangslänge 18)

Wie es funktioniert

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.
Dennis
quelle
2

Python 3 , 985 135 Bytes, Max Diff 0, Länge 42, Punktzahl 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

Probieren Sie es online!

Mit freundlicher Genehmigung von Bubbler

Ungolfed-Code:

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

Da andere Ansätze recht ineffizient erscheinen, habe ich versucht, einen zeitoptimalen Ansatz zu erstellen. Es ist sauber O (N) in N Bits der Codierung, was groß-O-optimal ist.

Hinweis: Versuchen Sie, an Pascals Dreieck für dieses zu denken ( dieses Diagramm zeigt es)

Beispielausgaben:

Input:  AAAAAAAA
Output: 000000000000000000000111111111111111111111

 

Input:  ZZZZZZZZ
Output: 011001000000011010011000111010110110111110

Ausführungszeit: <0,013 s (für alle Eingänge ungefähr konstant)

Echt
quelle
@Bubbler Unglaublich, ich hatte nicht die Fähigkeiten, um dies zu erreichen
Real
Sie sollten jedoch einige Anstrengungen unternehmen, um Ihre Punktzahl zu minimieren. Alle Einsendungen sollten sich ernsthaft bemühen, die Punktzahl zu optimieren, sonst ist sie ungültig.
user202729
@ user202729 Ich habe dann auf Bubblers Version umgestellt, die minimiert ist. Ich habe mich bemüht, meine Punktzahl zu minimieren, nur nicht durch die Codegröße.
Real
Über letzteren Punkt ... richtig.
user202729
2

Perl 5 , 55 Bytes, maximales Diff 0, Länge 42, Punktzahl 56 55

Dies funktioniert, wird aber lange dauern, aber machbar sein (ZZZZZZZZ hat auf meinem Computer 2,5 Tage ). Speicher ist kein Problem.

Verwendet A-Zals Eingabe und 1und Aals Kodierungszeichen. Sie sind immer perfekt ausbalanciert. Überspringt die ersten 26^7 = 8031810176ausgeglichenen Kombinationen, die Zeichenfolgen mit weniger als 8 Zeichen darstellen, aber das ist in Ordnung, da diese 538257874440verfügbar sind und ich 208827064575und verwende 208827064575 + 8031810176 < 538257874440.

Es "zählt" jedoch tatsächlich bis zu der Zielkombination, die sehr lange dauern wird. Aus diesem Grund habe ich im TIO-Link nur eine zu kurze Eingabezeichenfolge verwendet (die auch unterstützt wird), um zu demonstrieren, dass die Ausgabe korrekt ist. Funktioniert etwas besser als AAAAAAvor dem Timeout von TIO. ZZZZZZZZsollte etwa 26^3 = 17576mal langsamer sein.

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

Probieren Sie es online!

Der Decoder ist fast der gleiche:

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

Probieren Sie es online!

Tonne Hospel
quelle
1

> <> , 75 Bytes, Max Diff 0, Länge 42, Punktzahl 75

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

Probieren Sie es online!

Faire Warnung, es wird sehr, sehr lange dauern, bis dies auch für den unbedeutenden AAAAAAAAFall abgeschlossen ist. Durchläuft jede Binärdarstellung eines Zählers, bis die (Basis 26 Darstellung des Eingangs) 'te Binärzahl mit 21 1s erreicht ist. Wenn Sie das Programm testen möchten etwas können Sie die ersetzen ab+in der dritten Zeile mit 1denen die n - te binäre Zahl mit nur einem einzigen zurückzukehren 1, Probieren Sie es online!

Scherzen
quelle
1

Python 3 , 75 Bytes, Max Diff 0, Länge 42, Punktzahl 112

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

Probieren Sie es online!

Dies funktioniert theoretisch nur aufgrund von Speicherbeschränkungen. Es gibt538257874440 unterschiedliche symmetrische Null-Eins-Zeichenfolgen mit der Länge 42 und 208827064575möglichen Eingaben, sodass einige der möglichen Ausgaben nicht verwendet werden.

-37 Bytes dank @recursive

HyperNeutrino
quelle
Sie können int(s,26)den Indexwert verwenden, anstatt sum(...)den eingegebenen Zeichensatz zu ändern.
rekursiven
@recursive das würde unprintables erfordern. habe das schon
probiert
Unbedruckbares? Es nutzt [0-9A-P], nicht wahr? Auf meinem Computerint("123ABC",26) == 12855114
rekursiver
@recursive oh yeah du hast recht idk was ich dachte lol. Vielen Dank!
HyperNeutrino
1

C ++, 146 Bytes, 42 maximale Länge, 0 Unwucht, Punktzahl 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);}

Funktioniert für jeden fortlaufenden 26 Zeichen, aber Warnung, es läuft eine inakzeptable Zeit

l4m2
quelle
Es sieht so aus, als müssten Sie zusätzlich ein leeres Array übergeben. Ich denke nicht, dass das gültig ist. / Wenn Sie GCC verwenden , können Sie ersetzen #include<algorithm>mit #import<regex>.
user202729
Ich werde es ändern, wenn GCC beschließt, die Verwendung eines bestimmten Zeigers als Ausgabe zu
beenden
... das ist also ein Hinweis auf die Ausgabe? Sieht dann gültig aus. Sie sollten das Eingabe- / Ausgabeformat jedoch explizit erwähnen.
user202729