Schreiben Sie einen strahlengehärteten Strahler

17

Die Aufgabe besteht darin, einen strahlengehärteten Strahler zu schreiben. Was meine ich damit genau?

Ein Strahler ist ein Programm, das bei Eingabe einer Zeichenfolge alle möglichen Versionen der Zeichenfolge mit einem entfernten Zeichen ausgibt. Anhand der Eingabe Hello, world!sollte das Programm beispielsweise Folgendes ausgeben:

ello, world!
Hllo, world!
Helo, world!
Helo, world!
Hell, world!
Hello world!
Hello,world!
Hello, orld!
Hello, wrld!
Hello, wold!
Hello, word!
Hello, worl!
Hello, world

Ein Strahler muss jedoch vor seiner Strahlung geschützt werden, sodass der von Ihnen geschriebene Strahler auch dann überleben muss, wenn er von selbst durchdrungen wird. Das heißt, wenn ein einzelnes Byte Ihres Programms entfernt wird, muss das Programm weiterhin ordnungsgemäß funktionieren.

Testfälle

abc -> bc; ac; ab
foo bar -> oo bar:fo bar:fo bar:foobar:foo ar:foo br:foo ba
source -> ource;surce;sorce;souce;soure;sourc;

Spezifikationen

  • Sie können nach unseren Standard-E / A-Regeln Eingaben auf jede akzeptable Weise vornehmen
  • Die Ausgabe kann entweder eine Liste von Zeichenfolgen oder eine gedruckte Liste sein, die durch ein Zeichen oder eine Gruppe von Zeichen begrenzt ist. Ein nachgestelltes Trennzeichen ist zulässig
  • Die Ausgabe kann in beliebiger Reihenfolge erfolgen, sofern alle möglichen Versionen enthalten sind
  • Doppelte Einträge (wie die beiden Helo, world!im ersten Beispiel) können herausgefiltert werden, dies ist jedoch nicht erforderlich
  • Da es sich um , das kleinste Programm, in Bytes, gewinnt
TheOnlyMrCat
quelle
... oder Komma vielleicht?
Jonathan Allan
4
Dieser ist wirklich für Golf-Sprachen, weil C-Programm mit vin voidentfernt nicht kompilieren
Krzysztof Szewczyk
3
@Krzysztof tbh Ich denke, die meisten, wenn nicht alle praktischen Sprachen überleben die Strahlenhärtung aufgrund der Ausführlichkeit und der Syntax nicht. Nicht nur diese Herausforderung, sondern ALLE RH-Herausforderungen.
Shieru Asakoto

Antworten:

13

05AB1E , 29 26 Bytes

æIg<ùˆ\æIg<ùˆ\æIg<ùˆ¯¯{Å`s

Probieren Sie es online! , oder versuchen Sie es mit allen bestrahlten Versionen .

Der kürzeste Strahler, den ich finden konnte, ist 5 Bytes:

æ        # powerset of the input
 Ig      # length of the input
   <     # - 1
    ù    # elements of a with length b

Die Idee ist, dies dreimal zu wiederholen und dann mit der Mehrheit abzustimmen:

æIg<ù         # irradiate
     ˆ        # add the result to the global array
      \       # pop (in case the above instruction gets irradiated)
æIg<ùˆ\       # idem
æIg<ùˆ        # no pop, it's okay to dirty the stack at this point
¯             # push global array
 ¯            # and again, so at least one goes through
  {           # sort
   Å          # conveniently ignored by the parser
    `         # dump
     s        # swap
              # and implicitly output

Å ist ein Präfix für 2-Byte-Befehle, aber es gibt keine Å` Befehl, weshalb der Åignoriert wird. Wir werden es aber später brauchen.

Durch das Sortieren wird sichergestellt, dass sich die Mehrheitsabstimmung in der Mitte des Arrays befindet. Durch Dumping und anschließendes Austauschen wird dieser Wert an die Spitze des Stapels verschoben.

Jede Bestrahlung im ersten Teil führt nur zu einem Fehler im globalen Array, der durch die Mehrheitsabstimmung behoben wird. Bestrahlungen im letzten {Å`sBit sind viel schwieriger zu beurteilen:

  • Å wird sowieso ignoriert, es ist also in Ordnung, es zu bestrahlen

  • Wenn der Backtick bestrahlt Å`swird Ås, wird der erweiterte Befehl "Mitte des Arrays abrufen" angezeigt .

  • Wenn {oder sbestrahlt werden, bedeutet dies, dass nichts anderes vorhanden ist. Das globale Array hat also dreimal den gleichen Wert. In diesem Fall müssen wir nicht sortieren / tauschen, jeder Wert wird funktionieren.

Grimmig
quelle
3
Sehr beeindruckend! Ich hätte nicht gedacht, dass ich bei einer RH-Herausforderung eine 05AB1E-Antwort sehen würde. Ich werde sofort eine Prämie hinzufügen, um diese Antwort zu belohnen (und der Herausforderung auch ein bisschen mehr Aufmerksamkeit zu schenken, denke ich). Sie haben so viele Antworten von mir golfen, also verdienen Sie auch eine Menge Anerkennung für diese! :)
Kevin Cruijssen
3
Eigentlich habe ich 05AB1E-Antworten bei einer RH-Herausforderung schon einmal gesehen . Trotzdem sehr beeindruckend!
Kevin Cruijssen
5

8086-Computercode (MS-DOS .COM), 83 Byte

Kann in DOSBox oder Ihrer bevorzugten dampfbetriebenen Computer-Engine ausgeführt werden. Die zu bestrahlende Zeichenfolge wird als Befehlszeilenargument angegeben.

Binär:

00000000 : EB 28 28 8A 0E 80 00 49 BD 83 00 B4 02 51 8A 0E : .((....I.....Q..
00000010 : 80 00 BE 82 00 AC 39 EE 74 04 88 C2 CD 21 E2 F5 : ......9.t....!..
00000020 : 59 45 B2 0A CD 21 E2 E5 C3 90 EB D7 D7 8A 0E 80 : YE...!..........
00000030 : 00 49 BD 83 00 B4 02 51 8A 0E 80 00 BE 82 00 AC : .I.....Q........
00000040 : 39 EE 74 04 88 C2 CD 21 E2 F5 59 45 B2 0A CD 21 : 9.t....!..YE...!
00000050 : E2 E5 C3                                        : ...

Lesbar:

cpu 8086
org 0x100
    jmp part2
    db 0x28

part1:
    mov cl, [0x80]
    dec cx
    mov bp, 0x83
    mov ah, 0x02

.l:
    push cx
    mov cl, [0x80]
    mov si, 0x82
.k:
    lodsb
    cmp si, bp
    je .skip
    mov dl, al
    int 0x21
.skip:
    loop .k
    pop cx
    inc bp
    mov dl, 10
    int 0x21
    loop .l
    ret

    nop
part2:
    jmp part1
    db 0xd7
    mov cl, [0x80]
    dec cx
    mov bp, 0x83
    mov ah, 0x02

.l:
    push cx
    mov cl, [0x80]
    mov si, 0x82
.k:
    lodsb
    cmp si, bp
    je .skip
    mov dl, al
    int 0x21
.skip:
    loop .k
    pop cx
    inc bp
    mov dl, 10
    int 0x21
    loop .l
    ret

Heruntergewirtschaftet

Der aktive Teil wird dupliziert, so dass immer einer von der Strahlung unberührt bleibt. Wir wählen die gesunde Version durch Sprünge aus. Jeder Sprung ist ein kurzer Sprung und somit nur zwei Bytes lang, wobei das zweite Byte die Verschiebung (dh die Entfernung zum Sprung mit vorzeichenbestimmender Richtung) ist.

Wir können den Code in vier Teile aufteilen, die bestrahlt werden könnten: Sprung 1, Code 1, Sprung 2 und Code 2. Es soll sichergestellt werden, dass immer ein sauberer Codeteil verwendet wird. Wenn einer der Codeteile bestrahlt wird, muss der andere ausgewählt werden. Wenn jedoch einer der Sprünge bestrahlt wird, sind beide Codeteile sauber, sodass es egal ist, welcher ausgewählt wird.

Der Grund für das Vorhandensein von zwei Sprungteilen besteht darin, die Bestrahlung im ersten Teil durch Überspringen festzustellen. Wenn der erste Codeteil bestrahlt wird, bedeutet dies, dass wir ein Byte vor der Markierung ankommen. Wenn wir sicherstellen, dass eine solche verpatzte Landung Code 2 und eine richtige Landung Code 1 auswählt, sind wir golden.

Für beide Sprünge duplizieren wir das Verschiebungsbyte, wodurch jeder Sprungteil 3 Bytes lang wird. Dies stellt sicher, dass die Bestrahlung in einem der beiden letzten Bytes den Sprung weiterhin gültig macht. Die Bestrahlung im ersten Byte verhindert den Sprung, da die letzten beiden Bytes einen völlig anderen Befehl bilden.

Mach den ersten Sprung:

EB 28 28        jmp +0x28 / db 0x28

Wenn eines der 0x28Bytes entfernt wird, springt es immer noch an dieselbe Stelle. Wenn das 0xEBByte entfernt wird, erhalten wir stattdessen

28 28           sub [bx + si], ch

Dies ist eine harmlose Anweisung für MS-DOS (andere Varianten stimmen möglicherweise nicht überein), und dann fahren wir mit Code 1 fort, der sauber sein muss, da der Schaden bei Sprung 1 lag.

Wenn der Sprung gemacht ist, landen wir beim zweiten Sprung:

EB D7 D7        jmp -0x29 / db 0xd7

Wenn diese Bytesequenz intakt ist und wir direkt auf der Markierung landen, bedeutet dies, dass Code 1 sauber war und dieser Befehl zu diesem Teil zurückspringt. Das duplizierte Verschiebungsbyte garantiert dies, auch wenn eines dieser Verschiebungsbytes beschädigt wurde. Wenn wir entweder ein Byte weniger landen (wegen eines beschädigten Codes 1 oder Sprung 1) oder das 0xEBByte das beschädigte ist, sind die beiden verbleibenden Bytes auch hier gutartig:

D7 D7           xlatb / xlatb

Wie auch immer, wenn wir diese beiden Anweisungen ausführen, wissen wir, dass entweder Sprung 1, Code 1 oder Sprung 2 bestrahlt wurden, wodurch ein Durchbruch zu Code 2 sicher ist.

Testen

Das folgende Programm wurde verwendet, um automatisch alle Versionen der .COM-Datei zu erstellen. Außerdem wird eine BAT-Datei erstellt, die in der Zielumgebung ausgeführt werden kann, in der jede bestrahlte Binärdatei ausgeführt wird, und deren Ausgaben werden an separate Textdateien weitergeleitet. Der Vergleich der Ausgabedateien zur Validierung ist recht einfach, DOSBox jedoch nicht. Daher fcwurde sie nicht zur BAT-Datei hinzugefügt.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    FILE *fin, *fout, *fbat;
    int fsize;
    char *data;

    if (!(fin = fopen(argv[1], "rb")))
    {
        fprintf(stderr, "Could not open input file \"%s\".\n", argv[1]);
        exit(1);
    }

    if (!(fbat = fopen("tester.bat", "w")))
    {
        fprintf(stderr, "Could not create BAT test file.\n");
        exit(2);
    }

    fseek(fin, 0L, SEEK_END);
    fsize = ftell(fin);
    fseek(fin, 0L, SEEK_SET);

    if (!(data = malloc(fsize)))
    {
        fprintf(stderr, "Could not allocate memory.\n");
        exit(3);
    }

    fread(data, 1, fsize, fin);

    fprintf(fbat, "@echo off\n");

    for (int i = 0; i < fsize; i++)
    {
        char fname[512];

        sprintf(fname, "%03d.com", i);
        fprintf(fbat, "%s Hello, world! > %03d.txt\n", fname, i);

        fout = fopen(fname, "wb");

        fwrite(data, 1, i, fout);
        fwrite(data + i + 1, 1, fsize - i - 1, fout);

        fclose(fout);
    }

    free(data);
    fclose(fin);
    fclose(fbat);
}
Gastropner
quelle