Terjemahkan Prelude ke Befunge

19

Ini adalah Tantangan Mingguan # 2. Tema: Terjemahan

Tulis program atau fungsi yang mengambil kode sumber untuk program di Pendahuluan dan kode keluaran untuk program yang setara di Befunge-93 . Agar program menjadi setara, itu harus, untuk setiap input yang diberikan, menghasilkan output yang sama dengan program Prelude, dan berhenti jika dan hanya jika program Prelude berhenti.

Bahasa input: Pendahuluan

Penerjemah Python:

Program Prelude terdiri dari sejumlah "suara" yang menjalankan instruksi secara bersamaan. Instruksi untuk setiap suara berada pada jalur yang berbeda. Setiap suara memiliki tumpukan terpisah, yang diinisialisasi dengan jumlah nol yang tak terbatas. Eksekusi dimulai di kolom paling kiri, dan naik satu kolom ke kanan setiap centang, kecuali jika dipengaruhi oleh )atau (instruksi. Program berakhir ketika kolom terakhir tercapai.

Prelude spec untuk tantangan ini:

Digits 0-9      Push onto the stack a number from 0 to 9. Only single-digit
                    numeric literals can be used.
^               Push onto the stack the top value of the stack of the above 
                    voice.
v               Push onto the stack the top value of the stack of the below 
                    voice.
#               Remove the top value from the stack.
+               Pop the top two integers from the stack and push their sum.
-               Pop the top two integers from the stack, subtract the topmost 
                    from the second, and push the result.
(               If the top of the stack is 0, jump to the column after the 
                    matching `)` after the current column executes.
)               If the top of the stack is not 0, jump to the column after 
                    the matching `(` after the current column executes.
?               Read an integer from STDIN.
!               Pop one value from the stack and print it to STDOUT as an
                    integer.
<space>         No-op

Catatan

  • vdan ^bertindak secara siklis, sehingga vpada suara bagian bawah akan menyalin elemen tumpukan suara atas, dan ^pada suara atas akan menyalin dari suara bawah. Konsekuensi: Keduanya vdan ^menduplikasi bagian atas tumpukan dalam program suara tunggal.
  • A (dan pencocokannya )mungkin terletak di jalur yang berbeda. Namun , a )akan selalu melihat tumpukan suara di mana yang sesuai (ditempatkan, bukan tumpukan di mana suara )itu sendiri ditempatkan.
  • Nilai yang dihasilkan oleh ^dan vinstruksi beroperasi pada nilai yang ada sebelum selesainya operasi lain di kolom yang sama.
  • ?dan !beroperasi secara berbeda dari spesifikasi yang ditemukan di esolangs.org, jadi pastikan untuk menguji dengan penerjemah yang sedikit dimodifikasi yang disediakan dalam posting ini.

Input dijamin memiliki:

  • Tanda kurung yang cocok
  • Tidak lebih dari satu kurung dalam satu kolom
  • Jumlah karakter yang sama di setiap baris
  • Setidaknya satu baris
  • Tidak ada kolom dengan lebih dari satu instruksi I / O ( !atau ?)
  • Satu karakter linefeed setelah instruksi untuk setiap suara
  • Tidak ada karakter selain yang disebutkan di atas

Bahasa keluaran: Befunge-93

Befunge adalah bahasa berbasis tumpukan yang penghitung programnya (PC; pointer ke instruksi saat ini) bergerak bebas di kisi dua dimensi. Itu dimulai di sudut kiri atas, bergerak ke kanan. Playfield adalah toroidal, yaitu gerakan PC membungkus kedua sisi. Befunge juga memiliki tumpukan yang diinisialisasi ke angka nol tanpa batas. Befunge memiliki operasi berikut:

Anda dapat mengasumsikan karakteristik kompiler / juru bahasa Befunge-93 berikut:

  • Integer tidak terbatas presisi.
  • Ini memungkinkan kisi-kisi dalam berbagai ukuran.
  • Koordinat kisi (untuk gdan p) berbasis 0.

Mencetak gol

Untuk mencegah pengiriman yang hanya menghasilkan juru bahasa Prelude di Befunge dan meng-hardcode sumber Prelude ke dalamnya, tujuannya adalah untuk meminimalkan ukuran kode sumber Befunge yang dihasilkan.

Di bawah ini disediakan sejumlah program Pendahuluan. Penerjemah Anda akan menjalankan semua ini. Skor Anda adalah jumlah dari ukuran program Befunge, asalkan semuanya valid.

Penerjemah Anda sebaiknya tidak dioptimalkan secara khusus terhadap kasus uji ini (mis. Dengan program Befunge tulisan tangan hardcoding untuk mereka). Jika saya mencurigai ada jawaban yang melakukannya, saya berhak untuk mengubah input atau membuat input tambahan.

Input Sampel

Cetak n-1ke 0:

?(1-^!)

Logis dan:

?  (0)  
 ?(0  ) 
    1  !

Logis atau:

 ?   (0) 
? (0)    
   1  1 !

Periksa paritas input (yaitu modulo 2) dari nomor non-negatif:

?(1-)   
 ^  v   
 v1-^^-!

Kuadratkan input:

 ^    
  ^+ !
?(1-) 

Cetak angka Fibonacci ke- n , di mana n = 0sesuai dengan 0 dan n = 1sesuai dengan 1:

0 v+v!
1   ^ 
?(1-) 

Signum:

  1) v #  - !
 vv (##^v^+) 
?(#   ^   ## 

Pembagian untuk input non-negatif:

1 (#  1) v #  - 1+)   
     vv (##^v^+)      
?  v-(0 # ^   #       
 ?                    
   1+              1-!

Tentu saja, program Anda harus menunjukkan perilaku yang sama untuk semua kasus, bahkan jika perilaku program sampel untuk angka negatif tidak ditentukan.

Akhirnya, penerjemah Anda seharusnya tidak terlalu panjang:

  • Itu harus terkandung di dalam pos Stack Exchange
  • Ini harus memproses input sampel dalam waktu kurang dari 10 menit pada komputer desktop biasa.

Perhatikan bahwa input numerik untuk Prelude atau Befunge diberikan sebagai tanda minus opsional diikuti oleh satu atau lebih angka desimal, diikuti oleh baris baru. Input lain adalah perilaku yang tidak terdefinisi.

Anda dapat menulis penerjemah Anda dalam bahasa apa pun. Kode Befunge yang diterjemahkan terpendek, akan menang.

Papan peringkat

  • Sp3000 : 16430 byte
feersum
sumber
Saya tidak mengerti: "Tekan ke atas tumpukan nilai teratas pada tumpukan suara di atas." Tidak harus: "Tekan ke atas tumpukan nilai teratas dari tumpukan suara di atas."
Def
Dikatakan prelude mengeksekusi suara secara bersamaan, apakah itu berarti mereka benar-benar dieksekusi pada utas yang terpisah atau dapatkah saya menjalankan perintah pertama pada semua suara (atas ke bawah) kemudian perintah kedua dan seterusnya.
Def
@Deformyer Saya mengubahnya dari "on" ke "of", tapi saya pikir "nilai teratas di stack" juga tidak salah. Adapun simultanitas, tidak, Anda tidak perlu benar-benar menafsirkannya secara paralel. Yang penting adalah mereka semua bertindak pada keadaan tumpukan sebelumnya, dan tidak ada operasi dalam kolom yang diberikan dapat mempengaruhi operasi lain di kolom itu.
Martin Ender
Bukankah beberapa kasus uji melanggar "Tidak ada kolom dengan lebih dari satu instruksi I / O (! Atau?)?"
Fuwjax
@proudhaskeller Ini 1ada di dalam satu loop, jadi mungkin tidak didorong. Angka 0 dapat berasal dari jumlah tak terbatas 0s yang dimulai pada tumpukan.
feersum

Jawaban:

10

Python 3, akan mencetak gol nanti

from collections import defaultdict
from functools import lru_cache
import sys

NUMERIC_OUTPUT = True

@lru_cache(maxsize=1024)
def to_befunge_num(n):
    # Convert number to Befunge number, using base 9 encoding (non-optimal,
    # but something simple is good for now)

    assert isinstance(n, int) and n >= 0

    if n == 0:
        return "0"

    digits = []

    while n:
        digits.append(n%9)
        n //= 9

    output = [str(digits.pop())]

    while digits:
        output.append("9*")
        d = digits.pop()

        if d:
            output.append(str(d))
            output.append("+")

    output = "".join(output)

    if output.startswith("19*"):
        return "9" + output[3:]

    return output

def translate(program_str):
    if program_str.count("(") != program_str.count(")"):
        exit("Error: number of opening and closing parentheses do not match")

    program = program_str.splitlines()
    row_len = max(len(row) for row in program)
    program = [row.ljust(row_len) for row in program]
    num_stacks = len(program)


    loop_offset = 3
    stack_len_offset = program_str.count("(")*2 + loop_offset
    stack_offset = stack_len_offset + 1
    output = [[1, ["v"]], [1, [">"]]] # (len, [strings]) for each row
    max_len = 1 # Maximum row length so far

    HEADER_ROW = 0
    MAIN_ROW = 1
    FOOTER_ROW = 2
    # Then stack lengths, then loop rows, then stacks

    # Match closing parens with opening parens
    loop_map = {} # {column: (loop num, stack number to check, is_start)}
    loop_stack = []
    loop_num = 0

    for col in range(row_len):
        col_str = "".join(program[stack][col] for stack in range(num_stacks))

        if col_str.count("(") + col_str.count(")") >= 2:
            exit("Error: more than one parenthesis in a column")

        if "(" in col_str:
            stack_num = col_str.index("(")

            loop_map[col] = (loop_num, stack_num, True)
            loop_stack.append((loop_num, stack_num, False))
            loop_num += 1

        elif ")" in col_str:
            if loop_stack:
                loop_map[col] = loop_stack.pop()

            else:
                exit("Error: mismatched parentheses")


    def pad_max(row):
        nonlocal max_len, output

        while len(output) - 1 < row:
            output.append([0, []])

        if output[row][0] < max_len:
            output[row][1].append(" "*(max_len - output[row][0]))
            output[row][0] = max_len


    def write(string, row):
        nonlocal max_len, output

        output[row][1].append(string)
        output[row][0] += len(string)

        max_len = max(output[row][0], max_len)


    def stack_len(stack, put=False):
        return (to_befunge_num(stack) + # x
                str(stack_len_offset) + # y
                "gp"[put])


    def get(stack, offset=0):
        assert offset in [0, 1] # 1 needed for 2-arity ops

        # Check stack length
        write(stack_len(stack) + "1-"*(offset == 1) + ":0`", MAIN_ROW)

        pad_max(HEADER_ROW)
        pad_max(MAIN_ROW)
        pad_max(FOOTER_ROW)

        write(">" + to_befunge_num(stack + stack_offset) + "g", HEADER_ROW)
        write("|", MAIN_ROW)
        write(">$0", FOOTER_ROW)

        pad_max(HEADER_ROW)
        pad_max(MAIN_ROW)
        pad_max(FOOTER_ROW)

        write("v", HEADER_ROW)
        write(">", MAIN_ROW)
        write("^", FOOTER_ROW)


    def put(stack, value=""):
        put_inst = (value +
                    stack_len(stack) +
                    to_befunge_num(stack + stack_offset) +
                    "p")

        post_insts.append(put_inst)


    def pop(stack):
        put(stack, "0")


    def inc_stack_len(stack):
        post_insts.append(stack_len(stack) + "1+")
        post_insts.append(stack_len(stack, put=True))


    def dec_stack_len(stack):
        post_insts.append(stack_len(stack) + ":0`-") # Ensure nonnegativity
        post_insts.append(stack_len(stack, put=True))


    # Technically not necessary to initialise stack lengths per spec, but it makes it
    # more portable and easier to test against other Befunge interpreters

    for stack in range(num_stacks):
        write("0" + stack_len(stack, put=True), MAIN_ROW)

    for col in range(row_len):
        post_insts_all = []

        loop_start = False
        loop_end = False

        if col in loop_map:
            if loop_map[col][2]:
                loop_start = True
            else:
                loop_end = True

        if loop_start:
            loop_row = loop_offset + 2*loop_map[col][0]
            get(loop_map[col][1])

        elif loop_end:
            get(loop_map[col][1])
            write("!", MAIN_ROW)


        for stack in range(num_stacks-1, -1, -1):
            char = program[stack][col]
            post_insts = [] # Executed after the gets in reverse order, i.e. last added first

            if char in " ()":
                continue

            # Pre-inc, post-dec
            elif char.isdigit():
                inc_stack_len(stack)
                put(stack, char)

            elif char == "?":
                inc_stack_len(stack)
                put(stack, "&")

            elif char == "!":
                get(stack)
                post_insts.append(".91+," if NUMERIC_OUTPUT else ",")
                pop(stack)
                dec_stack_len(stack)

            elif char == "#":
                pop(stack)
                dec_stack_len(stack)

            elif char in "+-":
                get(stack, 1)
                get(stack)
                post_insts.append(char)
                pop(stack) # This one first in case of ! or 1!
                post_insts.append(stack_len(stack) + ":1`-:1\\`+") # Ensure >= 1
                post_insts.append(stack_len(stack, put=True))
                put(stack)                

            elif char in "^v":
                offset = -1 if char == "^" else 1

                get((stack + offset) % num_stacks)
                inc_stack_len(stack)
                put(stack)

            else:
                exit("Error: invalid character " + char)

            post_insts_all.append(post_insts)


        while post_insts_all:
            write("".join(post_insts_all.pop()), MAIN_ROW)

        if loop_start or loop_end:
            loop_row = loop_offset + 2*loop_map[col][0]

            pad_max(HEADER_ROW)
            pad_max(MAIN_ROW)
            pad_max(loop_row)
            pad_max(loop_row + 1)

            write(">v", HEADER_ROW)
            write("|>", MAIN_ROW)

            if loop_start:
                write(" ^", loop_row)
                write(">", loop_row + 1)

            else:
                write("<", loop_row)
                write(" ^", loop_row + 1)


    write("@", MAIN_ROW)
    return "\n".join("".join(row) for row_len, row in output)

if __name__ == '__main__':
    if len(sys.argv) < 3:
        exit("Usage: py -3 prefunge.py <input filename> <output filename>")

    with open(sys.argv[1]) as infile:
        with open(sys.argv[2], "w") as outfile:
            outfile.write(translate(infile.read()))

Jalankan seperti py -3 prefunge.py <input filename> <output filename>.

Ini minggu yang lambat bagi saya, jadi saya akhirnya cukup bosan untuk menangani pertanyaan enam bulan ini. Saya akan bertanya mengapa tidak ada orang lain yang mencoba, tetapi saya masih merasakan sakit karena debugging (dan mungkin masih ada bug yang tersisa untuk semua yang saya tahu).

Pertanyaannya tidak menyediakan penerjemah Befunge-93, jadi saya menggunakan yang ini , yang sedikit berbeda dari spek. Dua perbedaan utama adalah:

  • Jika char tidak ada di baris tertentu dari program, maka Anda tidak dapat menulis ke baris itu. Ini berarti Anda harus menekan Enter beberapa kali untuk memperkenalkan cukup baris baru di akhir . Jika Anda melihat NaNdi output, ini kemungkinan penyebabnya.

  • Sel-sel kisi tidak diinisialisasi ke nol - untuk kenyamanan saya telah memasukkan beberapa preinitialisation dalam output Befunge, tetapi karena itu tidak perlu saya mungkin mengambilnya ketika saya mulai mencetak.

Tata letak inti dari program keluaran adalah ini:

v [header row]
> [main row]
  [footer row]
  ---
   |
   | rows for loops (2 per loop)
   |
  ---
  [stack length row]
  ---
   |
   | rows for stack space (1 per voice)
   |
  ---

Ruang stack berada di luar program, oleh karena itu komentar Enter-spam baru dari sebelumnya.

Ide intinya adalah untuk menetapkan setiap suara baris yang berfungsi sebagai tumpukannya. Untuk mempertahankan tumpukan ini, kami juga memiliki baris panjang tumpukan khusus di mana panjang setiap tumpukan dicatat dalam sel di sepanjang baris. Program ini kemudian banyak gets dan puts, misal untuk mencetak prosesnya adalah:

  • Dapatkan sel di y = stack_row[stack], x = stack_length[stack]
  • Lakukan .91+,, yaitu cetak sebagai bilangan bulat lalu cetak baris baru
  • Ganti sel pada koordinat di atas dengan 0 (untuk mensimulasikan popping)
  • Pengurangan stack_length[stack]

Untuk melakukan evaluasi kolom secara simultan, semua sel yang diperlukan dibaca dan nilainya disimpan di tumpukan sebelum ada sel yang ditulis (misalnya untuk contoh pencetakan, mungkin ada lebih banyak instruksi di antara langkah pertama dan kedua).

`, yang lebih besar dari, digunakan untuk memastikan panjang stack tidak menjadi negatif, dan untuk mendorong 0 ketika stack kosong. Di sinilah percabangan yang terlihat jelas berasal, tapi saya punya ide yang akan menghapus percabangan, yang seharusnya menghapus banyak spasi putih dari baris pertama dan ketiga.

Untuk loop, karena Prelude loop dapat melompat dua arah, kami menggunakan dua baris per loop dalam konfigurasi seperti ini:

       >v                     >v
(cond) |>  (program)  (cond) !|>

        ^                     <
       >                       ^

Loop-loop ini saat ini merupakan mayoritas dari byte, tetapi dapat dengan mudah diturunkan dengan menempatkannya ke dalam kotak kode dengan p, yang saya rencanakan untuk dilakukan setelah saya senang bahwa penerjemah bekerja dengan benar.

Berikut adalah beberapa contoh keluaran ?(1-^!), yaitu cetak n-1ke 0:

v                        >6gv>v                      >6gv      >6gv                                 >6gv                   >6gv                           >6gv >v
>005p05g1+05p&05g6p05g:0`|  >|>05g1+05p105g6p05g1-:0`|  >05g:0`|  >-005g6p05g:1`-:1\`+05p05g6p05g:0`|  >05g1+05p05g6p05g:0`|  >.91+,005g6p05g:0`-05p05g:0`|  >!|>@
                         >$0^                        >$0^      >$0^                                 >$0^                   >$0^                           >$0^
                              ^                                                                                                                                <
                             >                                                                                                                                  ^

Input persegi:

v                                >8gv      >8gv             >v      >6gv                                   >8gv      >8gv        >7gv      >7gv                                                            >8gv >v      >7gv
>005p015p025p25g1+25p&25g8p25g:0`|  >25g:0`|  >05g1+05p05g6p|>05g:0`|  >15g1+15p15g7p25g1+25p125g8p25g1-:0`|  >25g:0`|  >15g1-:0`|  >15g:0`|  >+015g7p15g:1`-:1\`+15p15g7p-025g8p25g:1`-:1\`+25p25g8p25g:0`|  >!|>15g:0`|  >.91+,015g7p15g:0`-15p@
                                 >$0^      >$0^                     >$0^                                   >$0^      >$0^        >$0^      >$0^                                                            >$0^         >$0^
                                                             ^                                                                                                                                                  <
                                                            >                                                                                                                                                    ^

Divisi (disarankan input kecil):

v                                                                          >91+gv>v      >94+gv                                                         >95+gv      >95+gv        >93+gv      >93+gv                                                                    >93+gv      >93+gv               >v      >93+gv                                                     >93+gv >v      >92+gv                  >v      >92+gv                                       >92+gv                                       >91+gv                                       >93+gv                     >91+gv                       >92+gv      >92+gv        >91+gv      >91+gv                                                                                      >92+gv >v                        >91+gv      >91+gv                                     >91+gv >v                        >95+gv      >95+gv                                     >95+gv
>009p019p029p039p049p09g1+09p109g91+p29g1+29p&29g93+p39g1+39p&39g94+p09g:0`|    >|>39g:0`|    >009g91+p09g:0`-09p29g1+29p29g93+p49g1+49p149g95+p49g1-:0`|    >49g:0`|    >29g1-:0`|    >29g:0`|    >-029g93+p29g:1`-:1\`+29p29g93+p+049g95+p49g:1`-:1\`+49p49g95+p29g:0`|    >29g:0`|    >19g1+19p19g92+p|>29g:0`|    >09g1+09p109g91+p19g1+19p19g92+p29g1+29p029g93+p29g:0`|    >!|>19g:0`|    >029g93+p29g:0`-29p|>19g:0`|    >09g1+09p09g91+p019g92+p19g:0`-19p19g:0`|    >019g92+p19g:0`-19p29g1+29p29g93+p09g:0`|    >009g91+p09g:0`-09p19g1+19p19g92+p29g:0`|    >19g1+19p19g92+p09g:0`|    >19g1+19p19g92+p19g1-:0`|    >19g:0`|    >09g1-:0`|    >09g:0`|    >-009g91+p09g:1`-:1\`+09p09g91+p+019g92+p19g:1`-:1\`+19p19g92+p029g93+p29g:0`-29p19g:0`|    >!|>09g1+09p109g91+p09g1-:0`|    >09g:0`|    >+009g91+p09g:1`-:1\`+09p09g91+p09g:0`|    >!|>49g1+49p149g95+p49g1-:0`|    >49g:0`|    >-049g95+p49g:1`-:1\`+49p49g95+p49g:0`|    >.91+,049g95+p49g:0`-49p@
                                                                           >$0  ^        >$0  ^                                                         >$0  ^      >$0  ^        >$0  ^      >$0  ^                                                                    >$0  ^      >$0  ^                       >$0  ^                                                     >$0  ^         >$0  ^                          >$0  ^                                       >$0  ^                                       >$0  ^                                       >$0  ^                     >$0  ^                       >$0  ^      >$0  ^        >$0  ^      >$0  ^                                                                                      >$0  ^                           >$0  ^      >$0  ^                                     >$0  ^                           >$0  ^      >$0  ^                                     >$0  ^
                                                                                  ^                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        <
                                                                                 >                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ^
                                                                                                                                                                                                                                                                                                          ^                                                                        <
                                                                                                                                                                                                                                                                                                         >                                                                          ^
                                                                                                                                                                                                                                                                                                                                                                                                                    ^                                                                                                                                                                                                                                                                                                                                              <
                                                                                                                                                                                                                                                                                                                                                                                                                   >                                                                                                                                                                                                                                                                                                                                                ^

Ada juga sekelompok optimisations kecil lainnya yang datang ke pikiran, seperti mengganti 07p07gdengan :07p, tapi saya mengambil langkah ini satu per satu :)

Sp3000
sumber
Begitu. Banyak. Gratis. Waktu.
Pengoptimal
1
Will score later2 tahun dan terus bertambah! :)
HyperNeutrino