El hilo del desafío de los ladrones está aquí .

El desafío de los policías: diseñar un lenguaje de programación que parezca inutilizable para la programación, pero que admite la computación (o al menos la finalización de la tarea) a través de algún mecanismo no obvio.

Debe diseñar un lenguaje de programación simple que lea el código de un archivo de entrada y luego haga ... algo. Debe preparar un programa de solución que encuentre el tercer número más grande en la entrada cuando se ejecuta en su intérprete. Debe hacer que sea lo más difícil posible para los ladrones encontrar un programa de solución. Tenga en cuenta que los ladrones pueden publicar cualquier solución que realice la tarea, no solo la que tenía en mente.

Este es un concurso de popularidad. El objetivo de la policía es obtener la mayor cantidad de votos posible mientras sobrevive 8 días después de publicar el intérprete sin ser agrietado. Para este fin, las siguientes prácticas deberían ayudar:

• Explicando con precisión la semántica de tu idioma
• Escribir código legible

Se desaconsejan las siguientes tácticas:

• Usar cifrado, hash u otros métodos criptográficos. Si ve un lenguaje que emplea encriptación RSA, o se niega a ejecutar un programa a menos que su hash SHA-3 sea igual a 0x1936206392306, no dude en votar a favor.

Desafío de los ladrones: escriba un programa que encuentre el tercer entero más grande en la entrada cuando se ejecuta en el intérprete de la policía.

Este es relativamente sencillo. Para descifrar la respuesta de un policía, debe crear un programa que complete la tarea cuando se ejecute en su intérprete. Cuando descifre una respuesta, publique un comentario que diga "Agrietado" en la respuesta del policía que se vincula a su publicación. Quien descifra la mayor cantidad de policías gana el hilo de los ladrones.

Reglas de E / S

• Los intérpretes deben tomar un nombre de archivo en la línea de comando para el programa y utilizar entradas y salidas estándar cuando lo ejecutan.
• La entrada se dará en unario y constará solo de los caracteres 0y 1(48 y 49 en ASCII). Un número N se codifica como N 1s seguido de a 0. Hay un adicional 0antes del final del archivo. Ejemplo: para la secuencia (3, 3, 1, 14), la entrada es 11101110101111111111111100.
• Se garantiza que la entrada tenga al menos 3 números. Todos los números son enteros positivos.
• La salida será juzgada por el número de 1correos impresos antes de que el programa se detenga. Otros personajes son ignorados.

En los siguientes ejemplos, la primera línea es la entrada en formato decimal; el segundo es la entrada real del programa; el tercero es una salida de muestra.

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>

Reglas aburridas para respuestas de policías:

• Para evitar la seguridad a través de la oscuridad, el intérprete debe estar escrito en un idioma en el top 100 de este índice TIOBE y tener un compilador / intérprete disponible gratuitamente.
• El intérprete no debe interpretar un idioma que se publicó antes de este desafío.
• El intérprete debe caber en su publicación y no estar alojado externamente.
• El intérprete debe ser determinista.
• El intérprete debe ser portátil y seguir el estándar de su propio idioma; no use comportamientos o errores indefinidos
• Si el programa de solución es demasiado largo para caber en la respuesta, debe publicar un programa que lo genere.
• El programa de solución debe consistir solo en ASCII imprimible y líneas nuevas.
• Debe ejecutar su programa de solución en menos de 1 hora en su propia computadora para cada una de las entradas de ejemplo anteriores.
• El programa debería funcionar para todos los enteros menores de 10 ⁶ y cualquier número de enteros menores de 10 ⁶ (no necesariamente en menos de una hora), siempre que la longitud de entrada total sea menor de 10 ⁹ .
• Para estar seguro, un policía debe editar el programa de solución en la respuesta después de que hayan pasado 8 días.

Puntuación

El policía que se vuelve seguro con el puntaje más alto y un puntaje positivo, gana esta pregunta.

Changeling (seguro)

ShapeScript

ShapeScript es un lenguaje de programación natural. Los desplazadores de forma (o Changelings , como prefieren ser llamados) pueden transformarse en un conjunto de instrucciones que les permite procesar datos.

ShapeScript es un lenguaje basado en pila con una sintaxis relativamente simple. Como era de esperar, la mayoría de sus incorporados tratan de alterar la forma de las cuerdas. Se interpreta, carácter por carácter, de la siguiente manera:

• 'y "comienza una cadena literal.

  Hasta que se encuentre la cita coincidente en el código fuente, todos los caracteres entre estas citas coincidentes se recopilan en una cadena, que luego se inserta en la pila.

• 0para 9empujar los enteros 0 a 9 en la pila. Tenga en cuenta que 10empuja dos enteros.

• ! saca una cadena de la pila e intenta evaluarla como ShapeScript.

• ? saca un número entero de la pila y empuja una copia del elemento de la pila en ese índice.

  El índice 0 corresponde al elemento de la pila superior (LIFO) y el índice -1 al inferior.

• _ saca un iterable de la pila y empuja su longitud.

• @ saca dos elementos de la pila y los empuja en orden inverso.

• $saca dos cadenas de la pila y divide la más inferior en las instancias de la más alta. La lista resultante se empuja a cambio.

• &saca una cadena (la más alta) y un iterable de la pila, y se une al iterable, usando la cadena como separador. La cadena resultante se empuja a cambio.

• Si se usa ShapeScript en nuestro planeta, dado que las pitones son los parientes más cercanos de los Changelings en la Tierra, todos los demás caracteres c muestran dos elementos x e y (los más altos) de la pila e intentan evaluar el código de Python x c y.

  Por ejemplo, la secuencia de caracteres 23+se evaluaría 2+3, mientras que la secuencia de caracteres "one"3*se evaluaría 'one'*3y la secuencia de caracteres 1''Ase evaluaría 1A''.

  En el último caso, dado que el resultado no es Python válido, el Changeling se quejaría de que su forma actual no está propuesta (error de sintaxis), ya que no es ShapeScript válido.

Antes de ejecutar el código, el intérprete colocará toda la entrada del usuario en forma de una cadena en la pila. Después de ejecutar el código fuente, el intérprete imprimirá todos los elementos en la pila. Si falla alguna parte en el medio, el Changeling se quejará de que su forma actual es inadecuada (error de tiempo de ejecución).

Cambio de forma

En su estado natural, los Changelings no toman la forma de ShapeScript. Sin embargo, algunos de ellos pueden transformarse en un código fuente potencial (que no es necesariamente útil o incluso sintácticamente válido).

Todos los Changelings elegibles tienen la siguiente forma natural:

• Todas las líneas deben tener el mismo número de caracteres.

• Todas las líneas deben consistir en caracteres ASCII imprimibles, seguidos de un solo salto de línea.

• El número de líneas debe coincidir con el número de caracteres imprimibles por línea.

Por ejemplo, la secuencia de bytes ab\ncd\nes un Changeling elegible.

En su intento de cambiar a ShapeScript, Changeling sufre la siguiente transformación:

• Inicialmente, no hay código fuente.

• Para cada línea sucede lo siguiente:

  • El acumulador de Changeling se establece en cero.

  • Para cada carácter c de la línea (incluido el avance de línea final), el punto de código de c se XOR con el acumulador dividido por 2, y el carácter Unicode que corresponde al punto de código resultante se agrega al código fuente.

    Después, la diferencia entre el punto de código de c y el punto de código de un espacio (32) se agrega al acumulador.

Si alguna parte de lo anterior falla, el Changeling se quejará de que su forma actual es desagradable.

Después de que se hayan procesado todas las líneas, la transformación de Changeling en ShapeScript (con suerte válida) se completa y se ejecuta el código resultante.

Solución (ShapeScript)

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

ShapeScript en realidad resultó ser bastante utilizable; incluso puede realizar pruebas de primalidad ( prueba ) y, por lo tanto, satisface nuestra definición de lenguaje de programación.

He reeditado ShapeScript en GitHub , con una sintaxis ligeramente modificada y una mejor E / S.

El código hace lo siguiente:

"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.

Solución (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=....................
""# !......................

Al igual que todos los programas Changeling, este código tiene un salto de línea final.

ShapeScript producirá un error de inmediato en cualquier carácter que no se entienda, pero podemos insertar cadenas arbitrarias como rellenos y reventarlas más tarde. Esto nos permite poner solo una pequeña cantidad de código en cada línea (al principio, donde el acumulador es pequeño), seguido de una apertura ". Si comenzamos la siguiente línea con "#, cerramos y sacamos la cadena sin afectar el código real.

Además, tenemos que superar tres obstáculos menores:

• La cadena larga en el código ShapeScript es un token único, y no podremos ajustarlo en una línea.

  Vamos a empujar esta cadena en trozos ( '@', '1?', etc.), lo que vamos a concatenar más tarde.

• El punto de código de _es bastante alto, y empujar '_'será problemático.

  Sin embargo, podremos presionar '_@'sin esfuerzo, seguido de otro '@'para deshacer el intercambio.

El código ShapeScript que nuestro Changeling generará se ve así ¹ :

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

Encontré el código Changeling ejecutando el código ShapeScript anterior a través de este convertidor . ²

Intérprete (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)))

¹ _{Cada línea se rellena con basura aleatoria a la cantidad de líneas, y los avances de línea no están realmente presentes.}
² _{Los números en la parte inferior indican el punto de código más bajo y más alto en el código Changeling, que debe permanecer entre 32 y 126.}

Shuffle (escrito en C ++), ¡Agrietado! por Martin

Editar Martin lo descifró. Para ver su solución, haga clic en el enlace. Mi solución también ha sido añadida.

Editar Comando fijo print-dpara poder manejar tanto registros como pilas. Como este es un comando de depuración que no está permitido en una solución, no debería afectar a nadie que use la versión anterior del intérprete

Todavía soy nuevo en esto, así que si hay algún problema con mi respuesta o mi intérprete, hágamelo saber. Solicite aclaraciones si algo no está claro.

No me imagino que esto sea demasiado difícil, pero espero que proporcione algún tipo de desafío. Lo que hace que la reproducción aleatoria sea bastante inutilizable es que solo se imprimirá cuando las cosas estén en su lugar correcto.

-> Conceptos básicos:

Hay 24 pilas, las llamamos stack1, ... stack24. Estas pilas viven en una lista. Al comienzo de cualquier programa, estas pilas tienen cero empujado y comienzan en su lugar correcto, es decir, se apilan i en la posición i-ésima de la lista (tenga en cuenta que indexaremos comenzando desde 1, a diferencia de C ++). Durante el curso de un programa, el orden de las pilas dentro de la lista cambiará. Esto es importante por razones que se explicarán cuando discuta los comandos.

Hay 5 registros disponibles para su uso. Se llaman Alberto, Gertrude, Hans, Leopold, ShabbySam. Cada uno de estos se establece en cero al comienzo de un programa.

Entonces, al comienzo de cualquier programa, hay 24 pilas, cada una con su número que coincide con su índice en la lista de la pila. Cada pila tiene exactamente un cero en la parte superior. Cada uno de los cinco registros se inicializa a cero.

-> Comandos y sintaxis :

Hay 13 comandos (comando de depuración +1) que están disponibles en Shuffle. Son los siguientes

• cinpushEste comando no toma argumentos. Espera la entrada de la línea de comandos de la manera descrita en la pregunta (otra entrada conducirá a resultados no especificados / indefinidos). Luego divide la cadena de entrada en enteros, por ejemplo, 101011100-> 1,1,3. Para cada entrada recibida, hace lo siguiente: (1) permuta la lista de pilas en función del valor. Deje que el valor entero en cuestión se llame a . Si a es menor que 10, hace permutación u . Si a está entre 9 y 30 (no incluido), hace permutación d . De lo contrario, hace permutación r . (2) Luego empuja unen la pila que está primero en la lista. Tenga en cuenta que no me refiero stack1(aunque puede ser el caso que stack1es el primero en la lista). Las permutaciones se definen a continuación. Dado que cinpushes la única forma de obtener información del usuario , debe aparecer en cualquier solución.

• mov value registerEl movcomando es básicamente una asignación variable. Asigna valuea register. valuepuede tomar varias formas: puede ser (1) un número entero, por ejemplo 47 (2) el nombre de un registro diferente, por ejemplo Hans (3) el índice de una pila seguido de 's', por ejemplo 4s. Tenga en cuenta que este es el índice en la lista, no el número de la pila. Como tal, el número no debe exceder 24.

  Algunos movejemplos:

  mov 4s Hans 
  mov Hans ShabbySam
  mov 9999 Gertrude
  

• movfs index registerEsto significa 'moverse de la pila'. Es similar al movcomando. Existe para que pueda acceder a una pila indexada por un registro. Por ejemplo, si anteriormente configuró Hans igual a 4 ( mov 4 Hans) Entonces puede utilizar movfs Hans Gertrudepara establecer Gertrude igual a la parte superior de la pila 4. Este tipo de comportamiento no es accesible simplemente usando mov.

• inc register aumenta el valor del registro en 1.
• dec register disminuye el valor del registro en 1.
• compg value value registerEsto significa 'comparar más grande'. Establece el registro igual al mayor de los dos valores. valuepuede ser un número entero, un registro o un índice de pila seguido de 's', como se indicó anteriormente.
• compl value value register 'comparar menor' igual que el anterior, excepto que toma el valor más pequeño.
• gte value1 value2 registerComprueba si value1 >= value2luego pone el valor booleano (como 1 o 0) en register.
• POP!! indexaparece en la parte superior de la pila indexada indexen la lista de la pila.
• jmp labelsalta incondicionalmente a la etiqueta label. Este es un buen momento para hablar sobre etiquetas. Una etiqueta es una palabra seguida de ':'. El intérprete analiza previamente las etiquetas, por lo que puede saltar a las etiquetas y retroceder.
• jz value labelsalta a labelsi valuees cero.

• jnz value labelsalta a labelsi valueno es cero.

  Ejemplos de etiquetas y saltos:

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

• "shuffle" permutationAquí está el comando shuffle. Esto le permite permutar la lista de pilas. Hay tres permutaciones válidos que se pueden utilizar como argumentos, l, f, y b.

• print registerEsto verifica si todas las pilas están en sus posiciones iniciales, es decir, la pila i está en el índice i en la lista de la pila. Si este es el caso, imprime el valor en registeren unario. De lo contrario, imprime un error desagradable. Como puede ver, para generar cualquier cosa, todas las pilas deben estar en los lugares correctos.
• done!esto le dice al programa que salga sin error. Si el programa finaliza sin done!, imprimirá en la consola el número en la parte superior de cada pila seguido del número de la pila. El orden en que se imprimen las pilas es el orden en que aparecen en la lista de pilas. Si una pila está vacía, se omitirá. Este comportamiento tiene fines de depuración y no se puede usar en una solución.
• print-d valueesto imprime el valor de la pila, el registro o el entero dado (para acceder a la pila i , pasar iscomo argumento, como se explicó anteriormente). Esta es una herramienta de depuración y no forma parte del lenguaje, por lo que no está permitida en una solución.

-> Aquí está el código del intérprete

Todo el análisis ocurre en la función principal. Aquí es donde lo encontrará analizando comandos específicos.

#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;
}

-> Permutaciones Las permutaciones permutan los elementos de la lista de la pila de la siguiente manera:

Donde significa que

(Estos también aparecen en el código del intérprete. Si hay una discrepancia, el intérprete es correcto).

-> Ejemplo simple

Estos dos programas simples imprimen los números del 24 al 1 (en unario) sin espacios en blanco.

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

o

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

Son el mismo programa.

Explicación y solución:

Martin también tiene una buena explicación en su respuesta .

Como Martin descubrió, este lenguaje se inspiró en el cubo de bolsillo (también conocido como cubo de Rubik 2x2). Las 24 pilas son como los 24 cuadrados individuales en el cubo. Las permutaciones son los movimientos básicos permitidos: arriba, abajo, derecha, izquierda, adelante, atrás.

La lucha principal aquí es que cuando se empujan los valores, solo se usan tres movimientos: arriba, abajo y derecha. Sin embargo, no tienes acceso a estos movimientos cuando "barajas" las pilas. Solo tienes los otros tres movimientos.

Como resultado, ambos conjuntos de tres movimientos en realidad abarcan todo el grupo (es decir, son generadores), por lo que el problema es solucionable. Esto significa que en realidad puedes resolver cualquier cubo de Rubik 2x2 solo usando 3 de los movimientos.

Todo lo que queda por hacer es descubrir cómo deshacer los movimientos hacia arriba, hacia abajo y hacia la derecha usando los otros tres. Con este fin, empleé un sistema de álgebra computacional llamado GAP .

Después de deshacer las permutaciones, encontrar el tercer número más grande es bastante trivial.

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 y Chuck , agrietados por caja de cartón

Hace un tiempo que me intriga la idea de un lenguaje de programación en el que dos programas interactúan entre sí (probablemente inspirados por ROCB ). Este desafío fue un buen incentivo para abordar este concepto por fin al intentar mantener el lenguaje lo más mínimo posible. Los objetivos de diseño eran hacer que el lenguaje fuera completo de Turing, mientras que cada una de sus partes individualmente no es completo para Turing. Además, incluso los dos juntos no deberían estar completos de Turing sin hacer uso de la manipulación del código fuente. Creo que he tenido éxito con eso, pero aún no he probado ninguna de esas cosas formalmente. Entonces, sin más preámbulos, te presento ...

Los protagonistas

Brian y Chuck son dos programas similares a Brainfuck. Solo uno de ellos se está ejecutando en un momento dado, comenzando con Brian. El problema es que la cinta de memoria de Brian también es el código fuente de Chuck. Y la cinta de memoria de Chuck también es el código fuente de Brian. Además, el cabezal de cinta de Brian también es el puntero de instrucciones de Chuck y viceversa. Las cintas son semi-infinitas (es decir, infinitas a la derecha) y pueden contener enteros de precisión arbitraria firmados, inicializados a cero (a menos que el código fuente especifique lo contrario).

Dado que el código fuente también es una cinta de memoria, los comandos se definen técnicamente por valores enteros, pero corresponden a caracteres razonables. Existen los siguientes comandos:

• ,( 44): Lee un byte de STDIN en la celda de memoria actual. Solo Brian puede hacer esto. Este comando es un no-op para Chuck.
• .( 46): Escribe la celda de memoria actual, módulo 256, como un byte a STDOUT. Solo Chuck puede hacer esto. Este comando es un no-op para Brian.
• +( 43): Incrementa la celda de memoria actual.
• -( 45): Disminuye la celda de memoria actual.
• ?( 63): Si la celda de memoria actual es cero, esto es un no-op. De lo contrario, transfiera el control al otro programa. El cabezal de la cinta en el programa que utiliza ?permanecerá en el ?. El cabezal de la cinta del otro programa moverá una celda a la derecha antes de ejecutar el primer comando (por lo que la celda que se utiliza como prueba no se ejecuta).
• <( 60): Mueva el cabezal de la cinta una celda hacia la izquierda. Esto es un no-op si el cabezal de la cinta ya está en el extremo izquierdo de la cinta.
• >( 62): Mueva el cabezal de la cinta una celda hacia la derecha.
• {( 123): Mueva repetidamente el cabezal de la cinta hacia la izquierda hasta que la celda actual sea cero o se llegue al extremo izquierdo de la cinta.
• }( 125): Mueva repetidamente el cabezal de la cinta hacia la derecha hasta que la celda actual sea cero.

El programa termina cuando el puntero de instrucciones del programa activo alcanza un punto donde no hay más instrucciones a su derecha.

El código fuente

El archivo fuente se procesa de la siguiente manera:

• Si el archivo contiene la cadena ```, el archivo se dividirá en dos partes alrededor de la primera aparición de esa cadena. Todos los espacios en blanco iniciales y finales se eliminan y la primera parte se usa como código fuente para Brian y la segunda parte para Chuck.
• Si el archivo no contiene esta cadena, la primera línea del archivo se utilizará como fuente para Brian y la segunda parte para Chuck (aparte de la nueva línea delimitadora, no se eliminará ningún espacio en blanco).
• Todas las apariciones de _en ambos programas se reemplazan con bytes NULL.
• Las dos cintas de memoria se inicializan con los códigos de caracteres correspondientes a la cadena resultante.

Como ejemplo, el siguiente archivo fuente

  abc
```
0_1
23

Produciría las siguientes cintas iniciales:

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

El interprete

El intérprete está escrito en rubí. Se necesitan dos marcas de línea de comandos que no deben ser utilizadas por ninguna solución (ya que no forman parte de la especificación del lenguaje real):

• -d: Con esta bandera, Brian y Chuck entienden dos comandos más. !imprimirá una representación de cadena de ambas cintas de memoria, el programa activo se enumerará primero (a ^marcará los cabezales de cinta actuales). @también lo hará, pero luego terminará inmediatamente el programa. Como soy vago, ninguno de esos funciona si son el último comando del programa, así que si quieres usarlos allí, repítelos o escribe un no-op después de ellos.
• -D: Este es el modo de depuración detallado. Imprimirá la misma información de depuración que !después de cada tic. @También funciona en este modo.

Aquí está el código:

# 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)

Aquí está mi propia solución (manuscrita) al problema:

>}>}>
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:
{<{<?

Este código es ejecutable tal cual, porque todas las anotaciones usan no-ops y son omitidas por {y }.

La idea básica es:

1. Agregue un nuevo elemento cero a la lista (al final de la cinta de Chuck) y aumente la longitud de la lista en 1.
2. Mientras leemos 1s, incremente ese elemento.

3. Cuando estamos leyendo un 0, haz una limpieza. Si el entero resultante fue mayor que cero, regrese a 1.

   Ahora tenemos una lista de los números de entrada al final de la cinta de Chuck y sabemos la longitud de la lista.

4. Reste 2 de la longitud de la lista (por lo que los siguientes pasos ignoran los dos elementos más grandes), llame a esto N.

5. Mientras tanto N > 0, incremente un total acumulado y luego disminuya todos los elementos de la lista. Siempre que un elemento de la lista llegue a cero, disminuya N.

   Al final de esto, el total acumulado contendrá el tercer mayor número en la entrada, M.

6. Escriba Mcopias .al final de la cinta de Chuck.

7. En Chuck, busque un 1en la cinta de Brian y luego ejecute los generados .al final.

Después de terminar esto, me di cuenta de que podía simplificarlo bastante en algunos lugares. Por ejemplo, en lugar de hacer un seguimiento de ese contador y escribirlos .en la cinta de Chuck, podría imprimir uno de 1inmediato, cada vez antes de disminuir todos los elementos de la lista. Sin embargo, hacer cambios a este código es bastante difícil, ya que propaga otros cambios por todo el lugar, por lo que no me molesté en hacer el cambio.

Lo interesante es cómo hacer un seguimiento de la lista y cómo recorrerla. No puede simplemente almacenar los números consecutivamente en la cinta de Chuck, porque si desea verificar una condición en uno de los elementos de la lista, corre el riesgo de ejecutar el resto de la lista que puede contener un código válido. Tampoco sabe cuánto tiempo durará la lista, por lo que no puede reservar un espacio frente al código de Chuck.

El siguiente problema es que debemos dejar que la lista disminuya Nmientras la procesamos, y necesitamos volver al mismo lugar que antes. Pero {y }simplemente pasaría por alto la lista completa.

Entonces, necesitamos escribir algo de código dinámicamente en Chuck. De hecho, cada elemento de la lista itiene la forma:

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

1es un marcador que podemos establecer en cero para indicar dónde dejamos de procesar la lista. Su propósito es atrapar {o }que simplemente pasará sobre el código y el i. También usamos este valor para verificar si estamos al final de la lista durante el procesamiento, por lo tanto, mientras no lo estemos, esto será 1y el condicional ?cambiará el control a Chuck. Code Ase utiliza para manejar esa situación y mover la IP en Brian en consecuencia.

Ahora, cuando disminuimos i, necesitamos verificar si iya es cero. Si bien no es así, ?cambiará de nuevo el control, por lo que Code Bestá ahí para manejar eso.

HPR, escrito en Python 3 ( descifrado por TheNumberOne )

HPR (el nombre no significa nada) es un lenguaje para procesar listas de enteros. Está diseñado para ser minimalista , extremadamente limitado y libre de restricciones "artificiales" . La programación en HPR es dolorosa, no porque tenga que resolver un rompecabezas para evitar que el intérprete le grite, sino porque es difícil hacer que un programa haga algo útil. No sé si HPR es capaz de hacer algo sustancialmente más interesante que calcular el tercer elemento más grande de una lista.

Especificación de idioma

Un programa HPR se ejecuta en un entorno , que es un conjunto sin orden de duplicados de enteros no negativos y listas de enteros no negativos. Inicialmente, el entorno contiene solo la lista de entrada (el intérprete lo analiza por usted). Hay tres comandos y dos operadores de "flujo de control" que modifican el entorno:

• *elimina el primer elemento de cada lista no vacía en el entorno y lo coloca en el entorno. Las listas vacías no se ven afectadas. Por ejemplo, se transforma

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

• -disminuye todos los números en el entorno y luego elimina elementos negativos. Por ejemplo, se transforma

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

• $Rota cada lista del entorno un paso hacia la izquierda. Por ejemplo, se transforma

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

• !(A)(B), donde Ay Bson programas, es básicamente un whilebucle. Realiza la "acción" Ahasta que la "prueba" Bdé como resultado un entorno vacío. Esto puede producir un bucle infinito.
• #(A)(B), donde Ay Bson programas, aplica Ay Bal entorno actual y toma la diferencia simétrica de los resultados.

Los comandos se ejecutan de izquierda a derecha. Al final, el tamaño del entorno se imprime en unario.

El interprete

Este intérprete presenta el comando de depuración ?, que imprime el entorno sin modificarlo. No debería aparecer en ninguna solución a la tarea. Todos los caracteres excepto *-$!#()?se ignoran simplemente, por lo que puede escribir comentarios directamente en el código. Finalmente, el intérprete reconoce el modismo !(A)(#(A)())como "actuar Ahasta que el resultado ya no cambie", y lo optimiza para una velocidad adicional (lo necesitaba para que mi solución terminara en menos de una hora en el último caso de prueba).

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))

Mi solución

Mi solución de referencia tiene 484 bytes de longitud, muy corta en comparación con el programa de 3271 bytes de TheNumberOne. Esto es muy probable debido al sofisticado y sorprendente sistema macro que TheNumberOne desarrolló para programar en HPR. La idea principal en nuestros dos programas es similar:

1. Descubra cómo producir el elemento máximo de una lista.
2. Para eliminar el elemento máximo, gire la lista hasta que el primer elemento sea igual al máximo, luego revíselo.
3. Elimine el máximo dos veces, luego imprima el nuevo elemento máximo.

Sin embargo, por lo que puedo decir, los detalles exactos de implementación son bastante diferentes. Aquí está mi solución:

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

Y aquí está el programa comentado de Python que lo produce (nada lujoso aquí, solo manipulación básica de cadenas para deshacerse de toda la repetición):

# 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 (Para matar al dragón, necesitas una espada) - Cracked por Martin Büttner

EDITAR: He agregado mi solución y explicación debajo de la publicación principal.

Antecedentes

En este lenguaje, tomas el control de un valiente guerrero al que se le ha encomendado la tarea de matar a un terrible dragón. El dragón vive en un laberinto subterráneo, lleno de peligros y peligros, y hasta ahora, nadie ha sido capaz de mapearlo y sobrevivir. Esto significa que debes navegar hacia el dragón en la oscuridad total, con nada más que intuición y valentía para guiarte.

...

Bueno, no del todo. Has traído un suministro casi ilimitado de secuaces desechables contigo, y están dispuestos a ir por delante de ti para descubrir la ruta segura. Desafortunadamente, todos son tan gruesos como dos tablones cortos, y solo harán exactamente lo que les dices. Depende de usted encontrar un método inteligente para garantizar que sus secuaces descubran el camino correcto.

Algunos mas detalles

La guarida del dragón toma la forma de una cuadrícula de 10x10. Entre ciertos puntos adyacentes en la cuadrícula, hay una pasarela estrecha; entre otros, hay un profundo abismo y una muerte segura. Un diseño de ejemplo para una cuadrícula de 4x4 podría ser el siguiente:

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

Usted sabe que siempre hay una manera de llegar de un punto a otro, pero no más de lo que se le ha revelado.

Para derrotar con éxito al dragón, primero debes recolectar algunos elementos que podrás combinar para crear una cuchilla mágica que mata dragones. Convenientemente, todas las piezas de esta arma se han dispersado por la guarida del dragón. Simplemente tienes que recogerlos.

El giro es que cada pieza del arma ha quedado atrapada. Cada vez que se recolecta uno, cambia el diseño de las pasarelas. Los caminos previamente seguros ahora pueden conducir a una muerte segura, y viceversa.

Comandos

Solo hay 5 comandos válidos.

• < - Da un paso a la izquierda

• > - Da un paso a la derecha

• ^ - Da un paso hacia arriba

• v - Da un paso hacia abajo

• c- Recoge cualquier artículo que esté por ahí en tu posición actual. Si había elementos presentes, el diseño de la guarida cambia. Con las posiciones numeradas en filas como arriba, tome su posición módulo 10. Hay 10 diseños codificados en el intérprete, y el diseño cambia al correspondiente. Por ejemplo, si está en la posición 13, el diseño cambia alayouts[3]

Los diseños tal como aparecen en el intérprete se han codificado en enteros de la siguiente manera:

• El diseño vacío se codifica a cero.

• Para cada borde en el diseño, deje que xsea ​​la menor de las dos posiciones a las que se une.

  • Si el paso es horizontal, agréguelo 2^(2*x)a la codificación (eso es potencia, no XOR)

  • Si el paso es vertical, agréguelo 2^(2*x + 1)a la codificación.

Flujo de ejecución

El intérprete se ejecuta con el nombre de un archivo fuente como argumento de línea de comandos.

Cuando se ejecuta el intérprete, solicitará al usuario que proporcione una búsqueda. Esta entrada debe estar en la forma descrita en la pregunta, y determina las ubicaciones en la guarida de los componentes del arma. Específicamente, cada entero de entrada se toma el módulo 100 y se coloca en la ubicación correspondiente en la guarida.

Cada programa fuente consta de varias líneas, cada línea que consiste en una secuencia de los 5 caracteres válidos anteriores. Estas líneas representan tus secuaces. Usted, el guerrero, realiza un seguimiento de una secuencia de acciones que se sabe que son seguras. Inicialmente, no sabes nada sobre la guarida, por lo que esta secuencia está vacía. Tomando cada minion por turno, se realiza lo siguiente, comenzando desde la posición 0:

• El minion recibe instrucciones de realizar todas las acciones que se sabe que son seguras, seguidas de las acciones en su propia línea de código.

  • Si el súbdito muere en algún momento, se le notificará esto y la guarida se restablecerá a su configuración inicial. Todos los artículos se reemplazan y las pasarelas vuelven a sus posiciones iniciales.

  • Si, en cambio, el minion sobrevive, entonces lo vaporizas de todos modos, después de todo, es solo un minion. Como antes, esto activa el restablecimiento de la guarida a su estado inicial, pero esta vez, agrega las acciones de la línea de código del minion a la secuencia de acciones conocidas como seguras.

Una vez que todos los secuaces se han agotado, usted, el guerrero, realiza todas las acciones que se sabe que son seguras, nuevamente comenzando desde la posición 0. Hay dos resultados posibles:

• Recoges todas las piezas del arma; en este caso, matas con éxito al dragón y se emite un emocionante mensaje de victoria. Este mensaje de victoria contendrá, entre otros caracteres, nunos, donde nes el tercer número más alto proporcionado como entrada.

• No has podido recoger algunas de las piezas del arma; en este caso, el dragón sigue vivo y has fallado en tu búsqueda.

Código de intérprete (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()

Mucha suerte, valiente guerrero.

Mi solucion y explicacion

Aquí hay un script de Python que genera código fuente para resolver el problema. Por interés, el código fuente final de Martin es aproximadamente 5 veces más pequeño que el código producido por mi script. Por otro lado, mi script para generar el código es aproximadamente 15 veces más pequeño que el programa Mathematica de Martin ...

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')

Estructura basica

Esto genera 990 líneas de código fuente, que vienen en grupos de 10. Las primeras 10 líneas contienen instrucciones que intentan mover a un súbdito de una posición 0a otra 1, y luego recolectan un elemento, un conjunto para cada diseño posible. Las siguientes 10 líneas contienen instrucciones que intentan mover a un súbdito de una posición 1a otra 2y luego recoger un objeto. Y así sucesivamente ... Estos caminos se calculan con la pathfunción en el guión - que sólo hace un simple búsqueda en profundidad.

Si podemos asegurarnos de que, en cada grupo de 10, precisamente un minion tenga éxito, entonces habremos resuelto el problema.

El problema con el enfoque

Es posible que no siempre sea el caso de que precisamente un minion del grupo de 10 tenga éxito; por ejemplo, un minion diseñado para moverse de una posición 0a otra 1podría accidentalmente tener éxito en moverse de una posición 1a otra 2(debido a las similitudes en los diseños), y que el error de cálculo se propagará, lo que podría causar fallas.

Como arreglarlo

La solución que usé fue la siguiente:

Por cada súbdito que intente ir de una posición na otra n+1, primero hágale caminar de una posición na otra 0(la esquina superior izquierda) y de regreso, luego de una posición na otra 99(la esquina inferior derecha) y de regreso. Estas instrucciones solo pueden llevarse a cabo de forma segura desde ncualquier posición : cualquier otra posición inicial y el súbdito se alejará del borde.

Por lo tanto, estas instrucciones adicionales evitan que los súbditos vayan accidentalmente a un lugar al que no están destinados, y esto garantiza que exactamente un súbdito de cada grupo de 10 sea exitoso. Tenga en cuenta que no es necesariamente el súbdito que espera que sea; podría ser el caso de que el súbdito que cree que está en el diseño 0 tiene éxito, incluso cuando realmente estamos en el diseño 7, pero en cualquier caso, el hecho de que tenemos ahora cambiar de posición significa que todos los demás súbditos del grupo necesariamente morirán. La assert_atfunción calcula estos pasos adicionales y la safe_pathfunción devuelve una ruta que es la concatenación de estos pasos adicionales con la ruta ordinaria.

Firetype, agrietado por Martin Büttner

Una mezcla realmente extraña de BF y CJam. ¡Y quién sabe qué más! Estoy bastante seguro de que será fácil, pero de todos modos fue divertido. FYI, el nombre se refiere a Vermillion Fire de Final Fantasy Type-0 .

NOTA : Perdóneme por cualquier ambigüedad en esta descripción. No soy el mejor escritor ...: O

¡Martin resolvió esto muy rápido! Este fue mi programa original para resolver el problema:

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











`
~
+
|
%

_
=

\
@
-
-
!
<
>
>
>

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

Sintaxis

Un script Firetype es básicamente una lista de líneas. El primer carácter de cada línea es el comando a ejecutar. Las líneas vacías son básicamente NOP.

Semántica

Tiene una variedad de enteros y un puntero (piense BF). Puede mover elementos de izquierda a derecha o "empujar" en la matriz.

Emprendedor

Cuando "empujas" un elemento y estás al final de la matriz, se agregará un elemento adicional al final. Si no está al final, se anulará el siguiente elemento. En cualquier caso, el puntero siempre se incrementará.

Comandos

_

Empuje un cero en la matriz.

+

Incremente el elemento en el puntero actual.

-

Disminuya el elemento en el puntero actual.

*

Duplique el elemento en el puntero actual.

/

Reducir a la mitad el elemento en el puntero actual.

%

Tome el elemento en el puntero actual y salte varias líneas hacia adelante, y mueva el puntero hacia la izquierda. Si el valor es negativo, salta hacia atrás en su lugar.

=

Tome el elemento en el puntero actual y salte a esa línea + 1. Por ejemplo, si el elemento actual es 0, saltará a la línea 1. Esto también mueve el puntero a la izquierda.

,

Lea un carácter de la entrada estándar y presione su valor ASCII.

^

Tome el elemento en el puntero actual, inténtelo como el valor ASCII para un carácter y conviértalo en un entero. Por ejemplo, si el valor actual es 49 (el valor ASCII de 1), el elemento en el puntero actual se establecerá en el entero 1.

.

Escribe el número actual en la pantalla.

!

Tome el elemento en el puntero actual y repita la siguiente línea muchas veces. También mueve el puntero a la izquierda.

<

Mueve el puntero hacia la izquierda. Si ya está al principio, se produce un error.

>

Mueve el puntero hacia la derecha. Si ya está al final, se produce un error.

~

Si el elemento actual no es cero, reemplácelo con 0; de lo contrario, reemplácelo con 1.

|

Cuadrar el elemento actual.

@

Establecer el elemento actual a la longitud de la matriz.

`

Duplicar el elemento actual.

\

Ordenar los elementos en y antes del puntero.

#

Negar el elemento actual.

El interprete

También disponible en Github .

#!/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 !! (seguro)

Está de vuelta ...

... y con suerte definitivamente más a prueba de lagunas.

Ya leí el Acc! Especificaciones. ¿Cómo es Acc !! ¿diferente?

En Acc !! , las variables de bucle quedan fuera de alcance cuando el bucle sale. Solo puedes usarlos dentro del bucle. En el exterior, obtendrá un error "el nombre no está definido". Aparte de este cambio, los idiomas son idénticos.

Declaraciones

Los comandos se analizan línea por línea. Hay tres tipos de comando:

1. Count <var> while <cond>

Cuenta <var>desde 0 siempre que <cond>no sea cero, equivalente a C ++ for(int <var>=0; <cond>; <var>++). El contador de bucle puede ser cualquier letra minúscula. La condición puede ser cualquier expresión, que no implique necesariamente la variable de bucle. El ciclo se detiene cuando el valor de la condición se convierte en 0.

Los bucles requieren llaves rizadas de estilo K y R (en particular, la variante Stroustrup ):

Count i while i-5 {
 ...
}

Como se mencionó anteriormente, las variables de bucle solo están disponibles dentro de sus bucles ; intentar hacer referencia a ellos luego causa un error.

2. Write <charcode>

Emite un solo carácter con el valor ASCII / Unicode dado a stdout. El código de char puede ser cualquier expresión.

3. Expresión

Cualquier expresión en sí misma se evalúa y se asigna de nuevo al acumulador (al que se puede acceder como _). Por lo tanto, por ejemplo, 3es una declaración que establece el acumulador en 3; _ + 1incrementa el acumulador; y _ * Nlee un personaje y multiplica el acumulador por su código de char.

Nota: el acumulador es la única variable a la que se puede asignar directamente; variables de bucle y Nse pueden usar en cálculos pero no se pueden modificar.

El acumulador es inicialmente 0.

Expresiones

Una expresión puede incluir literales enteros, variables de bucle ( a-z), _para el acumulador y el valor especial N, que lee un carácter y evalúa su código de caracteres cada vez que se usa. Nota: esto significa que solo tienes una oportunidad para leer cada personaje; la próxima vez que lo uses N, leerás el siguiente.

Los operadores son:

• +, además
• -resta negación unaria
• *multiplicación
• /, División entera
• %módulo
• ^exponenciación

Los paréntesis pueden usarse para imponer la precedencia de las operaciones. Cualquier otro carácter en una expresión es un error de sintaxis.

Espacio en blanco y comentarios

Los espacios en blanco iniciales y finales y las líneas vacías se ignoran. El espacio en blanco en los encabezados del bucle debe ser exactamente como se muestra, con un solo espacio entre el encabezado del bucle y la llave de apertura. El espacio en blanco dentro de las expresiones es opcional.

# comienza un comentario de una sola línea.

De entrada y salida

Acc !! espera una sola línea de caracteres como entrada. Cada carácter de entrada se puede recuperar en secuencia y su código de char procesado usando N. Intentar leer más allá del último carácter de la línea provoca un error. Se puede generar un carácter pasando su código de char a la Writeinstrucción.

Interprete

El intérprete (escrito en Python 3) traduce Acc !! codifique en Python y execlisto.

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()

Solución

La caída del Acc! Original Eran variables de bucle que seguían siendo accesibles fuera de sus bucles. Esto permitió guardar copias del acumulador, lo que hizo que la solución fuera demasiado fácil.

Aquí, sin este agujero de bucle (lo siento), solo tenemos el acumulador para almacenar cosas. Sin embargo, para resolver la tarea, necesitamos almacenar cuatro valores arbitrariamente grandes. ¹ La solución: intercalar sus bits y almacenar el número de combinación resultante en el acumulador. Por ejemplo, un valor de acumulador de 6437 almacenaría los siguientes datos (utilizando el bit de orden más bajo como un indicador de un solo bit):

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

Podemos acceder a cualquier bit de cualquier número dividiendo el acumulador por la potencia apropiada de 2, mod 2. Esto también permite configurar o voltear bits individuales.

En el nivel macro, el algoritmo recorre los números unarios en la entrada. Lee un valor en el número 0, luego pasa el algoritmo de clasificación de burbujas para colocarlo en la posición correcta en comparación con los otros tres números. Finalmente, descarta el valor que queda en el número 0, ya que ahora es el más pequeño de los cuatro y nunca puede ser el tercero más grande. Cuando finaliza el ciclo, el número 1 es el tercero más grande, por lo que descartamos los demás y lo enviamos.

La parte más difícil (y la razón por la que tuve variables de bucle global en la primera encarnación) es comparar dos números para saber si intercambiarlos. Para comparar dos bits, podemos convertir una tabla de verdad en una expresión matemática; mi avance para Acc !! estaba encontrando un algoritmo de comparación que procedía de bits de orden bajo a orden alto, ya que sin variables globales no hay forma de recorrer los bits de un número de izquierda a derecha. El bit de orden más bajo del acumulador almacena una bandera que indica si se intercambian los dos números actualmente en consideración.

Sospecho que Acc !! es Turing completo, pero no estoy seguro de querer tomar la molestia de probarlo.

Aquí está mi solución con comentarios:

# 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
}

_{¹ Según la especificación de la pregunta, solo se deben admitir valores de hasta 1 millón. Me alegra que nadie haya aprovechado eso para una solución más fácil, aunque no estoy completamente seguro de cómo harían las comparaciones.}

Picofuck (seguro)

Picofuck es similar a Smallfuck . Funciona en una cinta binaria que está desatada a la derecha, unida a la izquierda. Tiene los siguientes comandos:

• > mover el puntero a la derecha

• <mueve el puntero hacia la izquierda. Si el puntero se cae de la cinta, el programa termina.

• * voltear el bit en el puntero

• (si el bit en el puntero es 0, salta al siguiente)

• )no hacer nada: los paréntesis en Picofuck son ifbloques, no whilebucles.

• .escriba para stdout el bit en el puntero como un ascii 0o 1.

• ,leemos desde stdin hasta que encontramos un 0o 1, y almacenamos esto en el bit en el puntero.

Envolturas de código Picofuck: una vez que se alcanza el final del programa, continúa desde el principio.

Además, Picofuck no permite paréntesis anidados. Los paréntesis que aparecen en un programa Picofuck deben alternar entre (y ), comenzando (y terminando con ).

Interprete

Escrito en Python 2.7

uso: 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)

Solución

El siguiente programa de Python 2.7 genera mi solución que se puede encontrar aquí

Puedo editar esta publicación más adelante con una explicación más detallada de cómo funciona, pero resulta que Picofuck está completo de Turing.

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 - ¡Seguro! / Solución proporcionada

Lo esencial

Todas las instrucciones implícitas tienen cuatro operandos de dirección de memoria:

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

¿Dónde vestá el tamaño de la memoria en los cuartetos?

Pᵢ, Qᵢ, Rᵢ, SᵢSon números enteros de tamaño nativo de la máquina firmado (por ejemplo, 16, 32 o 64 bits), que nos referiremos como palabras.

Para cada cuarteto i, la operación implícita, con []denotar indirección, es:

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

Tenga en cuenta que Subleq es un subconjunto de PQRS .

Subleq ha demostrado ser completo, por lo que PQRS también debería estar completo.

Estructura del programa

PQRS define un encabezado inicial de la siguiente manera:

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

H₀ H₁ H₂ H₃Es siempre la primera instrucción P₀ Q₀ R₀ S₀. H₀que H₃deben definirse en tiempo de carga.

PQRS tiene E / S rudimentaria, pero suficiente para el desafío.

H₄ H₅: al inicio del programa, lee un máximo de H₅caracteres ASCII de la entrada estándar y se guarda como palabras en el índice en H₄adelante. H₄y H₅deben definirse en el momento de la carga. Después de leer, H₅se establecerá el número de caracteres leídos (y las palabras guardadas).

H₆ H₇: al finalizar el programa, comenzando en el índice H₆, imprime todos los bytes que comprenden las H₇palabras a la salida estándar como caracteres ASCII. H₆y H₇debe definirse antes de que finalice el programa. '\0'Se omitirán los bytes nulos en la salida.

Terminación

La terminación se logra estableciendo Sᵢlímites i < 0o i ≥ v.

Trucos

Los cuartetos Pᵢ Qᵢ Rᵢ Sᵢno necesitan estar alineados o secuenciales, se permite la ramificación a intervalos de sub-cuarteto.

PQRS tiene indirección, por lo que, a diferencia de Subleq, hay suficiente flexibilidad para implementar subrutinas.

¡El código puede modificarse automáticamente!

Interprete

El intérprete está escrito en C:

#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;
}

Para usar, guarde lo anterior como pqrs.c y luego compile:

gcc -o pqrs pqrs.c

Programa de muestra

Los ecos ingresan hasta 40 caracteres, precedidos por 'PQRS-'.

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

Para ejecutar, guarde lo anterior como echo.pqrs, entonces:

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

Ejecutando los casos de prueba:

$ ./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

Todos los casos de prueba se ejecutan extremadamente rápido, por ejemplo, <500 ms.

El reto

PQRS puede considerarse estable, por lo que el desafío comienza 2015-10-31 13:00 y termina 2015-11-08 13:00, veces en UTC.

¡Buena suerte!

Solución

El lenguaje es bastante similar al utilizado en "Baby" , la primera máquina digital electrónica de programas almacenados del mundo. ¡En esa página hay un programa para encontrar el factor más alto de un entero en menos de 32 palabras de memoria (CRT!)!

Descubrí que escribir la solución para cumplir con las especificaciones no era compatible con el sistema operativo y la máquina que estaba usando (un derivado de Linux Ubuntu en hardware un poco más antiguo). Solo estaba solicitando más memoria de la disponible, y volcado del núcleo. En sistemas operativos con administración avanzada de memoria virtual o máquinas con al menos 8 GB de memoria, probablemente pueda ejecutar la solución según las especificaciones. He proporcionado ambas soluciones.

Es muy difícil codificar en PQRS directamente, similar al lenguaje de máquina de escribir, tal vez incluso microcódigo. En cambio, es más fácil escribir en una especie de lenguaje ensamblador que "compilarlo". A continuación se muestra el lenguaje ensamblador anotado para la solución optimizada para ejecutar los casos de prueba:

; 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

Lo que hace es analizar la entrada, convirtiendo unario a binario, luego una burbuja ordenando los números con los valores en orden decreciente, y finalmente genera el tercer valor más grande convirtiendo el binario de nuevo en unario.

¡Tenga en cuenta que INC(incremento) es negativo y DEC(decremento) es positivo! Donde está usando L#o L#+1as P-o Q-OPs, lo que está sucediendo es que está actualizando punteros: incrementando, decrementando, intercambiando, etc. El ensamblador se compiló a mano en PQRS sustituyendo las etiquetas con los desplazamientos. A continuación se muestra la solución optimizada PQRS :

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

El código anterior se puede guardar challenge-optimized.pqrspara ejecutar los casos de prueba.

Para completar, aquí están las fuentes por especificaciones:

; 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

Y solución:

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

Para ejecutar lo anterior, se necesitará comentar #define OPTIMIZEDy añadir #define PER_SPECSen pqrs.cy recompilar.

Este fue un gran desafío, ¡realmente disfruté el entrenamiento mental! Me llevó de vuelta a mis viejos días de ensamblador 6502 ...

Si tuviera que implementar PQRS como un lenguaje de programación "real", probablemente agregaría modos adicionales para acceso directo y doblemente indirecto además del acceso indirecto, así como posición relativa y posición absoluta, ¡ambas con opciones de acceso indirecto para la ramificación!

¡Zinc agrietado! por @Zgarb

También disponible en GitHub .

Necesitas Dart 1.12 y Pub. Simplemente ejecute pub getpara descargar la única dependencia, una biblioteca de análisis.

¡Esperemos que este dure más de 30 minutos! : O

El idioma

El zinc está orientado a redefinir operadores. ¡Puede redefinir todos los operadores en el idioma fácilmente!

La estructura de un programa típico de zinc se ve así:

let
<operator overrides>
in <expression>

Solo hay dos tipos de datos: enteros y conjuntos. No existe un conjunto literal, y los conjuntos vacíos no están permitidos.

Expresiones

Las siguientes son expresiones válidas en Zinc:

Literales

El zinc admite todos los literales enteros normales, como 1y -2.

Variables

El zinc tiene variables (como la mayoría de los idiomas). Para hacer referencia a ellos, solo use el nombre. De nuevo como la mayoría de los idiomas!

Sin embargo, hay una variable especial llamada Sque se comporta como Pyth Q. Cuando lo use por primera vez, leerá en una línea desde la entrada estándar y lo interpretará como un conjunto de números. Por ejemplo, la línea de entrada 1234231se convertiría en el conjunto {1, 2, 3, 4, 3, 2, 1}.

¡¡¡NOTA IMPORTANTE!!! En algunos casos, un literal al final de una anulación del operador se analiza incorrectamente, por lo que debe rodearse con paréntesis.

Operaciones binarias

Se admiten las siguientes operaciones binarias:

• Además a través de +: 1+1.
• La resta a través de -: 1-1.
• La multiplicación a través de *: 2*2.
• División a través de /: 4/2.
• La igualdad con =: 3=3.

Además, también se admite la siguiente operación unaria:

• Longitud con #: #x.

La precedencia es siempre correcta asociativa. Puede usar paréntesis para anular esto.

Solo la igualdad y la longitud trabajan en sets. Cuando intenta obtener la longitud de un número entero, obtendrá el número de dígitos en su representación de cadena.

Establecer comprensiones

Para manipular conjuntos, Zinc ha comprendido conjuntos. Se ven así:

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

Una cláusula es una cláusula when o una cláusula sort.

Una cláusula when parece ^<expression>. La expresión que sigue al símbolo de intercalación debe dar como resultado un número entero. El uso de la cláusula when tomará solo los elementos del conjunto para los cuales expressionno es cero. Dentro de la expresión, la variable _se establecerá en el índice actual del conjunto. Es más o menos equivalente a este Python:

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

Una cláusula de ordenación , que parece $<expression>, ordena el conjunto descendiendo por el valor de <expression>. Es igual a este Python:

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

Aquí hay algunos ejemplos de comprensión:

• Tome solo los elementos del conjunto sque son iguales a 5:

  {x:s^x=5}
  

• Ordene el conjunto spor el valor si sus elementos están al cuadrado:

  {x:s$x*x}
  

Anulaciones

Las anulaciones de operador le permiten redefinir operadores. Se ven así:

<operator>=<operator>

o:

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

En el primer caso, puede definir un operador para que sea igual a otro operador. Por ejemplo, puedo definir +restar realmente a través de:

+=-

Cuando haces esto, puedes redefinir un operador para que sea un operador mágico . Hay dos operadores mágicos:

• jointoma un conjunto y un entero y se une al contenido del conjunto. Por ejemplo, unirse {1, 2, 3}con 4dará como resultado el entero 14243.

• cuttambién toma un conjunto y un número entero y dividirá el conjunto en cada aparición del número entero. Usando cuton {1, 3, 9, 4, 3, 2}y 3creará {{1}, {9, 4}, {2}}... PERO cualquier conjunto de un solo elemento se aplana, por lo que el resultado será realmente {1, {9, 4}, 2}.

Aquí hay un ejemplo que redefine al +operador para que signifique join:

+=join

Para el último caso, puede redefinir un operador a la expresión dada. Como ejemplo, esto define la operación más para agregar los valores y luego agregar 1:

x+y=1+:x+:y

Pero lo que es +:? Puede agregar los dos puntos :a un operador para usar siempre la versión incorporada. Este ejemplo usa la +vía incorporada +:para sumar los números, luego agrega un 1 (recuerde, todo es asociativo correcto).

Anular el operador de longitud se parece a:

#x=<expression>

Tenga en cuenta que casi todas las operaciones integradas (excepto la igualdad) utilizarán este operador de longitud para determinar la longitud del conjunto. Si lo definiste como:

#x=1

cada parte de Zinc que funciona en conjuntos, excepto =que solo funcionaría en el primer elemento del conjunto que se le dio.

Anulaciones múltiples

Puede anular varios operadores separándolos con comas:

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

Impresión

No puede imprimir directamente nada en Zinc. Se inimprimirá el resultado de la siguiente expresión . Los valores de un conjunto se concatenarán con separador. Por ejemplo, toma esto:

let
...
in expr

Si expres el conjunto {1, 3, {2, 4}}, 1324se imprimirá en la pantalla una vez que finalice el programa.

Poniendolo todo junto

Aquí hay un programa simple de Zinc que parece agregar 2+2pero hace que el resultado sea 5:

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

El interprete

Esto entra en 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());
}

Y esto entra pubspec.yaml:

name: zinc
dependencies:
  parsers: any

Solución prevista

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

Sopa de brújula ( agrietada por cartón_caja )

Intérprete: C ++

Compass Soup es como una máquina de Turing con una cinta infinita de 2 dimensiones. El problema principal es que la memoria de instrucciones y la memoria de datos están en el mismo espacio, y la salida del programa es todo el contenido de ese espacio.

Cómo funciona

Un programa es un bloque de texto bidimensional. El espacio del programa comienza con todo el código fuente colocado con el primer carácter en (0,0). El resto del espacio del programa es infinito y se inicializa con caracteres nulos (ASCII 0).

Hay dos punteros que pueden moverse por el espacio del programa:

• El puntero de ejecución tiene una ubicación y una dirección (norte, sur, este u oeste). Cada tic, la instrucción bajo el puntero de ejecución se ejecuta, luego el puntero de ejecución se mueve en su dirección actual. El puntero de ejecución comienza a moverse hacia el este (x positivo), en la ubicación del !personaje o en (0,0) si eso no existe.
• El puntero de datos solo tiene una ubicación. Se mueve con las instrucciones x, X, y, y Y. Comienza en la ubicación del @personaje o en (0,0) si eso no existe.

Entrada

El contenido de stdin se imprime en el espacio del programa comenzando en la ubicación del >carácter, o en (0,0) si eso no existe.

Salida

El programa termina cuando el puntero de ejecución se ejecuta irremediablemente fuera de los límites. La salida es el contenido completo del espacio del programa en ese momento. Se envía a stdout y 'result.txt'.

Instrucciones

• n - redirige el puntero de ejecución Norte (y negativo)
• e - redirige el puntero de ejecución Este (x positivo)
• s - redirige el puntero de ejecución Sur (y positivo)
• w - redirige el puntero de ejecución Oeste (x negativo)
• y - mueve el puntero de datos al Norte (y negativo)
• X - mueve el puntero de datos al Este (x positivo)
• Y - mueve el puntero de datos al sur (y positivo)
• x - mueve el puntero de datos al oeste (x negativo)
• p- escribe el siguiente carácter encontrado por el puntero de ejecución en el puntero de datos. Ese personaje no se ejecuta como una instrucción.
• j- comprueba el siguiente carácter encontrado por el puntero de ejecución contra el carácter debajo del puntero de datos. Ese personaje no se ejecuta como una instrucción. Si son iguales, el puntero de ejecución salta sobre el siguiente carácter.
• c - escribe el carácter nulo en el puntero de datos.
• * - punto de interrupción: solo hace que el intérprete se rompa.

El puntero de ejecución ignora todos los demás caracteres.

Interprete

El intérprete toma el archivo fuente como argumento y entrada en stdin. Tiene un depurador steppable, que puede invocar con una instrucción de punto de interrupción en el código ( *). Cuando está roto, el puntero de ejecución se muestra como ASCII 178 (bloque sombreado más oscuro) y el puntero de datos se muestra como ASCII 177 (bloque sombreado más claro).

#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();
}