O tópico do desafio dos ladrões está aqui .

Desafio da polícia: crie uma linguagem de programação que pareça inutilizável para a programação, mas que admita a computação (ou pelo menos a conclusão da tarefa) por meio de algum mecanismo não óbvio.

Você deve criar uma linguagem de programação simples que leia o código de um arquivo de entrada e faça ... alguma coisa. Você deve preparar um programa de solução que encontre o terceiro maior número na entrada quando executado no seu intérprete. Você precisa dificultar o máximo possível para que os ladrões encontrem um programa de solução. Observe que os ladrões podem postar qualquer solução que realize a tarefa, não apenas a que você tinha em mente.

Este é um concurso de popularidade. O objetivo da polícia é obter o maior número possível de votos enquanto sobrevive 8 dias após a publicação do intérprete sem ser quebrado. Para esse fim, as seguintes práticas devem ajudar:

• Explicando com precisão a semântica do seu idioma
• Escrevendo código legível

As seguintes táticas são fortemente desencorajadas:

• Usando criptografia, hashes ou outros métodos criptográficos. Se você vir um idioma que emprega criptografia RSA ou se recusa a executar um programa, a menos que seu hash SHA-3 seja igual a 0x1936206392306, não hesite em votar novamente.

Desafio dos assaltantes: escreva um programa que encontre o terceiro maior número inteiro na entrada quando executado no intérprete da polícia.

Este é relativamente direto. Para obter uma resposta de policial, você deve criar um programa que conclua a tarefa quando executado em seu intérprete. Quando você quebrar uma resposta, poste um comentário dizendo "Rachado" na resposta do policial com link para sua postagem. Quem quebrar mais policiais ganha o fio dos assaltantes.

Regras de E / S

• Os intérpretes devem colocar um nome de arquivo na linha de comando do programa e usar entrada e saída padrão ao executá-lo.
• A entrada será dada em unário e consistirá apenas dos caracteres 0e 1(48 e 49 em ASCII). Um número N é codificado como N 1s seguido por a 0. Há um adicional 0antes do final do arquivo. Exemplo: Para a sequência (3, 3, 1, 14), a entrada é 11101110101111111111111100.
• A entrada é garantida para ter pelo menos 3 números. Todos os números são números inteiros positivos.
• A saída será julgada pelo número de 1s impressos antes que o programa pare. Outros caracteres são ignorados.

Nos exemplos a seguir, a primeira linha é a entrada no formato decimal; o segundo é a entrada real do programa; o terceiro é uma amostra de saída.

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>

Regras chatas para respostas policiais:

• Para evitar a segurança através da obscuridade, o intérprete deve ser escrito em um idioma entre os 100 principais deste índice TIOBE e ter um compilador / intérprete disponível gratuitamente.
• O intérprete não deve interpretar um idioma que foi publicado antes deste desafio.
• O intérprete deve caber na sua postagem e não ser hospedado externamente.
• O intérprete deve ser determinístico
• O intérprete deve ser portátil e seguir o padrão de seu próprio idioma; não use comportamento indefinido ou bugs
• Se o programa de solução for muito longo para caber na resposta, você deverá postar um programa que o gere.
• O programa de solução deve consistir apenas em ASCII e novas linhas imprimíveis.
• Você deve executar seu programa de solução em menos de 1 hora em seu próprio computador para cada uma das entradas de exemplo acima.
• O programa deve funcionar com números inteiros menores que 10 ⁶ e qualquer número inteiro com menos de 10 ⁶ (não necessariamente em menos de uma hora), desde que o comprimento total da entrada seja menor que 10 ⁹ .
• Para se tornar seguro, um policial deve editar o programa de solução na resposta após oito dias.

Pontuação

O policial que se torna seguro com a pontuação mais alta e uma pontuação positiva, ganha essa pergunta.

Changeling (seguro)

ShapeScript

O ShapeScript é uma linguagem de programação que ocorre naturalmente. Os shifters de forma (ou Changelings , como preferem ser chamados) podem se transformar em um conjunto de instruções que lhes permite processar dados.

O ShapeScript é uma linguagem baseada em pilha com uma sintaxe relativamente simples. Não é de surpreender que a maioria dos seus built-ins lide com a alteração do formato das cordas. É interpretado, caractere por caractere, da seguinte maneira:

• 'e "comece uma string literal.

  Até que a citação correspondente seja encontrada no código-fonte, todos os caracteres entre essas aspas correspondentes são coletados em uma sequência, que é empurrada na pilha.

• 0para 9empurrar os números inteiros de 0 a 9 na pilha. Observe que 10empurra dois números inteiros.

• ! aparece uma string da pilha e tenta avaliá-la como ShapeScript.

• ? exibe um número inteiro da pilha e empurra uma cópia do item da pilha nesse índice.

  O índice 0 corresponde ao item da pilha mais acima (LIFO) e o índice -1 ao mais abaixo.

• _ aparece um iterável da pilha e aumenta seu comprimento.

• @ aparece dois itens da pilha e os empurra em ordem inversa.

• $aparece duas cordas da pilha e divide a mais baixa nas ocorrências da mais alta. A lista resultante é enviada em retorno.

• &aparece uma sequência (superior) e uma iterável da pilha e junta-se à iterável, usando a sequência como separador. A sequência resultante é pressionada em troca.

• Se o ShapeScript for usado em nosso planeta, já que os pythons são os parentes mais próximos do Changelings na Terra, todos os outros caracteres c exibem dois itens x e y (acima) da pilha e tentam avaliar o código Python x c y.

  Por exemplo, a sequência de caracteres 23+seria avaliada 2+3, enquanto a sequência de caracteres "one"3*seria avaliada 'one'*3e a sequência de caracteres 1''Aseria avaliada 1A''.

  No último caso, como o resultado não é válido em Python, o Changeling reclamaria que sua forma atual não é proposital (erro de sintaxe), pois não é válido para o ShapeScript.

Antes de executar o código, o intérprete colocará toda a entrada do usuário na forma de uma sequência na pilha. Após executar o código fonte, o intérprete imprimirá todos os itens na pilha. Se alguma parte do meio falhar, o Changeling reclamará que sua forma atual é inadequada (erro de execução).

Mudança de forma

Em seu estado natural, os Changelings não assumem a forma do ShapeScript. No entanto, alguns deles podem se transformar em um código-fonte em potencial (o que não é necessariamente útil ou mesmo sintaticamente válido).

Todos os Changelings elegíveis têm a seguinte forma natural:

• Todas as linhas devem ter o mesmo número de caracteres.

• Todas as linhas devem consistir em caracteres ASCII imprimíveis, seguidos por um único avanço de linha.

• O número de linhas deve corresponder ao número de caracteres imprimíveis por linha.

Por exemplo, a sequência de bytes ab\ncd\né um Changeling elegível.

Na tentativa de mudar para o ShapeScript, o Changeling passa pela seguinte transformação:

• Inicialmente, não há código fonte.

• Para cada linha, acontece o seguinte:

  • O acumulador do Changeling está definido como zero.

  • Para cada caractere c da linha (incluindo o avanço de linha à direita), o ponto de código de c é XORed com o acumulador dividido por 2, e o caractere Unicode que corresponde ao ponto de código resultante é anexado ao código-fonte.

    Depois, a diferença entre o ponto de código de c e o ponto de código de um espaço (32) é adicionada ao acumulador.

Se alguma das partes acima falhar, o Changeling reclamará que sua forma atual é desagradável.

Depois que todas as linhas foram processadas, a transformação do Changeling em (possivelmente válido) ShapeScript está concluída e o código resultante é executado.

Solução (ShapeScript)

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

O ShapeScript acabou sendo bastante utilizável; ele pode até executar testes de primalidade ( prova ) e, portanto, satisfaz nossa definição de linguagem de programação.

Publiquei novamente o ShapeScript no GitHub , com uma sintaxe ligeiramente modificada e uma E / S melhor.

O código faz o seguinte:

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

Solução (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=....................
""# !......................

Como todos os programas Changeling, esse código possui um avanço de linha à direita.

O ShapeScript cometerá um erro imediato em qualquer caractere que não entenda, mas podemos enviar seqüências de caracteres arbitrárias como preenchimentos e colocá-las mais tarde. Isso nos permite colocar apenas uma pequena quantidade de código em cada linha (no início, onde o acumulador é pequeno), seguido por uma abertura ". Se começarmos a próxima linha com "#, fechamos e pop a string sem afetar o código real.

Além disso, temos que superar três obstáculos menores:

• A cadeia longa no código ShapeScript é um único token e não poderemos ajustá-lo em uma linha.

  Vamos empurrar esta string em pedaços ( '@', '1?', etc.), o que vamos concatenar mais tarde.

• O ponto de código de _é bastante alto e o envio '_'será problemático.

  No entanto, poderemos avançar '_@'sem esforço, seguidos por outro '@'para desfazer a troca.

O código ShapeScript que nosso Changeling gerará se parece com este ¹ :

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

Encontrei o código Changeling executando o código ShapeScript acima através deste conversor . ²

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 linha é preenchida com lixo aleatório para a quantidade de linhas e os feeds de linha não estão realmente presentes.}
² _{Os números na parte inferior indicam o ponto mais baixo e mais alto do código Changeling, que deve permanecer entre 32 e 126.}

Aleatório (escrito em C ++), Rachado! por Martin

Editar Martin quebrou. Para ver a solução dele, clique no link. Minha solução também foi adicionada.

Editar Comando fixo print-dpara poder lidar com registros e pilhas. Como este é um comando de depuração que não é permitido em uma solução, isso não deve afetar ninguém que esteja usando a versão anterior do intérprete

Ainda sou novo nisso; se houver algo errado com minha resposta ou meu intérprete, entre em contato. Por favor, peça esclarecimentos se algo não estiver claro.

Não imagino que isso seja terrivelmente difícil, mas espero que isso traga algum tipo de desafio. O que torna a reprodução aleatória bastante inutilizável é que ela será impressa apenas quando as coisas estiverem no seu devido lugar.

-> Noções básicas:

Existem 24 pilhas, como as chamamos stack1, ... stack24. Essas pilhas vivem em uma lista. No início de qualquer programa, essas pilhas têm zero empurrado e começam no seu devido lugar, ou seja, empilham i na i - ésima posição na lista (Observe que indexaremos a partir de 1, diferentemente do C ++). Durante o curso de um programa, a ordem das pilhas na lista mudará. Isso é importante por razões que serão explicadas quando eu discutir os comandos.

Existem 5 registros disponíveis para uso. Eles são nomeados Alberto, Gertrude, Hans, Leopold, ShabbySam. Cada um deles é definido como zero no início de um programa.

Portanto, no início de qualquer programa, existem 24 pilhas, cada uma com seu número correspondente ao seu índice na lista de pilhas. Cada pilha tem exatamente um zero no topo. Cada um dos cinco registros é inicializado em zero.

-> Comandos e sintaxe :

Existem 13 comandos (comando de depuração +1) disponíveis no Shuffle. Eles são os seguintes

• cinpusheste comando não aceita argumentos. Ele espera pela entrada da linha de comando da maneira descrita na pergunta (outra entrada levará a resultados não especificados / indefinidos). Em seguida, divide a sequência de entrada em números inteiros, por exemplo 101011100- -> 1,1,3. Para cada entrada recebida, é feito o seguinte: (1) permite a lista de pilhas com base no valor. Seja o valor inteiro em questão chamado a . Se a for menor que 10, permutará u . Se a estiver entre 9 e 30 (não inclusivo), ele fará a permutação d . Caso contrário, ele faz permutação r . (2) Em seguida, empurra umna pilha que é a primeira da lista. Note que não estou falando sério stack1(embora possa ser o stack1primeiro da lista). As permutações são definidas abaixo. Como cinpushé a única maneira de obter a entrada do usuário , ela deve aparecer em qualquer solução.

• mov value registerO movcomando é basicamente atribuição de variáveis. Ele atribui valuea register. valuepode assumir várias formas: pode ser (1) um inteiro, por exemplo 47 (2) o nome de um registro diferente, por exemplo Hans (3) o índice de uma pilha seguido por 's', por exemplo 4s. Observe que este é o índice da lista, não o número da pilha. Como tal, o número não deve exceder 24.

  Alguns movexemplos:

  mov 4s Hans 
  mov Hans ShabbySam
  mov 9999 Gertrude
  

• movfs index registerIsso significa 'mover da pilha'. É semelhante ao movcomando. Existe para que você possa acessar uma pilha indexada por um registro. Por exemplo, se você definiu Hans como 4 ( mov 4 Hans) anteriormente, você pode movfs Hans Gertrudedefinir Gertrude como o topo da pilha 4. Esse tipo de comportamento não pode ser acessado simplesmente usando mov.

• inc register aumenta o valor do registro em 1.
• dec register diminui o valor do registro em 1.
• compg value value registerIsso significa 'comparar maior'. Ele define o registro igual ao maior dos dois valores. valuepode ser um número inteiro, um registro ou um índice de pilha seguido por 's', como acima.
• compl value value register 'compare menor' o mesmo que acima, exceto que assume o valor menor.
• gte value1 value2 registerVerifica se, em value1 >= value2seguida, coloca o valor booleano (como 1 ou 0) register.
• POP!! indexaparece na parte superior da pilha indexada indexna lista de pilhas.
• jmp labelpula incondicionalmente para o rótulo label. É um bom momento para conversar sobre rótulos. Um rótulo é uma palavra seguida por ':'. O intérprete analisa previamente os rótulos, para que você possa avançar para os rótulos e também para trás.
• jz value labelpula para labelse valuefor zero.

• jnz value labelpula para labelse valuefor diferente de zero.

  Exemplos de etiquetas e saltos:

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

• "shuffle" permutationAqui está o comando de reprodução aleatória. Isso permite que você permita a lista de pilhas. Há três permutações válidos que podem ser usados como argumentos, l, f, e b.

• print registerIsso verifica se todas as pilhas estão em suas posições iniciais, ou seja, a pilha i está no índice i na lista de pilhas. Se for esse o caso, ele imprime o valor registerem unário. Caso contrário, ele imprime um erro desagradável. Como você pode ver, para produzir qualquer coisa, todas as pilhas devem estar nos lugares corretos.
• done!isso diz ao programa para sair sem erro. Se o programa terminar sem done!, ele imprimirá no console o número na parte superior de cada pilha, seguido pelo número da pilha. A ordem em que as pilhas são impressas é a ordem em que aparecem na lista de pilhas. Se uma pilha estiver vazia, será omitida. Esse comportamento é para fins de depuração e não pode ser usado em uma solução.
• print-d valueisso imprime o valor da pilha, registrador ou número inteiro fornecido (para acessar a pilha i , passe iscomo argumento, conforme explicado acima). Essa é uma ferramenta de depuração e não faz parte do idioma, portanto, não é permitida em uma solução.

-> Aqui está o código do intérprete

Toda a análise acontece na função principal. É aqui que você encontrará a análise de 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;
}

-> Permutações As permutações permitem os elementos da lista de pilhas da seguinte maneira:

Onde significa que

(Eles também aparecem no código do intérprete. Se houver discrepância, o intérprete está correto.)

-> Exemplo Simples

Esses dois programas simples imprimem os números de 24 para 1 (em unário) sem espaço em branco.

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

ou

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

Eles são o mesmo programa.

Explicação e Solução:

Martin tem uma boa explicação em sua resposta também.

Como Martin descobriu, essa linguagem foi inspirada no cubo de bolso (também conhecido como cubo de Rubik 2x2). As 24 pilhas são como os 24 quadrados individuais no cubo. As permutações são os movimentos básicos permitidos: cima, baixo, direita, esquerda, frente, trás.

A principal luta aqui é que, quando os valores são pressionados, apenas três movimentos são usados: para cima, para baixo e para a direita. No entanto, você não tem acesso a esses movimentos ao "embaralhar" as pilhas. Você tem apenas os outros três movimentos.

Como se vê, os dois conjuntos de três jogadas abrangem todo o grupo (ou seja, são geradores), então o problema é solucionável. Isso significa que você pode realmente resolver qualquer cubo 2x2 de Rubik usando apenas 3 dos movimentos.

Tudo o que resta fazer é descobrir como desfazer os movimentos para cima, para baixo e para a direita usando os outros três. Para esse fim, empreguei um sistema de álgebra computacional chamado GAP .

Depois de desfazer as permutações, encontrar o terceiro maior número é 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 & Chuck , Rachado por paper_box

Há algum tempo, fico intrigado com a idéia de uma linguagem de programação em que dois programas interagem entre si (provavelmente inspirados no ROCB ). Esse desafio foi um bom incentivo para finalmente enfrentar esse conceito enquanto tentava manter o idioma o mínimo possível. Os objetivos do projeto eram tornar a linguagem Turing completa, enquanto cada uma de suas partes individualmente não era Turing completa. Além disso, mesmo os dois juntos não devem estar completos com Turing sem fazer uso da manipulação do código-fonte. Eu acho que eu já conseguiu com isso, mas eu não provaram nenhuma dessas coisas ainda formalmente. Então, sem mais delongas, apresento a você ...

Os Protagonistas

Brian e Chuck são dois programas parecidos com o Brainfuck. Apenas um deles está sendo executado a qualquer momento, começando com Brian. O problema é que a fita de memória de Brian também é o código fonte de Chuck. E a fita de memória de Chuck também é o código fonte de Brian. Além disso, a cabeça de fita de Brian também é o indicador de instruções de Chuck e vice-versa. As fitas são semi-infinitas (ou seja, infinitas para a direita) e podem conter números inteiros de precisão arbitrária, inicializados em zero (a menos que especificado de outra forma pelo código-fonte).

Como o código-fonte também é uma fita de memória, os comandos são tecnicamente definidos por valores inteiros, mas correspondem a caracteres razoáveis. Existem os seguintes comandos:

• ,( 44): Leia um byte de STDIN na célula de memória atual. Apenas Brian pode fazer isso. Este comando é um no-op para Chuck.
• .( 46): Escreva a célula de memória atual, módulo 256, como um byte em STDOUT. Apenas Chuck pode fazer isso. Este comando é um no-op para Brian.
• +( 43): Incrementa a célula de memória atual.
• -( 45): Diminui a célula de memória atual.
• ?( 63): Se a célula de memória atual for zero, este é um modo não operacional. Caso contrário, passe o controle para o outro programa. A cabeça da fita no programa utilizado ?permanecerá no ?. O cabeçote de fita do outro programa moverá uma célula para a direita antes de executar o primeiro comando (para que a célula usada como teste não seja executada).
• <( 60): Mova a cabeça da fita uma célula para a esquerda. Isso não funciona se a cabeça da fita já estiver na extremidade esquerda da fita.
• >( 62): Mova a cabeça da fita uma célula para a direita.
• {( 123): Mova repetidamente a cabeça da fita para a esquerda até que a célula atual seja zero ou a extremidade esquerda da fita seja atingida.
• }( 125): Mova repetidamente a cabeça da fita para a direita até que a célula atual seja zero.

O programa termina quando o ponteiro de instruções do programa ativo atinge um ponto em que não há mais instruções à sua direita.

O Código Fonte

O arquivo de origem é processado da seguinte maneira:

• Se o arquivo contiver a string ```, ele será dividido em duas partes em torno da primeira ocorrência dessa string. Todo o espaço em branco à esquerda e à direita é removido e a primeira parte é usada como código-fonte para Brian e a segunda parte para Chuck.
• Se o arquivo não contiver essa sequência, a primeira linha do arquivo será usada como fonte para Brian e a segunda parte para Chuck (além da nova linha delimitadora, nenhum espaço em branco será removido).
• Todas as ocorrências de _ambos os programas são substituídas por bytes NULL.
• As duas fitas de memória são inicializadas com os códigos de caracteres correspondentes à sequência resultante.

Como exemplo, o seguinte arquivo de origem

  abc
```
0_1
23

Produziria as seguintes fitas iniciais:

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

O intérprete

O intérprete está escrito em Ruby. São necessários dois sinalizadores de linha de comando que não devem ser usados ​​por nenhuma solução (pois eles não fazem parte da especificação de idioma real):

• -d: Com esse sinalizador, Brian e Chuck entendem mais dois comandos. !imprimirá uma representação de seqüência de caracteres de ambas as fitas de memória, sendo o programa ativo listado primeiro (a ^marcará as cabeças de fita atuais).@também fará isso, mas, em seguida, encerre o programa imediatamente. Como sou preguiçoso, nenhum deles funcionará se for o último comando do programa; portanto, se você quiser usá-los lá, repita-os ou escreva um não-operacional depois deles.
• -D: Este é o modo de depuração detalhado. Ele imprimirá as mesmas informações de depuração que !após cada tick. @também funciona neste modo.

Aqui está o 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)

Aqui está minha própria solução (manuscrita) para o 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 é executável como está, porque todas as anotações usam no-ops e são ignoradas por {e }.

A ideia básica é:

1. Adicione um novo elemento zero à lista (no final da fita de Chuck) e aumente o comprimento da lista em 1.
2. Enquanto estamos lendo 1s, aumente esse elemento.

3. Ao ler um 0, faça uma limpeza. Se o número inteiro resultante for maior que zero, volte para 1.

   Agora temos uma lista dos números de entrada no final da fita de Chuck e sabemos o tamanho da lista.

4. Subtraia 2 do comprimento da lista (para que as etapas a seguir ignorem os dois maiores elementos), chame isso N.

5. Enquanto N > 0, incremente um total em execução e, em seguida, diminua todos os elementos da lista. Sempre que um elemento da lista atingir zero, diminua N.

   No final, o total atual conterá o terceiro maior número na entrada M,.

6. Escreva Mcópias de. para o final da fita de Chuck.

7. No Chuck, procure um 1na fita de Brian e execute os gerados .no final.

Depois de terminar isso, percebi que poderia simplificá-lo bastante em alguns lugares. Por exemplo, em vez de acompanhar esse contador e escrevê-los .na fita de Chuck, eu podia imprimir um 1imediatamente, cada vez antes de diminuir todos os elementos da lista. No entanto, fazer alterações nesse código é bastante trabalhoso, porque propaga outras alterações por todo o lugar, então não me incomodei em fazer a alteração.

O interessante é como acompanhar a lista e como iterá-la. Você não pode simplesmente armazenar os números consecutivamente na fita de Chuck, porque, se quiser verificar uma condição em um dos elementos da lista, corre o risco de executar o restante da lista, que pode conter código válido. Você também não sabe quanto tempo a lista levará, portanto, não pode apenas reservar algum espaço na frente do código de Chuck.

O próximo problema é que precisamos deixar a lista diminuir Nenquanto a processamos e precisamos voltar ao mesmo lugar em que estávamos antes. Mas {e }apenas pularia a lista inteira.

Então, precisamos escrever algum código dinamicamente no Chuck. De fato, cada elemento da lista item o formato:

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

1é um marcador que podemos definir como zero para indicar onde deixamos de processar a lista. Seu objetivo é capturar {ou }que apenas repassará o código e o i. Também usamos esse valor para verificar se estamos no final da lista durante o processamento; portanto, enquanto não estivermos, isso será 1e o condicional ?mudará o controle para Chuck. Code Aé usado para lidar com essa situação e mover o IP no Brian de acordo.

Agora, quando diminuímos i, precisamos verificar se ijá é zero. Enquanto não estiver, ?alternará novamente o controle, então Code Bexiste para lidar com isso.

HPR, escrito em Python 3 ( Cracked by TheNumberOne )

HPR (o nome não significa nada) é um idioma para processar listas de números inteiros. Ele foi projetado para ser minimalista , extremamente limitado e livre de restrições "artificiais" . A programação no HPR é dolorosa, não porque você precise resolver um quebra-cabeça para impedir que o intérprete grite com você, mas porque é difícil fazer um programa fazer algo útil. Não sei se o HPR é capaz de algo substancialmente mais interessante do que computar o terceiro maior elemento de uma lista.

Especificação de idioma

Um programa HPR é executado em um ambiente , que é um conjunto não ordenado e livre de duplicados de números inteiros não negativos e listas de números inteiros não negativos. Inicialmente, o ambiente contém apenas a lista de entrada (o intérprete a analisa para você). Existem três comandos e dois operadores de "fluxo de controle" que modificam o ambiente:

• *remove o primeiro elemento de cada lista não vazia no ambiente e coloca-o no ambiente. Listas vazias não são afetadas. Por exemplo, ele transforma

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

• -diminui todos os números no ambiente e remove elementos negativos. Por exemplo, ele transforma

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

• $gira todas as listas do ambiente um passo para a esquerda. Por exemplo, ele transforma

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

• !(A)(B), onde Ae Bsão programas, é basicamente um whileloop. Ele executa a "ação" Aaté que o "teste" Bresulte em um ambiente vazio. Isso pode produzir um loop infinito.
• #(A)(B), onde Ae quais Bsão os programas, se aplica Ae Bao ambiente atual e leva a diferença simétrica dos resultados.

Os comandos são executados da esquerda para a direita. No final, o tamanho do ambiente é impresso em unário.

O intérprete

Este intérprete apresenta o comando debug ?, que imprime o ambiente sem modificá-lo. Não deve aparecer em nenhuma solução para a tarefa. Quaisquer caracteres exceto *-$!#()?são simplesmente ignorados, para que você possa escrever comentários diretamente no código. Por fim, o intérprete reconhece o idioma !(A)(#(A)())como "executar Aaté que o resultado não seja mais alterado" e o otimiza para obter velocidade extra (eu precisava que minha solução fosse concluída em menos de uma hora no último caso de teste).

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

Minha solução

Minha solução de referência tem 484 bytes, muito curta em comparação com o programa de 3271 bytes do TheNumberOne. Isso provavelmente ocorre devido ao sofisticado e impressionante sistema de macro que TheNumberOne desenvolveu para programação em HPR. A idéia principal em ambos os nossos programas é semelhante:

1. Descubra como produzir o elemento máximo de uma lista.
2. Para remover o elemento máximo, gire a lista até o primeiro elemento igual ao máximo e, em seguida, pop-lo.
3. Remova o máximo duas vezes e imprima o novo elemento máximo.

No entanto, até onde eu sei, os detalhes exatos da implementação são bem diferentes. Aqui está a minha solução:

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

E aqui está o programa Python comentado que o produz (nada sofisticado aqui, apenas manipulação básica de strings para se livrar de toda a repetição):

# 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 o dragão, você precisa de uma espada) - Rachado por Martin Büttner

EDIT: Adicionei minha solução e explicação abaixo da postagem principal.

fundo

Nesta linguagem, você assume o controle de um valente guerreiro que foi incumbido de matar um terrível dragão. O dragão vive em um labirinto subterrâneo, cheio de perigos e perigos, e até agora, ninguém foi capaz de mapear e sobreviver. Isso significa que você deve navegar até o dragão na escuridão total, com nada além de intuição e coragem para guiá-lo.

...

Bem, não exatamente. Você trouxe um suprimento quase ilimitado de lacaios descartáveis ​​com você, e eles estão dispostos a ir além de você para descobrir o caminho seguro. Infelizmente, eles são todos grossos como duas tábuas curtas e só farão exatamente o que você manda. Cabe a você criar um método inteligente de garantir que seus lacaios descubram o caminho correto.

Mais alguns detalhes

O covil do dragão assume a forma de uma grade de 10x10. Entre certos pontos adjacentes na grade, há uma passagem estreita; entre outros, há um abismo profundo e uma morte certa. Um layout de exemplo para uma grade 4x4 pode ser o seguinte:

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

Você sabe que sempre existe uma maneira de ir de um ponto a outro, mas nada mais foi revelado a você.

Para derrotar o dragão com sucesso, você primeiro precisa coletar alguns itens que você poderá combinar para criar uma lâmina mágica de matar dragões. Convenientemente, todas as peças desta arma foram espalhadas pelo covil do dragão. Você simplesmente tem que colecioná-los.

A diferença é que cada peça da arma foi presa. Toda vez que uma é coletada, o layout das passarelas muda. Caminhos anteriormente seguros agora podem levar à morte certa e vice-versa.

Comandos

Existem apenas 5 comandos válidos.

• < - Dê um passo para a esquerda

• > - Dê um passo à direita

• ^ - Dê um passo para cima

• v - Dê um passo para baixo

• c- Colete todos os itens que estiverem na sua posição atual. Se houver itens presentes, o layout do covil muda. Com as posições numeradas nas linhas como acima, tome o módulo 10. da posição. Existem 10 layouts codificados no interpretador e o layout muda para o correspondente. Por exemplo, se você estiver na posição 13, o layout será alterado paralayouts[3]

Os layouts que aparecem no interpéter foram codificados para números inteiros da seguinte maneira:

• O layout vazio é codificado para zero.

• Para cada aresta no layout, xseja a menor das duas posições em que ela se une.

  • Se a etapa for horizontal, adicione 2^(2*x)à codificação (que é o poder, não o XOR)

  • Se a etapa for vertical, adicione 2^(2*x + 1)à codificação.

Fluxo de execução

O intérprete é executado com o nome de um arquivo de origem como argumento da linha de comando.

Quando o intérprete é executado, ele solicita que o usuário forneça uma missão. Essa entrada deve estar na forma descrita na pergunta e determina os locais no esconderijo dos componentes da arma. Especificamente, cada número inteiro de entrada é obtido no módulo 100 e colocado no local correspondente no covil.

Cada programa de origem consiste em várias linhas, cada linha consiste em alguma sequência dos 5 caracteres válidos acima. Essas linhas representam seus lacaios. Você, o guerreiro, acompanha uma sequência de ações conhecidas por serem seguras. Inicialmente, você não sabe nada sobre o covil, então essa sequência está vazia. Tomando cada lacaio por sua vez, é realizado o seguinte, começando na posição 0:

• O subordinado é instruído a executar todas as ações conhecidas como seguras, seguidas pelas ações em sua própria linha de código.

  • Se o lacaio morrer a qualquer momento, você será notificado e o covil será redefinido para sua configuração inicial. Todos os itens são substituídos e as passarelas retornam às suas posições iniciais.

  • Se, em vez disso, o lacaio sobreviver, então você o vaporiza de qualquer maneira - afinal, é apenas um lacaio. Como antes, isso aciona a redefinição do covil ao seu estado inicial, mas desta vez, você anexa as ações da linha de código do lacaio à sequência de ações conhecidas como seguras.

Depois que todos os lacaios estiverem exaustos, você, o guerreiro, executa todas as ações que são conhecidas por serem seguras, começando novamente na posição 0. Há dois resultados possíveis:

• Você coleciona todas as peças da arma - nesse caso, você mata com sucesso o dragão e uma emocionante mensagem de vitória é emitida. Essa mensagem de vitória conterá, entre outros caracteres, um n, onde né o terceiro número mais alto fornecido como entrada.

• Você falhou em coletar algumas das peças da arma - nesse caso, o dragão continua vivo e você falhou em sua missão.

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

Boa sorte, valente guerreiro.

Minha solução e explicação

Aqui está um script Python que gera código fonte para resolver o problema. Por interesse, o código fonte final de Martin é cerca de 5 vezes menor que o código produzido pelo meu script. Por outro lado, meu script para gerar o código é cerca de 15 vezes menor que o 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')

Estrutura básica

Isso gera 990 linhas de código fonte, que vêm em grupos de 10. As 10 primeiras linhas contêm instruções que tentam mover um lacaio de uma posição 0para 1outra e, em seguida, coletam um item - um conjunto para cada layout possível. As próximas 10 linhas contêm instruções que tentam mover um lacaio de uma posição 1para 2outra e coletam um item. E assim por diante ... Esses caminhos são calculados com opath função no script - apenas faz uma pesquisa simples e profunda.

Se pudermos garantir que, em cada grupo de 10, precisamente um lacaio seja bem-sucedido, teremos resolvido o problema.

O problema com a abordagem

Pode não ser sempre o caso de exatamente um lacaio do grupo dos 10 ter sucesso - por exemplo, um lacaio projetado para ir de uma posição 0para 1outra pode acidentalmente ter sucesso em mudar de posição 1em posição 2(devido a semelhanças nos layouts), e que um erro de cálculo será propagado, potencialmente causando falhas.

Como corrigi-lo

A correção que eu usei foi a seguinte:

Para cada lacaio que está tentando passar da posição npara n+1, primeiro faça-o andar de posição nem posição 0(no canto superior esquerdo) e recuar novamente, depois de posição nem posição 99(no canto inferior direito) e recuar. Essas instruções só podem ser executadas com segurança a partir da posição n- qualquer outra posição inicial e o lacaio sairá da borda.

Portanto, essas instruções extras impedem que lacaios acidentalmente cheguem a algum lugar que não deveriam, e isso garante que exatamente um lacaio de cada grupo de 10 seja bem-sucedido. Observe que não é necessariamente o lacaio que você espera que seja - pode ser que o lacaio que acredita que ele está no layout 0 seja bem-sucedido, mesmo quando estamos realmente no layout 7 - mas, de qualquer forma, o fato de termos A posição agora alterada significa que todos os outros subordinados do grupo necessariamente morrerão. Essas etapas extras são calculadas pela assert_atfunção e a safe_pathfunção retorna um caminho que é a concatenação dessas etapas extras com o caminho comum.

Firetype, Rachado por Martin Büttner

Uma mistura muito estranha de BF e CJam. E quem sabe o que mais! Tenho certeza de que será fácil, mas foi divertido de qualquer maneira. Para sua informação, o nome está se referindo a Vermillion Fire do Final Fantasy Type-0 .

NOTA : Por favor, perdoe-me por quaisquer ambiguidades nesta descrição. Eu não sou o melhor escritor ...: O

Martin rachou isso muito rapidamente! Este foi o meu programa original para resolver o problema:

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











`
~
+
|
%

_
=

\
@
-
-
!
<
>
>
>

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

Sintaxe

Um script Firetype é basicamente uma lista de linhas. O primeiro caractere de cada linha é o comando a ser executado. Linhas vazias são basicamente NOPs.

Semântica

Você tem uma matriz de números inteiros e um ponteiro (pense em BF). Você pode mover os elementos para a esquerda e direita ou "empurrar" na matriz.

Empurrando

Quando você "pressiona" um elemento e está no final da matriz, um elemento extra será anexado ao final. Se você não estiver no final, o próximo elemento será substituído. Independentemente, o ponteiro será sempre incrementado.

Comandos

_

Empurre um zero na matriz.

+

Incremente o elemento no ponteiro atual.

-

Reduza o elemento no ponteiro atual.

*

Duplique o elemento no ponteiro atual.

/

Divida pela metade o elemento no ponteiro atual.

%

Pegue o elemento no ponteiro atual e pule para frente muitas linhas e mova o ponteiro para a esquerda. Se o valor for negativo, pule para trás.

=

Pegue o elemento no ponteiro atual e pule para a linha + 1. Por exemplo, se o elemento atual estiver 0, ele irá pular para a linha 1. Isso também move o ponteiro para a esquerda.

,

Leia um caractere da entrada padrão e empurre seu valor ASCII.

^

Pegue o elemento no ponteiro atual, interprete-o como o valor ASCII de um caractere e converta-o em um número inteiro. Por exemplo, se o valor atual for 49 (o valor ASCII de 1), o elemento no ponteiro atual será definido como o número inteiro 1.

.

Escreva o número atual na tela.

!

Pegue o elemento no ponteiro atual e repita a próxima linha várias vezes. Também move o ponteiro para a esquerda.

<

Mova o ponteiro para a esquerda. Se você já está no começo, um erro é gerado.

>

Mova o ponteiro para a direita. Se você já está no final, um erro é gerado.

~

Se o elemento atual for diferente de zero, substitua-o por 0; caso contrário, substitua-o por 1.

|

Esquadre o elemento atual.

@

Defina o elemento atual para o comprimento da matriz.

`

Duplique o elemento atual.

\

Classifique os elementos no e antes do ponteiro.

#

Negue o elemento atual.

O intérprete

Também disponível no 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)

É baack ...

... e espero que definitivamente mais à prova de brechas.

Eu já li o Acc! spec. Como está o Acc !! diferente?

Em Acc !!, variáveis ​​de loop ficam fora do escopo quando o loop sai. Você só pode usá-los dentro do loop. Lá fora, você receberá um erro "o nome não está definido". Fora essa alteração, os idiomas são idênticos.

Afirmações

Os comandos são analisados ​​linha por linha. Existem três tipos de comando:

1. Count <var> while <cond>

Conta <var>desde 0, desde que <cond>seja diferente de zero, equivalente a C ++ for(int <var>=0; <cond>; <var>++). O contador de loop pode ser qualquer letra minúscula. A condição pode ser qualquer expressão, não necessariamente envolvendo a variável de loop. O loop é interrompido quando o valor da condição se torna 0.

Os loops requerem chaves estilo K&R (em particular, a variante Stroustrup ):

Count i while i-5 {
 ...
}

Como mencionado acima, as variáveis ​​de loop estão disponíveis apenas dentro de seus loops ; tentar referenciá-los posteriormente causa um erro.

2. Write <charcode>

Gera um único caractere com o valor ASCII / Unicode fornecido para stdout. O código pode ser qualquer expressão.

3. Expressão

Qualquer expressão autônoma é avaliada e atribuída de volta ao acumulador (acessível como _). Assim, por exemplo, 3é uma declaração que define o acumulador como 3; _ + 1incrementa o acumulador; e _ * Nlê um caractere e multiplica o acumulador por seu código.

Nota: o acumulador é a única variável que pode ser atribuída diretamente; variáveis ​​de loop e Npode ser usado em cálculos, mas não modificado.

O acumulador é inicialmente 0.

Expressões

Uma expressão pode incluir literais inteiros, variáveis ​​de loop ( a-z), _para o acumulador e o valor especial N, que lê um caractere e avalia seu código de cada vez que é usado. Nota: isso significa que você só tem uma chance de ler cada personagem; da próxima vez que você usarN , estará lendo a próxima.

Os operadores são:

• +, Adição
• -subtração; negação unária
• *multiplicação
• /divisão inteira
• %módulo
• ^exponenciação

Parênteses podem ser usados ​​para reforçar a precedência das operações. Qualquer outro caractere em uma expressão é um erro de sintaxe.

Espaço em branco e comentários

Os espaços em branco à esquerda e à direita e as linhas vazias são ignorados. O espaço em branco nos cabeçalhos do loop deve ser exatamente como mostrado, com um único espaço entre o cabeçalho do loop e a chave de abertura também. O espaço em branco dentro das expressões é opcional.

# inicia um comentário de linha única.

Entrada / Saída

Acc !! espera uma única linha de caracteres como entrada. Cada caractere de entrada pode ser recuperado em seqüência e seu código processado usando N. Tentar ler além do último caractere da linha causa um erro. Um caractere pode ser emitido passando seu código para a Writeinstrução

Intérprete

O intérprete (escrito em Python 3) traduz Acc !! código no Python e execpronto.

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

Solução

A queda do Acc original ! eram variáveis ​​de loop que continuavam acessíveis fora de seus loops. Isso permitiu salvar cópias do acumulador, o que facilitou muito a solução.

Aqui, sem esse buraco de loop (desculpe), temos apenas o acumulador para armazenar coisas. Para resolver a tarefa, no entanto, precisamos armazenar quatro valores arbitrariamente grandes. ¹ A solução: intercalar seus bits e armazenar o número de combinação resultante no acumulador. Por exemplo, um valor de acumulador de 6437 armazenaria os seguintes dados (usando o bit de menor ordem como um sinalizador de bit único):

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 acessar qualquer bit de qualquer número dividindo o acumulador pela potência apropriada de 2, mod 2. Isso também permite configurar ou inverter bits individuais.

No nível da macro, o algoritmo faz um loop sobre os números unários na entrada. Ele lê um valor no número 0 e, em seguida, passa o algoritmo de classificação de bolhas para colocá-lo na posição correta em comparação com os outros três números. Por fim, descarta o valor que resta no número 0, pois é o menor dos quatro agora e nunca pode ser o terceiro maior. Quando o loop termina, o número 1 é o terceiro maior, então descartamos os outros e o produzimos.

A parte mais difícil (e a razão pela qual tive variáveis ​​de loop global na primeira encarnação) é comparar dois números para saber se é necessário trocá-los. Para comparar dois bits, podemos transformar uma tabela verdade em uma expressão matemática; meu avanço para Acc !! estava encontrando um algoritmo de comparação que procedia de bits de ordem baixa a alta, pois sem variáveis ​​globais não há como fazer um loop sobre os bits de um número da esquerda para a direita. O bit de ordem mais baixa do acumulador armazena um sinalizador que indica se os dois números devem ser trocados atualmente em consideração.

Eu suspeito que Acc !! é Turing completo, mas não tenho certeza se quero me dar ao trabalho de provar isso.

Aqui está a minha solução com comentários:

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

_{¹ De acordo com a especificação da pergunta, somente valores de até 1 milhão precisam ser suportados. Fico feliz que ninguém tenha aproveitado isso para uma solução mais fácil - embora não tenha muita certeza de como você faria as comparações.}

Picofuck (seguro)

Picofuck é semelhante ao Smallfuck . Opera em uma fita binária que não está ligada à direita, encadernada à esquerda. Possui os seguintes comandos:

• > mova o ponteiro para a direita

• <mova o ponteiro para a esquerda. Se o ponteiro cair da fita, o programa termina.

• * virar a ponta do ponteiro

• (se o bit no ponteiro estiver 0, pule para o próximo)

• )não faça nada - os parênteses em Picofuck são ifblocos, nãowhile loops.

• .escreva para stdout o bit no ponteiro como um ascii 0ou1 .

• ,leia de stdin até encontrarmos um 0ou1 e armazene-o no bit no ponteiro.

O código Picofuck é encerrado - uma vez que o final do programa é alcançado, ele continua desde o início.

Além disso, o Picofuck não permite parênteses aninhados. Os parênteses exibidos em um programa Picofuck devem alternar entre (e ), começando com (e terminando com) .

Intérprete

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

Solução

O seguinte programa python 2.7 gera minha solução, que pode ser encontrada aqui

Posso editar este post mais tarde com uma explicação mais completa de como isso funciona, mas acontece que o Picofuck está completo em 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! / Solução fornecida

Fundamentos

Todas as instruções implícitas possuem quatro operandos de endereço de memória:

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

Onde vestá o tamanho da memória em quartetos.

Pᵢ, Qᵢ, Rᵢ, SᵢEstão inteiros em tamanho nativo da sua máquina assinado (por exemplo, 64 bits 16, 32 ou) que nós referimos como palavras.

Para cada quarteto i, a operação implícita, com []denotação indireta, é:

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

Observe que Subleq é um subconjunto do PQRS .

O Subleq foi provado completo, portanto o PQRS também deve estar completo!

Estrutura do Programa

O PQRS define um cabeçalho inicial da seguinte maneira:

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

H₀ H₁ H₂ H₃é sempre a primeira instrução P₀ Q₀ R₀ S₀. H₀ao H₃precisam ser definidos no momento do carregamento.

O PQRS possui E / S rudimentares, mas suficiente para o desafio.

H₄ H₅: no início do programa, lê no máximo H₅caracteres ASCII a partir da entrada padrão e salva como palavras no índice em H₄diante. H₄e H₅precisa ser definido no momento do carregamento. Após a leitura, H₅será definido o número de caracteres lidos (e as palavras salvas).

H₆ H₇: no encerramento do programa, iniciando no índice H₆, imprime todos os bytes que compõem as H₇palavras na saída padrão como caracteres ASCII. H₆e H₇precisa ser definido antes do término do programa. Os bytes nulos '\0'na saída serão ignorados.

Terminação

A rescisão é alcançada estabelecendo Sᵢfora dos limites i < 0ou i ≥ v.

Truques

Os quartetos Pᵢ Qᵢ Rᵢ Sᵢnão precisam ser alinhados ou seqüenciais; a ramificação é permitida em intervalos de sub-quarteto.

O PQRS tem indireção, portanto, diferentemente do Subleq, há flexibilidade suficiente para implementar sub-rotinas.

O código pode ser auto-modificável!

Intérprete

O intérprete está escrito em 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, salve o acima como pqrs.c e compile:

gcc -o pqrs pqrs.c

Programa de exemplo

O Echos insere até 40 caracteres, precedido por 'PQRS-'.

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

Para executar, salve as opções acima como echo.pqrs:

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

Executando os casos de teste:

$ ./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 os casos de teste são executados com extrema rapidez, por exemplo, <500 ms.

O desafio

O PQRS pode ser considerado estável; portanto, o desafio começa em 31/10/2015 às 13:00 e termina em 08/11/2015 às 13:00, horário em UTC.

Boa sorte!

Solução

A linguagem é bastante semelhante à usada em "Baby" - a primeira máquina digital eletrônica de programa armazenado do mundo. Nessa página, há um programa para encontrar o fator mais alto de um número inteiro em menos de 32 palavras da memória (CRT!)!

Descobri que escrever a solução em conformidade com as especificações não era compatível com o sistema operacional e a máquina que eu estava usando (um derivado do Linux Ubuntu em hardware um pouco mais antigo). Ele estava apenas solicitando mais memória do que o disponível e o core dumping. Em sistemas operacionais com gerenciamento avançado de memória virtual ou máquinas com pelo menos 8 GB de memória, provavelmente você pode executar a solução por especificações. Eu forneci as duas soluções.

É muito difícil codificar diretamente no PQRS , como escrever linguagem de máquina, talvez até microcódigo. Em vez disso, é mais fácil escrever em um tipo de linguagem assembly do que "compilá-lo". Abaixo está a linguagem assembly anotada para a solução otimizada para executar os casos de teste:

; 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

O que ele faz é analisar a entrada, convertendo unário em binário, depois uma classificação de bolha nos números com os valores em ordem decrescente e, finalmente, gera o terceiro maior valor convertendo binário novamente em unário.

Observe que INC(incremento) é negativo e DEC(decremento) é positivo! Onde ele está usando L#ou L#+1como P-ou Q-OPs, o que está acontecendo é que ele está atualizando ponteiros: incrementando, decrementando, trocando etc. O montador foi compilado manualmente no PQRS , substituindo os rótulos pelos deslocamentos. Abaixo está a solução otimizada para 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

O código acima pode ser salvo challenge-optimized.pqrspara executar os casos de teste.

Para completar, aqui está a fonte por especificações:

; 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

E solução:

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 executar o acima, você vai precisar para comentar #define OPTIMIZEDe adicionar #define PER_SPECSempqrs.c e recompilar.

Este foi um grande desafio - gostei muito do treino mental! Me levou de volta aos meus velhos dias de montagem 6502 ...

Se eu fosse implementar o PQRS como uma linguagem de programação "real", provavelmente adicionaria modos adicionais para acesso direto e duplamente indireto, além do acesso indireto, bem como posição relativa e posição absoluta, ambas com opções de acesso indireto para a ramificação!

Zinco, rachado! por @Zgarb

Também disponível no GitHub .

Você precisa do Dart 1.12 e do Pub. Apenas corrapub get para baixar a única dependência, uma biblioteca de análise.

Aqui está a esperança de que este dure mais de 30 minutos! : O

O idioma

O zinco é orientado para redefinir os operadores. Você pode redefinir todos os operadores no idioma facilmente!

A estrutura de um programa típico de zinco se parece com:

let
<operator overrides>
in <expression>

Existem apenas dois tipos de dados: números inteiros e conjuntos. Não existe um conjunto literal e conjuntos vazios não são permitidos.

Expressões

A seguir, expressões válidas no Zinc:

Literais

O zinco suporta todos os literais inteiros normais, como 1e -2.

Variáveis

O zinco tem variáveis ​​(como a maioria dos idiomas). Para referenciá-los, basta usar o nome Mais uma vez, como a maioria dos idiomas!

No entanto, existe uma variável especial chamada Sque se comporta como a de Pyth Q. Quando você o usa pela primeira vez, ele lê uma linha da entrada padrão e a interpreta como um conjunto de números. Por exemplo, a linha de entrada 1234231se transformaria no conjunto {1, 2, 3, 4, 3, 2, 1}.

NOTA IMPORTANTE!!!Em alguns casos, um literal no final de uma substituição de operador é analisado incorretamente, portanto, você deve colocá-lo entre parênteses.

Operações binárias

As seguintes operações binárias são suportadas:

• Além via +: 1+1.
• Subtração via -: 1-1.
• Multiplicação via *: 2*2.
• Divisão via /: 4/2.
• Igualdade com =: 3=3.

Além disso, a seguinte operação unária também é suportada:

• Corpo com #: #x.

A precedência é sempre associativa correta. Você pode usar parênteses para substituir isso.

Somente a igualdade e o comprimento funcionam nos sets. Quando você tenta obter o comprimento de um número inteiro, obtém o número de dígitos em sua representação de seqüência de caracteres.

Definir compreensões

Para manipular conjuntos, o zinco definiu suas compreensões. Eles se parecem com isso:

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

Uma cláusula é uma cláusula when ou uma cláusula de classificação.

A cláusula when se parece ^<expression>. A expressão após o sinal de intercalação deve resultar em um número inteiro. O uso da cláusula when utilizará apenas os elementos do conjunto que expressionnão sejam zero. Dentro da expressão, a variável _será configurada para o índice atual no conjunto. É aproximadamente equivalente a este Python:

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

Uma cláusula de classificação , que parece $<expression>, classifica o conjunto decrescente pelo valor de <expression>. É igual a este Python:

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

Aqui estão alguns exemplos de compreensão:

• Pegue apenas os elementos do conjunto sque são iguais a 5:

  {x:s^x=5}
  

• Classifique o conjunto spelo valor se seus elementos ao quadrado:

  {x:s$x*x}
  

Substituições

As substituições de operador permitem redefinir os operadores. Eles se parecem com isso:

<operator>=<operator>

ou:

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

No primeiro caso, você pode definir um operador para igualar outro operador. Por exemplo, eu posso definir +para realmente subtrair via:

+=-

Ao fazer isso, você pode redefinir um operador para ser um operador mágico . Existem dois operadores mágicos:

• joinpega um conjunto e um número inteiro e une o conteúdo do conjunto. Por exemplo, ingressar {1, 2, 3}com 4resultará no número inteiro 14243.

• cuttambém pega um conjunto e um número inteiro e particionará o conjunto a cada ocorrência do número inteiro. Usando cuton {1, 3, 9, 4, 3, 2}e 3criará {{1}, {9, 4}, {2}}... MAS qualquer conjunto de elemento único é achatado, portanto o resultado será realmente {1, {9, 4}, 2}.

Aqui está um exemplo que redefine o +operador para significar join:

+=join

Para o último caso, você pode redefinir um operador para a expressão fornecida. Como exemplo, isso define a operação mais para adicionar os valores e, em seguida, adicionar 1:

x+y=1+:x+:y

Mas o que é +:? Você pode anexar os dois pontos :a um operador para sempre usar a versão interna. Este exemplo usa o +via interno +:para adicionar os números e, em seguida, adiciona um 1 (lembre-se, tudo é associativo à direita).

A substituição do operador de comprimento se parece com:

#x=<expression>

Observe que quase todas as operações internas (exceto a igualdade) usarão esse operador de comprimento para determinar o comprimento do conjunto. Se você definiu para ser:

#x=1

toda parte do zinco que trabalha em conjuntos, exceto =, operaria apenas no primeiro elemento do conjunto que foi dado.

Várias substituições

Você pode substituir vários operadores, separando-os com vírgulas:

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

Impressão

Você não pode imprimir diretamente nada em zinco. O resultado da expressão a seguir inserá impresso. Os valores de um conjunto serão concatenados com o separador. Por exemplo, considere o seguinte:

let
...
in expr

Se exprfor o conjunto {1, 3, {2, 4}}, 1324será impresso na tela assim que o programa terminar.

Juntando tudo

Aqui está um programa simples de zinco que parece adicionar, 2+2mas faz com que o resultado seja 5:

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

O intérprete

Isso entra em 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());
}

E isso entra pubspec.yaml:

name: zinc
dependencies:
  parsers: any

Solução pretendida

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

Sopa de bússola ( rachada por caixa de papelão )

Intérprete: C ++

A sopa de bússola é como uma máquina de Turing com uma fita bidimensional infinita. O principal problema é que a memória de instruções e a memória de dados estão no mesmo espaço, e a saída do programa é todo o conteúdo desse espaço.

Como funciona

Um programa é um bloco de texto bidimensional. O espaço do programa começa com todo o código-fonte colocado com o primeiro caractere em (0,0). O restante do espaço do programa é infinito e é inicializado com caracteres nulos (ASCII 0).

Existem dois ponteiros que podem se mover pelo espaço do programa:

• O ponteiro de execução possui um local e uma direção (norte, sul, leste ou oeste). Cada tick, a instrução sob o ponteiro de execução é executada e o ponteiro de execução se move na direção atual. O ponteiro de execução começa a se mover para leste (x positivo), no local do! caractere ou em (0,0) se isso não existir.
• O ponteiro de dados possui apenas um local. Ele é movido com as instruções x, X, y, e Y. Começa na localização do @personagem ou em (0,0) se isso não existir.

Entrada

O conteúdo do stdin é impresso no espaço do programa, começando no local do >caractere ou em (0,0), se isso não existir.

Resultado

O programa termina quando o ponteiro de execução é executado irremediavelmente fora dos limites. A saída é todo o conteúdo do espaço do programa naquele momento. É enviado para stdout e 'result.txt'.

Instruções

• n - redireciona o ponteiro de execução para o norte (y negativo)
• e - redireciona o ponteiro de execução para o leste (x positivo)
• s - redireciona o ponteiro de execução para o sul (positivo y)
• w - redireciona o ponteiro de execução para oeste (x negativo)
• y - move o ponteiro de dados para o norte (y negativo)
• X - move o ponteiro de dados para o leste (x positivo)
• Y - move o ponteiro de dados para o sul (y positivo)
• x - move o ponteiro de dados para oeste (x negativo)
• p- escreve o próximo caractere encontrado pelo ponteiro de execução no ponteiro de dados. Esse personagem não é executado como uma instrução.
• j- verifica o próximo caractere encontrado pelo ponteiro de execução contra o caractere abaixo do ponteiro de dados. Esse personagem não é executado como uma instrução. Se eles são iguais, o ponteiro de execução pula sobre o próximo caractere.
• c - escreve o caractere nulo no ponteiro de dados.
• * - breakpoint - apenas faz com que o intérprete se quebre.

Todos os outros caracteres são ignorados pelo ponteiro de execução.

Intérprete

O intérprete toma o arquivo de origem como argumento e insere stdin. Ele possui um depurador escalonável, que você pode chamar com uma instrução de ponto de interrupção no código ( *). Quando quebrado, o ponteiro de execução é mostrado como ASCII 178 (bloco sombreado mais escuro) e o ponteiro de dados é mostrado como ASCII 177 (bloco sombreado mais 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();
}