Tulis iradiator yang dikeraskan dengan radiasi

17

Tugasnya adalah untuk menulis iradiator yang dikeraskan dengan radiasi. Apa yang saya maksud dengan itu, tepatnya?

Sebuah irradiator adalah program yang, ketika diberi string sebagai input, akan menampilkan semua versi string yang mungkin dengan satu karakter dihapus. Misalnya, diberi input Hello, world!, program harus menampilkan:

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

Iradiator, bagaimanapun, harus dilindungi dari sinarnya, sehingga iradiator yang Anda tulis juga harus bertahan ketika dimasukkan melalui dirinya sendiri. Yaitu, ketika byte tunggal dari program Anda dihapus, program tersebut masih harus berfungsi dengan baik.

Uji kasus

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;

Spesifikasi

  • Anda dapat mengambil input dengan metode apa pun yang dapat diterima oleh aturan I / O Standar kami
  • Outputnya bisa berupa daftar string atau daftar cetak yang dibatasi oleh karakter atau kelompok karakter. Pembatas trailing dapat diterima
  • Output mungkin dalam urutan apa pun asalkan berisi semua versi yang mungkin
  • Entri duplikat (seperti dua Helo, world!s pada contoh pertama) dapat disaring, tetapi ini tidak perlu
  • Karena ini adalah , program terkecil, dalam byte, menang
TheOnlyMrCat
sumber
... atau koma mungkin?
Jonathan Allan
4
yang satu ini benar-benar mendukung bahasa golf, karena program C dengan vdi voiddihapus tidak akan mengkompilasi
Krzysztof Szewczyk
3
@ Krzysztof tbh Saya pikir paling jika tidak semua bahasa praktis tidak akan selamat dari pengerasan radiasi karena verbositas dan sintaksis. Tidak hanya tantangan ini, tetapi SEMUA tantangan RH.
Shieru Asakoto

Jawaban:

13

05AB1E , 29 26 byte

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

Cobalah online! , atau coba semua versi iradiasi .

Iradiator terpendek yang dapat saya temukan adalah 5 byte:

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

Idenya adalah mengulangi itu 3 kali, lalu lakukan voting mayoritas:

æ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

Åadalah awalan untuk perintah 2-byte, tetapi tidak ada Å`perintah, itulah mengapa Ådiabaikan. Kami akan membutuhkannya nanti.

Penyortiran memastikan suara terbanyak ada di tengah array. Membuang lalu menukar membuat nilai itu ke atas tumpukan.

Setiap iradiasi di bagian awal hanya menghasilkan kesalahan dalam array global, yang diselesaikan dengan suara terbanyak. Iradiasi pada {Å`sbit terakhir jauh lebih sulit untuk dipikirkan:

  • Å tetap diabaikan, jadi tidak apa-apa untuk menyinari itu

  • Jika backtick diiradiasi, Å`smenjadi Ås, yang merupakan perintah "get middle of the array".

  • Jika {atau sdiradiasi, itu berarti tidak ada yang lain, jadi array global adalah nilai yang sama tiga kali. Dalam hal ini kita tidak perlu menyortir / bertukar, nilai apa pun akan berfungsi.

Grimmy
sumber
3
Sangat mengesankan! Saya tidak berpikir saya akan melihat jawaban 05AB1E pada tantangan kesehatan reproduksi. Saya akan menambahkan hadiah untuk membalas jawaban ini (dan saya kira tantangannya juga lebih banyak eksposur) segera. Anda telah menerima begitu banyak jawaban dari saya, jadi Anda juga pantas mendapatkan banyak pujian untuk itu! :)
Kevin Cruijssen
3
Sebenarnya, saya telah melihat jawaban 05AB1E pada tantangan kesehatan reproduksi sebelumnya . Tetap saja, sangat mengesankan!
Kevin Cruijssen
5

8086 kode mesin (MS-DOS .COM), 83 byte

Runnable di DOSBox atau mesin komputasi bertenaga uap favorit Anda. String untuk iradiasi diberikan sebagai argumen baris perintah.

Biner:

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

Dapat dibaca:

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

Kehabisan

Bagian aktif diduplikasi sehingga selalu ada satu yang tidak tersentuh oleh radiasi. Kami memilih versi sehat dengan cara melompat. Setiap lompatan adalah lompatan pendek, dan panjangnya hanya dua byte, di mana byte kedua adalah perpindahan (yaitu jarak untuk melompat, dengan tanda yang menentukan arah).

Kita dapat membagi kode menjadi empat bagian yang dapat diiradiasi: lompat 1, kode 1, lompat 2, dan kode 2. Idenya adalah untuk memastikan bagian kode yang bersih selalu digunakan. Jika salah satu bagian kode diiradiasi, yang lain harus dipilih, tetapi jika salah satu lompatan diiradiasi, kedua bagian kode akan bersih, sehingga tidak masalah mana yang dipilih.

Alasan memiliki dua bagian lompatan adalah untuk mendeteksi iradiasi pada bagian pertama dengan melompati bagian itu. Jika bagian kode pertama diiradiasi, itu berarti kita akan tiba satu byte dari sasaran. Jika kami memastikan bahwa pendaratan yang gagal memilih kode 2, dan pendaratan yang tepat memilih kode 1, kami emas.

Untuk kedua lompatan, kami menduplikasi byte perpindahan, membuat masing-masing lompatan bagian 3 byte. Ini memastikan bahwa iradiasi di salah satu dari dua byte terakhir masih akan membuat lompatan valid. Iradiasi pada byte pertama akan menghentikan lompatan yang terjadi sama sekali, karena dua byte terakhir akan membentuk instruksi yang sama sekali berbeda.

Ambil lompatan pertama:

EB 28 28        jmp +0x28 / db 0x28

Jika salah satu dari 0x28byte tersebut dihapus, masih akan melompat ke tempat yang sama. Jika 0xEBbyte dihapus, kita akan berakhir dengan

28 28           sub [bx + si], ch

yang merupakan instruksi jinak pada MS-DOS (rasa lain mungkin tidak setuju), dan kemudian kita masuk ke kode 1, yang harus bersih, karena kerusakan pada lompatan 1.

Jika lompatan diambil, kami mendarat di lompatan kedua:

EB D7 D7        jmp -0x29 / db 0xd7

Jika urutan byte ini utuh, dan kami mendarat tepat pada tanda, itu berarti bahwa kode 1 bersih, dan instruksi ini melompat kembali ke bagian itu. Byte perpindahan duplikat menjamin ini, bahkan jika itu adalah salah satu byte perpindahan ini yang rusak. Jika kita mendaratkan satu byte off (karena kode 1 rusak atau melompat 1) atau 0xEBbyte itu rusak, dua byte yang tersisa juga akan menjadi tidak berbahaya:

D7 D7           xlatb / xlatb

Apapun masalahnya, jika kita akhirnya mengeksekusi kedua instruksi itu, kita tahu bahwa lompatan 1, kode 1, atau lompatan 2 diiradiasi, yang membuat keamanan dari kode 2 jatuh.

Pengujian

Program berikut ini digunakan untuk secara otomatis membuat semua versi file .COM. Ini juga menciptakan file BAT yang dapat dijalankan di lingkungan target, yang menjalankan setiap biner yang diiradiasi, dan menyalurkan outputnya ke file teks yang terpisah. Membandingkan file output untuk divalidasi cukup mudah, tetapi DOSBox tidak punya fc, jadi itu tidak ditambahkan ke file 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
sumber