16
\$\begingroup\$

The task is to write a radiation-hardened irradiator. What do I mean by that, exactly?

An irradiator is a program that, when given a string as input, will output all possible versions of the string with one character removed. For example, given the input Hello, world!, the program should output:

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

An irradiator, however, must be protected from its radiation, so the irradiator you write must also survive when put through itself. That is, when any single byte of your program is removed, the program must still function properly.

Test cases

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;

Specifications

  • You may take input by any acceptable method by our Standard I/O rules
  • The output may be either a list of strings or a printed list delimited by a character or group of characters. A trailing delimiter is acceptable
  • The output may be in any order as long as it contains all of the possible versions
  • Duplicate entries (such as the two Helo, world!s in the first example) may be filtered out, but this is not necessary
  • As this is , the smallest program, in bytes, wins
\$\endgroup\$
  • \$\begingroup\$ ...or comma perhaps? \$\endgroup\$ – Jonathan Allan Aug 18 at 21:26
  • 4
    \$\begingroup\$ this one is really favouring golfing languages, because C program with v in void removed won't compile \$\endgroup\$ – Krzysztof Szewczyk Aug 19 at 9:51
  • 3
    \$\begingroup\$ @Krzysztof tbh I think most if not all practical languages won't survive radiation hardening because of the verbosity and the syntaxes. Not only this challenge, but ALL RH challenges. \$\endgroup\$ – Shieru Asakoto Aug 19 at 13:34
12
+300
\$\begingroup\$

05AB1E, 29 26 bytes

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

Try it online!, or try all irradiated versions.

The shortest irradiator I could find is 5 bytes:

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

The idea is to repeat that 3 times, then do majority voting:

æ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

Å is a prefix for 2-byte commands, but there's no Å` command, which is why the Å gets ignored. We'll need it later, though.

Sorting makes sure the majority vote is in the middle of the array. Dumping then swapping gets that value to the top of the stack.

Any irradiation in the initial part only results in an error in the global array, which gets solved by the majority vote. Irradiations in the final {Å`s bit are much trickier to reason about:

  • Å is ignored anyway, so it's okay to irradiate it

  • If the backtick is irradiated, Å`s becomes Ås, which is the "get middle of the array" extended command.

  • If { or s are irradiated, that means nothing else is, so the global array is the same value three times. In that case we don't need sorting/swapping, any value will work.

\$\endgroup\$
  • 3
    \$\begingroup\$ Very impressive! I didn't think I'd see a 05AB1E answer on a RH challenge. I'll add a bounty to reward this answer (and give the challenge a bit more exposure as well I guess) right away. You've golfed so many answers of mine, so you deserve loads of credit for those as well! :) \$\endgroup\$ – Kevin Cruijssen Sep 2 at 8:33
  • 3
    \$\begingroup\$ Actually, I've seen 05AB1E answers on a RH challenge before. Still, very impressive! \$\endgroup\$ – Kevin Cruijssen Sep 2 at 8:49
4
\$\begingroup\$

8086 machine code (MS-DOS .COM), 83 bytes

Runnable in DOSBox or your favourite steam-powered computing engine. The string to irradiate is given as a command line argument.

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

Readable:

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

Rundown

The active part is duplicated so that there is always one untouched by radiation. We select the healthy version by way of jumps. Each jump is a short jump, and so is only two bytes long, where the second byte is the displacement (i.e. distance to jump, with sign determining direction).

We can divide the code into four parts which could be irradiated: jump 1, code 1, jump 2, and code 2. The idea is to make sure a clean code part is always used. If one of the code parts is irradiated, the other must be chosen, but if one of the jumps is irradiated, both code parts will be clean, so it will not matter which one is chosen.

The reason for having two jump parts is to detect irradiation in the first part by jumping over it. If the first code part is irradiated, it means we will arrive one byte off the mark. If we make sure that such a botched landing selects code 2, and a proper landing selects code 1, we're golden.

For both jumps, we duplicate the displacement byte, making each jump part 3 bytes long. This ensures that irradiation in one of the two last bytes will still make the jump valid. Irradiation in the first byte will stop the jump from happening at all, since the last two bytes will form a completely different instruction.

Take the first jump:

EB 28 28        jmp +0x28 / db 0x28

If either of the 0x28 bytes are removed, it will still jump to the same place. If the 0xEB byte is removed, we will instead end up with

28 28           sub [bx + si], ch

which is a benign instruction on MS-DOS (other flavours might disagree), and then we fall through to code 1, which must be clean, since the damage was in jump 1.

If the jump is taken, we land at the second jump:

EB D7 D7        jmp -0x29 / db 0xd7

If this byte sequence is intact, and we land right on the mark, that means that code 1 was clean, and this instruction jumps back to that part. The duplicated displacement byte guarantees this, even if it is one of these displacement bytes that were damaged. If we either land one byte off (because of a damaged code 1 or jump 1) or the 0xEB byte is the damaged one, the two remaining bytes will also here be benign:

D7 D7           xlatb / xlatb

Whichever the case, if we end up executing those two instructions, we know that either jump 1, code 1, or jump 2 were irradiated, which makes a fall-through to code 2 safe.

Testing

The following program was used to automatically create all versions of the .COM file. It also creates a BAT file that can be run in the target environment, which runs each irradiated binary, and pipes their outputs to separate text files. Comparing the output files to validate is easy enough, but DOSBox does not have fc, so it was not added to the BAT file.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.