Herausforderung

Ihre Aufgabe ist es, eine Ganzzahl als eine Zeichenfolge aus ASCII- Zeichen zu codieren und sie dann erfolgreich zu decodieren, nachdem die Zeichenfolge zufällig gemischt wurde.

Sie schreiben zwei Programme / Funktionen , die als Encoder und Decoder bezeichnet werden .

Encoder

• Eingabe: eine ganze Zahl im Bereich von .$n$$[0,2^{31}-1]$
• Ausgang: ein String von ASCII - Zeichen (nicht unbedingt druckbar).$s$

Decoder

• Eingabe: eine zufällige Permutation der Zeichenkette .$s'$$s$
• Ausgabe: die ganze Zahl .$n$

Wertung

Sei die maximale Länge von über alle möglichen Werte von . Wenn der Encoder nicht deterministisch agiert (was zulässig ist, siehe unten), ist das die maximale Länge von , die auftreten kann (möglicherweise ).$A$$s$$n$$A$$s$$\infty$

Lassen das sein Länge des Encoder in Bytes und die Länge der Decoder in Bytes.$L_E$$L_D$

Dann lautet Ihre Punktzahl .$A\cdot(L_E+L_D)$

Der Sieg wird der Einreichung mit der niedrigsten Punktzahl zuerkannt .

Zeitlimit

Es gibt eine etwas willkürliche Zeitgrenze von 1 Minute auf der Ausführungszeit von sowohl dem Encoder und dem Decoder für einen einzelnen Testfall (dh ein einziger Wert von ).$n$

Das Ziel ist es, Lösungen zu vermeiden, die die Codierung brachial erzwingen, indem alle Sequenzen mit bestimmten Eigenschaften aufgelistet werden. Wenn Ihre Lösung etwas Klügeres als das tut, entspricht sie höchstwahrscheinlich der zeitlichen Beschränkung und wird als gültig betrachtet. Wenn es für einige zufällig ausgewählte Werte von auf TIO funktioniert , wird es ebenfalls als gültig betrachtet. Andernfalls werde ich es auf meinem Computer testen, aber beachten Sie, dass Ihre Lösung mit ziemlicher Sicherheit scheitern wird, wenn sie reine Brute-Force-Lösung ist.$n$

Regeln

• Der Encoder und der Decoder müssen in derselben Sprache geschrieben sein .
• Der Decoder muss für jede mögliche Permutation der vom Encoder zurückgegebenen Zeichenfolge die richtige Ganzzahl ausgeben .$n$$s'$$s$
• Der Encoder und Decoder sind nicht zu erlaubt Austausch von Informationen in irgendeiner Weise (zB durch globale Variablen oder Dateien).
• Der Ausgang des Encoder muss nicht sein deterministisch (das heißt, der gleiche Eingang können unterschiedliche Ausgabestrings erzeugen , wenn der Encoder mehrere Male ausgeführt wird), aber der Decoder muss immer erraten die richtige ganze Zahl n .$n$$n$
• Der Codierer und der Decodierer können die Ganzzahl $n$ auf jede zweckmäßige Weise annehmen und zurückgeben (z. B. wenn $n=14$ , ist die Eingabe in Ordnung 14, "14"oder [1,4]).
• Der Encoder ausgeben kann die String $s$ entweder durch Drucke auf stdout oder durch Rücksendung eine Zeichenfolge, eine Liste / Array von Zeichen oder eine Liste / Matrix von ganzen Zahlen im Bereich $[0,127]$ ; Beachten Sie, dass der Decoder als Eingabe eine Permutation von $s$ empfängt, wie sie vom Encoder zurückgegeben wird. Daher sollte er die Zeichenfolge $s'$ im gleichen Format wie $s$ akzeptieren .
• Standardlücken sind verboten.
• Wenn möglich, erläutern Sie, wie Ihr Code funktioniert und warum die von Ihnen angegebene Punktzahl korrekt ist.

Beispiel

Angenommen, $n=14$ .

• Der Encoder empfängt 14als Eingang. Es kann ausgegeben werden "qwerty".
• Der Decoder empfängt beispielsweise eine Permutation von "qwerty"als Eingabe "tweyqr". Es muss ausgegeben werden 14(in jedem geeigneten Format).

Der Encoder hätte auch zurückkehren [113,119,101,114,116,121]können. In diesem Fall hätte der Decoder beispielsweise empfangen [116,119,101,121,113,114].

Beachten Sie, dass der vom Encoder zurückgegebene String möglicherweise auch nicht druckbare ASCII-Zeichen enthält (jedoch immer im Bereich [0x00, ..., 0x7F]).

Gelee , (17 Bytes + 18 Bytes) × Länge 6 = 210 Punkte

b36µỤỤ + × 3µŒ¿b3U + Ṣ

: 3_J
Ṣ% 3Uḅ3œ? Çḅ36

Probieren Sie es online! (oder mit zusätzlichen Debug-Informationen)

Nachdem ich versucht hatte, diese Herausforderung mit dem Ziel der angegebenen Siegbedingung zu lösen, hielt ich es für interessant, eine hypothetische alternative Siegbedingung anzustreben: Codegolf mit einer minimal möglichen maximalen Länge für die Ausgabe.

Erläuterung

Codierung

Der erste Schritt bei der Codierung besteht darin, die Eingabe als Basis 36 ( b36) darzustellen . 36 ⁶ = 2176782336> 2147483647, daher enthält das Ergebnis höchstens 6 Ziffern, von denen jede im Bereich von 0 bis 35 liegt.

Als nächstes wandeln wir dies in eine Darstellung um, die 6 verschiedene Ziffern enthält . Hierfür gibt es mehrere mögliche Algorithmen. Hier wird jedoch 1 zur kleinsten Ziffer, 2 zur zweitkleinsten Ziffer, 3 zur drittkleinsten Ziffer usw. addiert. Dies bedeutet, dass wenn zwei Ziffern gleich wären, eine von ihnen willkürlich als kleiner betrachtet wird und sie sich somit unterscheiden. und offensichtlich kann dieser Algorithmus nicht dazu führen, dass zwei verschiedene Ziffern gleich werden. Um dies in Jelly darzustellen, verwenden wir Ụ("Indizes nach Werten sortieren"), um eine Liste der Indizes in sortierter Reihenfolge zu erhalten. Ụerneut, um dies umzukehren, wobei jedes Element des Originals in sortierter Reihenfolge seiner Position zugeordnet wird; undµ…+um das Original zur neuen Liste hinzuzufügen. Das Ergebnis ist eine Darstellung der eingegebenen Nummer als sechs verschiedene Ziffern im Bereich von 1 bis 41 (Minimum 0 + 1, Maximum 35 + 6).

Wir teilen dies dann in eine weitere Form auf: eine sortierte Liste von Ziffern im Bereich von 1 bis 41 sowie eine Zahl von 1 bis 720, die angibt, in welcher der 720 möglichen Permutationen sich die Ziffern befanden. (Die Œ¿und Ṣextrahieren die Permutationsnummer und sortieren jeweils auflisten.)

Schließlich konvertieren wir die Zahl von 1 nach 720 in die Basis 3 ( b3), kehren sie um ( U) und kodieren die sechs 3 - und sechs 1 - bis 41 - stelligen Ziffern, indem wir sie mit reverse divmod (dem Wert von) in ein einzelnes ASCII - Zeichen packen das zeichen mod 3 ist die 3-stellige basis, der durch 3 geteilte wert ist die 1–41-stellige). Der mögliche Bereich der Ergebnisse ist (1 × 3) + 0 = 3 mindestens und (41 × 3) + 2 = 125 höchstens und entspricht unserem ASCII-Bereich. Das Packen erfolgt über ×3und +zusammen mit einem zusätzlichen µBefehl, um sicherzustellen, dass jeder Befehl mit dem richtigen Datenbit arbeitet. (Hier gibt es einen kleinen Golf-Trick: Wir multiplizieren mit 3, bevor wir die Permutation extrahieren. Das erspart die Ausgabe eines Bytes für ein Gruppierungszeichen.)

Im Übrigen liegt der Grund für die Umkehrung der Zahl zur Basis 3 darin, dass sie möglicherweise weniger Ziffern als die Zahl von 1 bis 41 enthält. (Mehr kann es nicht geben; die kleinste Zahl, für die n !> 3 ⁿ etwas über 6 liegt.) Jelly fügt effektiv nachgestellte Nullen ein, wenn zwei Zahlen unterschiedlicher Länge addiert werden, damit sie übereinstimmen. Abschließende Nullen würden die Interpretation der Zahl beeinflussen, führende Nullen jedoch nicht. Umgekehrt wird also sichergestellt, dass die zusätzlichen Nullen an einem Ort landen, der unsere Antwort nicht durcheinander bringt.

Dekodierung

Der erste Schritt bei der Decodierung besteht darin, die beiden Zahlen (die Zahl zur Basis 3 und die Zahl von 1 bis 41) zu extrahieren. Wir können ihre Ziffern mit Division ( :3) bzw. Modulo ( %3) leicht genug ermitteln , aber woher wissen, in welcher Reihenfolge sie sich befanden? Nun, die 1–41-Nummer hatte ihre Ziffern in sortierter Reihenfolge, und die Ziffern an den entsprechenden Positionen der beiden Nummern wurden in denselben Zeichen gespeichert. Auf diese Weise können wir herausfinden, in welche Reihenfolge die Ziffern der 1–41 gemischt wurden (indem wir ihre relativen Werte betrachten) und wissen, dass die Ziffern der Basis-3 auf die gleiche Weise gemischt worden sein müssen. Tatsächlich, weil Zeichen unserer ASCII-Codierung genauso sortiert sind wie die Ziffern von 1 bis 41 (diese waren alle verschieden und sind signifikanter als die Zahlen der Basis 3).Ṣ. Beide Extraktionen beginnen also mit Ṣ, gefolgt von %3oder :3nach Bedarf.

Während die Ziffern der 1–41 noch in sortierter Reihenfolge sind, haben wir einen sehr praktischen / knappen Weg, um zu den Ziffern 0–35 der Basis 36 zurückzukehren. subtrahieren Sie einfach 1 von der ersten, 2 von der zweiten, 3 von der dritten und so weiter. In Jelly können wir das mit _J("subtract index") machen.

Währenddessen kehren wir im anderen Zweig der Dekodierung die Ziffern der Basis 3 wieder in order ( U) um und konvertieren sie von Basis 3 zurück in einen Permutationsindex mit ḅ3.

Wir können dann die beiden Zweige mit kombinieren œ?Ç; œ?bedeutet "permutieren bei gegebenem Permutationsindex" und Çbedeutet "das Ergebnis des Anwendens der darüber liegenden Zeile", dh es ist das, was Jelly anweist, beide Zeilen getrennt für dieselbe Eingabe auszuführen.

Was wir jetzt haben, sind die Ziffern der ursprünglichen Zahl, in der Basis 36 (aufgrund der _J) und in der ursprünglichen Reihenfolge (aufgrund der œ?), so dass wir einfach a tun können ḅ36, um von der Basis 36 in eine einzelne Ganzzahl zurück zu konvertieren.

Kommentar

Das TIO! Der obige Link verwendet 312699167 als zu verschlüsselnde Nummer. Diese Zahl in der Basis 36 ist [5, 6, 6, 8, 7, 35]und zeigt somit alle Aspekte der Codierung: Die 35 testet die Grenze des Bereichs von 0 bis 127, den wir haben; das Duplikat 6s testet die Auflösung identischer Ziffern in der ursprünglichen Basis 36; und die Tatsache, dass die Ziffern fast (aber nicht vollständig) sortiert sind, bedeutet, dass die Permutationszahl sehr klein ist, wodurch sie viel weniger Ziffern als die Basiszahl 36 aufweist und somit die Notwendigkeit zeigt, sie umzukehren, bevor sie zum Original hinzugefügt wird.

Es ist sehr praktisch, wie alle Konstanten hier zusammenpassen. 36 ⁶ ist nur gerade hoch genug, um 2 ³¹ , 3 ⁶ ist nur gerade hoch genug, um 6! Zu passen, und (36 + 6) × 3 ist nur gerade hoch genug, um in die 128 Möglichkeiten zu passen, die wir haben. (Die letzte Einschränkung ist die am wenigsten enge, da wir die 0-Indizierung anstelle der 1-Indizierung verwenden könnten, um Zeichen im Bereich 0-2 zu verwenden. Dennoch würde dies nur genug Platz bieten, um 37 als Basis zu verwenden als 36.)

Gelee , ( 4 3 Bytes + 6 5 Bytes) × Länge 8 = 80 64 Punkte

bä

ṢŻIṢŻ

Probieren Sie es online!

Gelee , ( 2 1 Byte + 4 3 Bytes) × Länge 10 = 60 40 Punkte

EIN

ṢŻI

Probieren Sie es online!

Erläuterung

Lösung 1

Dies verwendet einen anderen Algorithmus als die meisten anderen Antworten. Wir beginnen mit der Codierung des Wertes in hexadezimal ( b⁴), wie bei den anderen Antworten, und nehmen dann eine kumulative Summe ( Ä). Jede Eingabe gibt eindeutig eine andere Ausgabe aus (da beide Operationen umkehrbar sind), und vorausgesetzt, dass die hexadezimale Codierung höchstens 8 Stellen enthält, deren Maximum 7 (für die achte bis letzte Stelle) und 15 (für die letzte bis siebte Stelle) beträgt. letzte Stelle) beträgt die maximale Anzahl in der Ausgabeliste 7+ (7 × 15) = 112, weniger als die von der Frage geforderten 127. Außerdem muss die Ausgabe in sortierter Reihenfolge erfolgen, damit wir die Zufallswiedergabe umkehren können.

Für den Decoder kehren wir zuerst das Shuffle mit sort ( Ṣ) um; kehre dann die kumulative Summe um, indem du eine Null voranstellst ( Ż) und die Differenz aufeinanderfolgender Paare nimmst ( I); konvertiere dann zurück von hexadezimal ( ḅ⁴).

Lösung 2

Die Frage ermöglicht es uns, die Eingabe als Liste von (vermutlich dezimalen) Ziffern zu betrachten, sodass wir "schummeln" können, indem wir einfach die Basiskonvertierung entfernen. Die maximal in der Ausgabe verwendete Zahl ist dann 2 + (9 × 9) = 83 (tatsächlich 82, da 2999999999 außerhalb des Bereichs liegt, die schlechteste mögliche Eingabe also 1999999999). Die resultierende Codierung ist ziemlich schrecklich, da Codierungen für dieses Problem erforderlich sind, hat jedoch den Vorteil, dass sie sehr knapp zu generieren sind, was die Ausführlichkeit der Codierung überwiegt.

Diese Antwort fühlt sich so sehr wie Schummeln an, dass es nicht meine primäre Lösung für dieses Problem ist, aber es scheint, dass es sich lohnt, sie hinzuzufügen, da sie technisch den Regeln entspricht und eine bessere Punktzahl ergibt.

Kommentar

Ich habe einige Algorithmen im Sinn, um die Länge 8 zu unterschreiten, aber es scheint unwahrscheinlich, dass Sie einen Algorithmus der Länge 7 mit ≤ 9 Bytes (nicht betrügen) oder ≤ 5 Bytes (betrügen) implementieren können ist wahrscheinlich der beste Weg, um es zu tun. (Ich könnte trotzdem aus Spaß eine Lösung für die alternative Herausforderung "Minimiere die Länge der Codierung" ausprobieren.)

Anders als bei einigen anderen Lösungen ist die Verwendung von 16 als Basis hier nicht kritisch. Es gibt viele andere Zahlen, die für eine Lösung der Länge 8 funktionieren würden (z. B. 18). Ich habe 16 für die erste Lösung ausgewählt, nur weil Jelly eine 1-Byte-Methode hat, um dies darzustellen, und andere brauchbare Basen mehrere Bytes aus dem Programm verbrauchen müssten. Natürlich muss die zweite Lösung 10 als Basis verwenden, um die Lücke auszunutzen.

Vielen Dank an @Dennis für den Hinweis auf einige neuere Jelly-Befehle, die das Schreiben dieses Algorithmus noch schwieriger gemacht haben.

Shakespeare Programming Language , 10 * (264 + 494) = 8650 7910 7580

Encoder: 264 Bytes

,.Ajax,.Ford,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:Open mind.Be you nicer zero?You be the sum ofyou the product ofthe sum ofI a big big pig the sum ofa big big big big cat a big big pig.If soSpeak thy.Ford:You are the sum ofyou a cat.If soLet usAct I.

Probieren Sie es online!

Decoder: 494

,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:Open mind.Is you nicer a pig?If soRemember you.If soLet usAct I.Scene V:.Ford:Remember I.Ajax:Recall.Is you worse the sum ofPage twice the sum ofa big big cat a cat?If soYou be the difference betweenyou Page.If soOpen heart.If notlet usScene V.Scene X:.Ford:Recall.Ajax:Be I nicer zero?If soRemember I.If soLet usScene X.[Exit Ajax][Enter Page]Ford:You be the sum ofyou twice twice the sum ofa big big cat a pig.Let usAct I.

Probieren Sie es online!

Das war eine Sache.

Der Encoder codiert jede Ziffer als Ziffer plus dem Index der Ziffer mal zwölf. Der Decoder speichert alle Eingaben im Speicher des Ford und durchläuft dann eine Schleife über einen Zähler, wobei jede Stelle ausgegeben und gelöscht wird, die niedriger ist als der Zähler * 12 + 10.

Erläuterung:

Encoder

,.Ajax,.Ford,.Act I:.Scene I:.      Boilerplate introducing the two characters
[Exeunt][Enter Ajax and Ford]       Enter the two characters Ajax and Ford
                                    Ford will be handling the input
                                    Ajax will be the counter
Ajax:Open mind.                     Set Ford to the next character of input
Be you nicer zero?                  Check if it is EOF
You be the sum of                   Set Ford to the sum of 
    you                             His original value (48 to 58)
    the product of                 
          the sum of               
              I                     Ajax's value
              a big big pig         Minus 4 (this handles the offset of 48)
          the sum of                Multiplied by
              a big big big big cat 2^4
              a big big pig.        + -2^2 = 12
                                    This essentially sets Ford to (F+12*(A-4))
If soSpeak thy.                      If not EOF, print Ford's value
Ford:You are the sum ofyou a cat.   Increment Ajax's value
If soLet usAct I.                   If not EOF, Repeat again.

Decoder

,.Ajax,.Ford,.Page,.Act I:.Scene I:.  Boilerplate introducing three characters
                                      Ajax is the spare stack
                                      Ford is the storage stack
                                      Puck is the counter, increasing by 12
[Exeunt][Enter Ajax and Ford]            Enter Ajax and Ford onto the stage
Ajax:Open mind.                          Get the next character of input
Is you nicer a pig?                      If not EOF
If soRemember you.                         Store the value in Ford's memory
If soLet usAct I.                          And repeat the loop
Scene V:.                                Otherwise move to the next scene
Ford:Remember I.                         Store Ford's value (initially -1 from EOF) in Ajax's memory
Ajax:Recall.                             Get the next value from Ford's memory
Is you worse the sum of                  Is the value smaller than
        Puck                                  Puck's value
        twice the sum ofa big big cat a cat?  + 10 ?
                                              i.e. is it the next digit?
If soYou be the difference betweenyou Puck.   If so, subtract Puck's value from Ford
If soOpen heart.                              And print Ford's value
If notlet usScene V.                     If that was not the digit, repeat
Scene X:.
Ford:Recall.                             Get the next value from Ajax's memory
Ajax:Be I nicer zero?                    Until the -1
If soRemember I.                         Returning the values to Ford's memory
If soLet us Scene X.                     Repeat until Ajax's memory is exhausted
[Exit Ajax][Enter Page]                  Swap Ajax and Page
Ford:You be the sum of                   Set Puck's value to
              you                        Puck +   
              twice twice the sum of     2*2*(
                           a big big cat      4
                           a pig.             -1) = 12
Let usAct I.                             And start from the beginning again, having removed one number

Python 2.7, 31 * (52 + 37) = 2759

Encoder ( 69 52 Bytes):

lambda n:[chr(i)if n&(1<<i)else""for i in range(32)]

Decoder ( 41 37 Bytes):

lambda s:sum([1<<(ord(c))for c in s])

Speichert alle von Null verschiedenen Bits in der Eingangsnummer als ASCII-Werte. Der Wert des ASCII-Zeichens speichert die Position des gesetzten Bits. Zum Beispiel würde der Wert 'a' bedeuten, dass das 97. Bit gesetzt ist.

Ein paar Verbesserungen dank @ Delfad0r

Probieren Sie es online!

Stax , Ergebnis 8 × (10 + 9) = 152

Encoder, 10 Bytes

Ç·MÉJ'♀τ│½

Führen Sie es aus und debuggen Sie es

16|E{i16*+m Full program, implicit input
16|E        Get hexadecimal digits
    {     m Map:
     i16*+    Add 16 * loop index
            Implicit output as string

Der Encoder gibt den String in aufsteigender Reihenfolge aus.

Decoder, 9 Bytes

üL∟n╫k∞‼9

Führen Sie es aus und debuggen Sie es

o{16%m16|E Full program, implicit input
o          Sort string
 {16%m     Module each element by 16
      16|E Interpret as array of hex digits

05AB1E , 8 maximale Länge * (8 + 7) Bytes = 120

Encoder (8)

hεHN16*+

Probieren Sie es online!

Decoder (7)

{16%hJH

Probieren Sie es online!

Verwendet die gleiche Technik wie Wastl und Jonathan .

Python 3 , 8 * (45 + 38) = 664

Encoder (45 Bytes):

lambda n:[16*i+(n>>4*i)%16 for i in range(8)]

Decoder (38 Bytes):

lambda l:sum(x%16<<x//16*4 for x in l)

Probieren Sie es online!

JavaScript (ES6), 8 * (40 + 32) = 576

$0$$8$

Encoder (40 Bytes)

E=(n,k=0)=>n?[k|n&15,...E(n>>4,k+16)]:[]

Decoder (32 Bytes)

s=>s.map(c=>s|=c%16<<(c/4&~3))|s

Demo

Probieren Sie es online!

Wie?

Die Eingabe ist in 8 Blöcke mit jeweils 4 Bits unterteilt und jeder Block wird mit 1 von 16 möglichen Zeichen codiert. Das höchstwertige Bit des letzten Blocks wird niemals gesetzt.

       3222222222211111111110000000000
bit:   0987654321098765432109876543210
       \_/\__/\__/\__/\__/\__/\__/\__/
block:  7  6   5   4   3   2   1   0

block #0 is encoded with char. 00 to 0F (NUL to SI)
block #1 is encoded with char. 10 to 1F (DLE to ES)
block #2 is encoded with char. 20 to 2F (' ' to '/')
block #3 is encoded with char. 30 to 3F ('0' to '?')
block #4 is encoded with char. 40 to 4F ('@' to 'O')
block #5 is encoded with char. 50 to 5F ('P' to '_')
block #6 is encoded with char. 60 to 6F ('`' to 'o')
block #7 is encoded with char. 70 to 77 ('p' to 'w')

Jelly , (8 + 9) Bytes * 8 maximale Länge = 136

b⁴+J’Ɗ⁴¡

Encoder (Fußzeile formatiert die Liste aus Gründen der Übersichtlichkeit wie Python)

Ṣ_J‘Ɗ⁴¡ḅ⁴

Decoder

Es ist theoretisch möglich, eine maximale Länge von sechs zu haben. Kann das in 22 Bytes oder weniger geschehen?

Es ist unmöglich mit einer maximalen Länge von fünf da $\sum_{i=0}^{i=5}\binom{127+i}{127}=321402081< 2^{31}-1$

Wie?

Schon seit $2^{31}-1$kann als 8 hexadezimale Ziffern codiert werden ( 7fffffffoder [7,15,15,15,15,15,15,15]), dann können wir den auf Null basierenden Index jeder hexadezimalen Ziffer multipliziert mit 16 addieren, um sicherzustellen, dass eine solche Konvertierung immer in sortierter Reihenfolge erfolgt, wobei auch der am weitesten rechts stehende Wert (dh [7,15,15,15,15,15,15,15] + [0,16,32,48,64,80,96,112] = [7,31,47,63,79,95,111,127]) eingehalten wird . Das Decodieren kehrt dann denselben Prozess um.

Encoder :

b⁴+J’Ɗ⁴¡ - Link: integer, n    e.g. 1234
 ⁴       - literal 16               16          
b        - convert to base          [4,13,2]
       ¡ - repeat...
      ⁴  - ...16 times:
     Ɗ   -   last 3 links as a monad:
   J     -     range of length        [1,2,3]     iter 2    iter 3    ...  iter 16
  +      -     add                    [5,15,5]   [5,16,7]   [5,17,9]  ...  [5,30,35]
    ’    -     decrement              [4,14,4]   [4,15,6]   [4,16,8]  ...  [4,29,34]
         -                                                                 [4,29,34]

Decoder :

Ṣ_J‘Ɗ⁴¡ḅ⁴ - Link: list of integers   e.g. [29,34,4]
Ṣ         - sort                          [4,29,34]
      ¡   - repeat...
     ⁴    - ...16 times:
    Ɗ     -   last 3 links as a monad:
  J       -     range of length           [1,2,3]
 _        -     subtract                  [3,27,31]   [3,26,29]   [3,25,27]  ...  [3,12,1]
   ‘      -     increment                 [4,28,32]   [4,27,30]   [4,26,28]  ...  [4,13,2] 
        ⁴ - literal 16                    16
       ḅ  - from base                     1234

Shakespeare Programming Language , 31 * (472 + 383 379 344) = 26505 26381 25296

Bisherige Bewertung: 16909322 * (246 + 217) = 7829016086

Dies ist immer noch sehr hoch, aber es ist das niedrigste, an das ich momentan denken kann.

Encoder:

,.Ajax,.Ford,.Act I:.Scene I:.[Enter Ajax and Ford]Ajax:Remember a pig.Ford:Listen tothy.Scene V:.Ajax:Remember the remainder of the quotient betweenI a big cat.Ford:You be the quotient betweenyou a big cat.Be you nicer zero?If solet usScene V.Remember a pig.Scene X:.Ajax:Recall.Ford:Am I worse zero?If notremember I.If notlet usScene X.Ajax:You zero.Scene L:.Ford:Recall.Ajax:You be the sum ofyou a cat.Am I nicer zero?If sospeak thy.Am I worse zero?If notlet usScene L.

Probieren Sie es online!

Decoder:

,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:You cat.Ford:Open mind.Remember the sum ofyou I.Scene V:.Ajax:Am I nicer a cat?If soyou be twice you.Ford:If soyou be the sum ofyou a pig.If solet usScene V.[Exit Ford][Enter Page]Page:Recall.Ajax:Am I worse a cat?If notyou be the sum ofyou Ford.If notlet usAct I.Open heart

Probieren Sie es online!

Wenn die Zeichenfolge ein Zeichen mit dem ASCII-Code (n + 1) enthält, wird grundsätzlich die n-te Binärzahl festgelegt.

Python 3 (208 Bytes + 200 Bytes) * 6 Länge = 2448

Probieren Sie es online! (Enthält beide, das zusätzliche Byte ist der Zeilenumbruch zwischen ihnen).

-4 Bytes (-24 Punkte) durch Verwendung der leeren Liste (wodurch mehr Dinge bei 0 beginnen konnten)

Encoder (208 Byte)

def E(n,h=128):
    T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1
    d=l=0
    s=[]
    while n>=T(h,d):
        n-=T(h,d)
        d+=1
    for i in range(d):
        while n>=T(h-l,d+~i):
            n-=T(h-l,d+~i)
            l+=1
        s+=[l]
    return s

Decoder (200 Bytes)

def D(s):
    T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1
    s.sort()
    l=0
    d=len(s)
    n=sum(T(128,D)for D in range(d))
    for i in s:
        for j in range(l,i):
            n+=T(128-j,d-1)
        l=i
        d-=1
    return n

Beobachtungen:

• Das Mischen kann für streng nicht aufsteigende (dh sortierte) Listen verlustfrei rückgängig gemacht werden.

• Streng nicht ansteigende numerische Listen der gleichen Länge können vollständig sortiert werden (wie in Python).

• Wir können definieren, dass Listen zuerst nach Länge sortiert werden, um eine Gesamtreihenfolge aller sortierten Listen zu bilden.

• Wir können eine indizierbare Folge dieser Listen bilden, wenn wir definieren, dass die einzigen gültigen Werte in einer Liste Ganzzahlen von 0bis 127einschließlich sind (dh es gibt eine endliche Anzahl gültiger Listen mit Länge L).

Strategie:

• Drehregler: NSuchen Sie unter Angabe einer Zahl die Ngültige, nicht aufsteigende Liste.

• Decoder: Bei einer (gemischten) gültigen Liste sortieren Sie diese und geben den Index in der Reihenfolge der gültigen Listen zurück.

Allgemeine Code-Erklärung:

• T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1

• Berechnen Sie die nth d-simplex Zahl

  • Für d=0immer1

  • Für d=1, n(die Anzahl der Punkte in einer Reihe von Punkten mit Länge n)

  • Für d=2,$\sum_{i=1}^{n} i$, (die Anzahl der Punkte in einem Dreieck von Punkten mit Seitenlänge n)

  • Für d=3,$\sum_{j=1}^n \sum_{i=1}^{j} i$, (die Anzahl der Punkte in einem Tetraeder von Punkten mit Seitenlänge n)

Encoder Erklärung:

• def E(n,h=128): d=l=0, s=[]

• nist die Eingangsnummer, hist der "hohe Wert" (dh die höchste zulässige Zahl + 1), dist die Länge der Ausgabe, sist die Ausgabe, list der "niedrige Wert" (beginnend mit 0, wird später erklärt)

• while n>=T(h,d):, n-=T(h,d),d+=1

• Es gibt T(h,d)gültige Längenlisten d, und unsere Berechnung ist einfacher, wenn anstelle eines tatsächlichen Index nein Index relativ zur Liste [0]*d(am Index 0) angegeben wird n. Dies passt auch ddie Länge an, um für das Gegebene korrekt zu sein n.

• for i in range(d):

• Effektiv: "für die i+1th Nummer in der Liste"

  • Hier werde ich erklären l, der "niedrige Wert"

  • Nachdem eine Nummer in die Liste aufgenommen wurde, kann keine kleinere Nummer in die Liste aufgenommen werden (um sie sortiert zu halten). Dies list auch die letzte Nummer, die der Liste hinzugefügt wurde.

  • while n>=T(h-l,d+~i):, n-=T(h-l,d+~i),i+=1

  • Wenn nes zu groß ist, um mit ldieser "Ziffer" codiert zu werden , stellen Sie es nentsprechend ein und erhöhen Sie esl

  • s+=[l]

  • nMit einer lbei dieser "Ziffer" codieren .

  • Zuerst haben wir hOptionen, welche "Ziffer" als nächstes eingegeben werden soll, aber sobald wir eine "Ziffer" (die zugewiesen ist l) eingegeben haben, sind wir auf h-lOptionen für die nächste "Ziffer" beschränkt.

  • Zuerst gab es T(h,d) gültige Listen, aber wir haben eine "Ziffer" hinzugefügt l, wobei die Anzahl der verbleibenden "Ziffern" d-1und die Anzahl der gültigen nächsten "Ziffern" auf " verringert " wurde h-l, also die Anzahl der gültigen Listen danachT(h-l,d-1)

Erklärung zum Decoder:

• def D(s):, s.sort(), l=0,d=len(s)

• sist die (gemischte) Eingabeliste, also ist s.sort()es; list der "niedrige Wert" ( hder "hohe Wert" ist nur ein Literal 128s im Code, um Bytes zu sparen), nist die Ausgangsnummer,d ist die Länge.

• n=sum(T(128,D)for D in range(d))

• Einstellen n zu dem Punkt in der Sequenz von[0]*length

• for i in s:

• Für jede Ziffer:

  • for j in range(l,i):, n+=T(128-j,d-1)

  • Einstellen n zu dem Punkt in der Sequenz von[...prevdigits, thisdigit, 0...]

    • l=i: Stellen Sie den "niedrigen Wert" auf die letzte Ziffer ein

    • d-=1: Verringern Sie die Länge, da wir eine Ziffer verwendet haben

• return n: Nach n für alle Ziffern eingestellt wurde, ist es die richtige Zahl; Gib es zurück.

Tut mir leid, wenn dies nicht klar ist, aber hier ist meine originale, nicht mit Fehlern behaftete Debug-Version. Probieren Sie es online aus! , die die leere Liste nicht verwendet, ist also 1 von allen in dieser Version verwendeten Zahlen

Ruby , (36 + 29 Bytes) * 8, Punktzahl 520

Kodieren:

->n{(0..7).map{|x|(n>>x*=4)%16+x*4}}

Probieren Sie es online!

Dekodieren:

->a{a.sum{|x|x%16<<(x/4&28)}}

Probieren Sie es online!

Wie es funktioniert:

Die Nummer wird mit 4-Bit-Chunks und einem 3-Bit-Index codiert.

Der Decoder nimmt das Input-Array und setzt jedes Nibble wieder an seine Stelle.

Holzkohle , Punktzahl 10 * (10 + 15) = 250.

Verwendet dezimal; Die vorherige Lösung auf Basis von Base 16 erzielte 328 296 264 Punkte.

Kann nicht druckbare Zeichen ausgeben. Insbesondere die Eingabe von Zeichen 10 in Charcoal ist schwierig.

Encoder, 10 Bytes:

⭆⮌Ｓ℅⁺Ｉι×χκ

Probieren Sie es online!Link ist eine ausführliche Version des Codes.

Decoder, 15 Bytes:

ＩΣＥＳ×﹪℅ιχＸχ÷℅ιχ

Probieren Sie es online!Link ist eine ausführliche Version des Codes.

Die Version mit einer Liste von ganzen Zahlen ergibt 360 Punkte 296 (Basis 16; Dezimal würde 310 Punkte ergeben):

Encoder, 19 Bytes:

ＮθＩＥ⁸⁺﹪÷θＸ¹⁶ι¹⁶×¹⁶ι

Probieren Sie es online!Link ist eine ausführliche Version des Codes.

Decoder, 18 Bytes:

ＩΣＥＥ⁸Ｎ×﹪ι¹⁶Ｘ¹⁶÷ι¹⁶

Probieren Sie es online!Link ist eine ausführliche Version des Codes.

Version mit druckbaren Zeichen ergibt 360 (bisher 416) 384 368 in Basis 16):

Encoder, 19 Bytes:

⭆⮌Ｓ℅⁺Ｉι×χ⁺κ×⁵⊕׳÷κ⁵

Probieren Sie es online!Link ist eine ausführliche Version des Codes.

Decoder, 17 Bytes:

Ｆθ⊞υ⌈Φθ¬№υκ⭆υ﹪℅ιχ

Probieren Sie es online!Link ist eine ausführliche Version des Codes.

Brachylog , 17 + 18 Bytes * 8 Länge = 280

Encoder:

ḃ₁₆I∧7⟧₁;Iz₁~ḃ₁₆ᵐ

Decoder:

ḃ₁₆I∧7⟧₁;Iz₁~ḃ₁₆ᵐp

Ein p kann ohne Auswirkung an das Ende des Encoders angehängt werden. Der Decoder wird ausgeführt, indem das (gemischte) Ergebnis als Ausgabe verwendet und die ursprüngliche Nummer in die Eingabe übernommen wird.

Wenn es ein (ordnungsgemäß implementiertes) kumulatives Summenprädikat geben würde, könnte die Punktzahl auf 20 fallen

Probieren Sie es online!

05AB1E , Ergebnis: (2 + 2 Bytes ) * 11 maximale Länge = 44

Encoder (2 Bytes ):

.¥

Probieren Sie es online aus.

Decoder (2 Bytes ):

{¥

Probieren Sie es online aus.

Die Eingabe des Codierers und die Ausgabe des Decodierers sind eine Liste von Ziffern.

Port von @ ais523s 2. Gelee Antwort .

Erläuterung:

.¥    # Undelta (automatically prepends a 0)
      #  i.e. [3,0,4,7,8,2,0,1,9] → [0,3,3,7,14,22,24,24,25,34]

{     # Sort
      #  i.e. [14,7,22,25,24,3,0,24,34,3] → [0,3,3,7,14,22,24,24,25,34]
 ¥    # Deltas
      #  i.e. [0,3,3,7,14,22,24,24,25,34] → [3,0,4,7,8,2,0,1,9]

Da der .¥Ausgabe eine Null vorangestellt wird, entspricht die Länge der Ausgabe der Länge der Eingabe + 1. Since$2^{31}-1$ hat eine Länge von 10 Stellen, die maximale Länge der Ausgabe ist 11.

Gol> <> , 8 * (14 + 13) = 216

Encoder Probieren Sie es online! 14 Bytes:

I8FfPSD8*L+o|;

Decoder Probieren Sie es online! 13 Bytes:

iEh8SD4*2$X*+

Da dies nicht druckbare ASCII-Zeichen ausgeben kann und somit mit dem Decoder in Konflikt gerät, gibt es jetzt eine Version, die Zahlen in der Ausgabe / Eingabe verwendet:

Encoder Probieren Sie es online! 14 Bytes:

I8FfPSD8*L+N|;

Decoder Probieren Sie es online! 13 Bytes:

IEh8SD4*2$X*+

Codierung:

Die Codierung erfolgt durch Aufteilen der angegebenen Zahl in 8 x 4-Bit-Blöcke. Diese Chunks werden dann um 3 Bit nach rechts verschoben und die ursprüngliche Position des Chunks wird am Ende als Zahl zwischen 0 und 7 angehängt. Die Codierung sieht also folgendermaßen aus:

0AAAABBB
 |__|    -> the original part of the number
     |_| -> the position of the chunk inside the original number 0 = LSB and 7 = MSB

6 Perl , 10 * (10 + 12) = 340 220

Encoder:

{^@_ Z~@_}

Decoder:

{.sort X%10}

Probieren Sie es online!

Die Encoder-Funktion zippt jede Ziffer mit dem 0-Index der Nummer. Dann sortiert der Encoder die Liste der Zahlen und erhält das Modulo um 10, dh die zweite Ziffer der Zahl.

Die Summe ist 10, da dies die maximale Länge von 2 ³¹ -1 ist.

Haskell , 10 * (23 + 51) = 740

Hier ist ein Programm, das Werte codiert, mischt, decodiert und validiert: Probieren Sie es online aus!

Encoder, 23 Bytes

zipWith((+).(10*))[0..]

Probieren Sie es online!

Decoder, 51 Bytes

map snd.sortOn fst.map(`divMod`10)
import Data.List

Probieren Sie es online!

Erläuterung

Da wir die Eingabe als Dezimalstellen verwenden dürfen, werden wir diese verwenden. Der Encoder ordnet jede Ziffer zu, die vorkommt 10*index + digit. Beachten Sie, dass sich alle digits in befinden, [0..9]damit wir das Obige mit umkehren können divMod. Nach dem Wiederherstellen der Indizes und Ziffern muss nur noch nach den Indizes sortiert und diese entfernt werden.

Es wird erwartet, dass die Lösung für Werte bis zu funktioniert $2^{31} - 1 = 2147483647$ Das ist 10 Stellen lang, also wird der maximale Code-Punkt sein, den wir bekommen $9 \cdot 9 = 81 < 128$. Außerdem wird jede Ziffer in ein "Zeichen" umgewandelt, sodass wir eine maximale Länge von 10 haben.

Schale , 10 × (7 + 8) = 150

Gerader Port meiner Haskell-Lösung nur mit der Beobachtung, dass $10 \cdot 9 = 90 < 128$(Husk's Nist 1-basiert):

Encoder, 7 Bytes

zo+*10N

Probieren Sie es online!

Decoder, 8 Bytes

m→Ö←m‰10

Probieren Sie es online!

APL (Dyalog Unicode) ,$L_E+L_D=36; A=8 \rightarrow 288$.

d←{16⊥n-16×⍳≢n←⍵[⍋⍵]}
e←(⊢+16×⍳∘≢)16⊥⍣¯1⊢

Probieren Sie es online! (enthält 5 zusätzliche Bytes für die Zuweisungen und die Newline).

Verwendet ⎕IO←0

Wie:

(⊢+16×⍳∘≢)16⊥⍣¯1⊢ ⍝ Encoder; input 1234
          16⊥⍣¯1⊢ ⍝ Convert input to base 16 → 4 13 2
      ⍳∘≢          ⍝ [0..length of the list-1] → 0 1 2
   16×             ⍝ times 16 → 0 16 32
 ⊢+                ⍝ plus the original list → 4 29 34

{16⊥n-16×⍳≢n←⍵[⍋⍵]} ⍝ Decoder; input ⍵ → 34 4 29
              [⍋⍵]  ⍝ Grade ⍵ up → 2 0 1
             ⍵      ⍝ Index ⍵ with that list → 4 29 34
           n←       ⍝ assign that to n
      16×⍳≢         ⍝ 16×[0..length(n)-1] → 0 16 32
    n-              ⍝ subtract that from n → 4 13 2
 16⊥                ⍝ Decode from base 16 → 1234

PHP, 8 * (44 + 53) = 776

Encoder, 44 Bytes:

for(;$n=&$argn;$n>>=4)echo$n&15|16*$i++," ";

Gibt eine durch Leerzeichen getrennte Liste von Ganzzahlen aus. Als Rohr mit laufen lassen -nR.

Maximal 8 Bytes mit 4 Datenbits (unteres Halbbyte) und 3 Gewichtungsbits (oberes Halbbyte).

Einfach ausgedrückt:
Setzen Sie jede hexadezimale Ziffer in ein eigenes Zeichen und speichern Sie die Position der Ziffer in der oberen Hälfte des Bytes.

Beispiel:

1457893891( 0x56e5b203) Wird in drehen
0x03, 0x10, 0x22, 0x3b, 0x45, 0x5e, 0x66, 0x75
→3 16 34 59 69 94 102 117

Decoder, 53 Bytes:

while($i++<8)$n+=(15&$x=$argv[$i])<<($x>>4)*4;echo$n;

oder

while($i++<8)$n+=(15&$x=$argv[$i])<<($x/4&~3);echo$n;

oder

for(;$i<9;$x=$argv[++$i])$n+=$x%16<<($x/4&~3);echo$n;

Nehmen Sie Ganzzahlen aus Befehlszeilenargumenten. Laufen Sie mit -nr.

Probieren Sie sie online aus .

Python 2 , 10 * (68 + 54) = 1220

e=lambda n:"".join(chr(int(`i`+j))for i,j in enumerate(`n`)if j<'L')
d=lambda s:int("".join(`ord(c)%10`for c in sorted(s)))

Probieren Sie es online!

EDIT: Danke an Jo King für die Hinweise - nicht sicher, warum ich im Nachhinein um 32 versetzt habe.

Codiert die Position und den Wert jedes Ortes als ein einzelnes Zeichen, beginnend mit [Leerzeichen] (Position 0, Wert 0) dem NUL-Byte 0x0.

Dekodiert von:

• Sortieren der Zeichenfolge (Python sortiert Zeichen nach ihrem Ordnungswert)
• konvertiert jedes Zeichen in seinen Ordnungswert
• Nimmt die letzte Ziffer jeder Ordnungszahl
• Verbindet die ganzen Zahlen zu einer Zeichenkette
• wandelt den verbundenen String wieder in einen int um

C (gcc) , 10 · 112 = 1120

c,i;e(i,s)char*s;{for(c=1;i;c+=10,i/=10)*s++=c+i%10;*s=0;}
d(char*s){for(i=0;c=*s++;i+=--c%10*pow(10,c/10));s=i;}

Probieren Sie es online!

Ich habe globale Variablen, aber sie geben tatsächlich keine Informationen zwischen zwei Funktionen weiter. Die Variablendeklaration für cwird in beiden Funktionen verwendet, um 2 Byte Codelänge zu sparen.

Eine Version, die druckbares ASCII nur für eine 3 5-Byte-Strafe verwendet, ist hier:

c,i;e(i,s)char*s;{for(c=32;i;c+=10,i/=10)*s++=c+i%10;*s=0;}
d(char*s){for(i=0;c=*s++;i+=(c-=32)%10*pow(10,c/10));s=i;}

Vielen Dank an @ceilingcat für 70 Punkte Verbesserungen.