Escreva um irradiador endurecido por radiação

17

A tarefa é escrever um irradiador endurecido por radiação. O que quero dizer com isso exatamente?

Um irradiador é um programa que, quando recebe uma string como entrada, gera todas as versões possíveis da string com um caractere removido. Por exemplo, dada a entrada Hello, world!, o programa deve gerar:

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

Um irradiador, no entanto, deve ser protegido de sua radiação, de modo que o irradiador que você escreve também deve sobreviver quando for passado por si mesmo. Ou seja, quando qualquer byte único do seu programa é removido, o programa ainda deve funcionar corretamente.

Casos de teste

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;

Especificações

  • Você pode receber informações de qualquer método aceitável de acordo com nossas regras de E / S padrão
  • A saída pode ser uma lista de cadeias ou uma lista impressa delimitada por um caractere ou grupo de caracteres. Um delimitador à direita é aceitável
  • A saída pode estar em qualquer ordem, desde que contenha todas as versões possíveis
  • Entradas duplicadas (como as duas Helo, world!s no primeiro exemplo) podem ser filtradas, mas isso não é necessário
  • Como se trata de , o menor programa, em bytes, ganha
TheOnlyMrCat
fonte
... ou vírgula, talvez?
Jonathan Allan
4
este está realmente favorecendo as linguagens de golfe, porque o programa C com vin voidremovido não será compilado
Krzysztof Szewczyk
3
@Krzysztof tbh Acho que a maioria, se não todas as linguagens práticas, não sobreviverão ao endurecimento por radiação por causa da verbosidade e das sintaxes. Não apenas esse desafio, mas TODOS os desafios de RH.
Shieru Asakoto

Respostas:

13

05AB1E , 29 26 bytes

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

Experimente online! ou tente todas as versões irradiadas .

O irradiador mais curto que encontrei é de 5 bytes:

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

A idéia é repetir isso três vezes e, em seguida, votar por maioria:

æ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

Åé um prefixo para comandos de 2 bytes, mas não há Å`comando, e é por isso que eles Åsão ignorados. No entanto, precisaremos mais tarde.

A classificação garante que a maioria dos votos esteja no meio da matriz. Despejar e trocar trocam esse valor para o topo da pilha.

Qualquer irradiação na parte inicial resulta apenas em um erro na matriz global, que é resolvida pelo voto da maioria. As irradiações no {Å`sbit final são muito mais difíceis de raciocinar sobre:

  • Å é ignorado de qualquer maneira, então não há problema em irradiá-lo

  • Se o backtick for irradiado, Å`storna-se Ås, que é o comando estendido "get middle of the array".

  • Se {ou sfor irradiado, isso significa que nada mais é, portanto a matriz global terá o mesmo valor três vezes. Nesse caso, não precisamos de triagem / troca, qualquer valor funcionará.

Grimmy
fonte
3
Muito impressionante! Eu não acho que veria uma resposta 05AB1E em um desafio de RH. Vou adicionar uma recompensa para recompensar esta resposta (e dar ao desafio um pouco mais de exposição também, eu acho) imediatamente. Você já jogou tantas respostas minhas e merece muito crédito por essas também! :)
Kevin Cruijssen
3
Na verdade, eu já vi respostas 05AB1E em um desafio de RH antes . Ainda assim, muito impressionante!
Kevin Cruijssen 02/09/19
5

Código de máquina 8086 (MS-DOS .COM), 83 bytes

Executável no DOSBox ou no seu mecanismo de computação a vapor favorito. A cadeia a irradiar é fornecida como um argumento de linha de comando.

Binário:

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

Legível:

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

Atropelar

A parte ativa é duplicada para que sempre haja uma intocada pela radiação. Selecionamos a versão saudável por meio de saltos. Cada salto é um salto curto e, portanto, tem apenas dois bytes, onde o segundo byte é o deslocamento (ou seja, a distância do salto, com sinal determinando a direção).

Podemos dividir o código em quatro partes que podem ser irradiadas: salto 1, código 1, salto 2 e código 2. A idéia é garantir que uma parte limpa do código seja sempre usada. Se uma das partes do código for irradiada, a outra deverá ser escolhida, mas se um dos saltos for irradiado, ambas as partes do código estarão limpas, portanto, não importa qual delas for escolhida.

A razão para ter duas partes de salto é detectar a irradiação na primeira parte, saltando sobre ela. Se a primeira parte do código for irradiada, significa que chegaremos a um byte da marca. Se garantirmos que uma aterrissagem com falhas selecione o código 2 e uma aterragem adequada selecione o código 1, seremos dourados.

Nos dois saltos, duplicamos o byte de deslocamento, tornando cada salto com 3 bytes de comprimento. Isso garante que a irradiação em um dos dois últimos bytes ainda torne o salto válido. A irradiação no primeiro byte impedirá que o salto aconteça, uma vez que os dois últimos bytes formarão uma instrução completamente diferente.

Dê o primeiro salto:

EB 28 28        jmp +0x28 / db 0x28

Se um dos 0x28bytes for removido, ele ainda pulará para o mesmo local. Se o 0xEBbyte for removido, acabaremos com

28 28           sub [bx + si], ch

que é uma instrução benigna no MS-DOS (outros tipos podem discordar) e, então, passamos ao código 1, que deve estar limpo, pois o dano ocorreu no salto 1.

Se o salto for dado, pousamos no segundo salto:

EB D7 D7        jmp -0x29 / db 0xd7

Se essa sequência de bytes estiver intacta e aterrissarmos bem na marca, isso significa que o código 1 estava limpo e essa instrução retornará a essa parte. O byte de deslocamento duplicado garante isso, mesmo se um desses bytes de deslocamento estiver danificado. Se pousarmos um byte (por causa de um código danificado 1 ou pular 1) ou se o 0xEBbyte estiver danificado, os dois bytes restantes também serão benignos:

D7 D7           xlatb / xlatb

Seja qual for o caso, se acabarmos executando essas duas instruções, sabemos que o salto 1, o código 1 ou o salto 2 foram irradiados, o que torna seguro o detalhamento do código 2.

Teste

O programa a seguir foi usado para criar automaticamente todas as versões do arquivo .COM. Ele também cria um arquivo BAT que pode ser executado no ambiente de destino, que executa cada binário irradiado e canaliza suas saídas para separar arquivos de texto. Comparar os arquivos de saída para validar é fácil, mas o DOSBox não possui fc, portanto não foi adicionado ao arquivo 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);
}
gastropner
fonte