Zadanie polega na napisaniu utwardzanego promieniowaniem napromieniacza. Co mam dokładnie na myśli?

Naświetlacz to program, który po podaniu ciągu jako danych wyjściowych wyświetli wszystkie możliwe wersje ciągu z usuniętym jednym znakiem. Na przykład, biorąc pod uwagę dane wejściowe Hello, world!, program powinien wypisać:

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

Naświetlacz musi jednak być chroniony przed jego promieniowaniem, więc napisany przez niego naświetlacz musi również przetrwać po jego przepuszczeniu. Oznacza to, że po usunięciu dowolnego bajtu programu program musi nadal działać poprawnie.

Przypadki testowe

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;

Dane techniczne

• Możesz przyjmować dane wejściowe dowolną akceptowalną metodą według naszych standardowych zasad We / Wy
• Wynik może być listą ciągów lub listą drukowaną ograniczoną znakiem lub grupą znaków. Końcowy ogranicznik jest dopuszczalny
• Dane wyjściowe mogą być w dowolnej kolejności, o ile zawierają wszystkie możliwe wersje
• Zduplikowane wpisy (takie jak dwa Helo, world!w pierwszym przykładzie) mogą zostać odfiltrowane, ale nie jest to konieczne
• Ponieważ jest to kod-golf , wygrywa najmniejszy program w bajtach

05AB1E , 29 26 bajtów

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

Wypróbuj online! lub wypróbuj wszystkie napromieniowane wersje .

Najkrótszy naświetlacz, jaki udało mi się znaleźć, to 5 bajtów:

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

Chodzi o to, aby powtórzyć to 3 razy, a następnie przeprowadzić głosowanie większością głosów:

æ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

Åjest prefiksem dla komend 2-bajtowych, ale nie ma Å`komendy, dlatego Åignoruje się. Będziemy go jednak potrzebować później.

Sortowanie zapewnia, że ​​większość głosów znajduje się na środku tablicy. Zrzucanie, a następnie zamiana przenosi tę wartość na szczyt stosu.

Wszelkie napromieniowanie w części początkowej powoduje jedynie błąd w tablicy globalnej, który zostaje rozwiązany przez głosowanie większością. Napromienianie w ostatnim {Å`sfragmencie jest znacznie trudniejsze do uzasadnienia:

• Å i tak jest ignorowane, więc można go napromieniować

• Jeśli promieniowanie wsteczne zostanie napromieniowane, Å`sstaje się Ås, co jest rozszerzonym poleceniem „pobierz środek tablicy”.

• Jeśli {lub ssą napromieniowane, oznacza to, że nic innego nie jest, więc tablica globalna ma tę samą wartość trzy razy. W takim przypadku nie potrzebujemy sortowania / zamiany, każda wartość będzie działać.

Kod maszynowy 8086 (MS-DOS .COM), 83 bajty

Można go uruchomić w DOSBox lub ulubionym silniku obliczeniowym napędzanym parą. Ciąg do napromieniowania podano jako argument wiersza poleceń.

Dwójkowy:

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

Czytelny:

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

Zniszczony

Część aktywna jest powielana, tak że zawsze istnieje część nietknięta przez promieniowanie. Zdrową wersję wybieramy za pomocą skoków. Każdy skok jest krótkim skokiem, a więc ma tylko dwa bajty długości, gdzie drugi bajt to przemieszczenie (tj. Odległość do skoku, ze znakiem określającym kierunek).

Możemy podzielić kod na cztery części, które można napromieniować: skok 1, kod 1, skok 2 i kod 2. Chodzi o to, aby zawsze używać czystej części kodu. Jeśli jedna z części kodu jest napromieniowana, druga musi zostać wybrana, ale jeśli jedna ze skoków zostanie napromieniowana, obie części kodu będą czyste, więc nie będzie miało znaczenia, która zostanie wybrana.

Powodem posiadania dwóch części skoku jest wykrycie napromieniowania w pierwszej części przez przeskoczenie nad nim. Jeśli pierwsza część kodu zostanie napromieniowana, oznacza to, że dotrzemy o jeden bajt od znaku. Jeśli upewnimy się, że takie nieudane lądowanie wybiera kod 2, a prawidłowe lądowanie wybiera kod 1, jesteśmy złoci.

Dla obu skoków duplikujemy bajt przemieszczenia, dzięki czemu każdy skok ma długość 3 bajtów. Zapewnia to, że napromieniowanie jednego z dwóch ostatnich bajtów nadal sprawi, że skok będzie ważny. Napromieniowanie pierwszego bajtu w ogóle zatrzyma skok, ponieważ ostatnie dwa bajty utworzą zupełnie inną instrukcję.

Wykonaj pierwszy skok:

EB 28 28        jmp +0x28 / db 0x28

Jeśli jeden z 0x28bajtów zostanie usunięty, nadal przeskoczy w to samo miejsce. Jeśli 0xEBbajt zostanie usunięty, zamiast tego skończymy na

28 28           sub [bx + si], ch

co jest łagodną instrukcją na MS-DOS (inne smaki mogą się nie zgadzać), a następnie przechodzimy do kodu 1, który musi być czysty, ponieważ obrażenia były w skoku 1.

Jeśli skok zostanie wykonany, lądujemy przy drugim skoku:

EB D7 D7        jmp -0x29 / db 0xd7

Jeśli ta sekwencja bajtów jest nienaruszona, a my wylądujemy dokładnie na znaku, oznacza to, że kod 1 był czysty, a instrukcja wraca do tej części. Powielony bajt przemieszczenia gwarantuje to, nawet jeśli jest to jeden z tych bajtów przemieszczenia, który został uszkodzony. Jeśli wylądujemy jeden bajt (z powodu uszkodzonego kodu 1 lub skoku 1) lub 0xEBbajt jest uszkodzony, dwa pozostałe bajty również tutaj będą łagodne:

D7 D7           xlatb / xlatb

W każdym przypadku, jeśli wykonamy te dwie instrukcje, wiemy, że albo skok 1, kod 1, albo skok 2 zostały napromieniowane, co sprawia, że ​​przejście do kodu 2 jest bezpieczne.

Testowanie

Poniższy program został użyty do automatycznego utworzenia wszystkich wersji pliku .COM. Tworzy również plik BAT, który można uruchomić w środowisku docelowym, w którym działa każdy napromieniowany plik binarny, i przekazuje dane wyjściowe do osobnych plików tekstowych. Porównywanie plików wyjściowych do sprawdzenia jest dość łatwe, ale DOSBox nie ma fc, więc nie został dodany do pliku 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);
}