La tâche consiste à écrire un irradiateur durci aux radiations. Qu'est-ce que je veux dire par là, exactement?

Un irradiateur est un programme qui, lorsqu'il reçoit une chaîne en entrée, sortira toutes les versions possibles de la chaîne avec un caractère supprimé. Par exemple, étant donné l'entrée Hello, world!, le programme devrait sortir:

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

Un irradiateur, cependant, doit être protégé de son rayonnement, de sorte que l'irradiateur que vous écrivez doit également survivre lorsqu'il est traversé. Autrement dit, lorsqu'un octet unique de votre programme est supprimé, le programme doit toujours fonctionner correctement.

Cas de test

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;

Caractéristiques

• Vous pouvez prendre la saisie par toute méthode acceptable selon nos règles d'E / S standard
• La sortie peut être soit une liste de chaînes, soit une liste imprimée délimitée par un caractère ou un groupe de caractères. Un délimiteur de fin est acceptable
• La sortie peut être dans n'importe quel ordre tant qu'elle contient toutes les versions possibles
• Entrées en double (telles que les deux Helo, world! s dans le premier exemple) peuvent être filtrées, mais ce n'est pas nécessaire
• Comme il s'agit de code-golf , le plus petit programme, en octets, gagne

05AB1E , 29 26 octets

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

Essayez-le en ligne! ou essayez toutes les versions irradiées .

L'irradiateur le plus court que j'ai pu trouver est de 5 octets:

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

L'idée est de répéter cela 3 fois, puis de voter à la majorité:

æ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

Åest un préfixe pour les commandes à 2 octets, mais il n'y a pas de Å`commande, c'est pourquoi le Åest ignoré. Nous en aurons besoin plus tard, cependant.

Le tri garantit que le vote majoritaire se trouve au milieu du tableau. Le vidage puis l'échange permettent d'obtenir cette valeur en haut de la pile.

Toute irradiation dans la partie initiale se traduit uniquement par une erreur dans le tableau global, qui est résolue par le vote majoritaire. Les irradiations dans le {Å`sbit final sont beaucoup plus difficiles à raisonner:

• Å est ignoré de toute façon, il est donc normal de l'irradier

• Si le backtick est irradié, Å`sdevient Ås, qui est la commande étendue "get middle of the array".

• Si {ou ssont irradiés, cela signifie que rien d'autre ne l'est, donc le tableau global a la même valeur trois fois. Dans ce cas, nous n'avons pas besoin de trier / échanger, n'importe quelle valeur fonctionnera.

Code machine 8086 (MS-DOS .COM), 83 octets

Exécutable dans DOSBox ou votre moteur de calcul à vapeur préféré. La chaîne à irradier est donnée comme argument de ligne de commande.

Binaire:

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                                        : ...

Lisible:

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

Fatigué

La partie active est dupliquée afin qu'il y en ait toujours une non touchée par le rayonnement. Nous sélectionnons la version saine au moyen de sauts. Chaque saut est un saut court, et ne fait donc que deux octets de long, où le deuxième octet est le déplacement (c'est-à-dire la distance à sauter, le signe déterminant la direction).

Nous pouvons diviser le code en quatre parties qui pourraient être irradiées: saut 1, code 1, saut 2 et code 2. L'idée est de s'assurer qu'une partie de code propre est toujours utilisée. Si l'une des parties de code est irradiée, l'autre doit être choisie, mais si l'un des sauts est irradié, les deux parties de code seront propres, donc peu importe celle qui est choisie.

La raison d'avoir deux parties de saut est de détecter l'irradiation dans la première partie en sautant par-dessus. Si la première partie du code est irradiée, cela signifie que nous arriverons à un octet de la marque. Si nous nous assurons qu'un tel atterrissage bâclé sélectionne le code 2 et qu'un atterrissage correct sélectionne le code 1, nous sommes en or.

Pour les deux sauts, nous dupliquons l'octet de déplacement, ce qui fait que chaque partie de saut dure 3 octets. Cela garantit que l'irradiation dans l'un des deux derniers octets rendra toujours le saut valide. L'irradiation dans le premier octet empêchera le saut de se produire du tout, puisque les deux derniers octets formeront une instruction complètement différente.

Faites le premier saut:

EB 28 28        jmp +0x28 / db 0x28

Si l'un des 0x28octets est supprimé, il sautera toujours au même endroit. Si l' 0xEBoctet est supprimé, nous finirons à la place avec

28 28           sub [bx + si], ch

qui est une instruction bénigne sur MS-DOS (d'autres saveurs peuvent ne pas être d'accord), puis nous passons au code 1, qui doit être propre, car les dommages étaient au saut 1.

Si le saut est fait, on atterrit au deuxième saut:

EB D7 D7        jmp -0x29 / db 0xd7

Si cette séquence d'octets est intacte et que nous atterrissons directement sur la marque, cela signifie que le code 1 était propre et cette instruction revient à cette partie. L'octet de déplacement dupliqué garantit cela, même si c'est l'un de ces octets de déplacement qui a été endommagé. Si nous atterrissons un octet (en raison d'un code 1 endommagé ou d'un saut 1) ou si l' 0xEBoctet est celui endommagé, les deux octets restants seront également ici bénins:

D7 D7           xlatb / xlatb

Quel que soit le cas, si nous finissons par exécuter ces deux instructions, nous savons que le saut 1, le code 1 ou le saut 2 ont été irradiés, ce qui rend la transition vers le code 2 sûre.

Essai

Le programme suivant a été utilisé pour créer automatiquement toutes les versions du fichier .COM. Il crée également un fichier BAT qui peut être exécuté dans l'environnement cible, qui exécute chaque binaire irradié et dirige leurs sorties vers des fichiers texte séparés. La comparaison des fichiers de sortie à valider est assez simple, mais DOSBox n'en a pas fc, elle n'a donc pas été ajoutée au fichier BAT.

#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);
}