Minimiere Brainfuck

22

Ihre Herausforderung besteht darin, den Brainfuck- Code gemäß diesen Regeln zu minimieren :

  • Entfernen Sie alles, was nicht dazu gehört +-><[].,.
  • Wenn die Anzahl von s und s für eine Gruppe von aufeinanderfolgenden Zeichen +oder -Zeichen gleich ist, entfernen Sie sie.+-
  • Machen Sie dasselbe wie oben, aber mit >und <.
  • Entfernen Sie die +-><Zeichenfolgen, wenn Sie nichts tun. Zum Beispiel sollten Sie entfernen +>-<->+<. (Dies kann die schwierigste und schwierigste Implementierung sein.) Stellen Sie sicher, dass Sie keine falsch positiven Ergebnisse erhalten +>-<+>-<, die nicht entfernt werden sollten.

Testfälle:

Eingang

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

Ausgabe

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

Eingang

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

Ausgabe

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

Sie können Eingaben und Ausgaben akzeptieren, wie Sie möchten - stdin / stdout, eine Funktion usw., aber die Eingaben sind möglicherweise nicht fest codiert.

Dies ist , also gewinnt der kürzeste Code in der Anzahl der Zeichen.

Türknauf
quelle
4
Ich weiß, dass dies eine alte Herausforderung ist, aber die Testfälle sind unzureichend. ++>>++<<--sollte ausgeben >>++<<, und das wurde nicht abgedeckt. Bitte fügen Sie weitere Testfälle hinzu.
mbomb007
@ mbomb007 hat prüfen Sie den letzten Testfall +++>-<+>---<? Sie kann verkürzt werden, um unnötige Zeigerbewegungen zu vermeiden. Die erwartete Ausgabe lässt sie jedoch unverändert. Mein Verständnis basiert darauf, sowohl die Frage als auch die Antworten zu betrachten, dass Doorknob cool ist, wenn die Spezifikation locker genommen wird; Wir müssen alle zusammenhängenden No-Op- +-><Sequenzen entfernen, wie explizit angegeben, und darüber hinaus ist es zulässig, zusätzliche Minimierungen wie in Ihrem Beispiel vorzunehmen. ++>>++<<--Wir können auch Neuanordnungen vornehmen, solange sie die Funktionalität des Codes nicht ändern, z. B. >+<+in +>+<.
Mitch Schwartz
@MitchSchwartz "Entfernen Sie Sequenzen der Zeichen + -> <, wenn sie nichts bewirken. Sie sollten sie beispielsweise entfernen +>-<->+<. (Dies ist möglicherweise die schwierigste und schwierigste Implementierung.) Stellen Sie sicher, dass Sie keine falsch positiven Ergebnisse erhalten +>-<+>-<, z. was nicht entfernt werden sollte. " - das ist irgendwie vage
mbomb007
@ mbomb007 Der zweite und dritte Aufzählungspunkt sind überflüssig und unnötig, da sie im vierten Aufzählungspunkt enthalten sind. Na und? Es ist eine coole Aufgabe. Mein Kommentar sollte konstruktiv sein und Klarheit schaffen, nicht Sie angreifen. Bitte nehmen Sie es so, wie ich es beabsichtigt hatte, oder sagen Sie mir, wie ich es anders hätte sagen sollen. Weil du nicht wirklich angesprochen hast, was ich geschrieben habe; Es scheint nur so, als ob Sie versuchen, sich zu verteidigen, ohne wirklich konstruktiv zu sein. Inwiefern finden Sie es vage? Wie würden Sie es umschreiben? Möchten Sie die Frage bearbeiten? Möchtest du Doorknob fragen?
Mitch Schwartz
1
Oh, also müssen wir nur zusammenhängende Sequenzen entfernen?
mbomb007

Antworten:

10

REBEL - 104

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

Verwendung:

Eingabe: Liest eine Zeile von stdin.

Ausgabe: Druckt eine Zeile auf Standardausgabe.

Anomalien *:

  • Die Eingabe _bewirkt, dass eine andere Zeile gelesen und verwendet wird, anstatt nichts auszugeben.
  • Der zweite Test gibt ++++>----<statt +++>-<+>---<. Aber das ist in Ordnung, oder? ;)
  • >-<+etc. werden ersetzt durch +>-<etc.

Spoiler:

Das Implementieren von Anomalie 3 macht die Dinge ziemlich trivial.

* Es ist kein Fehler, es ist ein Feature!

Kendall Frey
quelle
"Es ist kein Fehler, es ist eine Funktion" +1!
Rohan Jhunjhunwala
36

Brainfuck, 579 Bytes

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

Mit Formatierung und einigen Kommentaren:

,
[
  <<+>> >>+<<
  [
    [<+> >+<-]
    ++++++[>-------<-]
    >-
    [
      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
          ++.[-]
          >>>>>>>
        ]
        <
      ]
    ]
    >>
  ]
  <[>>>>>>>]
  +[-<<<<<[-]<<]
  ,
]

Dies erfolgt nach dem gleichen Ansatz wie bei Keith Randalls Lösung, bei dem alle aufeinander folgenden Sequenzen +-<>durch Simulation optimal minimiert werden. Zum Beispiel +++>-<+>---<wird ++++>----<und >+<+<<+>+<->>>>wird +<+>>+>.

Probieren Sie es online aus. (Wenn sich der Absolutwert einer simulierten Zelle 256 nähert, treten Überlaufprobleme auf.)

Die Gesamtstruktur ist

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

Das Band ist in 7-Zellen-Knoten unterteilt. am anfang der inneren schleife befindet sich das speicherlayout

0 s 0 c 0 a b

Dabei sist ein Boolesches Flag für die Startzelle cdas aktuelle Zeichen, ader negative Teil des simulierten Zellenwerts (plus eins) und bder positive Teil des simulierten Zellenwerts.

Wenn die verkleinerte Sequenz gedruckt wird, lautet das Speicherlayout

d n e 0 0 a b

woher d ist ein Boolesches Flag für Richtung aund bsind wie zuvor (werden aber eins / null, wenn gedruckt), und nund esind nur ungleich Null für den Endknoten; nhängt davon ab, wie oft der Knoten gesehen wurde, und eist der Wert des Zeichens, das die innere Schleife angehalten hat (plus eins).

Ursprünglich dachte ich darüber nach, mehr Informationen pro Knoten zu erfassen: linker und rechter Knoten als Boolesche Flags und die Position des Knotens in Bezug auf den Start- und Endknoten. Wir können dies jedoch vermeiden, indem wir bei Bedarf auf benachbarte Zellen schauen und nach links und rechts scannen, um den Startknoten zu finden.

Wenn wir die verkleinerte Sequenz drucken und entscheiden, wie der simulierte Zeiger bewegt werden soll, können wir einen allgemeinen Ansatz verfolgen: Beginnen Sie, indem Sie sich vom Endknoten wegbewegen (in einer beliebigen Richtung, wenn Start- und Endknoten gleich sind), und drehen Sie sich ganz links und ganz rechts herum Knoten und Stopp basierend auf der Häufigkeit, mit der der Endknoten gesehen wurde: 3 Mal, wenn Start- und Endknoten identisch sind, andernfalls 2 Mal.

Mitch Schwartz
quelle
2
Quelle: Brainfuck. Ziel: Brainfuck. +1
Erik the Outgolfer
2
Dies erfüllt eine unbestimmte Prämie
Destructible Lemon
1
Ich lasse dies ein wenig Aufmerksamkeit erregen und
vergebe
1
@MitchSchwartz Haben Sie Ihren Code zufällig mit Ihrem Code verglichen? Sie können es tatsächlich verkürzen! #meta
WallyWest
1
@WallyWest (Das scheint 7 Bytes zu sparen!) Ach, der Code im Permalink hat Zeilenumbrüche.
Dennis
7

Python, 404 Zeichen

Dieser Code optimiert alle Teilsequenzen von +-<>. Ein bisschen mehr, als Sie verlangt haben, aber los geht's.

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) 

Dies funktioniert durch Simulieren der +-<>Vorgänge auf dem Band t. sist die Startposition auf dem Band und pist die aktuelle Position. Nach der Simulation wird der Umfang ermittelt [a,b], der bearbeitet werden muss, und alle +/- in einem optimalen Durchgang ausgeführt.

Keith Randall
quelle
1

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 (bitte verzeihen Sie die Verwendung von bit.ly hier, die gesamte URL würde die Markierung aufheben)

Unkomprimierte Version (mit Debug-Code):

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
TimWolla
quelle
Eine alternative Möglichkeit, Coffeescript-Demos zu veröffentlichen, ist die Verwendung von JSFiddle . Am linken Rand befindet sich ein "Languages" -Konfigurationsfenster, in dem Sie CoffeeScript anstelle von JS verwenden können.
Peter Taylor
@PeterTaylor Danke, ich wusste schon vorher über JSFiddle Bescheid, aber nicht, dass es CoffeeScript
TimWolla
Dies schlägt fehl >+.-<und erzeugt die leere Zeichenfolge, anstatt sie unverändert zu lassen.
Mitch Schwartz