Der Räuberherausforderungs-Thread ist da .

Die Herausforderung von Cops: Entwerfen Sie eine Programmiersprache, die für die Programmierung unbrauchbar zu sein scheint, aber die Berechnung (oder zumindest den Abschluss der Aufgabe) über einen nicht offensichtlichen Mechanismus zulässt.

Sie sollten eine einfache Programmiersprache entwerfen, die Code aus einer Eingabedatei liest und dann ... etwas unternimmt. Sie müssen ein Lösungsprogramm vorbereiten , das die drittgrößte Zahl in der Eingabe findet, wenn es in Ihrem Interpreter ausgeführt wird. Sie müssen es den Räubern so schwer wie möglich machen, ein Lösungsprogramm zu finden. Beachten Sie, dass Räuber jede Lösung posten können , die die Aufgabe erfüllt, und nicht nur die, die Sie sich vorgestellt haben.

Dies ist ein Beliebtheitswettbewerb. Das Ziel der Polizei ist es, so viele Stimmen wie möglich zu erhalten, während sie 8 Tage nach dem Absenden des Dolmetschers überlebt, ohne geknackt zu werden. Zu diesem Zweck sollten die folgenden Vorgehensweisen hilfreich sein:

• Erklären Sie genau die Semantik Ihrer Sprache
• Lesbaren Code schreiben

Von folgenden Taktiken wird dringend abgeraten:

• Verwenden von Verschlüsselung, Hashes oder anderen kryptografischen Methoden. Wenn Sie eine Sprache sehen, die RSA-Verschlüsselung verwendet, oder die Ausführung eines Programms verweigert, es sei denn, der SHA-3-Hash ist gleich 0x1936206392306, zögern Sie nicht, eine Ablehnung vorzunehmen.

Die Herausforderung von Robbers: Schreiben Sie ein Programm, das die drittgrößte Ganzzahl in der Eingabe findet, wenn es im Interpreter der Polizei ausgeführt wird.

Dieser ist relativ einfach. Um eine Cop-Antwort zu knacken, müssen Sie ein Programm erstellen, das die Aufgabe abschließt, wenn es in seinem Interpreter ausgeführt wird. Wenn Sie eine Antwort knacken, geben Sie in der Antwort des Polizisten, die mit Ihrem Beitrag verknüpft ist, einen Kommentar mit der Aufschrift "Geknackt" ein. Wer die meisten Bullen knackt, gewinnt den Raubfaden.

E / A-Regeln

• Dolmetscher sollten in der Befehlszeile einen Dateinamen für das Programm verwenden und beim Ausführen die Standardeingabe und -ausgabe verwenden.
• Die Eingabe erfolgt unär und besteht nur aus den Zeichen 0und 1(48 und 49 in ASCII). Eine Zahl N wird als N 1s gefolgt von a codiert 0. Es gibt eine zusätzliche 0vor dem Ende der Datei. Beispiel: Für die Sequenz (3, 3, 1, 14) lautet die Eingabe 11101110101111111111111100.
• Die Eingabe hat garantiert mindestens 3 Zahlen. Alle Zahlen sind positive ganze Zahlen.
• Die Ausgabe wird anhand der Anzahl der 1gedruckten Sekunden beurteilt, bevor das Programm angehalten wird. Andere Zeichen werden ignoriert.

In den folgenden Beispielen ist die erste Zeile die Eingabe im Dezimalformat. die zweite ist die tatsächliche Programmeingabe; Die dritte ist eine Beispielausgabe.

1, 1, 3
101011100
1

15, 18, 7, 2, 15, 12, 3, 1, 7, 17, 2, 13, 6, 8, 17, 7, 15, 11, 17, 2
111111111111111011111111111111111101111111011011111111111111101111111111110111010111111101111111111111111101101111111111111011111101111111101111111111111111101111111011111111111111101111111111101111111111111111101100
111111,ir23j11111111111u

247, 367, 863, 773, 808, 614, 2
<omitted>
<contains 773 1's>

Langweilige Regeln für Cop Antworten:

• Um Sicherheit durch Unklarheit zu verhindern, sollte der Interpreter in einer Sprache geschrieben sein, die in den Top 100 dieses TIOBE-Index steht, und über einen frei verfügbaren Compiler / Interpreter verfügen.
• Der Dolmetscher darf keine Sprache interpretieren, die vor dieser Aufforderung veröffentlicht wurde.
• Der Dolmetscher sollte in Ihre Stelle passen und nicht extern gehostet werden.
• Der Dolmetscher sollte deterministisch sein
• Der Dolmetscher sollte tragbar sein und dem Standard seiner eigenen Sprache folgen. Verwenden Sie keine undefinierten Verhaltensweisen oder Fehler
• Wenn das Lösungsprogramm zu lang ist, um in die Antwort zu passen, müssen Sie ein Programm veröffentlichen, das es generiert.
• Das Lösungsprogramm sollte nur aus druckbarem ASCII und Zeilenumbrüchen bestehen.
• Sie müssen Ihr Lösungsprogramm für jede der obigen Beispieleingaben in weniger als 1 Stunde auf Ihrem eigenen Computer ausführen.
• Das Programm sollte für Ganzzahlen unter 10 ⁶ und für eine beliebige Anzahl von Ganzzahlen unter 10 ⁶ (nicht unbedingt in weniger als einer Stunde) funktionieren , vorausgesetzt, die Gesamteingabelänge beträgt weniger als 10 ⁹ .
• Um sicher zu gehen, muss ein Polizist das Lösungsprogramm nach Ablauf von 8 Tagen in der Antwort bearbeiten.

Wertung

Der Cop, der mit der höchsten Punktzahl und einer positiven Punktzahl in Sicherheit ist, gewinnt diese Frage.

Changeling (sicher)

ShapeScript

ShapeScript ist eine natürlich vorkommende Programmiersprache. Shape Shifter (oder Changelings , wie sie am liebsten genannt werden) können in eine Reihe von Anweisungen umgewandelt werden, mit denen sie Daten verarbeiten können.

ShapeScript ist eine stapelbasierte Sprache mit einer relativ einfachen Syntax. Es ist nicht verwunderlich, dass sich die meisten der integrierten Funktionen mit der Änderung der Form von Saiten befassen. Es wird zeichenweise wie folgt interpretiert:

• 'und "beginne ein String-Literal.

  Bis das übereinstimmende Zitat im Quellcode gefunden wird, werden alle Zeichen zwischen diesen übereinstimmenden Zitate in einer Zeichenfolge gesammelt, die dann auf den Stapel verschoben wird.

• 09um die ganzen Zahlen 0 bis 9 auf den Stapel zu schieben . Beachten Sie, dass 10schiebt zwei ganzen Zahlen.

• ! Fügt eine Zeichenfolge aus dem Stapel hinzu und versucht, sie als ShapeScript auszuwerten.

• ? Fügt eine Ganzzahl aus dem Stapel hinzu und legt eine Kopie des Stapelelements an diesem Index ab.

  Index 0 entspricht dem obersten Stapelelement (LIFO) und Index -1 dem untersten.

• _ Entfernt ein Iterationsobjekt aus dem Stapel und verschiebt seine Länge.

• @ Löst zwei Elemente aus dem Stapel und verschiebt sie in umgekehrter Reihenfolge.

• $Löst zwei Zeichenfolgen aus dem Stapel und teilt die unterste Zeichenfolge bei Auftreten der obersten Zeichenfolge auf. Die resultierende Liste wird zurückgeschoben.

• &Fügt eine Zeichenfolge (ganz oben) und ein Iterationszeichen aus dem Stapel hinzu und fügt das Iterationszeichen hinzu, wobei die Zeichenfolge als Trennzeichen verwendet wird. Die resultierende Zeichenfolge wird zurückgegeben.

• Wenn ShapeScript auf unserem Planeten verwendet wird, da Pythons die Wechselbälger engsten Verwandten auf der Erde sind, alle anderen Zeichen c zwei Artikel Pop - x und y (oberste) vom Stapel, und versuchen , den Python - Code zu bewerten x c y.

  Beispielsweise 23+würde die Zeichenfolge ausgewertet 2+3, während die Zeichenfolge "one"3*ausgewertet 'one'*3und die Zeichenfolge 1''Aausgewertet würde 1A''.

  Im letzten Fall würde sich der Changeling beschweren, da das Ergebnis kein gültiges Python ist, da es kein gültiges ShapeScript ist (Syntaxfehler).

Vor dem Ausführen des Codes legt der Interpreter die gesamte Benutzereingabe in Form einer Zeichenfolge auf dem Stapel ab. Nach dem Ausführen des Quellcodes druckt der Interpreter alle Elemente auf dem Stapel. Wenn ein Teil dazwischen ausfällt, wird der Changeling beschweren, dass seine aktuelle Form unangemessen ist (Laufzeitfehler).

Formänderung

In ihrem natürlichen Zustand haben Änderungen nicht die Form von ShapeScript. Einige von ihnen können sich jedoch in einen potenziellen Quellcode verwandeln (was nicht unbedingt nützlich oder sogar syntaktisch gültig ist).

Alle berechtigten Änderungen haben die folgende natürliche Form:

• Alle Zeilen müssen die gleiche Anzahl von Zeichen haben.

• Alle Zeilen müssen aus druckbaren ASCII-Zeichen bestehen, gefolgt von einem einzelnen Zeilenvorschub.

• Die Anzahl der Zeilen muss mit der Anzahl der druckbaren Zeichen pro Zeile übereinstimmen.

Beispielsweise ist die Bytesequenz ab\ncd\neine zulässige Änderung.

Bei dem Versuch, in ShapeScript zu wechseln, wird das Changeling wie folgt transformiert:

• Anfangs gibt es keinen Quellcode.

• Für jede Zeile passiert folgendes:

  • Der Akkumulator des Changeling wird auf Null gesetzt.

  • Für jedes Zeichen c der Zeile (einschließlich des nachfolgenden Zeilenvorschubs) wird der Codepunkt von c mit dem durch 2 geteilten Akkumulator XOR-verknüpft, und das Unicode-Zeichen, das dem resultierenden Codepunkt entspricht, wird an den Quellcode angehängt.

    Danach wird die Differenz zwischen dem Codepunkt von c und dem Codepunkt eines Leerzeichens (32) zum Akkumulator addiert.

Wenn ein Teil des oben genannten fehlschlägt, wird der Changeling sich darüber beklagen, dass seine aktuelle Form unangenehm ist.

Nachdem alle Zeilen verarbeitet wurden, ist die Umwandlung von Changeling in (hoffentlich gültiges) ShapeScript abgeschlossen und der resultierende Code wird ausgeführt.

Lösung (ShapeScript)

"0"@"0"$"0"2*&"0"@+0?_'@1?"0"$_8>"1"*+@1?"0"+$""&'*!#

ShapeScript erwies sich tatsächlich als recht brauchbar. es kann sogar Primalitätstests ( Beweise ) durchführen und erfüllt daher unsere Definition der Programmiersprache.

Ich habe ShapeScript auf GitHub neu veröffentlicht , mit einer leicht geänderten Syntax und besseren E / A.

Der Code bewirkt Folgendes:

"0"@    Push "0" (A) and swap it with the input string (S).
"0"$    Split S at 0's.
"0"2*   Push "00".
&       Join the split S, using "00" as separator.
"0"@+   Prepend "0" to S.
        The input has been transformed into
        "0<run of 1's>000<run of 1's>0...0<run of 1's>0000".
0?_     Push a copy and compute its length (L).
'       Push a string that, when evaluated, does the following:
  @1?     Swap A on top of S, and push a copy of S.
  "0"$    Split the copy of S at 0's.
  _8>     Get the length of the resulting array and compare it with 8.
          If this returns True, there are more than eight chunks, so there are
          more then seven 0's. With two 0's surrounding each run of 1's and
          three extra 0's at the end, this means that there still are three or
          more runs of 1's in the string.
  "1"*    Push "1" if '>' returned True and "" if it returned False.
  +       Append "1" or "" to A.
  @1?     Swap S on top of A, and push a copy of A.
  "0"+    Append "0" to the copy of A.
  $       Split S at occurrences of A+"0".
  ""&     Flatten the resulting array of strings.
'       This removes all occurrences of "010" in the first iteration, all
        occurrences of "0110" in the second, etc., until there are less than
        three runs of 1's left in S. At this point, A is no longer updated,
        and the code inside the string becomes a noop.
*!      Repeat the code string L times and evaluate.
#       Drop S, leaving only A on the stack.

Lösung (Changeling)

"1+-.......................
""B1.......................
"" 2)+7....................
"" 2)=<....................
""( $86=...................
""B8=......................
""247......................
""]`b......................
""B1.......................
""%D1=.....................
""%500=....................
""%&74?....................
""%&#.2....................
""%[bdG....................
""%D1=.....................
""%<5?.....................
""%:6>.....................
""%&65?....................
""%&-%7>...................
""%D1=.....................
""%500=....................
""%&74?....................
""%&,)5>...................
""%&%,79...................
"" )$?/=...................
""),-9=....................
""# !......................

Wie alle Changeling-Programme verfügt dieser Code über einen nachgestellten Zeilenvorschub.

ShapeScript wird Fehler sofort auf jedes Zeichen nicht verstehen, aber wir können beliebige Zeichenfolgen als Füllstoffe drücken und sie später einfügen. Dies ermöglicht es uns, nur eine kleine Menge Code in jede Zeile zu schreiben (am Anfang, wo der Akku klein ist), gefolgt von einer Öffnung ". Wenn wir die nächste Zeile mit beginnen "#, schließen wir den String und fügen ihn ein, ohne den eigentlichen Code zu beeinflussen.

Außerdem müssen wir drei kleine Hindernisse überwinden:

• Die lange Zeichenfolge im ShapeScript-Code ist ein einzelnes Token und kann nicht in eine Zeile eingefügt werden.

  Wir werden diesen String in Chunks ( '@', '1?'usw.) verschieben, die wir später verketten werden.

• Der Codepunkt von _ist ziemlich hoch und das Drücken '_'wird problematisch sein.

  Wir können jedoch '_@'mühelos pushen , gefolgt von einem anderen '@', um den Swap rückgängig zu machen.

Der ShapeScript Code unserer Wechselbalg wird wie folgt aussieht erzeugen ¹ :

"0""
"#@"
"#"0"$"
"#"0"2"
"#*&"0""
"#@+"
"#0?"
"#_@"
"#@"
"#'@'"
"#'1?'"
"#'"0'"
"#'"$'"
"#'_@'"
"#'@'"
"#'8'"
"#'>'"
"#'"1'"
"#'"*+'"
"#'@'"
"#'1?'"
"#'"0'"
"#'"+$'"
"#'""&'"
"#"+"77"
"#+*!*"
"#!#"

Ich habe den Changeling-Code gefunden, indem ich den obigen ShapeScript-Code über diesen Konverter ausgeführt habe . ²

Dolmetscher (Python 3)

#!/usr/bin/env python3

import fileinput

def error(code):
  print("This shape is " + ["unpleasant", "unpurposed", "inadequate"][code - 1] + ".")
  exit(code)

def interpret(code):
  global stack
  stringing = 0
  for char in code:
    quote = (char == "'") + 2 * (char == '"')
    if quote or stringing:
      if not stringing:
        string = ""
        stringing = quote
      elif stringing == quote:
        stack.append(string)
        stringing = 0
      else:
        string += char
    elif char in "0123456789":
      stack.append(int(char))
    else:
      x = stack.pop()
      if char == '!':
        interpret(x)
      else:
        if char == '?':
          y = stack[~x]
        elif char == "_":
          y = len(x)
        else:
          y = stack.pop()
          if char == '@':
            stack.append(x)
          elif char == '$':
            y = y.split(x)
          elif char == '&':
            y = x.join(map(str, y))
          else:
            try:
              y = eval(repr(y) + char + repr(x))
            except SyntaxError:
              error(2)
        stack.append(y)

source = ""
lengths = []

for line in fileinput.input():
  if not line or sorted(line)[:2][-1] < " " or max(line) > "~":
    error(1)
  lengths.append(len(line))
  accumulator = 0
  for char in line:
    value = ord(char)
    try:
      source += chr(value ^ (accumulator >> 1))
    except:
      error(1)
    accumulator += value - 32

lengths.append(len(lengths) + 1)

if min(lengths) != max(lengths):
  error(1)

stack = ""

for line in fileinput.input("-"):
  stack += line

stack = [stack]

try:
  interpret(source)
except:
  error(3)

print("".join(map(str, stack)))

¹ _{Jede Zeile wird mit Zufallsmüll auf die Anzahl der Zeilen aufgefüllt, und die Zeilenvorschübe sind tatsächlich nicht vorhanden.}
² _{Die Zahlen unten geben den niedrigsten und höchsten Codepunkt im Changeling-Code an, der zwischen 32 und 126 liegen muss.}

Shuffle (geschrieben in C ++), Cracked! von Martin

Edit Martin hat es geknackt. Klicken Sie auf den Link, um seine Lösung anzuzeigen. Meine Lösung wurde ebenfalls hinzugefügt.

Edit Fixed- print-dBefehl, um sowohl Register als auch Stapel verarbeiten zu können. Da dies ein Debugging-Befehl ist, der in einer Lösung nicht zulässig ist, sollte dies niemanden betreffen, der die vorherige Version des Interpreters verwendet

Ich bin noch neu in diesem Bereich. Wenn also etwas mit meiner Antwort oder meinem Dolmetscher nicht stimmt, lassen Sie es mich bitte wissen. Bitte fragen Sie nach einer Klärung, wenn etwas nicht klar ist.

Ich kann mir nicht vorstellen, dass dies zu schwierig sein wird, aber ich hoffe, dass es eine Herausforderung sein wird. Was Shuffle ziemlich unbrauchbar macht, ist, dass es nur gedruckt wird, wenn sich die Dinge an ihrem richtigen Ort befinden.

-> Grundlagen:

Es gibt 24 Stapel, wir nennen sie stack1, ... stack24. Diese Stapel leben in einer Liste. Zu Beginn eines Programms haben diese Stapel den Wert Null und beginnen an der richtigen Stelle, dh Stapel i an der i-ten Position in der Liste (Beachten Sie, dass wir im Gegensatz zu C ++ ab 1 indexieren). Während eines Programmablaufs ändert sich die Reihenfolge der Stapel in der Liste. Dies ist aus Gründen wichtig, die im Zusammenhang mit den Befehlen erläutert werden.

Es stehen 5 Register zur Verfügung. Sie sind benannt Alberto, Gertrude, Hans, Leopold, ShabbySam. Jedes von diesen wird zu Beginn eines Programms auf Null gesetzt.

Zu Beginn eines Programms gibt es also 24 Stapel, von denen jeder eine Nummer hat, die seinem Index in der Stapelliste entspricht. Jeder Stapel hat genau eine Null oben. Jedes der fünf Register wird auf Null initialisiert.

-> Befehle und Syntax :

Es gibt 13 Befehle (+1 Debugging-Befehl), die in Shuffle verfügbar sind. Sie sind wie folgt

• cinpushDieser Befehl akzeptiert keine Argumente. Es wartet auf die in der Frage beschriebene Eingabe in der Befehlszeile (andere Eingaben führen zu nicht festgelegten / undefinierten Ergebnissen). Anschließend teilt die Eingabezeichenfolge in ganzen Zahlen, zum Beispiel 101011100-> 1,1,3. Für jede empfangene Eingabe wird Folgendes ausgeführt: (1) Die Liste der Stapel wird basierend auf dem Wert permutiert. Der betreffende ganzzahlige Wert sei a . Wenn a kleiner als 10 ist, erfolgt die Permutation u . Wenn a zwischen 9 und 30 liegt (nicht einschließend), wird Permutation d ausgeführt . Ansonsten macht es die Permutation r . (2) Es drückt dann aauf den Stapel, der an erster Stelle in der Liste steht. Beachten Sie, dass ich das nicht meine stack1(obwohl es der Fall sein kann, der an stack1erster Stelle in der Liste steht). Die Permutationen sind unten definiert. Da dies cinpushder einzige Weg ist, Benutzereingaben zu erhalten , müssen diese in jeder Lösung erscheinen.

• mov value registerDer movBefehl ist im Grunde eine variable Zuweisung. Es weist valuezu register. valuekann verschiedene Formen annehmen: Es kann (1) eine Ganzzahl sein, zB 47 (2) der Name eines anderen Registers, zB Hans (3) der Index eines Stapels gefolgt von 's', zB 4s. Beachten Sie, dass dies der Index in der Liste ist, nicht die Nummer des Stapels. Daher sollte die Anzahl 24 nicht überschreiten.

  Einige movBeispiele:

  mov 4s Hans 
  mov Hans ShabbySam
  mov 9999 Gertrude
  

• movfs index registerDies steht für "Move from Stack". Es ist dem movBefehl ähnlich . Es ist vorhanden, damit Sie auf einen durch ein Register indizierten Stapel zugreifen können. Wenn Sie beispielsweise zuvor Hans auf 4 ( mov 4 Hans) gesetzt haben, können Sie movfs Hans GertrudeGertrude mit auf den Anfang von Stapel 4 setzen. Auf diese Art von Verhalten kann nicht einfach mit zugegriffen werden mov.

• inc register Erhöht den Registerwert um 1.
• dec register verringert den Registerwert um 1.
• compg value value registerDies steht für "größer vergleichen". Es setzt das Register gleich dem größeren der beiden Werte. valuekann eine Ganzzahl, ein Register oder ein Stapelindex sein, gefolgt von 's', wie oben.
• compl value value register 'compare lesser' wie oben, außer dass der kleinere Wert verwendet wird.
• gte value1 value2 registerPrüft, ob value1 >= value2dann der Boolesche Wert (als 1 oder 0) eingegeben wird register.
• POP!! indexEntfernt sich vom oberen Rand des Stapels, der indexin der Stapelliste durch gekennzeichnet ist.
• jmp labelspringt bedingungslos zum Etikett label. Dies ist ein guter Zeitpunkt, um über Labels zu sprechen. Ein Label ist ein Wort gefolgt von ':'. Der Interpreter parst Labels vor, sodass Sie sowohl vorwärts als auch rückwärts zu Labels springen können.
• jz value labelspringt zu labelwenn valueNull ist.

• jnz value labelspringt zu labelwenn valueungleich Null ist.

  Beispiele für Beschriftungen und Springen:

  this_is_my_label:
       jmp this_is_my_label
  
  mov 10 Hans
  jnz Hans infinite_loop
  
  infinite_loop:
       jmp infinite_loop
  

• "shuffle" permutationHier ist der Shuffle-Befehl. Auf diese Weise können Sie die Liste der Stapel verschieben. Es gibt drei gültige Permutationen , die als Argumente verwendet werden können l, fund b.

• print registerDies prüft, ob sich alle Stapel in ihrer Anfangsposition befinden, dh der Stapel i befindet sich am Index i in der Stapelliste. Wenn dies der Fall ist, wird der Wert mit registerunär ausgegeben. Andernfalls wird ein böser Fehler ausgegeben. Wie Sie sehen, müssen sich alle Stapel an den richtigen Stellen befinden, um etwas auszugeben.
• done!Dies weist das Programm an, ohne Fehler zu beenden. Wenn das Programm ohne beendet done!wird, druckt es die Nummer über jedem Stapel, gefolgt von der Nummer des Stapels, auf die Konsole. Die Reihenfolge, in der die Stapel gedruckt werden, ist die Reihenfolge, in der sie in der Stapelliste angezeigt werden. Wenn ein Stapel leer ist, wird er weggelassen. Dieses Verhalten dient zum Debuggen und kann möglicherweise nicht in einer Lösung verwendet werden.
• print-d valueDies gibt den Wert des angegebenen Stapels, Registers oder der angegebenen Ganzzahl aus (um auf den Stapel i zuzugreifen , übergeben Sie ihn isals Argument, wie oben erläutert). Dies ist ein Debugging-Tool und nicht Teil der Sprache, da dies in einer Lösung nicht zulässig ist.

-> Hier ist der Interpretercode

Das gesamte Parsen findet in der Hauptfunktion statt. Hier finden Sie das Parsen für bestimmte Befehle.

#include<fstream>
#include<iostream>
#include<string>
#include<stack>
#include<cmath>

using namespace std;

class superStack: public stack<long> {
    private:
        int m_place;
    public:
        static int s_index;


        superStack() {
            m_place = s_index;
            s_index++;
        }

        int place() {
            return m_place;
        }
};
int superStack::s_index=1;

superStack  stack1,stack2,stack3,stack4,stack5,stack6,stack7,stack8,stack9,stack10,stack11, \
            stack12,stack13,stack14,stack15,stack16,stack17,stack18,stack19,stack20,stack21,stack22,stack23,stack24;


superStack* stackptrs[]=    { \
                        &stack1,&stack2,&stack3,&stack4,&stack5,&stack6,&stack7,&stack8,&stack9,&stack10,&stack11, \
                        &stack12,&stack13,&stack14,&stack15,&stack16,&stack17,&stack18,&stack19,&stack20,&stack21,&stack22,&stack23,&stack24 \
                        };


long Gertrude=0;
long Hans=0;
long Alberto=0;
long ShabbySam=0;
long Leopold=0;


void SWAP( int i, int j) {    // 0 < i,j < 25

    i--;
    j--;


    superStack* tempptr = stackptrs[i];
    stackptrs[i]=stackptrs[j];
    stackptrs[j] = tempptr;



}

void u() {
    int list[3][4] = {
                        {1,9,6,13},
                        {2,10,5,14},
                        {17,19,20,18},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void d() {
    int list[3][4] = {
                        {3,11,8,15},
                        {4,12,7,16},
                        {22,24,23,21},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void r() {
    int list[3][4] = {
                        {2,17,8,24},
                        {4,18,6,23},
                        {9,10,12,11},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void l() {
    int list[3][4] = {
                        {1,19,7,22},
                        {3,20,5,21},
                        {14,13,15,16},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void f() {
    int list[3][4] = {
                        {20,9,24,16},
                        {18,11,22,14},
                        {1,2,4,3},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void b() {
    int list[3][4] = {
                        {19,10,23,15},
                        {17,12,21,13},
                        {5,6,8,7},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}

void splitpush(string input) {
    long value=0;

    for(long i=0;i<input.size();i++) {

        if(input[i]=='1'){
            value++;
        }
        else if(input[i]=='0' && value!=0 ) {
            if(value<10) {
                u();
            }
            else if (value<30) {
                d();

            }
            else {
                r();
            }
            (*stackptrs[0]).push(value);
            value=0;

        }
        else {
            break;
        }

    }

}

long strToInt(string str) { // IF STRING HAS NON DIGITS, YOU WILL GET GARBAGE, BUT NO ERROR
    long j=str.size()-1;
    long value = 0;
    for(long i=0;i<str.size();i++) {
        long x = str[i]-48;

        value+=x*floor( pow(10,j) );
        j--;
    }
    return value;
}

bool isEmpty(superStack stk) {
    if( stk.size()>0){return false; }
    else {return true;}

}    

long getValue(string str) {
    if(str=="ShabbySam") {
        return ShabbySam;
    }
    else if(str=="Hans") {
        return Hans;
    }
    else if(str=="Gertrude") {
        return Gertrude;
    }
    else if(str=="Alberto") {
        return Alberto;
    }   
    else if(str=="Leopold") {
        return Leopold;
    }
    else if(str[ str.size()-1 ]=='s'){
        str.pop_back();

        long index = strToInt(str)-1;

        if( !isEmpty( (*stackptrs[index]) ) ) {
            return (*stackptrs[index]).top();
        }
        else {
            cerr<<"Bad Expression or Empty Stack";


        }   
    }
    else {
        return strToInt(str);
    }

}

void printUnary(long i) {
    while(i>0) {
        cout<<1;
        i--;
    }
}

int main(int argc, char**argv) {

    if(argc<2){std::cerr<<"No input file given"; return 1;}
    ifstream inf(argv[1]);
    if(!inf){std::cerr<<"File open failed";return 1;}

    for(int i=0;i<24;i++) { 
        (*stackptrs[i]).push(0);         // Pre push a zero on every stack
    }

    string labels[20];
    unsigned labelPoints[20];
    int index=0;



    string str;
    while(inf) { //  parse for labels
        inf>>str;
        //cout<<inf.tellg()<<" ";
        if(inf) {
            if(str[str.size()-1]==':') {
                str.pop_back();
                bool alreadyExists = false;
                for(int i=0; i<index;i++){
                    if(labels[i] == str ) { alreadyExists=true;}
                }
                if(!alreadyExists) {
                    labels[index]=str;
                    labelPoints[index]= inf.tellg();
                    index++;
                }
            }

        }

    }
    inf.clear();
    inf.seekg(0,inf.beg);

    while(inf) { // parse for other commands 
        inf>>str;

        if(inf) {


            if(str=="cinpush") {
                string input;
                cin>>input;
                splitpush(input);
            }

            else if(str=="mov") {
                inf>>str;
                long value = getValue(str);

                inf>>str;
                if(str=="Gertrude"){Gertrude=value;}
                else if(str=="Hans"){Hans=value;}
                else if(str=="ShabbySam"){ShabbySam=value;}
                else if(str=="Alberto"){Alberto=value;}
                else if(str=="Leopold"){Leopold=value;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="movfs") {
                inf>>str;
                long index = getValue(str);
                if(!isEmpty( *stackptrs[index-1] )) {
                    inf>>str;
                    long value = (*stackptrs[index-1]).top();
                    if(str=="Gertrude"){Gertrude=value;}
                    else if(str=="Hans"){Hans=value;}
                    else if(str=="ShabbySam"){ShabbySam=value;}
                    else if(str=="Alberto"){Alberto=value;}
                    else if(str=="Leopold"){Leopold=value;}
                    else {cerr<<"Bad register name.";}
                }
                else {
                    cerr<<"Empty Stack";
                }



            }

            else if(str=="inc") {
                inf>>str;
                if(str=="Gertrude"){Gertrude++;}
                else if(str=="Hans"){Hans++;}
                else if(str=="ShabbySam"){ShabbySam++;}
                else if(str=="Alberto"){Alberto++;}
                else if(str=="Leopold"){Leopold++;}
                else {cerr<<"Bad register name. ";}
            }
            else if(str=="dec") {
                inf>>str;
                if(str=="Gertrude"){Gertrude--;}
                else if(str=="Hans"){Hans--;}
                else if(str=="ShabbySam"){ShabbySam--;}
                else if(str=="Alberto"){Alberto--;}
                else if(str=="Leopold"){Leopold--;}
                else {cerr<<"Bad register name. ";}
            }


            else if(str=="compg") {
                inf>>str;
                long value1 = getValue(str);
                inf>>str;
                long value2 = getValue(str);
                inf>>str;
                long larger;
                if(value1>value2){larger = value1;}
                else {larger = value2;}

                if(str=="Gertrude"){Gertrude=larger;}
                else if(str=="Hans"){Hans=larger;}
                else if(str=="ShabbySam"){ShabbySam=larger;}
                else if(str=="Alberto"){Alberto=larger;}
                else if(str=="Leopold"){Leopold=larger;}
                else {cerr<<"Bad register name. ";}

            }
            else if(str=="compl") {
                inf>>str;
                long value1 = getValue(str);
                inf>>str;
                long value2 = getValue(str);
                inf>>str;
                long larger; //LARGER IS REALLY SMALLER HERE
                if(value1>value2){larger = value2;}
                else {larger = value1;}

                if(str=="Gertrude"){Gertrude=larger;}
                else if(str=="Hans"){Hans=larger;}
                else if(str=="ShabbySam"){ShabbySam=larger;}
                else if(str=="Alberto"){Alberto=larger;}
                else if(str=="Leopold"){Leopold=larger;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="gte") {
                inf>>str;
                long value1= getValue(str);
                inf>>str;
                long value2= getValue(str);
                inf>>str;
                bool torf = value1 >= value2;

                if(str=="Gertrude"){Gertrude=torf;}
                else if(str=="Hans"){Hans=torf;}
                else if(str=="ShabbySam"){ShabbySam=torf;}
                else if(str=="Alberto"){Alberto=torf;}
                else if(str=="Leopold"){Leopold=torf;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="lte") {
                inf>>str;
                long value1= getValue(str);
                inf>>str;
                long value2= getValue(str);
                inf>>str;
                bool torf = value1 <= value2;

                if(str=="Gertrude"){Gertrude=torf;}
                else if(str=="Hans"){Hans=torf;}
                else if(str=="ShabbySam"){ShabbySam=torf;}
                else if(str=="Alberto"){Alberto=torf;}
                else if(str=="Leopold"){Leopold=torf;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="POP!!") {
                inf>>str;
                long index = getValue(str);
                index--; //because we (C++ and this interpreter) index differently
                if(!isEmpty( *stackptrs[index] )) {
                    (*stackptrs[index]).pop();
                }
                else {cerr<<"Can't POP!! from empty stack";}

            }

            else if(str=="push"){cerr<<" You can't. ";}

            /*
            else if(str[str.size()-1]==':') {
                str.pop_back();
                bool alreadyExists = false;
                for(int i=0; i<index;i++){
                    if(labels[i] == str ) { alreadyExists=true;}
                }
                if(!alreadyExists) {
                    labels[index]=str;
                    labelPoints[index]= inf.tellg();
                    index++;
                }
            }*/

            else if(str=="jmp") {
                inf>>str;
                for(int i=0;i<index;i++) {
                    if( labels[i]==str) {
                        inf.seekg( labelPoints[i], ios::beg);
                    }
                }
            }
            else if(str=="jz") {
                inf>>str;
                long value = getValue(str);

                if(value==0) {
                    inf>>str;
                    for(int i=0;i<index;i++) {
                        if( labels[i]==str) {
                            inf.seekg( labelPoints[i], ios::beg);
                        }
                    }
                }
            }

            else if(str=="jnz") {
                inf>>str;
                long value = getValue(str);

                if(value!=0) {
                    inf>>str;
                    for(int i=0;i<index;i++) {
                        if( labels[i]==str) {
                            inf.seekg( labelPoints[i], ios::beg);
                        }
                    }
                }
            }

            else if(str== "\"shuffle\"") {
                inf>>str;
                if(str=="l"){ l(); }
                else if(str=="f"){ f(); }
                else if(str=="b"){ b(); }
                else {cerr<<"Bad shuffle parameter";}

            }

            else if(str=="print") {

                for(int i=0;i<24;i++) {

                    if( (i+1) != (*stackptrs[i]).place() ) {
                        cerr<< "Sorry, your stacks are in the wrong place! You can't print unless you put them back! Exiting. ";
                        return 1;
                    }

                }
                inf>>str;
                if(str=="Gertrude"){printUnary(Gertrude);}
                else if(str=="Hans"){printUnary(Hans);}
                else if(str=="ShabbySam"){printUnary(ShabbySam);}
                else if(str=="Alberto"){printUnary(Alberto);}
                else if(str=="Leopold"){printUnary(Leopold);}
                else {cerr<<"Bad register name. ";}


            }

            else if(str=="done!") {return 0;}

            else if(str=="print-d" ){
                inf>>str;
                long value = getValue(str);
                cout<<str;
              }
        }

    }







    /*for(int i=1;i<25;i++) {
        (*(stackptrs[i-1])).push(i);
    }

    u();d();r();l();f();b();
    */

    cout<<"\n";
    for(int i=1;i<25;i++) {
        if( (*(stackptrs[i-1])).size()>0 ) {
            cout<<(*(stackptrs[i-1])).top()<<" "<<(*(stackptrs[i-1])).place()<<"\n";
            (*(stackptrs[i-1])).pop();
        }
    }
    /*
    for (int i=0;i<index;i++) {
        cout<<labels[i]<<": "<<labelPoints[i]<<"\n";
    }*/

    return 1;
}

-> Permutationen Die Permutationen durchdringen die Elemente der Stapelliste auf folgende Weise:

Wo bedeutet das?

(Diese werden auch im Interpretercode angezeigt. Wenn eine Diskrepanz besteht, ist der Interpreter korrekt.)

-> Einfaches Beispiel

Diese beiden einfachen Programme geben die Zahlen von 24 bis 1 (in unary) ohne Leerzeichen aus.

mov 24 Hans
start:
    print Hans
    dec Hans
    jnz Hans start
done!

oder

mov 24 Hans start: print Hans dec Hans jnz Hans start done!

Sie sind das gleiche Programm.

Erklärung und Lösung:

Martin hat auch eine gute Erklärung in seiner Antwort .

Wie Martin herausfand, wurde diese Sprache vom Pocket Cube (auch bekannt als 2x2 Rubik's Cube) inspiriert. Die 24 Stapel sind wie die 24 einzelnen Quadrate auf dem Würfel. Die Permutationen sind die erlaubten Grundbewegungen: hoch, runter, rechts, links, vorne, hinten.

Der Hauptkampf besteht darin, dass beim Drücken von Werten nur drei Züge ausgeführt werden: hoch, runter und rechts. Sie haben jedoch keinen Zugriff auf diese Züge, wenn Sie die Stapel "mischen". Sie haben nur die anderen drei Züge.

Wie sich herausstellt, erstrecken sich beide Sätze von drei Zügen tatsächlich über die gesamte Gruppe (dh sind Generatoren), sodass das Problem lösbar ist. Das bedeutet, dass Sie einen beliebigen 2x2 Rubik-Würfel nur mit 3 Zügen lösen können.

Alles, was Sie tun müssen, ist herauszufinden, wie Sie die Bewegungen nach oben, unten und rechts mithilfe der anderen drei rückgängig machen können. Zu diesem Zweck habe ich ein Computeralgebrasystem namens GAP eingesetzt .

Nachdem Sie die Permutationen rückgängig gemacht haben, ist es ziemlich trivial, die drittgrößte Zahl zu finden.

cinpush
main:
    mov 1s ShabbySam
    POP!! 1
    jmp compare
    continue:
        gte 0 ShabbySam Leopold
        jnz Leopold end
        gte ShabbySam 9 Leopold
        jz Leopold uinverse
        gte ShabbySam 29 Leopold
        jz Leopold dinverse
        jnz Leopold rinverse
compare:
    gte ShabbySam Alberto Leopold
    jz Leopold skip
    mov Gertrude Hans
    mov Alberto Gertrude
    mov ShabbySam Alberto
    jmp continue
    skip:
        gte ShabbySam Gertrude Leopold
        jz Leopold skip_2
        mov Gertrude Hans
        mov ShabbySam Gertrude
        jmp continue
    skip_2:
        gte ShabbySam Hans Leopold
        jz Leopold continue
        mov ShabbySam Hans
        jmp continue
uinverse: 
    "shuffle" f
    "shuffle" f
    "shuffle" f
    "shuffle" l
    "shuffle" b
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" l
    "shuffle" l
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" l
    "shuffle" l
    "shuffle" l
    "shuffle" f
    jmp main
dinverse:
    "shuffle" f
    "shuffle" b
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" f
    "shuffle" f
    "shuffle" f
    jmp main
rinverse: 
    "shuffle" b "shuffle" l "shuffle" f "shuffle" l "shuffle" b
    "shuffle" f "shuffle" f "shuffle" f "shuffle" b
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" b "shuffle" b "shuffle" b
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" f "shuffle" l "shuffle" f
    "shuffle" l "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l 
    "shuffle" f "shuffle" l "shuffle" l 
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" l "shuffle" l "shuffle" l "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" f "shuffle" l "shuffle" f "shuffle" l "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    jmp main
end:
    print Hans
    done!

Brian & Chuck , Gebrochen von cardboard_box

Ich bin schon seit einiger Zeit von der Idee einer Programmiersprache fasziniert, in der zwei Programme miteinander interagieren (wahrscheinlich inspiriert von ROCB ). Diese Herausforderung war ein guter Anreiz, dieses Konzept endlich in Angriff zu nehmen und gleichzeitig die Sprache so gering wie möglich zu halten. Die Entwurfsziele waren, die Sprache Turing-vollständig zu machen, während jedes seiner Teile einzeln nicht Turing-vollständig ist. Darüber hinaus sollten auch beide zusammen nicht vollständig sein, ohne den Quellcode zu manipulieren. Ich glaube, das ist mir gelungen, aber ich habe noch keines dieser Dinge formal bewiesen. Also präsentiere ich Ihnen ohne weiteres ...

Die Protagonisten

Brian und Chuck sind zwei Brainfuck-ähnliche Programme. Es wird immer nur einer hingerichtet, beginnend mit Brian. Der Haken ist, dass Brians Memory Tape auch Chucks Quellcode ist. Und Chucks Memory Tape ist auch Brians Quellcode. Außerdem ist Brians Tonkopf auch Chucks Anweisungszeiger und umgekehrt. Die Bänder sind semi-infinite (dh unendlich rechts) und können vorzeichenbehaftete Ganzzahlen mit willkürlicher Genauigkeit enthalten, die mit Null initialisiert sind (sofern im Quellcode nichts anderes angegeben ist).

Da der Quellcode auch ein Speicherband ist, werden Befehle technisch durch ganzzahlige Werte definiert, sie entsprechen jedoch sinnvollen Zeichen. Die folgenden Befehle sind vorhanden:

• ,( 44): Liest ein Byte von STDIN in die aktuelle Speicherzelle. Das kann nur Brian. Dieser Befehl ist ein No-Op für Chuck.
• .( 46): Schreibe die aktuelle Speicherzelle, Modulo 256, als Byte nach STDOUT. Das kann nur Chuck. Dieser Befehl ist ein No-Op für Brian.
• +( 43): Erhöht die aktuelle Speicherzelle.
• -( 45): Dekrementiert die aktuelle Speicherzelle.
• ?( 63): Wenn die aktuelle Speicherzelle Null ist, ist dies ein No-Op. Andernfalls übergeben Sie die Steuerung an das andere Programm. Der Bandkopf des verwendeten Programms ?verbleibt auf der ?. Der Bandkopf des anderen Programms verschiebt eine Zelle nach rechts, bevor der erste Befehl ausgeführt wird (die als Test verwendete Zelle wird also nicht selbst ausgeführt).
• <( 60): Bewegen Sie den Bandkopf eine Zelle nach links. Dies ist ein No-Op, wenn sich der Bandkopf bereits am linken Ende des Bandes befindet.
• >( 62): Bewegen Sie den Bandkopf eine Zelle nach rechts.
• {( 123): Bewegen Sie den Bandkopf wiederholt nach links, bis entweder die aktuelle Zelle Null ist oder das linke Ende des Bandes erreicht ist.
• }( 125): Bewegen Sie den Bandkopf wiederholt nach rechts, bis die aktuelle Zelle Null ist.

Das Programm wird beendet, wenn der Befehlszeiger des aktiven Programms einen Punkt erreicht, an dem rechts von ihm keine Befehle mehr vorhanden sind.

Der Quellcode

Die Quelldatei wird wie folgt verarbeitet:

• Wenn die Datei die Zeichenfolge enthält ```, wird die Datei um das erste Vorkommen dieser Zeichenfolge in zwei Teile aufgeteilt. Alle führenden und nachfolgenden Leerzeichen werden entfernt und der erste Teil wird als Quellcode für Brian und der zweite Teil für Chuck verwendet.
• Wenn die Datei diesen String nicht enthält, wird die erste Zeile der Datei als Quelle für Brian und der zweite Teil für Chuck verwendet (abgesehen von der abgrenzenden neuen Zeile werden keine Leerzeichen entfernt).
• Alle Vorkommen _in beiden Programmen werden durch NULL-Bytes ersetzt.
• Die beiden Speicherbänder werden mit den Zeichencodes initialisiert, die der resultierenden Zeichenfolge entsprechen.

Als Beispiel die folgende Quelldatei

  abc
```
0_1
23

Würde die folgenden anfänglichen Bänder ergeben:

Brian: [97 98 99 0 0 0 0 ...]
Chuck: [48 0 49 10 50 51 0 0 0 0 ...]

Der Dolmetscher

Der Interpreter ist in Ruby geschrieben. Es dauert zwei Kommandozeilen - Flags , die müssen nicht von einer Lösung verwendet werden (da sie nicht Teil der eigentlichen Sprachspezifikation sind):

• -d: Mit dieser Flagge verstehen Brian und Chuck zwei weitere Befehle. !druckt eine Zeichenfolgendarstellung beider Speicherbänder, wobei das aktive Programm zuerst aufgelistet wird (a ^markiert die aktuellen Bandköpfe). @werde das auch machen, dann aber sofort das programm beenden. Da ich faul bin, funktioniert keiner dieser Befehle, wenn es sich um den letzten Befehl im Programm handelt. Wenn Sie sie dort verwenden möchten, wiederholen Sie sie oder schreiben Sie ein No-Op nach ihnen.
• -D: Dies ist der ausführliche Debug-Modus. Es werden die gleichen Debug-Informationen wie !nach jedem einzelnen Tick ausgegeben. @funktioniert auch in diesem Modus.

Hier ist der Code:

# coding: utf-8

class Instance
    attr_accessor :tape, :code, :ip

    OPERATORS = {
        '+'.ord  => :inc,
        '-'.ord  => :dec,
        '>'.ord  => :right,
        '<'.ord  => :left,
        '}'.ord  => :scan_right,
        '{'.ord  => :scan_left,
        '?'.ord  => :toggle,
        ','.ord  => :input,
        '.'.ord  => :output,
        '!'.ord  => :debug,
        '@'.ord  => :debug_terminate
    }

    OPERATORS.default = :nop

    def initialize(src)
        @code = src.chars.map(&:ord)
        @code = [0] if code.empty?

        @ip = 0
    end

    def tick
        result = :continue
        case OPERATORS[@code[@ip]]
        when :inc
            @tape.set(@tape.get + 1)
        when :dec
            @tape.set(@tape.get - 1)
        when :right
            @tape.move_right
        when :left
            @tape.move_left
        when :scan_right
            @tape.move_right while @tape.get != 0
        when :scan_left
            @tape.move_left while @tape.ip > 0 && @tape.get != 0
        when :toggle
            if @tape.get != 0
                @tape.move_right
                result = :toggle
            end
        when :input
            input
        when :output
            output
        when :debug
            result = :debug
        when :debug_terminate
            result = :debug_terminate
        end

        return :terminate if result != :toggle && @ip == @code.size - 1

        move_right if result != :toggle

        return result
    end

    def move_right
        @ip += 1
        if @ip >= @code.size
            @code << 0
        end
    end

    def move_right
        @ip += 1
        if @ip >= @code.size
            @code << 0
        end
    end

    def move_left
        @ip -= 1 if @ip > 0
    end

    def get
        @code[@ip]
    end

    def set value
        @code[@ip] = value
    end

    def input() end
    def output() end

    def to_s
        str = self.class.name + ": \n"
        ip = @ip
        @code.map{|i|(i%256).chr}.join.lines.map do |l|
            str << l.chomp << $/
            str << ' '*ip << "^\n" if 0 <= ip && ip < l.size
            ip -= l.size
        end
        str
    end
end

class Brian < Instance
    def input
        byte = STDIN.read(1)
        @tape.set(byte ? byte.ord : -1)
    end
end

class Chuck < Instance
    def output
        $> << (@tape.get % 256).chr
    end
end

class BrianChuck

    class ProgramError < Exception; end

    def self.run(src, debug_level=0)
        new(src, debug_level).run
    end

    def initialize(src, debug_level=false)
        @debug_level = debug_level

        src.gsub!('_',"\0")

        if src[/```/]
            brian, chuck = src.split('```', 2).map(&:strip)
        else
            brian, chuck = src.lines.map(&:chomp)
        end

        chuck ||= ""

        brian = Brian.new(brian)
        chuck = Chuck.new(chuck)

        brian.tape = chuck
        chuck.tape = brian

        @instances = [brian, chuck]
    end

    def run
        (puts @instances; puts) if @debug_level > 1

        loop do
            result = current.tick

            toggle if result == :toggle

            (puts @instances; puts) if @debug_level > 1 || @debug_level > 0 && (result == :debug || result == :debug_terminate)

            break if result == :terminate || @debug_level > 0 && result == :debug_terminate
        end
    end

    private

    def current
        @instances[0]
    end

    def toggle
        @instances.reverse!
    end
end

case ARGV[0]
when "-d"
    debug_level = 1
when "-D"
    debug_level = 2
else
    debug_level = 0
end

if debug_level > 0
    ARGV.shift
end

BrianChuck.run(ARGF.read, debug_level)

Hier ist meine eigene (handschriftliche) Lösung für das Problem:

>}>}>
brace left: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace left: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>} Append a bunch of 1s as a dummy list element:
+>+>+>+>+>+>+>+>+>+
Append two 1s and some code to the list; the first is a marker for later; the latter will be the integer
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow right: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
_
{<<<<<<<<<{<{    Move back to the start
Read a character and subtract 48 to get actual 0 or 1
,------------------------------------------------
?   If 1 switch to Chuck otherwise continue
>}>}>>>>>>>>>}<<<<<<- Subtract 1 from the result to account for initial 1
?   If integer was positive switch to Chuck
@todo: process end
_
This code is run when reading 1:
}>}>>>>>>>>>}<<<<<<+ Move to the end of Chuck; skip one null cell; move to the end of the list
{<<<<<<<<<{<?   Move back to the code that resets this loop.
_
This code is run after finalising an integer:
change the code after the integer first
<<--<--<--}
Append two 1s and some code to the list; the first is a marker for later; the latter will be the integer
1: +
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow right: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
{<<<<<<<+<<{<{    Move back to the start; incrementing the list length
Read a character and subtract 48 to get actual 0 or 1
,------------------------------------------------
?   If 1 switch to Chuck otherwise continue
>}>}>>>>>>>>>}
Leave the resetting code, but remove the rest of the last list element:
<<<--<--<--
1: <-
question mk: <---------------------------------------------------------------
arrow left: <------------------------------------------------------------
brace right: <-----------------------------------------------------------------------------------------------------------------------------
1: <-
<{< Move back to the cell we reserved for the counter
<<<<<<-- decrement list size by two so we don't process the two largest elements
_

<{<<<<<<{<{<{<{<{>}>}>>>>>>> This is the beginning of the loop which decrements all list elements by 1
+ Add 1 to the running total
>>- Set marker of dummy list element to zero
_ Beginning of loop that is run for each list element
<{<<<<<<{<{<{<{<{>}>}>}>}+ set last marker back to 1
>>>>>>>>>> move to next marker
? Skip the next bit if we're not at the end of the list
<? Move back to the beginning of the loop
@ we should never get here
_
This is run when we're not at the end of the list
<<<- Set marker to 0 to remember current position
>>>>- Move to the current value and decrement it
? Move back to loop beginning if value is not zero yet
- Make element negative so it's skipped in the future
{<{<{>- Move to remaining list length and decrement it
? If it's nonzero switch to Chuck
>>>>>>>>->->->->->->->->->- Remove the dummy list to make some space for new code:
>}+ Fill in the marker in the list
{<<<<<<<<< Add some loop resetting code after the result:
brace left: +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
_
This loop adds a print command to Chuck's code while decrementing the result
>>>>>>>>}>>>>>}>>>>>} Move to the very end of Chuck's code and leave some space to seek the 1
print: ++++++++++++++++++++++++++++++++++++++++++++++
{<<<<<{<<<<<{<<<<<<<{<
- decrement the result
? if nonzero run loop again
At this point we just need to make Chuck seek for the 1 at the end of this code print it often enough
>>}>>>>>>>}>>>>>}
arrow right: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
<?1 Switch to Chuck which moves Brian's tape head onto the 1 and then prints it N times


```

_   Dummy cell to hold input
This code is run when reading a 1:
{<{<{<{ ensure we're at the start
}>}<? Skip 0 handling code and switch to Brian
_ This code is run after a 1 has been processed:
{<{<?

Dieser Code kann so ausgeführt werden, wie er ist, da alle Anmerkungen No-Ops verwenden und von {und übersprungen werden }.

Die Grundidee ist:

1. Fügen Sie der Liste ein neues Nullelement hinzu (am Ende von Chucks Band) und erhöhen Sie die Listenlänge um 1.
2. Während wir 1s lesen , erhöhen Sie dieses Element.

3. Wenn wir a lesen 0, machen Sie eine Bereinigung. Wenn die resultierende Ganzzahl größer als Null war, kehren Sie zu 1 zurück.

   Jetzt haben wir eine Liste der Eingangsnummern am Ende von Chucks Band und wir kennen die Länge der Liste.

4. Subtrahieren Sie 2 von der Länge der Liste (in den folgenden Schritten werden die beiden größten Elemente ignoriert). Rufen Sie dies auf N.

5. Erhöhen Sie N > 0währenddessen eine laufende Summe und dekrementieren Sie dann alle Listenelemente. Immer wenn ein Listenelement Null erreicht, wird dekrementiert N.

   Am Ende enthält die laufende Summe die drittgrößte Zahl in der Eingabe M.

6. Schreiben Sie MKopien von .bis zum Ende von Chucks Band.

7. Suchen Sie auf Chuck nach einem 1auf Brians Band und führen Sie dann die .am Ende generierten aus .

Als ich damit fertig war, stellte ich fest, dass ich es an einigen Stellen ziemlich stark vereinfachen konnte. Zum Beispiel .könnte ich , anstatt den Zähler zu verfolgen und diese auf Chucks Band zu schreiben 1, jedes Mal sofort einen ausdrucken , bevor ich alle Listenelemente dekrementiere. Änderungen an diesem Code vorzunehmen ist jedoch ein ziemlicher Schmerz, da er andere Änderungen über den gesamten Bereich verbreitet, sodass ich mich nicht darum gekümmert habe, die Änderung vorzunehmen.

Das Interessante ist, wie man die Liste im Auge behält und wie man sie durchläuft. Sie können die Zahlen nicht einfach hintereinander auf Chucks Band speichern. Wenn Sie dann eine Bedingung für eines der Listenelemente überprüfen möchten, besteht die Gefahr, dass der Rest der Liste ausgeführt wird, der möglicherweise gültigen Code enthält. Sie wissen auch nicht, wie lang die Liste sein wird, deshalb können Sie nicht einfach etwas Platz vor Chucks Code reservieren.

Das nächste Problem ist, dass wir die Liste dekrementieren müssen, Nwährend wir sie verarbeiten, und wir müssen an den Ort zurückkehren, an dem wir vorher waren. Aber {und }würde einfach die gesamte Liste überspringen.

Also müssen wir dynamisch Code auf Chuck schreiben. Tatsächlich hat jedes Listenelement idie Form:

[1 <Code A> i <Code B>]

1ist ein Marker, den wir auf Null setzen können, um anzuzeigen, wo wir die Verarbeitung der Liste unterbrochen haben. Sein Zweck ist es zu fangen {oder }was wird nur über den Code und die i. Wir verwenden diesen Wert auch, um zu prüfen, ob wir während der Verarbeitung am Ende der Liste stehen. Wenn dies nicht der Fall ist, wird dies der Fall sein 1und die Bedingung ?wechselt die Steuerung zu Chuck. Code Awird verwendet, um mit dieser Situation umzugehen und die IP von Brian entsprechend zu verschieben.

Wenn wir jetzt dekrementieren i, müssen wir prüfen, ob ibereits Null ist. Während dies nicht der Fall ist, ?wird die Steuerung erneut umgeschaltet, damit muss Code Balso umgegangen werden.

HPR, geschrieben in Python 3 ( Cracked by TheNumberOne )

HPR (der Name bedeutet nichts) ist eine Sprache zum Verarbeiten von Listen mit ganzen Zahlen. Es ist minimalistisch , extrem begrenzt und frei von "künstlichen" Einschränkungen . Das Programmieren in HPR ist schmerzhaft, nicht weil Sie ein Rätsel lösen müssen, um den Interpreter davon abzuhalten, Sie anzuschreien, sondern weil es schwierig ist, ein Programm dazu zu bringen, irgendetwas Nützliches zu tun. Ich weiß nicht, ob HPR wesentlich interessanter ist, als das drittgrößte Element einer Liste zu berechnen.

Sprachspezifikation

Ein HPR-Programm wird in einer Umgebung ausgeführt , bei der es sich um einen ungeordneten, duplikationsfreien Satz nichtnegativer Ganzzahlen und Listen nichtnegativer Ganzzahlen handelt. Anfänglich enthält die Umgebung nur die Eingabeliste (der Interpreter analysiert sie für Sie). Es gibt drei Befehle und zwei "Kontrollfluss" -Operatoren, die die Umgebung ändern:

• *Entfernt das erste Element jeder nicht leeren Liste in der Umgebung und platziert es in der Umgebung. Leere Listen sind nicht betroffen. Zum Beispiel verwandelt es sich

  {4,1,[0,2],[1,3],[]} -> {4,1,0,[2],[3],[]}
  

• -dekrementiert alle Zahlen in der Umgebung und entfernt dann negative Elemente. Zum Beispiel verwandelt es sich

  {4,2,0,[0,2],[4,4,4]} -> {3,1,[0,2],[4,4,4]}
  

• $Dreht jede Liste in der Umgebung um einen Schritt nach links. Zum Beispiel verwandelt es sich

  {4,1,[0,2],[3,4,1]} -> {4,1,[2,0],[4,1,3]}
  

• !(A)(B), wo Aund Bsind Programme, ist im Grunde eine whileSchleife. Es führt die "Aktion" aus, Abis der "Test" Bzu einer leeren Umgebung führen würde. Dies kann eine Endlosschleife erzeugen.
• #(A)(B), wo Aund Bsind Programme, gilt Aund Bfür die aktuelle Umgebung und nimmt die symmetrische Differenz der Ergebnisse.

Die Befehle werden von links nach rechts ausgeführt. Am Ende wird die Größe der Umgebung in Unary gedruckt.

Der Dolmetscher

Dieser Interpreter enthält den Befehl debug ?, der die Umgebung druckt, ohne sie zu ändern. Es sollte in keiner Lösung der Aufgabe vorkommen. Alle Zeichen außer *-$!#()?werden einfach ignoriert, sodass Sie Kommentare direkt in den Code schreiben können. Schließlich erkennt der Interpreter die Redewendung !(A)(#(A)())als "ausführen, Abis sich das Ergebnis nicht mehr ändert" und optimiert sie für zusätzliche Geschwindigkeit (ich brauchte sie, damit meine Lösung im letzten Testfall in weniger als einer Stunde fertig ist).

import sys

def parse(prog):
    "Parse a prefix of a string into an AST. Return it and the remaining input."
    ret = []
    while prog:
        if prog[0] in "#!":
            sub1, prog1 = parse(prog[2:])
            sub2, prog2 = parse(prog1[1:])
            ret += [prog[0],sub1,sub2]
            prog = prog2
        elif prog[0] == ')':
            prog = prog[1:]
            break
        else:
            ret += [prog[0]]
            prog = prog[1:]
    return ret, prog

def intp(ast, L_env, N_env):
    "Interpret the AST on an environment, return the resulting environment."
    ptr = 0
    while ptr < len(ast):
        cmd = ast[ptr]
        if cmd == '*':
            N_env = N_env | set(L[0] for L in L_env if L)
            L_env = set(L[1:] for L in L_env)
            ptr += 1
        elif cmd == '-':
            N_env = set(N-1 for N in N_env if N>0)
            ptr += 1
        elif cmd == '$':
            L_env = set(L[1:]+L[:1] for L in L_env)
            ptr += 1
        elif cmd == '!':
            # Speed optimization
            cond = ast[ptr+2]
            if cond == ['#', ast[ptr+1], []]:
                L_next, N_next = intp(ast[ptr+1], L_env, N_env)
                while L_next != L_env or N_next != N_env:
                    L_env, N_env = L_next, N_next
                    L_next, N_next = intp(ast[ptr+1], L_env, N_env)
            else:
                while True:
                    L_test, N_test = intp(cond, L_env, N_env)
                    if not L_test and not N_test:
                        break
                    L_env, N_env = intp(ast[ptr+1], L_env, N_env)
            ptr += 3
        elif cmd == '#':
            L_env1, N_env1 = intp(ast[ptr+1], L_env, N_env)
            L_env2, N_env2 = intp(ast[ptr+2], L_env, N_env)
            L_env = L_env1 ^ L_env2
            N_env = N_env1 ^ N_env2
            ptr += 3
        elif cmd == '?':
            print(L_env | N_env)
            ptr += 1
        else:
            ptr += 1
    return L_env, N_env

def main(p, L):
    "Run the program on the input, return the output."
    # Parse the input list
    L = ''.join(c for c in L if c in "01")
    while "00" in L:
        L = L.replace("00","0")
    L = [-2] + [i for i in range(len(L)-1) if L[i:i+2] == "10"]
    L = tuple(b-a-1 for (a,b) in zip(L, L[1:]))
    # Parse the program
    ast = parse(p)[0]
    L_env, N_env = intp(ast, set([L]), set())
    return '1'*(len(L_env) + len(N_env))

if __name__ == "__main__":
    filename = sys.argv[1]
    f = open(filename, 'r')
    prog = f.read()
    f.close()
    L = input()
    print(main(prog, L))

Meine Lösung

Meine Referenzlösung ist 484 Byte lang, also ziemlich kurz im Vergleich zum 3271-Byte-Programm von TheNumberOne. Dies ist höchstwahrscheinlich auf das ausgeklügelte und großartige Makrosystem TheNumberOne zurückzuführen, das für die Programmierung in HPR entwickelt wurde. Die Grundidee in unseren beiden Programmen ist ähnlich:

1. Finden Sie heraus, wie Sie das maximale Element einer Liste erzeugen.
2. Um das maximale Element zu entfernen, drehen Sie die Liste, bis das erste Element dem maximalen Element entspricht, und platzieren Sie es dann.
3. Entfernen Sie das Maximum zweimal und drucken Sie dann das neue Maximum-Element.

Soweit ich das beurteilen kann, sind die genauen Implementierungsdetails jedoch sehr unterschiedlich. Hier ist meine Lösung:

!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())-#(!(-)(#(-)()))()

Und hier ist das kommentierte Python-Programm, das es produziert (nichts Besonderes hier, nur grundlegende String-Manipulation, um alle Wiederholungen loszuwerden):

# No numbers in the environment
no_nums = "#(-)()"
# No non-empty lists in the environment
no_lists = "#(*)()"
# Remove all numbers from the environment
del_nums = "!(-)(" + no_nums + ")"
# Remove all lists from the environment
del_lists = "#(" + del_nums + ")()"
# Splat the list to the environment:
#  pop the list until it's empty and delete the empty list,
#  then take symmetric difference with all numbers removed
splat = "#(!(*)(" + no_lists + ")" + del_lists + ")(" + del_nums + ")"
# Put into the environment all numbers up to list maximum:
#  decrement and splat until a fixed point is reached.
#  Without the speed optimization, this is very slow if the list elements are large.
splat_upto = "!(-" + splat + ")(#(-" + splat + ")())"
# Copy maximum element to environment:
#  take all elements up to maximum,
#  then take symmetric difference of decrement and list deletion
copy_max = splat_upto + "#(-)(" + del_lists + ")"
# Delete maximum element from list:
#  rotate until first element is maximal, then pop and delete it
del_max = "!($)(" + del_nums + "#(" + copy_max + ")(*)" + del_lists + ")*" + del_nums
# Full program:
#  remove the maximum twice, then produce all numbers up to maximum,
#  then decrement and remove lists. The environment will contain exactly
#  the integers from 0 to third largest - 1, and their number is printed.
main = del_max + del_max + splat_upto + "-" + del_lists
print(main)

TKDYNS (Um den Drachen zu töten, brauchst du ein Schwert) - Gebrochen von Martin Büttner

EDIT: Ich habe meine Lösung und Erklärung unter dem Hauptbeitrag hinzugefügt.

Hintergrund

In dieser Sprache übernimmst du die Kontrolle über einen tapferen Krieger, der beauftragt wurde, einen schrecklichen Drachen zu töten. Der Drache lebt in einem unterirdischen Labyrinth voller Gefahren und Gefahren, und bis jetzt war niemand in der Lage, dies zu erfassen und zu überleben. Das bedeutet, dass Sie sich in völliger Dunkelheit auf den Weg zum Drachen machen müssen und dabei nur über Intuition und Mut verfügen müssen, um Sie zu führen.

...

Nicht ganz. Sie haben einen nahezu unbegrenzten Vorrat an Einweg-Dienern mitgebracht, und sie sind bereit, Ihnen vorauszugehen, um den sicheren Weg zu finden. Leider sind sie alle so dick wie zwei kurze Bretter und tun nur genau das, was Sie ihnen sagen. Es liegt an Ihnen, eine clevere Methode zu finden, um sicherzustellen, dass Ihre Schergen den richtigen Weg finden.

Noch ein paar Details

Das Versteck des Drachen hat die Form eines 10x10-Gitters. Zwischen bestimmten benachbarten Punkten im Raster befindet sich ein schmaler Gehweg. zwischen anderen gibt es eine tiefe Kluft und einen sicheren Tod. Ein Beispiellayout für ein 4x4-Raster könnte wie folgt aussehen:

 0---1   2---3
     |   |   |
 4---5---6   7
 |           |
 8   9--10  11
     |       |
12--13--14--15

Sie wissen, dass es immer einen Weg gibt, von einem Punkt zu einem anderen zu gelangen, aber nicht mehr als das wurde Ihnen offenbart.

Um den Drachen erfolgreich zu besiegen, musst du zuerst einige Gegenstände einsammeln, die du zu einer magischen Drachentötungsklinge kombinieren kannst. Praktischerweise sind alle Teile für diese Waffe in der Drachenhöhle verteilt. Sie müssen sie nur einsammeln.

Die Wendung ist, dass jedes Stück der Waffe Sprengfallen hat. Bei jeder Abholung ändert sich die Anordnung der Gehwege. Bisher sichere Wege könnten jetzt zum sicheren Tod führen und umgekehrt.

Befehle

Es gibt nur 5 gültige Befehle.

• < - Machen Sie einen Schritt nach links

• > - Machen Sie einen Schritt nach rechts

• ^ - Machen Sie einen Schritt nach oben

• v - Machen Sie einen Schritt nach unten

• c- Sammeln Sie alle Gegenstände, die an Ihrer aktuellen Position herumliegen. Wenn Gegenstände vorhanden waren, ändert sich das Layout der Höhle. Nehmen Sie Ihre Position modulo 10, wobei die Positionen wie oben in Zeilen nummeriert sind. Der Interpreter enthält 10 fest codierte Layouts, und das Layout ändert sich in das entsprechende Layout. Wenn Sie sich beispielsweise an Position 13 befinden, ändert sich das Layout inlayouts[3]

Die Layouts, wie sie im Interpeter erscheinen, wurden wie folgt in Ganzzahlen codiert:

• Das leere Layout wird zu Null codiert.

• Sei für jede Kante im Layout xdie kleinere der beiden Positionen, die sie verbindet.

  • Wenn der Schritt horizontal ist, fügen Sie 2^(2*x)die Codierung hinzu (das ist die Potenz von, nicht XOR)

  • Wenn der Schritt vertikal ist, fügen Sie 2^(2*x + 1)der Codierung hinzu.

Ausführungsablauf

Der Interpreter wird mit dem Namen einer Quelldatei als Befehlszeilenargument ausgeführt.

Wenn der Interpreter ausgeführt wird, fordert er den Benutzer auf, eine Quest einzugeben. Diese Eingabe sollte in der in der Frage beschriebenen Form erfolgen und die Positionen der Komponenten der Waffe im Versteck bestimmen. Insbesondere wird jede eingegebene Ganzzahl modulo 100 genommen und an der entsprechenden Stelle in der Höhle platziert.

Jedes Quellprogramm besteht aus mehreren Zeilen, wobei jede Zeile aus einer Folge der oben genannten 5 gültigen Zeichen besteht. Diese Linien repräsentieren Ihre Schergen. Du, der Krieger, verfolgst eine Abfolge von Aktionen, von denen bekannt ist, dass sie sicher sind. Anfangs wissen Sie nichts über die Höhle, daher ist diese Sequenz leer. Bei jedem Diener wird ab Position 0 Folgendes ausgeführt:

• Der Diener wird angewiesen, alle als sicher bekannten Aktionen auszuführen, gefolgt von den Aktionen in seiner eigenen Codezeile.

  • Wenn der Diener zu irgendeinem Zeitpunkt stirbt, werden Sie darüber informiert und das Versteck wird auf seine ursprüngliche Konfiguration zurückgesetzt. Alle Gegenstände werden ersetzt und die Laufstege kehren in ihre Ausgangsposition zurück.

  • Wenn stattdessen der Diener überlebt, verdampft man ihn trotzdem - es ist schließlich nur ein Diener. Wie zuvor löst dies das Zurücksetzen des Verstecks ​​in den Ausgangszustand aus, aber dieses Mal hängen Sie die Aktionen aus der Codezeile des Schergen an die Sequenz der als sicher bekannten Aktionen an.

Sobald alle Schergen erschöpft sind, führen Sie als Krieger alle als sicher bekannten Aktionen aus, und zwar wieder ab Position 0. Es gibt zwei mögliche Ergebnisse:

• Sie sammeln alle Teile der Waffe - in diesem Fall töten Sie den Drachen erfolgreich und es wird eine aufregende Siegesbotschaft ausgegeben. Diese Siegesnachricht enthält unter anderem Zeichen, nwobei ndie dritthöchste Zahl als Eingabe angegeben wird.

• Sie haben einige Waffenteile nicht eingesammelt - in diesem Fall lebt der Drache weiter und Sie haben Ihre Suche nicht bestanden.

Dolmetschercode (Python 2)

import collections
import copy
import sys

size = 10
layouts = [108705550239329248440770931020110627243913363144548922111951,108386637020100924277694952798729434993885646706222210602969,133885860318189115027934177821170081234850573770998325845482,102397795295522647918061101991513921833376565032742993744791,131948019244359669407266662537098175265242405785636894694611,127512068876349726396523358265982765442984953916545984706958,106817519055019354200334114020150263381328246524221867629943,33472343358375525802921815863230485208221126168622186265959,133909781123963725874096031069972704024813281938330035579187,132244654022332695610020359820518831299843076834682749020986]

class Interpreter(object):

    def __init__(self, source_file):
        self.source_filename = source_file
        self.layout = layouts[0]
        self.position = 0
        self.ingredients = []
        self.quest_items = {}
        self.attempts = collections.deque()

        self.safe_position = 0
        self.safe_ingredients = []
        self.safe_quest_items = {}
        self.safe_layout = layouts[0]

    def get_input(self):
        s = raw_input("Which quest would you like to embark on today?")
        ind = s.find('00')
        s = s[:ind]
        items = map(len, s.split('0'))
        for item in items:
            if item not in self.safe_quest_items:
                self.safe_quest_items[item] = 1
            else:
                self.safe_quest_items[item] += 1

    def parse_attempts(self):
        with open(self.source_filename, 'r') as source:
            for line in source:
                self.attempts.append(line.strip())

    def enc(self, x, y):
        x, y = min(x, y), max(x, y)
        if x < 0:
            return 0
        if y == x + 1:
            return 1 << (2*x)
        elif y == x + size:
            return 1 << (2*x + 1)
        else:
            return 0

    def exec_command(self, char):
        if char == '<':
            if self.enc(self.position, self.position-1) & self.layout:
                self.position -= 1
            else:
                return False
        elif char == '>':
            if self.enc(self.position, self.position+1) & self.layout:
                self.position += 1
            else:
                return False
        elif char == '^':
            if self.enc(self.position, self.position-size) & self.layout:
                self.position -= size
            else:
                return False
        elif char == 'v':
            if self.enc(self.position, self.position+size) & self.layout:
                self.position += size
            else:
                return False
        elif char == 'c':
            for item in xrange(self.position, 10**6, size*size):
                if item in self.quest_items:
                    self.ingredients += ([item] * self.quest_items.pop(item))
                    self.ingredients.sort()
                    self.layout = layouts[self.position % 10]
        else:
            raise ValueError

        return True

    def run_minion(self):
        minion = self.attempts.popleft()
        self.position = self.safe_position
        self.ingredients = copy.copy(self.safe_ingredients)
        self.quest_items = copy.copy(self.safe_quest_items)
        self.layout = self.safe_layout
        dead = False

        for cmd in minion:
            if not self.exec_command(cmd):
                dead = True

        if not dead:
            self.safe_position = self.position
            self.safe_ingredients = copy.copy(self.ingredients)
            self.safe_quest_items = copy.copy(self.quest_items)
            self.safe_layout = self.layout

    def process_minions(self):
        while self.attempts:
            self.run_minion()

    def final_run(self):
        if len(self.safe_quest_items) == 0:
            print "You killed the dragon" + "!!1" * self.safe_ingredients[-3]
        else:
            print "The dragon lives on. Better luck next time..."

    def interpret(self):
        self.get_input()
        self.parse_attempts()
        self.process_minions()
        self.final_run()

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print "Wrong number of arguments"
    else:
        test = Interpreter(sys.argv[1])
        test.interpret()

Viel Glück, tapferer Krieger.

Meine Lösung und Erklärung

Hier ist ein Python-Skript, das Quellcode generiert, um das Problem zu lösen. Aus Gründen des Interesses ist Martins endgültiger Quellcode etwa fünfmal kleiner als der von meinem Skript erzeugte Code. Andererseits ist mein Skript zum Generieren des Codes ungefähr 15-mal kleiner als Martins Mathematica-Programm ...

size = 10
layouts = [108705550239329248440770931020110627243913363144548922111951,108386637020100924277694952798729434993885646706222210602969,133885860318189115027934177821170081234850573770998325845482,102397795295522647918061101991513921833376565032742993744791,131948019244359669407266662537098175265242405785636894694611,127512068876349726396523358265982765442984953916545984706958,106817519055019354200334114020150263381328246524221867629943,33472343358375525802921815863230485208221126168622186265959,133909781123963725874096031069972704024813281938330035579187,132244654022332695610020359820518831299843076834682749020986]

def enc(edge):
    x,y = min(edge), max(edge)
    if x < 0:
        return 0
    if y == x + 1:
        return 1 << (2*x)
    elif y == x + size:
        return 1 << (2*x + 1)

def path(x, y, tree):
    stack = [(x,'')]
    while stack[-1][0] != y:
        vertex, path = stack.pop()
        if (enc((vertex, vertex+1))&tree) and ((not path) or path[-1] != '<'):
            stack.append((vertex+1, path+'>'))
        if (enc((vertex, vertex-1))&tree) and ((not path) or path[-1] != '>'):
            stack.append((vertex-1, path+'<'))
        if (enc((vertex, vertex+size))&tree) and ((not path) or path[-1] != '^'):
            stack.append((vertex+size, path+'v'))
        if (enc((vertex, vertex-size))&tree) and ((not path) or path[-1] != 'v'):
            stack.append((vertex-size, path+'^'))
    return stack[-1][1]

def reverse(path):
    rev = ''
    for i in xrange(len(path)-1, -1 ,-1):
        if path[i] == '<':
            rev += '>'
        if path[i] == '>':
            rev += '<'
        if path[i] == 'v':
            rev += '^'
        if path[i] == '^':
            rev += 'v'
    return rev

def assert_at(x, tree):
    path_ul = path(x, 0, tree)
    path_dr = path(x, size*size - 1, tree)
    return path_ul + reverse(path_ul) + path_dr + reverse(path_dr)

def safe_path(x, y, tree):
    return assert_at(x, tree) + path(x, y, tree)

with open('source.txt', 'w') as f:
    for x in xrange(size*size - 1):
        for tree in layouts:
            f.write(safe_path(x, x+1, tree) + 'c\n')

Grundstruktur

Dadurch werden 990 Quellcodezeilen generiert, die in Gruppen zu 10 vorliegen. Die ersten 10 Zeilen enthalten Anweisungen, die versuchen, einen Diener von Position 0zu Position zu bewegen 1, und dann einen Gegenstand zu sammeln - einen Satz für jedes mögliche Layout. Die nächsten 10 Zeilen enthalten alle Anweisungen, die versuchen, einen Diener von Position 1zu Position zu bewegen 2und dann einen Gegenstand zu sammeln. Und so weiter ... Diese Pfade werden mit der pathFunktion im Skript berechnet - es wird nur eine einfache Tiefensuche durchgeführt.

Wenn wir sicherstellen können, dass in jeder Zehnergruppe genau ein Diener erfolgreich ist, haben wir das Problem gelöst.

Das Problem mit dem Ansatz

Es mag nicht immer der Fall sein, dass genau ein Diener aus der Gruppe der 10 erfolgreich ist - zum Beispiel könnte es einem Diener, der von Position 0zu Position gelangen soll, 1versehentlich gelingen, sich von Position 1zu Position zu bewegen 2(aufgrund von Ähnlichkeiten in den Layouts), und das Fehleinschätzungen breiten sich aus und können zu Fehlern führen.

Wie man es repariert

Das Update, das ich verwendet habe, war wie folgt:

Lassen Sie ihn für jeden Diener, der versucht, von Position nzu Position zu gelangen n+1, zuerst von Position nzu Position 0(die linke obere Ecke) und wieder zurück, dann von Position nzu Position 99(die rechte untere Ecke) und wieder zurück. Diese Anweisungen können nur aus sicherer Position ausgeführt werden n- jede andere Startposition und der Diener wird von der Kante laufen.

Diese zusätzlichen Anweisungen verhindern daher, dass Schergen versehentlich an einen Ort gelangen, für den sie nicht bestimmt sind, und dies stellt sicher, dass genau ein Schergen aus jeder Gruppe von 10 erfolgreich ist. Beachten Sie, dass es nicht unbedingt der Günstling ist, von dem Sie erwarten, dass er es ist - es kann sein, dass der Günstling, der glaubt, er sei in Layout 0, erfolgreich ist, selbst wenn wir uns wirklich in Layout 7 befinden - aber auf jeden Fall die Tatsache, dass wir es haben Eine geänderte Position bedeutet, dass alle anderen Schergen in der Gruppe notwendigerweise sterben werden. Diese zusätzlichen Schritte werden von der assert_atFunktion berechnet , und die safe_pathFunktion gibt einen Pfad zurück, der die Verknüpfung dieser zusätzlichen Schritte mit dem normalen Pfad darstellt.

Firetype, Cracked von Martin Büttner

Eine wirklich seltsame Mischung aus BF und CJam. Und wer weiß was noch! Ich bin mir ziemlich sicher, dass dies eine einfache Aufgabe sein wird, aber es hat trotzdem Spaß gemacht. Zu Ihrer Information, der Name bezieht sich auf Vermillion Fire von Final Fantasy Type-0 .

HINWEIS : Bitte verzeihen Sie mir Unklarheiten in dieser Beschreibung. Ich bin nicht der beste Schriftsteller ...: O

Martin hat das wirklich schnell geknackt! Dies war mein ursprüngliches Programm zur Lösung des Problems:

_
,
^
~
+
|
|
-
%
+
_
+
=











`
~
+
|
%

_
=

\
@
-
-
!
<
>
>
>

_
+
.
<
-
`
~
~
+
|
|
-
#
%

Syntax

Ein Firetype-Skript ist im Grunde eine Liste von Zeilen. Das erste Zeichen jeder Zeile ist der auszuführende Befehl. Leerzeilen sind grundsätzlich NOPs.

Semantik

Sie haben ein Array von ganzen Zahlen und einen Zeiger (denken Sie an BF). Sie können Elemente nach links und rechts verschieben oder auf das Array "schieben".

Schieben

Wenn Sie ein Element "pushen" und sich am Ende des Arrays befinden, wird ein zusätzliches Element an das Ende angehängt. Wenn Sie nicht am Ende sind, wird das nächste Element überschrieben. Unabhängig davon wird der Zeiger immer erhöht.

Befehle

_

Schieben Sie eine Null auf das Array.

+

Erhöhen Sie das Element am aktuellen Zeiger.

-

Dekrementieren Sie das Element am aktuellen Zeiger.

*

Verdoppeln Sie das Element am aktuellen Zeiger.

/

Halbieren Sie das Element am aktuellen Zeiger.

%

Nehmen Sie das Element am aktuellen Zeiger, springen Sie so viele Zeilen vorwärts und bewegen Sie den Zeiger nach links. Wenn der Wert negativ ist, springen Sie stattdessen zurück.

=

Nehmen Sie das Element am aktuellen Zeiger und springen Sie zu dieser Zeile + 1. Wenn es sich beispielsweise um das aktuelle Element handelt 0, wird zur Zeile gesprungen 1. Dadurch wird auch der Zeiger nach links bewegt.

,

Liest ein Zeichen von der Standardeingabe und drückt seinen ASCII-Wert.

^

Nehmen Sie das Element am aktuellen Zeiger, interpretieren Sie es als ASCII-Wert für ein Zeichen und konvertieren Sie es in eine Ganzzahl. Wenn der aktuelle Wert beispielsweise 49 (der ASCII-Wert von 1) ist, wird das Element am aktuellen Zeiger auf die Ganzzahl gesetzt 1.

.

Schreiben Sie die aktuelle Nummer auf den Bildschirm.

!

Nehmen Sie das Element am aktuellen Zeiger und wiederholen Sie die nächste Zeile so oft wie möglich. Bewegt auch den Zeiger nach links.

<

Bewegen Sie den Zeiger nach links. Wenn Sie bereits am Anfang sind, wird ein Fehler ausgelöst.

>

Bewegen Sie den Zeiger nach rechts. Wenn Sie bereits am Ende sind, wird ein Fehler ausgelöst.

~

Wenn das aktuelle Element ungleich Null ist, ersetzen Sie es durch 0; Andernfalls ersetzen Sie es durch 1.

|

Quadrieren Sie das aktuelle Element.

@

Stellen Sie das aktuelle Element auf die Länge des Arrays ein.

`

Dupliziere das aktuelle Element.

\

Sortieren Sie die Elemente an und vor dem Zeiger.

#

Negiere das aktuelle Element.

Der Dolmetscher

Auch bei Github erhältlich .

#!/usr/bin/env python

# The FireType interpreter.
# Runs under Python 2 and 3.
import sys

class Array(object):
    def __init__(self):
        self.array = []
        self.ptr = 0

    def push_zero(self):
        if self.ptr == len(self.array):
            self.array.append(0)
        else:
            self.array[self.ptr] = 0
        self.ptr += 1

    def left(self):
        self.ptr -= 1
        assert self.ptr >= 0 and self.array, 'pointer underflow (at %d)' % i

    def right(self):
        self.ptr += 1
        assert self.ptr <= len(self.array), 'pointer overflow (at %d)' % i

    def sort(self):
        lhs = self.array[:self.ptr-1]
        rhs = self.array[self.ptr-1:]
        lhs.sort()
        lhs.reverse()
        self.array = lhs + rhs

    def __call__(self, *args):
        args = list(args)
        assert self.array, 'out-of-bounds (at %d)' % i
        if not args:
            return self.array[self.ptr-1]
        self.array[self.ptr-1] = args.pop()
        assert not args

    def __len__(self):
        return len(self.array)

    def __str__(self):
        return 'Array(array=%s, ptr=%s)' % (self.array, self.ptr)

    def __repr__(self):
        return 'Array(array=%r, ptr=%r)' % (self.array, self.ptr)

def execute(lines):
    global i, array
    i = 0
    array = Array()
    rep = 0
    while i < len(lines):
        line = lines[i]
        if not line:
            i += 1
            continue
        line = line[0]
        if line == '_':
            array.push_zero()
        elif line == '+':
            array(array() + 1)
        elif line == '-':
            array(array() - 1)
        elif line == '*':
            array(array() * 2)
        elif line == '/':
            array(int(array() / 2))
        elif line == '%':
            i += array()
            array.left()
        elif line == '=':
            i = array()-1
            array.left()
        elif line == ',':
            array.push_zero()
            array(ord(sys.stdin.read(1)))
        elif line == '.':
            sys.stdout.write(str(array()))
        elif line == '!':
            rep = array()
            array.left()
            i += 1
        elif line == '<':
            array.left()
        elif line == '>':
            array.right()
        elif line == '^':
            array(int(chr(array())))
        elif line == '~':
            array(int(not array()))
        elif line == '|':
            array(array() ** 2)
        elif line == '@':
            array(len(array))
        elif line == '`':
            top = array()
            array.push_zero()
            array(top)
        elif line == '\\':
            array.sort()
        elif line == '#':
            array(-array())

        if rep:
            rep -= 1
        else:
            i += 1

def main(args):
    try:
        _, path = args
    except ValueError:
        sys.exit('usage: %s <file to run, - for stdin>')

    if path == '-':
        data = sys.stdin.read()
    else:
        with open(path) as f:
            data = f.read()

    try:
        execute(data.split('\n'))
    except:
        print('ERROR!')
        print('Array was %r' % array)
        print('Re-raising error...')
        raise

if __name__ == '__main__':
    main(sys.argv)

Acc !! (sicher)

Es ist zurück ...

... und hoffentlich definitiv lückenloser.

Ich habe schon das Acc gelesen ! spez. Wie ist Acc !! anders?

In Übereinstimmung !!, Schleifenvariablen verlassen den Gültigkeitsbereich, wenn die Schleife beendet wird. Sie können sie nur innerhalb der Schleife verwenden. Außerhalb erhalten Sie die Fehlermeldung "Name ist nicht definiert". Abgesehen von dieser Änderung sind die Sprachen identisch.

Aussagen

Befehle werden Zeile für Zeile analysiert. Es gibt drei Arten von Befehlen:

1. Count <var> while <cond>

Zählt <var>von 0 bis zu einem <cond>Wert ungleich Null, was C ++ entspricht for(int <var>=0; <cond>; <var>++). Der Schleifenzähler kann ein beliebiger Kleinbuchstabe sein. Die Bedingung kann ein beliebiger Ausdruck sein, an dem nicht unbedingt die Schleifenvariable beteiligt ist. Die Schleife wird angehalten, wenn der Wert der Bedingung 0 wird.

Für Loops sind geschweifte Klammern im K & R-Stil erforderlich (insbesondere die Stroustrup-Variante ):

Count i while i-5 {
 ...
}

Wie oben erwähnt, sind Schleifenvariablen nur innerhalb ihrer Schleifen verfügbar . Der Versuch, sie später zu referenzieren, führt zu einem Fehler.

2. Write <charcode>

Gibt ein einzelnes Zeichen mit dem angegebenen ASCII / Unicode-Wert an stdout aus. Der Zeichencode kann ein beliebiger Ausdruck sein.

3. Ausdruck

Jeder Ausdruck, der für sich alleine steht, wird ausgewertet und dem Akkumulator (der zugänglich ist als _) zugewiesen . So ist zB 3eine Anweisung, die den Akkumulator auf 3 setzt; _ + 1erhöht den Akku; und _ * Nliest ein Zeichen und multipliziert den Akku mit seinem Zeichencode.

Hinweis: Der Akku ist die einzige Variable, die direkt zugewiesen werden kann. Schleifenvariablen und Nkönnen in Berechnungen verwendet, aber nicht geändert werden.

Der Akku ist anfangs 0.

Ausdrücke

Ein Ausdruck kann ganzzahlige Literale, Schleifenvariablen ( a-z) _für den Akkumulator und den speziellen Wert enthalten N, der ein Zeichen liest und bei jeder Verwendung auf seinen Zeichencode hin bewertet. Hinweis: Dies bedeutet, dass Sie nur einen Schuss erhalten, um jedes Zeichen zu lesen. Wenn Sie das nächste Mal verwenden N, lesen Sie das nächste Mal.

Betreiber sind:

• +zusätzlich
• -Subtraktion; unäre Verneinung
• *Multiplikation
• /ganzzahlige Division
• %modulo
• ^Potenzierung

Klammern können verwendet werden, um die Priorität von Operationen zu erzwingen. Jedes andere Zeichen in einem Ausdruck ist ein Syntaxfehler.

Leerzeichen und Kommentare

Führende und nachfolgende Leerzeichen und Leerzeilen werden ignoriert. Leerzeichen in Schleifenköpfen müssen genau so sein wie gezeigt, mit einem Leerzeichen zwischen dem Schleifenkopf und der öffnenden geschweiften Klammer. Leerzeichen in Ausdrücken sind optional.

# beginnt einen einzeiligen Kommentar.

Input-Output

Acc !! erwartet eine einzelne Zeichenzeile als Eingabe. Jedes eingegebene Zeichen kann der Reihe nach abgerufen und sein Zeichencode mit verarbeitet werden N. Der Versuch, über das letzte Zeichen der Zeile hinauszulesen, führt zu einem Fehler. Ein Zeichen kann ausgegeben werden, indem sein Zeichencode an die WriteAnweisung übergeben wird.

Dolmetscher

Der Interpreter (geschrieben in Python 3) übersetzt Acc !! Code in Python und execs it.

import re, sys

def main():
    if len(sys.argv) != 2:
        print("Please supply a filename on the command line.", file=sys.stderr)
        return
    codeFile = sys.argv[1]
    with open(codeFile) as f:
        code = f.readlines()
    code = translate(code)
    exec(code, {"inputStream": (ord(char) for char in input())})

def translate(accCode):
    indent = 0
    loopVars = []
    pyCode = ["_ = 0"]
    for lineNum, line in enumerate(accCode):
        if "#" in line:
            # Strip comments
            line = line[:line.index("#")]
        line = line.strip()
        if not line:
            continue
        lineNum += 1
        if line == "}":
            if indent:
                loopVar = loopVars.pop()
                pyCode.append(" "*indent + loopVar + " += 1")
                indent -= 1
                pyCode.append(" "*indent + "del " + loopVar)
            else:
                raise SyntaxError("Line %d: unmatched }" % lineNum)
        else:
            m = re.fullmatch(r"Count ([a-z]) while (.+) \{", line)
            if m:
                expression = validateExpression(m.group(2))
                if expression:
                    loopVar = m.group(1)
                    pyCode.append(" "*indent + loopVar + " = 0")
                    pyCode.append(" "*indent + "while " + expression + ":")
                    indent += 1
                    loopVars.append(loopVar)
                else:
                    raise SyntaxError("Line %d: invalid expression " % lineNum
                                      + m.group(2))
            else:
                m = re.fullmatch(r"Write (.+)", line)
                if m:
                    expression = validateExpression(m.group(1))
                    if expression:
                        pyCode.append(" "*indent
                                      + "print(chr(%s), end='')" % expression)
                    else:
                        raise SyntaxError("Line %d: invalid expression "
                                          % lineNum
                                          + m.group(1))
                else:
                    expression = validateExpression(line)
                    if expression:
                        pyCode.append(" "*indent + "_ = " + expression)
                    else:
                        raise SyntaxError("Line %d: invalid statement "
                                          % lineNum
                                          + line)
    return "\n".join(pyCode)

def validateExpression(expr):
    "Translates expr to Python expression or returns None if invalid."
    expr = expr.strip()
    if re.search(r"[^ 0-9a-z_N()*/%^+-]", expr):
        # Expression contains invalid characters
        return None
    elif re.search(r"[a-zN_]\w+", expr):
        # Expression contains multiple letters or underscores in a row
        return None
    else:
        # Not going to check validity of all identifiers or nesting of parens--
        # let the Python code throw an error if problems arise there
        # Replace short operators with their Python versions
        expr = expr.replace("^", "**")
        expr = expr.replace("/", "//")
        # Replace N with a call to get the next input character
        expr = expr.replace("N", "inputStream.send(None)")
        return expr

if __name__ == "__main__":
    main()

Lösung

Der Untergang des ursprünglichen Acc!war Schleifenvariablen, die weiterhin außerhalb ihrer Schleifen zugänglich waren. Dies ermöglichte das Speichern von Kopien des Akkus, was die Lösung viel zu einfach machte.

Hier ohne diese Schleife Loch (sorry), haben wir nur den Speicher zum Speichern von Sachen. Um die Aufgabe zu lösen, müssen wir jedoch vier beliebig große Werte speichern. ¹ Die Lösung: Verschachteln Sie ihre Bits und speichern Sie die resultierende Kombinationsnummer im Akkumulator. Zum Beispiel würde ein Akkumulatorwert von 6437 die folgenden Daten speichern (unter Verwendung des niedrigstwertigen Bits als Einzelbit-Flag):

1100100100101  Binary representation of accumulator
321032103210F  Key

The flag is 1 and the four numbers are
Number 0: 010 = 2
Number 1: 001 = 1
Number 2: 100 = 4
Number 3: 110 = 6

Wir können auf jedes Bit einer beliebigen Anzahl zugreifen, indem wir den Akkumulator durch die entsprechende Potenz von 2, Mod 2, teilen. Dies ermöglicht auch das Setzen oder Umdrehen einzelner Bits.

Auf der Makroebene durchläuft der Algorithmus die unären Zahlen in der Eingabe. Es liest einen Wert in die Zahl 0 und führt dann einen Durchlauf des Blasensortierungsalgorithmus durch, um ihn im Vergleich zu den anderen drei Zahlen an der richtigen Position zu platzieren. Schließlich wird der Wert verworfen, der in der Zahl 0 verbleibt, da dies der kleinste der vier Werte ist und niemals der drittgrößte sein kann. Wenn die Schleife beendet ist, ist Nummer 1 die drittgrößte, also verwerfen wir die anderen und geben sie aus.

Der schwierigste Teil (und der Grund, warum ich in der ersten Inkarnation globale Schleifenvariablen hatte) besteht darin, zwei Zahlen zu vergleichen, um zu wissen, ob sie ausgetauscht werden müssen. Um zwei Bits zu vergleichen, können wir eine Wahrheitstabelle in einen mathematischen Ausdruck umwandeln. mein Durchbruch für Acc !! Es wurde ein Vergleichsalgorithmus gefunden, der von niederwertigen zu höherwertigen Bits überging, da es ohne globale Variablen keine Möglichkeit gibt, die Bits einer Zahl von links nach rechts zu durchlaufen. Das niedrigstwertige Bit des Akkumulators speichert ein Flag, das signalisiert, ob die beiden aktuell betrachteten Zahlen vertauscht werden sollen.

Ich vermute, dass Acc !! ist Turing-complete, aber ich bin mir nicht sicher, ob ich mich die Mühe machen will, es zu beweisen.

Hier ist meine Lösung mit Kommentaren:

# Read and process numbers until the double 0

Count y while N-48 {
    # Read unary number and store it (as binary) in number 0
    # The above loop header consumed the first 1, so we need to add 1 to number 0

    _ + 2

    # Increment number 0 for each 1 in input until next 0

    Count z while N-48 {
        # In this context, the flag indicates a need to carry; set it to 1
        _ - _%2 + 1

        # While carry flag is set, increment the next bit in line
        Count i while _%2 {
            # Set carry flag to 1 if i'th bit is 1, 0 if it's 0
            # Set i'th bit to 1 if it was 0, 0 if it was 1
            _ - _%2 + _/2^(i*4+1)%2 + (-1)^(_/2^(i*4+1)%2)*2^(i*4+1)
        }
    }

    # Bubble number 0 upwards

    Count n while n-3 {
        # The flag (rightmost bit of accumulator) needs to become 1 if we want to swap
        # numbers (n) and (n+1) and 0 if we don't
        # Iterate over bit-groups of accumulator, RTL
        Count i while _/2^(i*4+1) {
            # Adjust the flag as follows:
            # _/2^(i*4+n+1)%4 is the current bit of number (n+1) followed by the current
            # bit of number (n), a value between 0 and 3
            # - If this quantity is 1 (01), number (n) is bigger so far; set flag to 1
            # - If this quantity is 2 (10), number (n+1) is bigger so far; set flag to 0
            # - If this quantity is 0 (00) or 3 (11), the two bits are the same; keep
            #   current value of flag
            _ + (_/2^(i*4+n+1)%4%3 + 1)/2*(_/2^(i*4+n+1)%4%3%2 - _%2)
        }

        # Now swap the two if the flag is 1
        Count i while (_%2)*(_/2^(i*4+1)) {
            # _/2^(i*4+n+1)%2 is the current bit of number (n)
            # _/2^(i*4+n+2)%2 is the current bit of number (n+1)
            _ - (_/2^(i*4+n+1)%2)*2^(i*4+n+1) - (_/2^(i*4+n+2)%2)*2^(i*4+n+2) + (_/2^(i*4+n+2)%2)*2^(i*4+n+1) + (_/2^(i*4+n+1)%2)*2^(i*4+n+2)
        }
    }

    # Discard number 0, setting it to all zeros for the next iteration
    Count i while _/2^(i*4+1) {
        _ - _/2^(i*4+1)%2*2^(i*4+1)
    }
}

# Once the loop is over, all input has been read and the result is in number 1
# Divide by 2 to get rid of flag bit

_ / 2

# Zero out numbers 2 and 3

Count i while _/2^(i*4) {
    _ - _/2^(i*4+2)%2*2^(i*4+2)
}

Count i while _/2^(i*4) {
    _ - _/2^(i*4+3)%2*2^(i*4+3)
}

# Move bits of number 1 down to their final locations

Count i while _/2^i {
    _ - _/2^(i*4+1)%2*2^(i*4+1) + _/2^(i*4+1)%2*2^i
}

# _ now contains the correct answer in decimal; to output in unary:

Count z while z-_ {
    Write 49
}

_{¹ Laut Fragenspezifikation müssen nur Werte bis zu 1 Million unterstützt werden. Ich bin froh, dass dies niemand für eine einfachere Lösung ausgenutzt hat - obwohl ich nicht ganz sicher bin, wie Sie die Vergleiche durchführen würden.}

Picofuck (sicher)

Picofuck ähnelt Smallfuck . Es arbeitet mit einem Binärband, das rechts und links ungebunden ist. Es hat die folgenden Befehle:

• > Bewegen Sie den Zeiger nach rechts

• <Bewegen Sie den Zeiger nach links. Wenn der Zeiger vom Band fällt, wird das Programm beendet.

• * klappe das Bit auf den Zeiger

• (Wenn das Bit am Zeiger ist 0, springen Sie zum nächsten)

• )nichts tun - Klammern in Picofuck sind ifBlöcke, keine whileSchleifen.

• .Schreiben, um das Bit am Zeiger als ASCII 0oder ASCII auszugeben 1.

• ,lese von stdin, bis wir auf ein 0oder stoßen 1, und speichere dies im Bit am Zeiger.

Picofuck-Codeumbrüche - Sobald das Ende des Programms erreicht ist, wird es von Anfang an fortgesetzt.

Außerdem lässt Picofuck geschachtelte Klammern nicht zu. Klammern in einem Picofuck Programm erscheint abwechselnd muss zwischen (und ), beginnend mit (und endend mit ).

Dolmetscher

Geschrieben in Python 2.7

Verwendungszweck: python picofuck.py <source_file>

import sys

def interpret(code):
    # Ensure parentheses match and are not nested.
    in_if_block = False
    for c in code:
        if c == '(':
            if in_if_block:
                print "NESTED IFS DETECTED!!!!!"
                return
            in_if_block = True
        elif c == ')':
            if not in_if_block:
                print "Unmatched parenthesis"
                return
            in_if_block = False
    if in_if_block:
        print "Unmatched parenthesis"
        return


    code_ptr = 0
    array = [0]
    ptr = 0

    while 1:
        command = code[code_ptr]
        if command == '<':
            if ptr == 0:
                break
            ptr -= 1
        elif command == '>':
            ptr += 1
            if ptr == len(array):
                array.append(0)
        elif command == '*':
            array[ptr] = 1-array[ptr]
        elif command == '(':
            if array[ptr] == 0:
                while code[code_ptr] != ')':
                    code_ptr = (code_ptr + 1) % len(code)
        elif command == ',':
            while True:
                c = sys.stdin.read(1)
                if c in ['0','1']:
                    array[ptr] = int(c)
                    break
        elif command == '.':
            sys.stdout.write(str(array[ptr]))
        code_ptr = (code_ptr+1)%len(code)

if __name__ == "__main__":
    with open(sys.argv[1]) as source_file:
        code = source_file.read()
    interpret(code)

Lösung

Das folgende Python 2.7-Programm gibt meine Lösung aus, die hier zu finden ist

Ich kann diesen Beitrag später mit einer gründlicheren Erläuterung der Funktionsweise bearbeiten, aber es stellt sich heraus, dass Picofuck Turing-complete ist.

states = {
    "SETUP":(
        "*>",
        "GET_NUMBER",
        "GET_NUMBER"
    ),

    "GET_NUMBER":(
        ",",
        "CHANGE_A",
        "PREPARE_PRINT_C"
    ),

    "GET_DIGIT":(
        ",",
        "CHANGE_A",
        "GOT_DIGIT"
    ),

    "GOT_DIGIT":(
        ">>>>",
        "GO_BACK",
        "GO_BACK"
    ),

    "CHANGE_A":(
        ">",
        "CHANGE_B",
        "SET_A"
    ),

    "SET_A":(
        "*>>>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CHANGE_B":(
        ">",
        "CHANGE_C",
        "SET_B"
    ),

    "SET_B":(
        "*>>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CHANGE_C":(
        ">",
        "CONTINUE_GET_NUMBER",
        "SET_C"
    ),

    "SET_C":(
        "*>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CONTINUE_GET_NUMBER":(
        ">>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "GO_BACK":(
        "<<<<<",
        "FINISH_GO_BACK",
        "GO_BACK"
    ),

    "FINISH_GO_BACK":(
        ">",
        "GET_NUMBER",
        "GET_NUMBER"
    ),

    "PREPARE_PRINT_C":(
        ">>>",
        "PRINT_C",
        "PRINT_C"
    ),

    "PRINT_C":(
        ".>>>>>",
        "PRINT_C",
        "TERMINATE"
    ),

    "TERMINATE":(
        "<",
        "TERMINATE",
        "TERMINATE"
    ),
}

def states_to_nanofuck(states,start_state):
    state_list = list(states)
    state_list.remove(start_state)
    state_list.insert(0,start_state)

    states_by_index = []
    for i,state in enumerate(state_list):
        commands, next1, next0 = states[state]
        states_by_index.append((commands,state_list.index(next1),state_list.index(next0)))


    # setup first state
    fragments = ['*(*>>>>>*<<<<<)>>>>>']

    # reset states that don't match
    for index in range(len(states_by_index)):
        for bool in range(2):
            # at state_0_0
            state_dist = index*3 + bool
            # move state to curstate
            fragments.append('>'*state_dist)
            fragments.append('(*')
            fragments.append(  '<'*state_dist)
            fragments.append(  '<<*>>')
            fragments.append(  '>'*state_dist)
            fragments.append(')')
            fragments.append('<'*state_dist)

            # go to arr
            fragments.append('<<<')

            if bool == 0:
                #flip arr
                fragments.append('*')

            # compute match = arr & curstate
            fragments.append('(>)(>*<)<(<)>')

            if bool == 0:
                #flip arr
                fragments.append('*')

            # reset curstate
            fragments.append('>(*)')

            # move match to matchstate, go back to state_0_0
            matchstate_dist = index*3 + 2
            fragments.append('>(*>')
            fragments.append(  '>'*matchstate_dist)
            fragments.append(  '*')
            fragments.append(  '<'*matchstate_dist)
            fragments.append('<)>')

    #fragments.append('|')

    # do the commands of the matching state
    for index,state in enumerate(states_by_index):
        for bool in range(2):
            # at state_0_0
            matchstate_dist = index*3 + 2
            # move matchstate to curstate
            fragments.append('>'*matchstate_dist)
            fragments.append('(*')
            fragments.append(  '<'*matchstate_dist)
            fragments.append(  '<<*>>')
            fragments.append(  '>'*matchstate_dist)
            fragments.append(')')
            fragments.append('<'*matchstate_dist)

            # if curstate, reset curstate
            fragments.append('<<(*')

            # go to arr
            fragments.append('<')

            # do commands
            commands,next1,next0 = state
            for c in commands:
                if c in '<>':
                    fragments.append(c*(3*len(states_by_index)+5))
                else:
                    fragments.append(c)

            # go to state_0_0
            fragments.append('>>>')

            # set next states
            for dist in [next0*3, next1*3+1]:
                fragments.append('>'*dist)
                fragments.append('*')
                fragments.append('<'*dist)

            # go to curstate
            fragments.append('<<')

            # end if
            fragments.append(')')

            # go to state_0_0
            fragments.append('>>')


    # go back to setup and set it
    fragments.append('<<<<<*')

    code = ''.join(fragments)

    return code



print states_to_nanofuck(states, "SETUP")

PQRS - Sicher! / Lösung zur Verfügung gestellt

Grundlagen

Alle implizierten Anweisungen haben vier Speicheradressenoperanden:

P₀ Q₀ R₀ S₀
P₁ Q₁ R₁ S₁
...
Pᵥ₋₁ Qᵥ₋₁ Rᵥ₋₁ Sᵥ₋₁

Wo vist die Größe des Speichers in Quartetten.

Pᵢ, Qᵢ, Rᵢ, SᵢSigniert ganze Zahlen in Ihrem Gerät nativen Größe (zB 16, 32 oder 64 Bit) , die wir als Worte beziehen.

Für jedes Quartett lautet idie implizite Operation mit der []Bezeichnung Indirektion:

if (([Pᵢ] ← [Qᵢ] − [Rᵢ]) ≤ 0) go to Sᵢ else go to Pᵢ₊₁

Beachten Sie, dass Subleq eine Teilmenge von PQRS ist .

Subleq wurde als vollständig erwiesen, daher sollte auch PQRS vollständig sein!

Programmstruktur

PQRS definiert einen anfänglichen Header wie folgt:

H₀ H₁ H₂ H₃ H₄ H₅ H₆ H₇

H₀ H₁ H₂ H₃ist immer die erste Anweisung P₀ Q₀ R₀ S₀. müssen zur Ladezeit definiert werden.H₀H₃

PQRS verfügt über eine rudimentäre E / A, die jedoch für die Herausforderung ausreicht.

H₄ H₅: Beim Programmstart werden maximal H₅ASCII-Zeichen aus der Standardeingabe eingelesen und ab Index als Wörter gespeichert H₄. H₄und H₅müssen zum Ladezeitpunkt definiert werden. Nach dem Lesen H₅wird auf die Anzahl der gelesenen Zeichen (und der gespeicherten Wörter) gesetzt.

H₆ H₇: Bei Programmende werden ab Index H₆alle Bytes der H₇Wörter als ASCII-Zeichen an die Standardausgabe ausgegeben. H₆und H₇müssen definiert werden, bevor das Programm endet. Null-Bytes '\0'in der Ausgabe werden übersprungen.

Beendigung

Die Kündigung erfolgt durch Setzen Sᵢvon Grenzen i < 0oder i ≥ v.

Tricks

Quartette Pᵢ Qᵢ Rᵢ Sᵢmüssen nicht ausgerichtet oder sequentiell sein, Verzweigungen sind in Intervallen von Unterquartetten zulässig.

PQRS verfügt über eine Indirektion, sodass im Gegensatz zu Subleq genügend Flexibilität zum Implementieren von Subroutinen vorhanden ist.

Code kann sich selbst ändern!

Dolmetscher

Der Interpreter ist in C geschrieben:

#include <stdlib.h>
#include <stdio.h>

// The "architecture"
enum {P, Q, R, S, START_OF_INPUT, LENGTH_OF_INPUT, START_OF_OUTPUT, LENGTH_OF_OUTPUT};
const int NEXT = S + 1;

// Recommend optimized!
#define OPTIMIZED

#ifdef PER_SPECS
// This may not work on all OSes and architectures - just too much memory needed!
const int K = 1002000200;
#else // OPTIMIZED
// This provides enough space to run the test cases with challenge-optimized.pqrs
const int K = 5200;
#endif

int main(int argc, char *argv[])
{
    int i, *M;
    char *p;
    FILE *program;

    // Allocate enough memory
    M = calloc(K, sizeof(int));

    // Load the program
    for (i = 0, program = fopen(argv[1], "r"); i < K && !feof(program); i++)
        if (!fscanf(program, "%d", M + i))
            break;
    fclose(program);

    // Read in the input
    for (i = 0; i < M[LENGTH_OF_INPUT] && !feof(stdin); i++)
    {
        int c = fgetc(stdin);
        if (c != EOF)
            M[M[START_OF_INPUT] + i] = c;
        else
            break;
    }
    M[LENGTH_OF_INPUT] = i;

    // Execute until terminated
    for (i = 0; i >= 0 && i < K; )
        i = (M[M[P + i]] = M[M[Q + i]] - M[M[R + i]]) <= 0? M[S + i]: i + NEXT;

    // Write the output
    for (i = 0, p = (char *)(M + M[START_OF_OUTPUT]); i < M[LENGTH_OF_OUTPUT] * sizeof(int); i++)
        // Ignore '\0'
        if (p[i])
            fputc(p[i], stdout);

    // Done
    free(M);

    return 0;
}

Um es zu benutzen, speichern Sie es als pqrs.c und kompilieren Sie:

gcc -o pqrs pqrs.c

Beispielprogramm

Echos geben bis zu 40 Zeichen ein, denen 'PQRS-' vorangestellt ist.

8 8 8 -1 14 40 9 45 0 80 81 82 83 45

Speichern Sie zum Ausführen die oben genannten echo.pqrsInformationen unter:

$ ./prqs echo.pqrs
greetings[enter]
[ctrl-D]
PQRS-greetings

Ausführen der Testfälle:

$ ./pqrs challenge-optimized.pqrs < test-1.txt
1

$ ./pqrs challenge-optimized.pqrs < test-2.txt
11111111111111111

$ ./pqrs challenge-optimized.pqrs < test-3.txt
[lots of ones!]

$ ./pqrs challenge-optimized.pqrs < test-3.txt | wc
0       1     773

Alle Testfälle laufen extrem schnell ab, zB <500 ms.

Die Herausforderung

PQRS kann als stabil eingestuft werden, daher beginnt die Challenge am 31.10.2015 um 13:00 Uhr und endet am 08.11.2015 um 13:00 Uhr, jeweils in UTC.

Viel Glück!

Lösung

Die Sprache ist der in "Baby" - der weltweit ersten elektronischen Digitalmaschine mit gespeicherten Programmen - verwendeten Sprache sehr ähnlich . Auf dieser Seite befindet sich ein Programm, mit dem der höchste Faktor einer Ganzzahl in weniger als 32 Wörtern (CRT!) Speicher ermittelt werden kann!

Ich fand das Schreiben der spezifikationskonformen Lösung nicht kompatibel mit dem Betriebssystem und der Maschine, die ich verwendete (ein Linux-Ubuntu-Derivat auf etwas älterer Hardware). Es wurde nur mehr Speicher angefordert als verfügbar, und es wurde ein Core-Dump ausgeführt. Auf Betriebssystemen mit erweiterter virtueller Speicherverwaltung oder Computern mit mindestens 8 GB Arbeitsspeicher können Sie die Lösung wahrscheinlich nach Spezifikation ausführen. Ich habe beide Lösungen bereitgestellt.

Es ist sehr schwierig, PQRS direkt zu codieren , ähnlich wie Maschinensprache, vielleicht sogar Mikrocode. Stattdessen ist es einfacher, in einer Art Assemblersprache zu schreiben, als sie zu "kompilieren". Unten finden Sie eine kommentierte Assemblersprache für die für die Ausführung der Testfälle optimierte Lösung:

; ANNOTATED PQRS ASSEMBLER CODE
; MINIMAL SIZED BUFFERS TO RUN THE TEST CASES

;OFFSET   LABEL       P-OP        Q-OP        R-OP        S-OP
0                     TEMP        ZERO        ZERO        L1

; INPUT AND OUTPUT LOCATIONS AND SIZES
4                     INPUT       4000        
6         L0:         OUTPUT      1000        

; GET CURRENT INPUT
8         L1:         TEMP        INPUT       ASCII_ZERO  L2
12                    SUM         SUM         INC         IGNORE
16                    L1+1        L1+1        INC         IGNORE
20                    TEMP        ZERO        ZERO        L1

; CHECK IF END OF NUMBERS
24        L2:         NUMBERS     SUM         ZERO        L3

; ADVANCE TO NEXT NUMBER
28                    L2          L2          INC         IGNORE

; ADVANCE COUNT
32                    COUNT       COUNT       INC         IGNORE
36                    L1+1        L1+1        INC         IGNORE

; CLEAR SUM AND GO BACK
40                    SUM         ZERO        ZERO        L1

; SORT NUMBERS                
44        L3:         P           NUMBERS     ZERO        LA
48        L4:         Q           NUMBERS+1   ZERO        L9

; COMPARE                
52                    TEMP        Q           P           L8

; SWAP IF OUT OF ORDER
56                    L5+1        L3+1        ZERO        IGNORE
60                    L6          L3+1        ZERO        IGNORE
64                    L6+1        L4+1        ZERO        IGNORE
68                    L7          L4+1        ZERO        IGNORE
72        L5:         TEMP        P           ZERO        IGNORE
76        L6:         P           Q           ZERO        IGNORE
80        L7:         Q           TEMP        ZERO        IGNORE

; INCREMENT INNER INDEX
84        L8:         L4+1        L4+1        INC         IGNORE
88                    TEMP        ZERO        ZERO        L3

; INCREMENT OUTER INDEX AND RESET INNER INDEX
92        L9:         L3+1        L3+1        INC         IGNORE
96                    L4+1        L3+1        INC         IGNORE
100                   TEMP        ZERO        ZERO        L3

; OUTPUT THIRD LARGEST NUMBER
104                   L0+1        NUMBERS+2   ZERO        IGNORE
108       LA:         TEMP        NUMBERS+2   ZERO        EXIT
112       LB:         OUTPUT      ASCII_ONE   ZERO        IGNORE
116                   LB          LB          INC         IGNORE
120                   NUMBERS+2   NUMBERS+2   DEC         EXIT
124                   TEMP        ZERO        ZERO        LA

; SAFETY LOOP – JUST IN CASE IGNORE DOESN'T WORK AS PLANNED!
128       IGNORE:     TEMP        ZERO        ZERO        IGNORE

; CONSTANTS
132       ZERO:        0
133       INC:        -1
134       DEC:         1
135       ASCII_ZERO: 48
136       ASCII_ONE:  49

; VARIABLES
137       TEMP:       [1]
138       SUM:        [1]
139       COUNT:      [1]
140       P:          [1]
141       Q:          [1]

; WORKING SPACE
142       NUMBERS:    [10]

; I/O SPACE
152       INPUT:      [4000]
4152      OUTPUT:     [1000]
5152

Analysiert die Eingabe, konvertiert Unär in Binär, sortiert die Zahlen mit den Werten in absteigender Reihenfolge und gibt schließlich den drittgrößten Wert aus, indem Binär zurück in Unär konvertiert wird.

Beachten Sie, dass INC(Inkrement) negativ und DEC(Dekrement) positiv ist! Wo L#oder L#+1wie P-oder Q-OPs verwendet wird, werden Zeiger aktualisiert: Inkrementieren, Dekrementieren, Austauschen usw. Der Assembler wurde von Hand in PQRS kompiliert, indem die Beschriftungen durch die Offsets ersetzt wurden. Nachfolgend finden Sie die für PQRS optimierte Lösung:

137 132 132 8
152 4000
4152 1000
137 152 135 24
138 138 133 128
9 9 133 128
137 132 132 8
142 138 132 44
24 24 133 128
139 139 133 128
9 9 133 128
138 132 132 8
140 142 132 108
141 143 132 92
137 141 140 84
73 45 132 128
76 45 132 128
77 49 132 128
80 49 132 128
137 140 132 128
140 141 132 128
141 137 132 128
49 49 133 128
137 132 132 44
45 45 133 128
49 45 133 128
137 132 132 44
7 144 132 128
137 144 132 -1
4152 136 132 128
112 112 133 128
144 144 134 -1
137 132 132 108
137 132 132 128
0
-1
1
48
49

Der obige Code kann gespeichert werden challenge-optimized.pqrs, um die Testfälle auszuführen.

Der Vollständigkeit halber sind hier die Quellenangaben aufgeführt:

; ANNOTATED PQRS ASSEMBLER CODE
; FULL SIZED BUFFERS TO RUN ACCORDING TO SPECS

;OFFSET   LABEL       P-OP        Q-OP        R-OP        S-OP
0                     TEMP        ZERO        ZERO        L1

; INPUT AND OUTPUT LOCATIONS AND SIZES
4                     INPUT       10^9        
6         L0:         OUTPUT      10^6        

; GET CURRENT INPUT
8         L1:         TEMP        INPUT       ASCII_ZERO  L2
12                    SUM         SUM         INC         IGNORE
16                    L1+1        L1+1        INC         IGNORE
20                    TEMP        ZERO        ZERO        L1

; CHECK IF END OF NUMBERS
24        L2:         NUMBERS     SUM         ZERO        L3

; ADVANCE TO NEXT NUMBER
28                    L2          L2          INC         IGNORE

; ADVANCE COUNT
32                    COUNT       COUNT       INC         IGNORE
36                    L1+1        L1+1        INC         IGNORE

; CLEAR SUM AND GO BACK
40                    SUM         ZERO        ZERO        L1

; SORT NUMBERS                
44        L3:         P           NUMBERS     ZERO        LA
48        L4:         Q           NUMBERS+1   ZERO        L9

; COMPARE                
52                    TEMP        Q           P           L8

; SWAP IF OUT OF ORDER
56                    L5+1        L3+1        ZERO        IGNORE
60                    L6          L3+1        ZERO        IGNORE
64                    L6+1        L4+1        ZERO        IGNORE
68                    L7          L4+1        ZERO        IGNORE
72        L5:         TEMP        P           ZERO        IGNORE
76        L6:         P           Q           ZERO        IGNORE
80        L7:         Q           TEMP        ZERO        IGNORE

; INCREMENT INNER INDEX
84        L8:         L4+1        L4+1        INC         IGNORE
88                    TEMP        ZERO        ZERO        L3

; INCREMENT OUTER INDEX AND RESET INNER INDEX
92        L9:         L3+1        L3+1        INC         IGNORE
96                    L4+1        L3+1        INC         IGNORE
100                   TEMP        ZERO        ZERO        L3

; OUTPUT THIRD LARGEST NUMBER
104                   L0+1        NUMBERS+2   ZERO        IGNORE
108       LA:         TEMP        NUMBERS+2   ZERO        EXIT
112       LB:         OUTPUT      ASCII_ONE   ZERO        IGNORE
116                   LB          LB          INC         IGNORE
120                   NUMBERS+2   NUMBERS+2   DEC         EXIT
124                   TEMP        ZERO        ZERO        LA

; SAFETY LOOP – JUST IN CASE IGNORE DOESN'T WORK AS PLANNED!
128       IGNORE:     TEMP        ZERO        ZERO        IGNORE

; CONSTANTS
132       ZERO:        0
133       INC:        -1
134       DEC:         1
135       ASCII_ZERO: 48
136       ASCII_ONE:  49

; VARIABLES
137       TEMP:       [1]
138       SUM:        [1]
139       COUNT:      [1]
140       P:          [1]
141       Q:          [1]

; WORKING SPACE
142       NUMBERS:    [10^6]

; I/O SPACE
1000142   INPUT:      [10^9]
1001000142 OUTPUT:    [10^6]
1002000142

Und Lösung:

137 132 132 8
1000142 1000000000
1001000142 1000000
137 1000142 135 24
138 138 133 128
9 9 133 128
137 132 132 8
142 138 132 44
24 24 133 128
139 139 133 128
9 9 133 128
138 132 132 8
140 142 132 108
141 143 132 92
137 141 140 84
73 45 132 128
76 45 132 128
77 49 132 128
80 49 132 128
137 140 132 128
140 141 132 128
141 137 132 128
49 49 133 128
137 132 132 44
45 45 133 128
49 45 133 128
137 132 132 44
7 144 132 128
137 144 132 -1
1001000142 136 132 128
112 112 133 128
144 144 134 -1
137 132 132 108
137 132 132 128
0
-1
1
48
49

Um die oben ausgeführt, müssen Sie einen Kommentar aus #define OPTIMIZEDund fügen Sie #define PER_SPECSin pqrs.cund neu kompilieren.

Dies war eine großartige Herausforderung - ich habe das mentale Training sehr genossen! Brachte mich zurück in meine alten 6502 Assembler-Tage ...

Wenn ich PQRS als "echte" Programmiersprache implementieren würde, würde ich wahrscheinlich zusätzlich zum indirekten Zugriff zusätzliche Modi für den direkten und doppelt indirekten Zugriff sowie für die relative und absolute Position hinzufügen, beide mit indirekten Zugriffsoptionen für die Verzweigung!

Zink, geknackt! von @Zgarb

Auch bei GitHub erhältlich .

Du brauchst Dart 1.12 und Pub. Einfach ausführen pub get, um die einzige Abhängigkeit, eine Parsing-Bibliothek, herunterzuladen.

Hier ist zu hoffen, dass dies länger als 30 Minuten dauert! :O

Die Sprache

Zink orientiert sich an der Neudefinition von Operatoren. Sie können alle Operatoren in der Sprache einfach neu definieren!

Die Struktur eines typischen Zinkprogramms sieht folgendermaßen aus:

let
<operator overrides>
in <expression>

Es gibt nur zwei Datentypen: Ganzzahlen und Mengen. Es gibt kein Mengenliteral, und leere Mengen sind nicht zulässig.

Ausdrücke

Folgendes sind gültige Ausdrücke in Zink:

Literale

Zink unterstützt alle normalen ganzzahligen Literale wie 1und -2.

Variablen

Zink hat Variablen (wie die meisten Sprachen). Um sie zu referenzieren, verwenden Sie einfach den Namen. Wieder wie die meisten Sprachen!

Es gibt jedoch eine spezielle Variable S, die sich wie Pyths verhält Q. Bei der ersten Verwendung wird eine Zeile aus der Standardeingabe eingelesen und als eine Reihe von Zahlen interpretiert. Zum Beispiel 1234231würde die Eingabezeile in die Menge verwandelt {1, 2, 3, 4, 3, 2, 1}.

WICHTIGE NOTIZ!!! In einigen Fällen wird ein Literal am Ende einer Operatorüberschreibung falsch analysiert, sodass Sie es mit Klammern umgeben müssen.

Binäre Operationen

Die folgenden binären Operationen werden unterstützt:

• Die Zugabe über +: 1+1.
• Subtraction über -: 1-1.
• Multiplikation über *: 2*2.
• Division über /: 4/2.
• Gleichheit mit =: 3=3.

Darüber hinaus wird die folgende unäre Operation unterstützt:

• Länge mit #: #x.

Vorrang ist immer rechtsassoziativ. Sie können Klammern verwenden, um dies zu überschreiben.

Nur Gleichheit und Länge wirken auf Mengen. Wenn Sie versuchen, die Länge einer Ganzzahl zu ermitteln, erhalten Sie die Anzahl der Stellen in der Zeichenfolgendarstellung.

Setze Verständnis

Um Mengen zu manipulieren, hat Zink Mengenverständnisse. Sie sehen so aus:

{<variable>:<set><clause>}

Eine Klausel ist entweder eine when-Klausel oder eine sort-Klausel.

Eine when-Klausel sieht so aus ^<expression>. Der Ausdruck nach dem Caret muss eine ganze Zahl ergeben. Wenn Sie die when-Klausel verwenden, werden nur die Elemente in der Menge verwendet, deren expressionWert nicht Null ist. Innerhalb des Ausdrucks wird die Variable _auf den aktuellen Index in der Menge gesetzt. Es ist ungefähr gleichbedeutend mit diesem Python:

[<variable> for _, <variable> in enumerate(<set>) when <expression> != 0]

Eine Sortierklausel , die so aussieht $<expression>, sortiert die Menge absteigend nach dem Wert von <expression>. Es ist gleich dieser Python:

sorted(<set>, key=lambda <variable>: <expression>)[::-1]

Hier einige Beispiele zum Verständnis:

• Nehmen Sie nur die Elemente der Menge s, die gleich 5 sind:

  {x:s^x=5}
  

• Sortieren Sie die Menge snach dem Wert, wenn die Elemente im Quadrat sind:

  {x:s$x*x}
  

Überschreibt

Mit Operator-Overrides können Sie Operatoren neu definieren. Sie sehen so aus:

<operator>=<operator>

oder:

<variable><operator><variable>=<expression>

Im ersten Fall können Sie einen Operator definieren, der einem anderen Operator entspricht. Zum Beispiel kann ich definieren, +um tatsächlich zu subtrahieren über:

+=-

Wenn Sie dies tun, können Sie einen Operator neu definieren, um ein magischer Operator zu sein . Es gibt zwei magische Operatoren:

• joinNimmt eine Menge und eine ganze Zahl und fügt den Inhalt der Menge hinzu. Wenn Sie beispielsweise {1, 2, 3}mit verbinden 4, erhalten Sie die Ganzzahl 14243.

• cutNimmt auch eine Menge und eine ganze Zahl und partitioniert die Menge bei jedem Auftreten der ganzen Zahl. Mit cuton {1, 3, 9, 4, 3, 2}und 3wird erstellt {{1}, {9, 4}, {2}}... ABER alle Einzelelementsätze werden abgeflacht, so dass das Ergebnis tatsächlich ist {1, {9, 4}, 2}.

Hier ist ein Beispiel, das den +Operator neu definiert join:

+=join

Im letzteren Fall können Sie einen Operator für den angegebenen Ausdruck neu definieren. Als Beispiel definiert dies die Plus-Operation, um die Werte hinzuzufügen und dann 1 hinzuzufügen:

x+y=1+:x+:y

Aber was ist +:? Sie können den Doppelpunkt :an einen Operator anhängen , um immer die integrierte Version zu verwenden. In diesem Beispiel wird die eingebaute +über +:die Zahlen zu addieren, dann fügt es ein 1 (denken Sie daran, alles ist rechtsassoziativ).

Das Überschreiben des Längenoperators sieht ungefähr so ​​aus:

#x=<expression>

Beachten Sie, dass fast alle eingebauten Operationen (außer Gleichheit) diesen Längenoperator verwenden, um die Länge der Menge zu bestimmen. Wenn Sie es so definiert haben:

#x=1

Jeder Teil von Zink, der an Mengen arbeitet, außer =an dem ersten Element der Menge, die ihm gegeben wurde.

Mehrfache Überschreibungen

Sie können mehrere Operatoren überschreiben, indem Sie sie durch Kommas trennen:

let
+=-,
*=/
in 1+2*3

Drucken

Sie können in Zink nichts direkt drucken. Das Ergebnis des folgenden Ausdrucks inwird gedruckt. Die Werte einer Menge werden mit dem Trennzeichen verknüpft. Nehmen wir zum Beispiel Folgendes:

let
...
in expr

Ist dies exprder Fall {1, 3, {2, 4}}, 1324wird nach Beendigung des Programms auf dem Bildschirm gedruckt.

Alles zusammen

Hier ist ein einfaches Zinkprogramm, das anscheinend hinzugefügt wird 2+2, das Ergebnis jedoch 5 ergibt:

let
x+y=1+:x+:y
in 1+2

Der Dolmetscher

Das geht in bin/zinc.dart:

import 'package:parsers/parsers.dart';
import 'dart:io';

// An error.
class Error implements Exception {
  String cause;
  Error(this.cause);
  String toString() => 'error in Zinc script: $cause';
}


// AST.
class Node {
  Obj interpret(ZincInterpreter interp) => null;
}

// Identifier.
class Id extends Node {
  final String id;
  Id(this.id);
  String toString() => 'Id($id)';
  Obj interpret(ZincInterpreter interp) => interp.getv(id);
}

// Integer literal.
class IntLiteral extends Node {
  final int value;
  IntLiteral(this.value);
  String toString() => 'IntLiteral($value)';
  Obj interpret(ZincInterpreter interp) => new IntObj(value);
}

// Any kind of operator.
class Anyop extends Node {
  void set(ZincInterpreter interp, OpFuncType func) {}
}

// Operator.
class Op extends Anyop {
  final String op;
  final bool orig;
  Op(this.op, [this.orig = false]);
  String toString() => 'Op($op, $orig)';
  OpFuncType get(ZincInterpreter interp) =>
    this.orig ? interp.op0[op] : interp.op1[op];
  void set(ZincInterpreter interp, OpFuncType func) { interp.op1[op] = func; }
}

// Unary operator (len).
class Lenop extends Anyop {
  final bool orig;
  Lenop([this.orig = false]);
  String toString() => 'Lenop($orig)';
  OpFuncType get(ZincInterpreter interp) =>
    this.orig ? interp.op0['#'] : interp.op1['#'];
  void set(ZincInterpreter interp, OpFuncType func) { interp.op1['#'] = func; }
}

// Magic operator.
class Magicop extends Anyop {
  final String op;
  Magicop(this.op);
  String toString() => 'Magicop($op)';
  Obj interpret_with(ZincInterpreter interp, Obj x, Obj y) {
    if (op == 'cut') {
      if (y is! IntObj) { throw new Error('cannot cut int with non-int'); }
      if (x is IntObj) {
        return new SetObj(x.value.toString().split(y.value.toString()).map(
          int.parse));
      } else {
        assert(x is SetObj);
        List<List<Obj>> res = [[]];
        for (Obj obj in x.vals(interp)) {
          if (obj == y) { res.add([]); }
          else { res.last.add(obj); }
        }
        return new SetObj(new List.from(res.map((l) =>
          l.length == 1 ? l[0] : new SetObj(l))));
      }
    } else if (op == 'join') {
      if (x is! SetObj) { throw new Error('can only join set'); }
      if (y is! IntObj) { throw new Error('can only join set with int'); }
      String res = '';
      for (Obj obj in x.vals(interp)) {
        if (obj is! IntObj) { throw new Error('joining set must contain ints'); }
        res += obj.value.toString();
      }
      return new IntObj(int.parse(res));
    }
  }
}

// Unary operator (len) expression.
class Len extends Node {
  final Lenop op;
  final Node value;
  Len(this.op, this.value);
  String toString() => 'Len($op, $value)';
  Obj interpret(ZincInterpreter interp) =>
    op.get(interp)(interp, value.interpret(interp), null);
}

// Binary operator expression.
class Binop extends Node {
  final Node lhs, rhs;
  final Op op;
  Binop(this.lhs, this.op, this.rhs);
  String toString() => 'Binop($lhs, $op, $rhs)';
  Obj interpret(ZincInterpreter interp) =>
    op.get(interp)(interp, lhs.interpret(interp), rhs.interpret(interp));
}

// Clause.
enum ClauseKind { Where, Sort }
class Clause extends Node {
  final ClauseKind kind;
  final Node expr;
  Clause(this.kind, this.expr);
  String toString() => 'Clause($kind, $expr)';
  Obj interpret_with(ZincInterpreter interp, SetObj set, Id id) {
    List<Obj> res = [];
    List<Obj> values = set.vals(interp);
    switch (kind) {
    case ClauseKind.Where:
      for (int i=0; i<values.length; i++) {
        Obj obj = values[i];
        interp.push_scope();
        interp.setv(id.id, obj);
        interp.setv('_', new IntObj(i));
        Obj x = expr.interpret(interp);
        interp.pop_scope();
        if (x is IntObj) {
          if (x.value != 0) { res.add(obj); }
        } else { throw new Error('where clause condition must be an integer'); }
      }
      break;
    case ClauseKind.Sort:
      res = values;
      res.sort((x, y) {
        interp.push_scope();
        interp.setv(id.id, x);
        Obj x_by = expr.interpret(interp);
        interp.setv(id.id, y);
        Obj y_by = expr.interpret(interp);
        interp.pop_scope();
        if (x_by is IntObj && y_by is IntObj) {
          return x_by.value.compareTo(y_by.value);
        } else { throw new Error('sort clause result must be an integer'); }
      });
      break;
    }
    return new SetObj(new List.from(res.reversed));
  }
}

// Set comprehension.
class SetComp extends Node {
  final Id id;
  final Node set;
  final Clause clause;
  SetComp(this.id, this.set, this.clause);
  String toString() => 'SetComp($id, $set, $clause)';
  Obj interpret(ZincInterpreter interp) {
    Obj setobj = set.interpret(interp);
    if (setobj is SetObj) {
      return clause.interpret_with(interp, setobj, id);
    } else { throw new Error('set comprehension rhs must be set type'); }
  }
}

// Operator rewrite.
class OpRewrite extends Node {
  final Anyop op;
  final Node value;
  final Id lid, rid; // Can be null!
  OpRewrite(this.op, this.value, [this.lid, this.rid]);
  String toString() => 'OpRewrite($lid, $op, $rid, $value)';
  Obj interpret(ZincInterpreter interp) {
    if (lid != null) {
      // Not bare.
      op.set(interp, (interp,x,y) {
        interp.push_scope();
        interp.setv(lid.id, x);
        if (rid == null) { assert(y == null); }
        else { interp.setv(rid.id, y); }
        Obj res = value.interpret(interp);
        interp.pop_scope();
        return res;
      });
    } else {
      // Bare.
      if (value is Magicop) {
        op.set(interp, (interp,x,y) => value.interpret_with(interp, x, y));
      } else {
        op.set(interp, (interp,x,y) => (value as Anyop).get(interp)(x, y));
      }
    }
    return null;
  }
}

class Program extends Node {
  final List<OpRewrite> rws;
  final Node expr;
  Program(this.rws, this.expr);
  String toString() => 'Program($rws, $expr)';
  Obj interpret(ZincInterpreter interp) {
    rws.forEach((n) => n.interpret(interp));
    return expr.interpret(interp);
  }
}


// Runtime objects.
typedef Obj OpFuncType(ZincInterpreter interp, Obj x, Obj y);

class Obj {}

class IntObj extends Obj {
  final int value;
  IntObj(this.value);
  String toString() => 'IntObj($value)';
  bool operator==(Obj rhs) => rhs is IntObj && value == rhs.value;
  String dump() => value.toString();
}

class SetObj extends Obj {
  final List<Obj> values;
  SetObj(this.values) {
    if (values.length == 0) { throw new Error('set cannot be empty'); }
  }
  String toString() => 'SetObj($values)';
  bool operator==(Obj rhs) => rhs is SetObj && values == rhs.values;
  String dump() => values.map((x) => x.dump()).reduce((x,y) => x+y);
  List<Obj> vals(ZincInterpreter interp) {
    Obj lenobj = interp.op1['#'](interp, this, null);
    int len;
    if (lenobj is! IntObj) { throw new Error('# operator must return an int'); }
    len = lenobj.value;
    if (len < 0) { throw new Error('result of # operator must be positive'); }
    return new List<Obj>.from(values.getRange(0, len));
  }
}


// Parser.
class ZincParser extends LanguageParsers {
  ZincParser(): super(reservedNames: ['let', 'in', 'join', 'cut']);
  get start => prog().between(spaces, eof);
  get comma => char(',') < spaces;
  get lp => symbol('(');
  get rp => symbol(')');
  get lb => symbol('{');
  get rb => symbol('}');
  get colon => symbol(':');
  get plus => symbol('+');
  get minus => symbol('-');
  get star => symbol('*');
  get slash => symbol('/');
  get eq => symbol('=');
  get len => symbol('#');
  get in_ => char(':');
  get where => char('^');
  get sort => char('\$');

  prog() => reserved['let'] + oprw().sepBy(comma) + reserved['in'] + expr() ^
            (_1,o,_2,x) => new Program(o,x);
  oprw() => oprw1() | oprw2() | oprw3();
  oprw1() => (basicop() | lenop()) + eq + (magicop() | op()) ^
             (o,_,r) => new OpRewrite(o,r);
  oprw2() => (id() + op() + id()).list + eq + expr() ^
             (l,_,x) => new OpRewrite(l[1], x, l[0], l[2]);
  oprw3() => lenop() + id() + eq + expr() ^ (o,a,_,x) => new OpRewrite(o, x, a);
  magicop() => (reserved['join'] | reserved['cut']) ^ (s) => new Magicop(s);
  basicop() => (plus | minus | star | slash | eq) ^ (op) => new Op(op);
  op() => (basicop() + colon ^ (op,_) => new Op(op.op, true)) | basicop();
  lenop() => (len + colon ^ (_1,_2) => new Lenop(true)) |
             len ^ (_) => new Lenop();
  expr() => setcomp() | unop() | binop() | prim();
  setcomp() => lb + id() + in_ + rec(expr) + clause() + rb ^
               (_1,i,_2,x,c,_3) => new SetComp(i,x,c);
  clausekind() => (where ^ (_) => ClauseKind.Where) |
                  (sort  ^ (_) => ClauseKind.Sort);
  clause() => clausekind() + rec(expr) ^ (k,x) => new Clause(k,x);
  unop() => lenop() + rec(expr) ^ (o,x) => new Len(o,x);
  binop() => prim() + op() + rec(expr) ^ (l,o,r) => new Binop(l,o,r);
  prim() => id() | intlit() | parens(rec(expr));
  id() => identifier ^ (i) => new Id(i);
  intlit() => intLiteral ^ (i) => new IntLiteral(i);
}


// Interpreter.
class ZincInterpreter {
  Map<String, OpFuncType> op0, op1;
  List<Map<String, Obj>> scopes;
  ZincInterpreter() {
    var beInt = (v) {
      if (v is IntObj) { return v.value; }
      else { throw new Error('argument to binary operator must be integer'); }
    };
    op0 = {
      '+': (_,x,y) => new IntObj(beInt(x)+beInt(y)),
      '-': (_,x,y) => new IntObj(beInt(x)-beInt(y)),
      '*': (_,x,y) => new IntObj(beInt(x)*beInt(y)),
      '/': (_,x,y) => new IntObj(beInt(x)/beInt(y)),
      '=': (_,x,y) => new IntObj(x == y ? 1 : 0),
      '#': (i,x,_2) =>
        new IntObj(x is IntObj ? x.value.toString().length : x.values.length)
    };
    op1 = new Map<String, OpFuncType>.from(op0);
    scopes = [{}];
  }

  void push_scope() { scopes.add({}); }
  void pop_scope() { scopes.removeLast(); }
  void setv(String name, Obj value) { scopes[scopes.length-1][name] = value; }
  Obj getv(String name) {
    for (var scope in scopes.reversed) {
      if (scope[name] != null) { return scope[name]; }
    }
    if (name == 'S') {
      var input = stdin.readLineSync() ?? '';
      var list = new List.from(input.codeUnits.map((c) =>
        new IntObj(int.parse(new String.fromCharCodes([c])))));
      setv('S', new SetObj(list));
      return getv('S');
    } else throw new Error('undefined variable $name');
  }
}


void main(List<String> args) {
  if (args.length != 1) {
    print('usage: ${Platform.script.toFilePath()} <file to run>');
    return;
  }
  var file = new File(args[0]);
  if (!file.existsSync()) {
    print('cannot open ${args[0]}');
    return;
  }
  Program root = new ZincParser().start.parse(file.readAsStringSync());
  ZincInterpreter interp = new ZincInterpreter();
  var res = root.interpret(interp);
  print(res.dump());
}

Und das geht in pubspec.yaml:

name: zinc
dependencies:
  parsers: any

Beabsichtigte Lösung

let
#x=((x=S)*(-2))+#:x,
/=cut
in {y:{x:S/0$#:x}^_=2}

Kompasssuppe ( geknackt von cardboard_box )

Dolmetscher: C ++

Die Kompasssuppe ähnelt einer Turingmaschine mit einem unendlichen zweidimensionalen Klebeband. Der wichtigste Haken ist, dass sich der Anweisungsspeicher und der Datenspeicher im selben Bereich befinden und die Ausgabe des Programms den gesamten Inhalt dieses Bereichs enthält.

Wie es funktioniert

Ein Programm ist ein zweidimensionaler Textblock. Der Programmraum beginnt mit dem gesamten Quellcode, wobei das erste Zeichen bei (0,0) steht. Der Rest des Programmraums ist unendlich und wird mit Nullzeichen (ASCII 0) initialisiert.

Es gibt zwei Zeiger, die sich im Programmraum bewegen können:

• Der Ausführungszeiger hat eine Position und eine Richtung (Nord, Süd, Ost oder West). Bei jedem Tick wird der Befehl unter dem Ausführungszeiger ausgeführt, dann bewegt sich der Ausführungszeiger in seine aktuelle Richtung. Der Ausführungszeiger beginnt sich nach Osten zu bewegen (positives x), an der Stelle des! Zeichens oder bei (0,0), wenn dies nicht vorhanden ist.
• Der Datenzeiger hat nur eine Position. Es ist mit den Anweisungen bewegt x, X, y, und Y. Es beginnt an der Stelle des @Zeichens oder bei (0,0), wenn dies nicht vorhanden ist.

Eingang

Der Inhalt von stdin wird ab dem Speicherort von in den Programmraum gedruckt > Zeichens oder, falls nicht vorhanden, ab (0,0) .

Ausgabe

Das Programm wird beendet, wenn der Ausführungszeiger unwiederbringlich außerhalb der Grenzen läuft. Die Ausgabe ist der gesamte Inhalt des Programmraums zu diesem Zeitpunkt. Es wird an stdout und 'result.txt' gesendet.

Anleitung

• n - leitet den Ausführungszeiger nach Norden um (negatives y)
• e - leitet den Ausführungszeiger nach Osten um (positives x)
• s - leitet den Ausführungszeiger nach Süden um (positiv y)
• w - leitet den Ausführungszeiger nach Westen um (negatives x)
• y - bewegt den Datenzeiger nach Norden (negatives y)
• X - bewegt den Datenzeiger nach Osten (positives x)
• Y - bewegt den Datenzeiger nach Süden (positives y)
• x - bewegt den Datenzeiger nach Westen (negatives x)
• p- schreibt das nächste Zeichen, auf das der Ausführungszeiger trifft, an den Datenzeiger. Dieses Zeichen wird nicht als Anweisung ausgeführt.
• j- prüft das nächste Zeichen, auf das der Ausführungszeiger trifft, gegen das Zeichen unter dem Datenzeiger. Dieses Zeichen wird nicht als Anweisung ausgeführt. Wenn sie gleich sind, springt der Ausführungszeiger über das nächste Zeichen.
• c - schreibt das Nullzeichen an den Datenzeiger.
• * - breakpoint - bewirkt nur, dass der Interpreter unterbrochen wird.

Alle anderen Zeichen werden vom Ausführungszeiger ignoriert.

Dolmetscher

Der Interpreter nimmt die Quelldatei als Argument und gibt sie in stdin ein. Es hat einen schrittweisen Debugger, den Sie mit einer Haltepunktanweisung im Code ( *) aufrufen können . Wenn der Ausführungszeiger beschädigt ist, wird er als ASCII 178 (Block mit dunklerer Schattierung) und der Datenzeiger als ASCII 177 (Block mit hellerer Schattierung) angezeigt.

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>

// Compass Soup programming language interpreter
// created by Brian MacIntosh (BMacZero)
// for https://codegolf.stackexchange.com/questions/61804/create-a-programming-language-that-only-appears-to-be-unusable
//
// 31 October 2015

struct Point
{
    int x, y;
    Point(int ix, int iy) { x = ix; y = iy; };
    bool operator==(const Point &other) const
    {
        return other.x == x && other.y == y;
    }
    bool operator!=(const Point &other) const
    {
        return other.x != x || other.y != y;
    }
};

struct Bounds
{
    int xMin, xMax, yMin, yMax;
    Bounds(int xmin, int ymin, int xmax, int ymax)
    {
        xMin = xmin; yMin = ymin; xMax = xmax; yMax = ymax;
    }
    bool contains(Point pt)
    {
        return pt.x >= xMin && pt.x <= xMax && pt.y >= yMin && pt.y <= yMax;
    }
    int getWidth() { return xMax - xMin + 1; }
    int getHeight() { return yMax - yMin + 1; }
    bool operator==(const Bounds &other) const
    {
        return other.xMin == xMin && other.xMax == xMax && other.yMin == yMin && other.yMax == yMax;
    }
    bool operator!=(const Bounds &other) const
    {
        return other.xMin != xMin || other.xMax != xMax || other.yMin != yMin || other.yMax != yMax;
    }
};

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

Bounds hull(Point a, Bounds b)
{
    return Bounds(min(a.x, b.xMin), min(a.y, b.yMin), max(a.x, b.xMax), max(a.y, b.yMax));
}

Bounds hull(Bounds a, Bounds b)
{
    return Bounds(min(a.xMin, b.xMin), min(a.yMin, b.yMin), max(a.xMax, b.xMax), max(a.yMax, b.yMax));
}

Bounds programBounds(0,0,0,0);
char** programSpace;

Point execPtr(0,0);
Point execPtrDir(1,0);
Point dataPtr(0,0);
Point stdInPos(0,0);

bool breakpointHit = false;
char breakOn = 0;

/// reads the character from the specified position
char read(Point pt)
{
    if (programBounds.contains(pt))
        return programSpace[pt.x - programBounds.xMin][pt.y - programBounds.yMin];
    else
        return 0;
}

/// read the character at the data pointer
char readData()
{
    return read(dataPtr);
}

/// read the character at the execution pointer
char readProgram()
{
    return read(execPtr);
}

/// gets the bounds of the actual content of the program space
Bounds getTightBounds(bool debug)
{
    Bounds tight(0,0,0,0);
    for (int x = programBounds.xMin; x <= programBounds.xMax; x++)
    {
        for (int y = programBounds.yMin; y <= programBounds.yMax; y++)
        {
            if (read(Point(x, y)) != 0)
            {
                tight = hull(Point(x, y), tight);
            }
        }
    }
    if (debug)
    {
        tight = hull(dataPtr, tight);
        tight = hull(execPtr, tight);
    }
    return tight;
}

/// ensure that the program space encompasses the specified rectangle
void fitProgramSpace(Bounds bounds)
{
    Bounds newBounds = hull(bounds, programBounds);

    if (newBounds == programBounds) return;

    // allocate new space
    char** newSpace = new char*[newBounds.getWidth()];

    // copy content
    for (int x = 0; x < newBounds.getWidth(); x++)
    {
        newSpace[x] = new char[newBounds.getHeight()];
        for (int y = 0; y < newBounds.getHeight(); y++)
        {
            Point newWorldPos(x + newBounds.xMin, y + newBounds.yMin);
            newSpace[x][y] = read(newWorldPos);
        }
    }

    // destroy old space
    for (int x = 0; x < programBounds.getWidth(); x++)
    {
        delete[] programSpace[x];
    }
    delete[] programSpace;

    programSpace = newSpace;
    programBounds = newBounds;
}

/// outputs the current program space to a file
void outputToStream(std::ostream &stream, bool debug)
{
    Bounds tight = getTightBounds(debug);
    for (int y = tight.yMin; y <= tight.yMax; y++)
    {
        for (int x = tight.xMin; x <= tight.xMax; x++)
        {
            char at = read(Point(x, y));
            if (debug && x == execPtr.x && y == execPtr.y)
                stream << (char)178;
            else if (debug && x == dataPtr.x && y == dataPtr.y)
                stream << (char)177;
            else if (at == 0)
                stream << ' ';
            else
                stream << at;
        }
        stream << std::endl;
    }
}

/// writes a character at the specified position
void write(Point pt, char ch)
{
    fitProgramSpace(hull(pt, programBounds));
    programSpace[pt.x - programBounds.xMin][pt.y - programBounds.yMin] = ch;
}

/// writes a character at the data pointer
void write(char ch)
{
    write(dataPtr, ch);
}

/// writes a line of text horizontally, starting at the specified position
void writeLine(Point loc, std::string str, bool isSource)
{
    fitProgramSpace(Bounds(loc.x, loc.y, loc.x + str.size(), loc.y));
    for (unsigned int x = 0; x < str.size(); x++)
    {
        programSpace[x + loc.x][loc.y] = str[x];

        // record locations of things
        if (isSource)
        {
            switch (str[x])
            {
            case '>':
                stdInPos = Point(loc.x + x, loc.y);
                break;
            case '!':
                execPtr = Point(loc.x + x, loc.y);
                break;
            case '@':
                dataPtr = Point(loc.x + x, loc.y);
                break;
            }
        }
    }
}

void advanceExecPtr()
{
    execPtr.x += execPtrDir.x;
    execPtr.y += execPtrDir.y;
}

void breakpoint()
{
    breakpointHit = true;
    outputToStream(std::cout, true);
    std::cout << "[Return]: step | [Space+Return]: continue | [<char>+Return]: continue to <char>" << std::endl;
    while (true)
    {
        std::string input;
        std::getline(std::cin, input);
        if (input.size() == 0)
        {
            break;
        }
        else if (input.size() == 1)
        {
            if (input[0] == ' ')
            {
                breakpointHit = false;
                break;
            }
            else
            {
                breakOn = input[0];
                breakpointHit = false;
                break;
            }
        }
    }
}

int main(int argc, char** argv)
{
    if (argc != 2)
    {
        printf("Usage: CompassSoup <source-file>");
        return 1;
    }

    // open source file
    std::ifstream sourceIn(argv[1]);

    if (!sourceIn.is_open())
    {
        printf("Error reading source file.");
        return 1;
    }

    programSpace = new char*[1];
    programSpace[0] = new char[1];
    programSpace[0][0] = 0;

    // read starting configuration
    std::string line;
    int currentLine = 0;
    while (std::getline(sourceIn, line))
    {
        writeLine(Point(0, currentLine), line, true);
        currentLine++;
    }

    sourceIn.close();

    // take stdin
    std::string input;
    std::cout << ">";
    std::cin >> input;
    std::cin.ignore();
    writeLine(stdInPos, input, false);

    // execute
    while (programBounds.contains(execPtr))
    {
        if (execPtrDir.x == 0 && execPtrDir.y == 0)
        {
            printf("Implementation error: execPtr is stuck.");
            break;
        }

        advanceExecPtr();

        char command = readProgram();

        // breakpoint control code
        if (breakpointHit || (breakOn != 0 && command == breakOn))
        {
            breakOn = 0;
            breakpoint();
        }

        switch (command)
        {
        case 'n':
            execPtrDir = Point(0,-1);
            break;
        case 'e':
            execPtrDir = Point(1,0);
            break;
        case 's':
            execPtrDir = Point(0,1);
            break;
        case 'w':
            execPtrDir = Point(-1,0);
            break;
        case 'x':
            dataPtr.x--;
            break;
        case 'X':
            dataPtr.x++;
            break;
        case 'y':
            dataPtr.y--;
            break;
        case 'Y':
            dataPtr.y++;
            break;
        case 'p':
            advanceExecPtr();
            write(readProgram());
            break;
        case 'j':
            advanceExecPtr();
            if (readData() == readProgram())
            {
                advanceExecPtr();
            }
            break;
        case 'c':
            write(0);
            break;
        case '*':
            breakpoint();
            break;
        }
    }

    std::ofstream outputFile("result.txt");
    outputToStream(outputFile, false);
    outputToStream(std::cout, false);
    outputFile.close();
}