Perkecil Brainfuck

Tantangan Anda adalah mengecilkan kode Brainfuck , sesuai dengan aturan ini:

• Hapus apa pun yang bukan salah satunya +-><[].,.
• Untuk grup berurutan +atau -karakter apa pun, jika jumlah +s dan -s sama, hapuslah.
• Lakukan hal yang sama seperti di atas, tetapi dengan >dan <.
• Hapus urutan +-><karakter jika mereka tidak melakukan apa-apa. Misalnya, Anda harus menghapus +>-<->+<. (Ini mungkin yang paling sulit dan paling sulit untuk diterapkan.) Pastikan Anda tidak mendapatkan positif palsu, seperti +>-<+>-<, yang tidak boleh dihapus.

Kasus uji:

Memasukkan

++++++[->++++++<]>.   prints a $
[-]<                  resets tape
>,[>,]<[.<]           reverses NUL terminated input string
++-->><<              does nothing

Keluaran

++++++[->++++++<]>.[-],[>,]<[.<]

Memasukkan

Should disappear: ++>>+<+++<->-->-<<->-<
Should disappear: +++>-<--->+<
Should stay: +++>-<+>---<

Keluaran

+++>-<+>---<

Anda dapat menerima input dan output namun Anda ingin - stdin / stdout, suatu fungsi, dll., Tetapi input mungkin tidak dikodekan dengan keras.

Ini adalah kode-golf , jadi kode terpendek dalam jumlah karakter akan menang.

REBEL - 104

_/^_$/$</([^][<>.,+-]|\+-|-\+|<>|><)//((?<X>(<|>))+[+-]+(?!\2)(?<-X><|>)+(?(X)(?!)))([+-]+)/$3$1/.+/$>$&

Pemakaian:

Input: Membaca satu baris dari stdin.

Output: Mencetak satu baris ke stdout.

Anomali *:

• Memasuki _menyebabkan baris lain dibaca dan digunakan, alih-alih tidak menghasilkan apa-apa.
• Hasil tes kedua ++++>----<bukannya +++>-<+>---<. Tapi tidak apa-apa, kan? ;)
• >-<+dll diganti dengan +>-<dll.

Spoiler:

Menerapkan anomali # 3 membuat banyak hal sepele.

_{* Ini bukan bug, ini fitur!}

Brainfuck, 579 byte

,[<<+>>>>+<<[[<+>>+<-]++++++[>-------<-]>-[-[-[-[--------------[--[<+++++[>-----
-<-]>+[--[<<[-]>>-]]<]>[>>-<<<<<[-]<[<]<<<[<]>>>>>>>>[<]<-[+>]+[->+]>>>>+>[<-]<[
>+<-<]>]<]>[<<<[-]-[<]>>>>>>>>>>>[<]<<<<<<[<]<-[+>]+[-<+]<<<+<[>-<<<]>[-<+<]]]<]
>[+>[-<]<[<<]<[-]>>]]<]+>[-[<-]<[>+>+<<-<]<[-]>+>]<<[>-]>[,>]<]<+<[>]>[>>>[<<<<[
-<]<<<]>>>+>>>>[<<<<->>>>[>>>[-<]>>>>]]]>[<<<[<+[-->>]]>[-[.[-]]]>[<]>[<<++++++[
>+++++++<-]>+>>[<<.>>-]<<++>-[<.>-]+++[<+++++>-]+<<<<<<+>[<<[>->>>>>.[[-]<<<<]<<
<+>>>]>[->->>>>[-]]]<[->+[>>>>>]>>[<]<<<<<<<<[[-]<]>[++.[-]>>>>>>>]<]]>>]<[>>>>>
>>]+[-<<<<<[-]<<],]

Dengan pemformatan dan beberapa komentar:

,
[
  <<+>> >>+<<
  [
    [<+> >+<-]
    ++++++[>-------<-]
    >-
    [
      not plus
      -
      [
        not comma
        -
        [
          not minus
          -
          [
            not period
            --------------
            [
              not less than
              --
              [
                not greater than
                <+++++[>------<-]>+
                [
                  not open bracket
                  --
                  [
                    not close bracket
                    <<[-]>>-
                  ]
                ]
                <
              ]
              >
              [
                greater than
                >>-<<
                <<<[-]<[<]<<<[<]
                >>>>>>>>[<]
                <-[+>]
                +[->+]
                >>>>+>[<-]
                <[>+<-<]
                >
              ]
              <
            ]
            >
            [
              less than
              <<<[-]-[<]
              >>>> >>>>>>>[<]
              <<<<<<[<]
              <-[+>]
              +[-<+]
              <<<+<[>-<<<]
              >[-<+<]
            ]
          ]
          <
        ]
        >
        [
          minus
          +>[-<]
          <[<<]
          <[-]>>
        ]
      ]
      <
    ]
    +>
    [
      plus
      -[<-]
      <[>+>+<<-<]
      <[-]>+>
    ]
    <<
    [
      comma or period or bracket
      >-
    ]
    >[,>]
    <
  ]
  comma or period or bracket or eof
  <+<
  [
    start and end same cell
    >
  ]
  >
  [
    >>>
    [
      <<<<[-<]<<<
    ]
    >>>+>>>>
    [
      start right of end
      <<<<->>>>
      [>>>[-<]>>>>]
    ]
  ]
  >
  [
    <<<
    [
      <+[-->>]
    ]
    >[-[.[-]]]
    >[<]
    >
    [
      <<++++++[>+++++++<-]>+>>
      [<<.>>-]
      <<++>-[<.>-]
      +++[<+++++>-]
      +<<<<< <+>
      [
        <<
        [
          go left
          >->>>>>.
          [[-]<<<<]
          <<<+>>>
        ]
        >
        [
          toggle left right
          ->->>>>[-]
        ]
      ]
      <
      [
        toggle right left
        ->+[>>>>>]>>[<]
        <<<<<<<<
        [
          [-]<
        ]
        >
        [
          go right
          ++.[-]
          >>>>>>>
        ]
        <
      ]
    ]
    >>
  ]
  <[>>>>>>>]
  +[-<<<<<[-]<<]
  ,
]

Ini menggunakan pendekatan yang sama dengan solusi Keith Randall, meminimalkan semua urutan yang berdekatan +-<>secara optimal dengan simulasi. Misalnya, +++>-<+>---<menjadi ++++>----<dan >+<+<<+>+<->>>>menjadi +<+>>+>.

Cobalah online. (Jika nilai absolut sel yang disimulasikan mendekati 256, akan ada masalah melimpah.)

Struktur keseluruhannya adalah

while not EOF:
  while not EOF and next char not in ",.[]":
    process char
  print minified sequence (followed by the char in ",.[]" if applicable)

Rekaman ini dibagi menjadi 7-sel node; di awal loop dalam, tata letak memori

0 s 0 c 0 a b

di mana sadalah bendera boolean untuk sel awal, cadalah karakter saat ini, aadalah bagian negatif dari nilai sel yang disimulasikan (ditambah satu), dan bmerupakan bagian positif dari nilai sel yang disimulasikan.

Ketika urutan yang diperkecil sedang dicetak, tata letak memori

d n e 0 0 a b

di mana dbendera boolean untuk arah, adan bseperti sebelumnya (tetapi menjadi satu / nol saat dicetak), dan ndan ebukan nol untuk simpul akhir; nterkait dengan berapa kali node telah terlihat, dan enilai dari char yang menghentikan loop dalam (plus satu).

Awalnya saya mempertimbangkan untuk melacak lebih banyak informasi per node: node paling kiri dan paling kanan sebagai flag boolean, dan posisi node dalam kaitannya dengan node start dan end. Tetapi kita dapat menghindarinya dengan melihat sel tetangga saat dibutuhkan, dan dengan melakukan pemindaian kiri dan kanan untuk menemukan titik awal.

Saat mencetak urutan yang diperkecil dan memutuskan cara memindahkan pointer yang disimulasikan, kita dapat mengambil pendekatan umum: mulai dengan menjauh dari titik akhir (dalam arah yang berubah-ubah jika titik awal dan titik akhir sama), putar ke kiri dan ke kanan node, dan berhenti berdasarkan berapa kali node akhir telah terlihat: 3 kali jika node awal dan akhir sama, jika tidak 2.

Python, 404 karakter

Kode ini melakukan optimalisasi sempurna dari semua tahapan dari +-<>. Sedikit lebih banyak dari yang Anda minta, tapi itu dia.

M=lambda n:'+'*n+'-'*-n                                                           
def S(b):                                                                         
 s=p=0;t=[0];G,L='><'                                                             
 for c in b:                                                                      
  if'+'==c:t[p]+=1                                                                
  if'-'==c:t[p]-=1                                                                
  if G==c:p+=1;t+=[0]                                                             
  if L==c:s+=1;t=[0]+t                                                            
 if p<s:k=len(t)-1;t,p,s,G,L=t[::-1],k-p,k-s,L,G                                  
 r=[i for i,n in enumerate(t)if n]+[s,p];a,b=min(r),max(r);return(s-a)*L+''.join(M(n)+G for n in t[a:b])+M(t[b])+(b-p)*L                                           
s=b=''                                                                            
for c in raw_input():                                                             
 if c in'[].,':s+=S(b)+c;b=''                                                     
 else:b+=c                                                                        
print s+S(b) 

Ini bekerja dengan mensimulasikan +-<>operasi pada rekaman itu t. sadalah posisi awal pada kaset dan pposisi saat ini. Setelah simulasi, ia mencari tahu sejauh mana [a,b]yang perlu dioperasikan dan melakukan semua +/- dalam satu lintasan optimal.

CoffeeScript - 403 397

i=prompt().replace /[^\]\[,.+-><]/g,''
x=(c)->
 t={};p=n=0
 for d in c
  t[p]?=0;switch d
   when'+'then n=1;t[p]++;when'-'then n=1;t[p]--;when'<'then p--;when'>'then p++
 (n=0if v!=0)for k,v of t;n
s=e=0;((e++;(i=(i.substr 0,s)+i.substr e;e=s=0)if x (i.substr s,e-s).split "")while(i[e]||0)!in['[',']',0];e=++s)while s<=i.length
r=/(\+-|-\+|<>|><|^[<>]$)/g
i=i.replace r,'' while r.test i
alert i

Demo (maafkan penggunaan bit.ly di sini, seluruh URL akan memecah markdown)

Versi tidak terkompresi (kode debug):

console.clear()
input = """Should disappear: ++>>+<+++<->-->-<<->-<
Should disappear: +++>-<--->+<
Should stay: +++>-<+>---<"""

input = input.replace /[^\]\[,.+-><]/g, ''
console.log input

execute = (code) ->
  stack = {}
  item = 0
  console.log code
  nop = false
  for char in code
    switch char
      when '+' then nop = true; stack[item]?=0;stack[item]++
      when '-' then nop = true; stack[item]?=0;stack[item]--
      when '<' then item--
      when '>' then item++
  console.debug stack
  (nop = false if v != 0) for k,v of stack
  nop
start = 0
end = 0

while start <= input.length
 while input.charAt(end) not in [ '[', ']', '' ]
  end++
  if execute (input.substring start, end).split("")
    input = (input.substring 0, start) + input.substring end
    end = start = 0
    console.log input
 end = ++start
input = input.replace /(\+-|-\+|<>|><|^(<|>)$)/g, '' while /(\+-|-\+|<>|><)/.test input
console.log 'Result: ' + input