Задача состоит в том, чтобы написать радиационно-стойкий облучатель. Что я имею в виду именно?

Облучатель - это программа, которая при вводе строки в качестве входных данных выведет все возможные версии строки с одним удаленным символом. Например, с учетом ввода Hello, world!программа должна вывести:

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

Облучатель, однако, должен быть защищен от излучения, поэтому излучатель, который вы пишете, также должен выживать при прохождении через себя. То есть, когда удаляется какой-либо один байт вашей программы, программа все равно должна функционировать должным образом.

Контрольные примеры

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;

Характеристики

• Вы можете принять ввод любым приемлемым способом по нашим Стандартным правилам ввода / вывода.
• Вывод может быть либо списком строк, либо распечатанным списком, разделенным символом или группой символов. Конечный разделитель приемлем
• Вывод может быть в любом порядке, если он содержит все возможные версии
• Повторяющиеся записи (такие как два Helo, world! в первом примере) могут быть отфильтрованы, но это не обязательно
• Поскольку это code-golf , выигрывает самая маленькая программа в байтах

05AB1E , 29 26 байт

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

Попробуйте онлайн! или попробуйте все облученные версии .

Самый короткий облучатель, который я смог найти, составляет 5 байт:

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

Идея состоит в том, чтобы повторить это 3 раза, а затем сделать большинство голосов:

æ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

Åявляется префиксом для 2-байтовых команд, но нет Å`команды, поэтому Åигнорируется. Нам это понадобится позже, хотя.

Сортировка удостоверяет, что большинство голосов находится в середине массива. Сброс, а затем свопинг возвращает это значение на вершину стека.

Любое облучение в начальной части приводит только к ошибке в глобальном массиве, которая решается большинством голосов. Облучения в финале{Å`s бите гораздо сложнее рассуждать о:

• Å в любом случае игнорируется, так что это нормально, чтобы облучать его

• Если спина облучена, Å`sстановитсяÅs , что является расширенной командой «получить середину массива».

• Если {или sоблучены, это означает, что больше ничего нет, поэтому глобальный массив имеет одно и то же значение три раза. В этом случае нам не нужна сортировка / замена, любое значение будет работать.

8086 машинный код (MS-DOS .COM), 83 байта

Запускается в DOSBox или в вашем любимом паровом вычислительном движке. Строка для облучения задается в качестве аргумента командной строки.

Binary:

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

Удобочитаемый:

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

Спуститься

Активная часть дублируется, так что всегда есть одна, не затронутая излучением. Мы выбираем здоровую версию в виде прыжков. Каждый прыжок - это короткий прыжок, поэтому длина его составляет всего два байта, где второй байт - это смещение (т. Е. Расстояние до прыжка со знаком, определяющим направление).

Мы можем разделить код на четыре части, которые можно облучать: переход 1, код 1, переход 2 и код 2. Идея состоит в том, чтобы всегда использовать чистую часть кода. Если одна из частей кода облучается, должна быть выбрана другая, но если один из переходов облучается, обе части кода будут чистыми, поэтому не будет иметь значения, какая из них выбрана.

Причиной наличия двух частей прыжка является обнаружение облучения в первой части путем перепрыгивания через него. Если первая часть кода облучается, это означает, что мы прибудем на один байт от метки. Если мы удостоверимся, что при такой неудачной посадке выбирается код 2, а при правильной посадке выбирается код 1, у нас все в порядке.

Для обоих переходов мы дублируем байт смещения, делая каждую часть перехода длиной 3 байта. Это гарантирует, что облучение в одном из двух последних байтов все еще сделает переход действительным. Облучение в первом байте вообще не даст возможности перейти, так как последние два байта сформируют совершенно другую инструкцию.

Сделай первый прыжок:

EB 28 28        jmp +0x28 / db 0x28

Если один из 0x28байтов будет удален, он все равно перейдет в то же место. Если 0xEBбайт удален, вместо этого мы получим

28 28           sub [bx + si], ch

что является доброкачественной инструкцией для MS-DOS (другие разновидности могут не согласиться), а затем мы переходим к коду 1, который должен быть чистым, поскольку повреждение было в прыжке 1.

Если прыжок сделан, мы приземляемся при втором прыжке:

EB D7 D7        jmp -0x29 / db 0xd7

Если эта последовательность байтов не повреждена, и мы попадаем прямо на отметку, это означает, что код 1 был чистым, и эта инструкция возвращается к этой части. Дублированный байт смещения гарантирует это, даже если это один из этих байтов смещения, который был поврежден. Если мы либо выгрузим один байт (из-за поврежденного кода 1 или скачка 1), либо из- 0xEBза поврежденного байта, два оставшихся байта также будут доброкачественными:

D7 D7           xlatb / xlatb

В любом случае, если мы в конечном итоге выполняем эти две инструкции, мы знаем, что либо переход 1, код 1, либо переход 2 были облучены, что делает переход к коду 2 безопасным.

тестирование

Следующая программа использовалась для автоматического создания всех версий файла .COM. Он также создает BAT-файл, который можно запустить в целевой среде, который запускает каждый облученный двоичный файл и направляет их выходные данные в отдельные текстовые файлы. Сравнение выходных файлов для проверки достаточно просто, но DOSBox не имеет fc, поэтому он не был добавлен в 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);
}