Apakah kaset bundar mengasyikkan?

32

Turunan Brainfuck

Mari kita mendefinisikan bahasa pemrograman sederhana seperti Brainfuck . Ini memiliki pita dua arah sel, dan masing-masing sel memegang satu bit. Semua bit awalnya 0. Ada kepala bergerak di kaset, awalnya di posisi 0. Program adalah string di atas karakter <>01!, dieksekusi dari kiri ke kanan, dengan semantik berikut:

  • < menggerakkan kepala satu langkah ke kiri.
  • > menggerakkan kepala satu langkah ke kanan.
  • 0 menempatkan 0 di sel saat ini.
  • 1 menempatkan 1 di sel saat ini.
  • ! membalik sel saat ini.

Tidak ada loop, jadi program n karakter berakhir setelah langkah n persis . Suatu program membosankan jika semua sel berisi 0 pada akhir eksekusi, dan menarik jika ada setidaknya satu 1. Perhatikan bahwa ukuran rekaman itu tidak ditentukan, jadi tergantung pada implementasinya, mungkin dua arah tak terbatas atau bundar.

Contoh program

Pertimbangkan programnya 1>>>!<<<<0>!>>>!. Pada rekaman tanpa batas, eksekusi berlangsung sebagai berikut:

     v
00000000000000  Put 1
     v
00000100000000  Move by >>>
        v
00000100000000  Flip
        v
00000100100000  Move by <<<<
    v
00000100100000  Put 0
    v
00000100100000  Move by >
     v
00000100100000  Flip
     v
00000000100000  Move by >>>
        v
00000000100000  Flip
        v
00000000000000

Pada akhirnya, semua sel adalah 0, jadi program ini membosankan. Sekarang, mari kita jalankan program yang sama pada pita bundar dengan panjang 4.

v
0000  Put 1
v
1000  Move by >>>
   v
1000  Flip
   v
1001  Move by <<<< (wrapping around at the edge)
   v
1001  Put 0
   v
1000  Move by > (wrapping back)
v
1000  Flip
v
0000  Move by >>>
   v
0000  Flip
   v
0001

Kali ini, ada sel dengan nilai 1, jadi programnya menarik! Kami melihat apakah suatu program membosankan atau menarik tergantung pada ukuran rekaman itu.

Tugas

Input Anda adalah string yang tidak kosong <>01!yang mewakili program dalam bahasa pemrograman di atas. Berbagai karakter juga merupakan format input yang dapat diterima. Program ini dijamin akan membosankan ketika dijalankan pada kaset tanpa batas. Output Anda akan menjadi daftar panjang tape di mana program ini menarik. Perhatikan bahwa Anda hanya perlu menguji program pada kaset yang lebih pendek dari panjang program.

Solusi dengan jumlah byte terendah dalam setiap bahasa adalah pemenangnya. Aturan standar berlaku.

Uji kasus

> : []
110 : []
1>0<! : [1]
0>>1>0<<>! : [1]
1>>>!<<<<0>!>>>! : [2, 4]
!<!<><<0>!>!<><1!>>0 : [2]
>>!>><>001>0<1!<<!>< : [1, 2, 3]
1!><<!<<<!!100><>>>! : [1, 3]
!!1>!>11!1>>0<1!0<!<1><!0<!<0> : [3, 4]
<><<>>!<!!<<<!0!!!><<>0>>>>!>> : [1, 2, 4]
0>>><!<1><<<0>!>>!<<!!00>!<>!0 : [3]
0000!!!!><1<><>>0<1><<><<>>!<< : []
!>!>!>!>!>1>!>0<!<!<!<0<!<0<!<!<!<1>!>0<<! : [1, 2, 5, 7]
<!!>!!><<1<>>>!0>>>0!<!>1!<1!!><<>><0<<!>><<!<<!>< : [1, 2, 4, 5]
!>1<<11<1>!>!1!>>>0!!>!><!!00<><<<0<<>0<<!<<<>>!!> : [1, 2, 3, 5, 6]
Zgarb
sumber
1
Bisakah kita memilih karakter yang berbeda dan konsisten <>01!?
Tn. Xcoder
1
Apakah array instruksi merupakan input yang dapat diterima?
Arnauld
@ Mr.Xcoder Tidak, Anda harus menggunakan karakter yang tepat ini.
Zgarb
@Arnauld Array karakter cukup dekat ke string, saya akan mengizinkannya.
Zgarb

Jawaban:

6

Haskell, 119 byte

t#'<'=last t:init t
(h:t)#c|c<'#'=1-h:t|c>'='=t++[h]|1<2=read[c]:t
f p=[n|n<-[1..length p],sum(foldl(#)(0<$[1..n])p)>0]

Cobalah online!

Fungsi #adalah penerjemah untuk satu perintah c. Seluruh program pdijalankan oleh folding #dengan pita mulai menjadi p. fdijalankan puntuk setiap pita dan menyimpannya di tempat jumlah sel setidaknya 1.

nimi
sumber
n<-[1..length p] ... 0<$[1..n]sepertinya cukup panjang, pasti ada jalan yang lebih pendek.
nimi
Saya tidak bisa melihat cara yang lebih pendek. Masalah yang saya lihat adalah bahwa Anda benar-benar membutuhkan nilai nsebagai hasilnya, jadi jika Anda membuat 0<$[1..n]cara yang berbeda (katakanlah dengan scanr(:)), Anda harus mengambilnya length. (Saya juga mencoba menggunakan 1(untuk mengganti lengthdengan sum) atau False(untuk menggunakan oruntuk tes) alih-alih 0, tetapi tidak keluar lebih pendek.)
Ørjan Johansen
@ ØrjanJohansen: ya, saya mencoba n<-init$scanr(:)[]$0<$p ... nyang lebih pendek 2 byte, tetapi mengembalikan daftar kaset awal bukannya panjangnya, mis [[0],[0,0,0]]. Dengan sedikit aturan yang tertekuk sehingga bisa melihat kaset sebagai angka unary, jadi mungkin tidak apa-apa.
nimi
init$dapat diganti dengan menempatkan [0]daftar awal, tetapi masih belum cukup pendek. Saya pikir unary hanya diperbolehkan untuk bahasa tanpa representasi bilangan yang lebih alami .
Ørjan Johansen
4

Stax , 56 54 43 38 35 byte CP437

è¥%►BΣ░ÜY⌂y(â&.═ªê►V½▲y▌)▀♫♂╣ª?√»!#

42 byte saat dibongkar,

%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a

Jalankan dan debug online!

-2 byte per komentar oleh @recursive

Penjelasan

Saya akan menggunakan versi dengan awalan i(yaitu i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a) untuk menjelaskan dan saya akan menjelaskan mengapa ibisa dihapus

i               Suppress implicit eval
                    This prevents the test case "110" from being interpreted as a number
                    However, this can be removed because a program containing only numbers cannot be exciting and the output will be empty anyway.
                    This is based on the fact that the program is boring on non-circular tapes
 %f             Filter range [1..n] with the rest of this program
                    Where n is the length of the input
                    Implicit output the array after filtering, one element per line
   z(           Initialize the tape
     y{  F      Run the program
          |a    Any cell is non-zero

Kode untuk menjalankan program:

{|(}                                 Block to rotate left by one element
    {|)}                             Block to rotate right by one element
        {B!s+}                       Block to perform logical not on the element at index 0
              {0_]e&}                Block to obtain current instruction,
                                         Convert it to a number
                                         And assign to element at index 0

                     4l              Pack the 4 blocks in an array
                       s"<>! "I      Find the index of current instruction in string, if not found, the index will be -1
                                         And when indexed with -1, it wraps around to the 4th element.

                               @!    And execute the corresponding block.
Weijun Zhou
sumber
1
Saya menambahkan kotak uji semua digit untuk memvalidasi icek Anda .
Zgarb
0]*dapat diganti dengan z(. Juga, jika Anda mengubah string ke "<>!", Maka 0dan 1akan memberikan indeks -1, sehingga cara daftar blokir Anda hanya membutuhkan 4 blok, bukan 5. Ini akan berfungsi karena toh 0dan 1handler identik pula.
rekursif
@recursive Poin bagus diambil.
Weijun Zhou
3

CJam , 57 56 49 46 byte

-7 terima kasih kepada @MartinEnder

{:T,({)0a*T{i23%")!+(+ W0tW1t)\+"3/=~}/:+},:)}

Cobalah online!

Buah Esolanging
sumber
2

Perl 5 ( -F), 101 byte

map{$,=@a=(0)x$_;map{$,+=/>/-/</;$a[$,%@a]=$&if/0|1/;$a[$,%@a]=!$a[$,%@a]if/!/}@F;say if@a~~/1/}1..@F

Cobalah online!

Xcali
sumber
2

Merah , 243 byte

func[p][repeat n length? p[b: copy[]insert/dup b 0 n i: 1
parse p[any["<"(i: i - 1 if i < 1[i: n])|">"(i: i + 1 if i > n[i: 1])|"0"(b/(i): 0)|"1"(b/(i): 1)|"!"(b/(i): either b/(i) = 0[1][0])|
skip]]s: 0 foreach c b[s: s + c]if s > 0[print n]]]

Cobalah online!

Prety verbose dan implementasi langsung. Pengindeksan 1 merah tidak memungkinkan saya untuk mengurangi jumlah byte dengan menggunakan aritmatika modular untuk perulangan melalui kaset melingkar.

Tidak disatukan

f: func[p][ 
    repeat n length? p[
        b: [] 
        insert/dup b 0 n
        i: 1
        parse p[
            some [
                 "<" (i: i - 1 if i < 1[i: n])
               | ">" (i: i + 1 if i > n[i: 1])
               | "0" (b/(i): 0)
               | "1" (b/(i): 1)
               | "!" (b/(i): either b/(i) = 0 [1][0])
               | skip 
            ]
        ]
        s: 0
        foreach c b[s: s + c]
        if s > 0 [print n]
    ]
]
Galen Ivanov
sumber
2

Python 2 , 139 135 133 132 131 byte

-3 byte terima kasih kepada Tn. Xcoder

def f(p):i=0;exec"i+=1;s=[0]*i\nfor c in p:c=ord(c)-61;s=c>-2and s[c:]+s[:c]or[[s.pop(0)^1,0,1][c%7]]+s\nif 1in s:print i\n"*len(p)

Cobalah online!

tongkat
sumber
131 byte?
Tn. Xcoder
2

Retina , 121 byte

.+
$.&*0¶$&
\G0
0$`¶
{ms`^.(?=.*¶¶(0|1))
$1
"¶¶!"&mT`d`10`^.
"¶¶>"&`(.)(.*)¶
$2$1¶
"¶¶<"&`(.*)(.)¶
$2$1¶
)`¶¶.
¶¶
G`1
%`.

Cobalah online! Penjelasan:

.+
$.&*0¶$&
\G0
0$`¶

Buat larik kaset dengan panjang masing-masing hingga panjang program input.

{

Ulangi sampai program dikonsumsi.

ms`^.(?=.*¶¶(0|1))
$1

Jika karakter berikutnya dalam program adalah 0 atau 1, ubah karakter pertama pada setiap baris ke karakter itu.

"¶¶!"&mT`d`10`^.

Jika a !maka beralih karakter pertama di setiap baris.

"¶¶>"&`(.)(.*)¶
$2$1¶
"¶¶<"&`(.*)(.)¶
$2$1¶

Jika itu adalah >atau <kemudian putar garis. (Lebih mudah daripada menggerakkan kepala.)

)`¶¶.
¶¶

Hapus instruksi dan akhiri loop.

G`1

Pertahankan hanya garis yang menarik.

%`.

Hitung panjang setiap baris.

Neil
sumber
2

JavaScript (ES6), 126 118 byte

Disimpan 3 byte berkat @ user71546

Mengambil input sebagai array string 1 karakter.

f=(s,l=0,p=0,t=[])=>s[l++]?s.map(c=>1/c?t[p%l]=+c:c>'='?p++:c>';'?p+=l-1:t[p%l]^=1)&&+t.join``?[l,...f(s,l)]:f(s,l):[]

Cobalah online!

Arnauld
sumber
Mengganti t.some(x=>x)?dengan +t.join``?memeriksa array sebagai digit (dan 0 menunjukkan semua-nol tape), tetapi 3 byte lebih sedikit.
Shieru Asakoto
2

APL (Dyalog Unicode) , 79 64 54 byte ( Adám's SBCS )

⍸⊂{∨/⍎⍕(↓',',⍨5 3'0@11@1~@1 1⌽¯1⌽')['01!<'⍳⌽⍺]⍵}¨0=,\

Cobalah online!

-15 Berkat Adám (lupa tentang monadik ).
-10 Terima kasih kepada ngn .

Erik the Outgolfer
sumber
64
Adm
@ Adm Hm, sepertinya itu tidak optimal (misalnya Anda tidak perlu ). Saya akan memeriksanya dan memperbarui. :)
Erik the Outgolfer
Tetapi jika Anda menghapus Anda akan membutuhkan ;, bukan?
Adám
@ Adám tidak , mengapa Anda mau?
Erik the Outgolfer
1

MATL , 46 39 byte

f"@:~G"@59>?@61-YS}@33=?t1)~}@U]1(]]a?@

Cobalah online! Atau verifikasi semua kasus uji .

Bagaimana itu bekerja

f             % Push indices of nonzero chars of (implicit) input string: gives
              % [1 2 ... n] where n is input length
"             % For each k in [1 2 ... n]. These are the possible tape lengths
  @:~         %   Push array of k zeros. This is the tape, in its initial state
  G           %   Push input string
  "           %   For each char in the input string
    @59>?     %     If code point of current char exceeds 59 (so it is '<' or '>')
      @61-    %       Push code point minus 61: gives -1 for '<', or 1 for '>'
      YS      %       Circularly shift the tape by that amount. Instead of moving
              %       the head, we shift the tape and keep the head at entry 1
    }         %     Else
      @33=?   %       If code point of current char is 33 (so it is '!')
        t1)   %         Duplicate the array representing the tape, and get its
              %         first entry
        ~     %         Logical negate
      }       %       Else
        @U    %         Push current char (it is '0' or '1') converted to number
      ]       %       End
      1(      %       Write (either 0, 1 or old value negated) at entry 1
    ]         %     End
  ]           %   End
  a?          %   If the tape contains at least a nonzero value
    @         %     Push tape length, k
              %   End (implicit)
              % End (implicit)
              % Display (implicit)
Luis Mendo
sumber
1

APL (Dyalog Unicode) , 192 78 byte

⊂{t/⍵⊣⍵{t[m]←('01!'⍳⍵)⊃0 1,e,⍨~et[m←⍺|ii+←¯1 1 0⊃⍨'<>'⍳⍵]}¨⍺⊣i←⊃t←⍬⍳⍺}¨1+⍳∘≢

Cobalah online! (hasil tidak rata)

Cobalah online! (diratakan)

Setelah beberapa waktu menghabiskan membenturkan kepala ke dinding, saya memutuskan untuk membuat Tradfn, bukan Dfn. Ini hasilnya. Orang yang lebih pintar daripada saya mungkin bisa bermain golf dari ini.

Kejutan, kejutan, seseorang yang lebih pintar dariku melakukan golf dari ini. Terima kasih untuk 114 byte.

Dia berkata:

Perhatikan bahwa ini adalah program persis Anda, kecuali menggunakan pengindeksan bukan bagian dalam: Ifs dan collapsing: For-loop ke {_} ¨ sambil memberikan argumen kiri untuk menggantikan global.

Fungsi ini mengasumsikan ⎕IO←0.


Bagaimana?

(Penjelasan ini menggunakan versi "ungolfed" untuk memfasilitasi membaca)

⊂{                                   Enclose
      i←⊃t←⍬⍳⍺                       Assign a vector of 0s to t (the tape), then assign the first 0 to i.
      t/⍵⊣⍵{                         Use  as left argument for the nested function, then compress the result into t. If there is a 1 anywhere in t, the result will be a vector of the result. If not, the result is an empty vector.
          i+←¯1 1 0⊃⍨'<>'⍳⍵          Map the string '<>' to the argument (which is the BF program). That yields 0 for <, 1 for >, and 2 for anything else.
                                     The resulting vector will then be used as the argument for  to add -1 (index 0), 1 (index 1) or 0 (index 2) to the variable i.
          et[m←⍺|i]                 Assign i mod  (left arg) to m, and use it to index t. Then, assign the value to e.
          t[m]←('01!'⍳⍵)⊃0 1,e,⍨~e   Map the string '01!' to ⍵. As before, this yields 0 for 0, 1 for 1, 2 for ! and 3 for anything else.
                                     Then, concatenate (not e) with e, then concatenate that with the vector 0 1. This is used as argument to be picked from, and it is assigned to t[m].
      }¨⍺                            Do that for each argument
  1+⍳∘≢                            And do that for each possible tape length from 1 to the length of the input.
J. Sallé
sumber
1
Simpan satu byte dengan t←l⍴0menjadi t←l⍴i←0, dan hapus baris di atasnya. Anda juga dapat menyimpan yang lain dengan mengubah t[i|⍨≢t]←1-t[i|⍨≢t]ke t[i|⍨≢t]←~t[i|⍨≢t].
Zacharý
2
@ Zacharý benar, dan selanjutnya menyimpan 112 byte tambahan . Kode yang persis sama, hanya sedikit golf.
Adm
Ya, itu hanya dinamakan "sedikit". Apakah kamu tidak perlu s?
Zacharý
@ Zacharý Apa ? Ini adalah fungsi diam-diam.
Adám
@ Zacharý Saya akan menganggap ini cukup Adám'd, bukan?
J. Sallé
0

Jelly , 41 byte

JR0ṁð3“1⁺¦01¦¬1¦ṙ1 ṙ- ”s“10!<>”,yẎvЀ⁸Ẹ€T

Cobalah online!

Erik the Outgolfer
sumber
0

C (dentang) , 171 byte

l,i;f(S){for(char*p,t[l=strlen(S)];l;memchr(t,1,l)&&printf("%d ",l),l--)for(memset(t,i=0,l),p=S;*p;p++)*p==60?i=i?i-1:l-1:*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1);}

Cobalah online!

Harus menggunakan dentang, karena menggunakan char*p,t[l=strlen(S)]sebagai ekspresi inisialisasi untuk beberapa alasan membuat GCC berpikir saya ingin mendeklarasikan strlenalih-alih menyebutnya.

Cukup lurus ke depan: Menjalankan program pada kaset melingkar dengan panjang yang semakin berkurang, menghasilkan panjang yang menghasilkan 1 di suatu tempat di pita.

Mencoba memperpendek kusut operator ternary, tetapi akhirnya membutuhkan lebih banyak tanda kurung daripada yang sehat.

gastropner
sumber
Sarankan i=0,bzero(t,l)alih-alih memset(t,i=0,l)dan *p-62?t[i]=*p^33?*p-48:t[i]^1:(i=~i+l?i+1:0)bukannya*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1)
ceilingcat