Le fil de défi des voleurs est ici .

Le défi de Cops: concevoir un langage de programmation qui semble inutilisable pour la programmation, mais admet le calcul (ou au moins l'achèvement de la tâche) via un mécanisme non évident.

Vous devriez concevoir un langage de programmation simple qui lit le code à partir d'un fichier d'entrée, puis fait ... quelque chose. Vous devez préparer un programme de solution qui trouve le 3ème plus grand nombre dans l'entrée lorsqu'il est exécuté dans votre interprète. Il faut que les voleurs aient le plus de difficulté possible pour trouver un programme de solution. Notez que les cambrioleurs peuvent publier n’importe quelle solution permettant d’accomplir cette tâche, pas seulement celle que vous aviez à l’esprit.

C'est un concours de popularité. L’objectif des flics est d’obtenir le plus de votes possible tout en survivant 8 jours après avoir posté l’interprète sans se faire craquer. À cette fin, les pratiques suivantes devraient aider:

• Expliquer avec précision la sémantique de votre langue
• Écrire du code lisible

Les tactiques suivantes sont fortement déconseillées:

• Utilisation du cryptage, des hachages ou d'autres méthodes cryptographiques. Si vous voyez une langue qui utilise le chiffrement RSA ou refuse d'exécuter un programme à moins que son hachage SHA-3 soit égal à 0x1936206392306, n'hésitez pas à voter par virement négatif.

Défi des voleurs: écrivez un programme qui trouve le troisième plus grand nombre entier dans l'entrée lorsqu'il est exécuté dans l'interpréteur des flics.

Celui-ci est relativement simple. Afin de déchiffrer une réponse d'un flic, vous devez créer un programme qui termine la tâche lorsqu'il est exécuté dans son interpréteur. Lorsque vous déchiffrez une réponse, postez un commentaire portant la mention "fissuré" dans la réponse du flic qui renvoie à votre message. Celui qui casse le plus de flics gagne le fil des voleurs.

Règles I / O

• Les interprètes doivent utiliser un nom de fichier sur la ligne de commande du programme et utiliser les entrées et les sorties standard lors de son exécution.
• Les données saisies seront unaires et composeront uniquement des caractères 0et 1(48 et 49 en ASCII). Un nombre N est codé sous la forme N 1s suivi de a 0. Il y en a un 0avant la fin du fichier. Exemple: Pour la séquence (3, 3, 1, 14), l'entrée est 11101110101111111111111100.
• L'entrée est garantie d'avoir au moins 3 chiffres. Tous les nombres sont des entiers positifs.
• La sortie sera jugée par le nombre de 1s imprimés avant l’arrêt du programme. Les autres caractères sont ignorés.

Dans les exemples suivants, la première ligne correspond à l’entrée au format décimal; la seconde est l'entrée réelle du programme; le troisième est un exemple de sortie.

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>

Règles ennuyeuses pour les réponses des flics:

• Pour éviter la sécurité par obscurité, l'interprète doit être écrit dans un langage figurant dans le top 100 de cet index TIOBE et disposer d'un compilateur / interprète disponible gratuitement.
• L'interprète ne doit pas interpréter une langue qui a été publiée avant ce défi.
• L'interprète doit s'intégrer à votre message et ne pas être hébergé à l'extérieur.
• L'interprète doit être déterministe
• L'interprète doit être portable et respecter les normes de sa propre langue. n'utilisez pas de comportement indéfini ou de bugs
• Si le programme de solution est trop long pour tenir dans la réponse, vous devez poster un programme qui le génère.
• Le programme de solution ne doit comporter que des fichiers ASCII et des nouvelles lignes imprimables.
• Vous devez exécuter votre programme de solution en moins d'une heure sur votre propre ordinateur pour chacun des exemples de saisie ci-dessus.
• Le programme doit fonctionner pour tout nombre entier inférieur à 10 ⁶ et tout nombre entier inférieur à 10 ⁶ (pas nécessairement inférieur à une heure), à ​​condition que la longueur totale en entrée soit inférieure à 10 ⁹ .
• Pour être en sécurité, un flic doit modifier le programme de la solution dans la réponse au bout de 8 jours.

Notation

Le flic qui est en sécurité avec le score le plus élevé et un score positif remporte cette question.

Changeling (coffre-fort)

ShapeScript

ShapeScript est un langage de programmation naturel. Les changeurs de forme (ou Changelings , comme ils préfèrent être appelés) peuvent se transformer en un ensemble d'instructions leur permettant de traiter des données.

ShapeScript est un langage basé sur une pile avec une syntaxe relativement simple. Sans surprise, la plupart de ses fonctions intégrées traitent de la modification de la forme des cordes. Il est interprété, caractère par caractère, comme suit:

• 'et "commencez un littéral de chaîne.

  Jusqu'à ce que la citation correspondante soit trouvée dans le code source, tous les caractères entre ces citations correspondantes sont rassemblés dans une chaîne, qui est ensuite placée dans la pile.

• 0pour 9pousser les entiers 0 à 9 sur la pile. Notez que 10pousse deux entiers.

• ! extrait une chaîne de la pile et tente de l'évaluer en tant que ShapeScript.

• ? extrait un entier de la pile et pousse une copie de l'élément de pile à cet index.

  L'index 0 correspond à l'élément de pile le plus haut (LIFO) et l'index -1 à l'élément le plus bas.

• _ saute une itérable de la pile et pousse sa longueur.

• @ sort deux éléments de la pile et les pousse dans l’ordre inverse.

• $enlève deux chaînes de la pile et divise la plus basse des occurrences de la plus haute. La liste résultante est poussée en retour.

• &ouvre une chaîne (la plus haute) et une variable de la pile, puis la joint, en utilisant la chaîne comme séparateur. La chaîne résultante est poussée en retour.

• Si ShapeScript est utilisé sur notre planète, car pythons sont les parents les plus proches Changelings sur Terre, tous les autres caractères c pop deux points x et y (supérieure) de la pile, et de tenter d'évaluer le code Python x c y.

  Par exemple, la séquence de caractères est 23+évaluée 2+3, tandis que la séquence de caractères est "one"3*évaluée 'one'*3et la séquence de caractères est 1''Aévaluée 1A''.

  Dans le dernier cas, le résultat n'étant pas valide en Python, Changeling se plaindrait de ce que sa forme actuelle n'est pas définie (erreur de syntaxe), car ce n'est pas ShapeScript valide.

Avant d'exécuter le code, l'interprète placera la totalité de l'entrée utilisateur sous la forme d'une chaîne sur la pile. Après avoir exécuté le code source, l’interprète imprimera tous les éléments de la pile. Si une partie entre les deux échoue, le Changeling se plaint que sa forme actuelle est inadéquate (erreur d'exécution).

Changement de forme

Dans leur état naturel, Changelings ne prend pas la forme de ShapeScript. Cependant, certains d'entre eux peuvent se transformer en un code source potentiel (qui n'est pas forcément utile ni même syntaxiquement valide).

Tous les changelings éligibles ont la forme naturelle suivante:

• Toutes les lignes doivent avoir le même nombre de caractères.

• Toutes les lignes doivent comporter des caractères ASCII imprimables, suivis d'un seul saut de ligne.

• Le nombre de lignes doit correspondre au nombre de caractères imprimables par ligne.

Par exemple, la séquence d'octets ab\ncd\nest un Changeling éligible.

Dans sa tentative de passer à ShapeScript, le Changeling subit la transformation suivante:

• Au départ, il n'y a pas de code source.

• Voici ce qui se passe pour chaque ligne:

  • L'accumulateur de Changeling est mis à zéro.

  • Pour chaque caractère c de la ligne (y compris le saut de ligne de fin), le point de code de c est divisé en deux par l'accumulateur, et le caractère Unicode correspondant au point de code résultant est ajouté au code source.

    Ensuite, la différence entre le point de code de c et le point de code d'un espace (32) est ajoutée à l'accumulateur.

Si une partie de ce qui précède échoue, le Changeling se plaint que sa forme actuelle est désagréable.

Une fois toutes les lignes traitées, la transformation de Changeling en ShapeScript (valide, espérons-le) est terminée et le code obtenu est exécuté.

Solution (ShapeScript)

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

ShapeScript s’est avéré être tout à fait utilisable; il peut même effectuer des tests de primalité ( preuve ) et satisfait donc notre définition du langage de programmation.

J'ai republié ShapeScript sur GitHub , avec une syntaxe légèrement modifiée et de meilleures E / S.

Le code fait ce qui suit:

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

Solution (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=....................
""# !......................

Comme tous les programmes Changeling, ce code a un retour à la ligne final.

ShapeScript commettra une erreur immédiate sur n'importe quel caractère s'il ne comprend pas, mais nous pouvons insérer des chaînes arbitraires en tant que charges et les extraire ultérieurement. Cela nous permet de ne mettre qu'une petite quantité de code sur chaque ligne (au début, où l'accumulateur est petit), suivie d'une ouverture ". Si nous commençons par la ligne suivante "#, nous fermons et sautons la chaîne sans affecter le code réel.

En outre, nous devons surmonter trois obstacles mineurs:

• La longue chaîne dans le code ShapeScript est un simple jeton et nous ne pourrons pas l'ajuster sur une ligne.

  Nous allons pousser cette chaîne en morceaux ( '@', '1?', etc.), que nous allons concaténer plus tard.

• Le point de code de _est assez élevé, et pousser '_'sera problématique.

  Cependant, nous pourrons pousser '_@'sans effort, suivis par un autre '@'pour annuler l'échange.

Le code ShapeScript que notre Changeling va générer ressemble à ceci ¹ :

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

J'ai trouvé le code Changeling en exécutant le code ShapeScript ci-dessus via ce convertisseur . ²

Interprète (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)))

¹ _{Chaque ligne est complétée avec une quantité aléatoire de déchets, et les sauts de ligne ne sont pas réellement présents.}
² _{Les numéros du bas indiquent les points de code le plus bas et le plus haut du code de Changeling, qui doit rester compris entre 32 et 126.}

Shuffle (écrit en C ++), fissuré! par Martin

Edit Martin a craqué. Pour voir sa solution, cliquez sur le lien. Ma solution a également été ajoutée.

Edit Commande fixe print-dpour pouvoir gérer les registres et les piles. Comme il s'agit d'une commande de débogage non autorisée dans une solution, cela ne devrait affecter personne utilisant la version précédente de l'interpréteur.

Je suis encore nouveau dans ce domaine, alors s'il y a quelque chose qui ne va pas dans ma réponse ou dans mon interprète, merci de me le faire savoir. S'il vous plaît demander des précisions si quelque chose n'est pas clair.

Je ne pense pas que ce sera trop difficile, mais j'espère que cela constituera un défi. Ce qui rend le mélange assez inutilisable, c'est qu'il n'imprimera que lorsque les choses seront à leur place.

-> Bases:

Il y a 24 piles, nous les appelons stack1, ... stack24. Ces piles vivent dans une liste. Au début de tout programme, ces piles sont mises à zéro et commencent à la place qui leur convient, c'est-à-dire que la pile i est à la iième position dans la liste (notez que nous indexerons à partir de 1, contrairement à C ++). Au cours d'un programme, l'ordre des piles dans la liste changera. Ceci est important pour des raisons qui seront expliquées lorsque je discuterai des commandes.

Il y a 5 registres disponibles pour utilisation. Ils sont nommés Alberto, Gertrude, Hans, Leopold, ShabbySam. Chacun de ceux-ci est mis à zéro au début d'un programme.

Ainsi, au début de tout programme, il y a 24 piles, chacune ayant son numéro correspondant à son index dans la liste des piles. Chaque pile a exactement un zéro en haut. Chacun des cinq registres est initialisé à zéro.

-> Commandes et syntaxe :

Il y a 13 commandes (+1 commande de débogage) disponibles dans Shuffle. Ils sont comme suit

• cinpushcette commande ne prend aucun argument. Il attend une entrée de ligne de commande de la manière décrite dans la question (toute autre entrée entraînera des résultats non spécifiés / non définis). Il divise ensuite la chaîne d'entrée en entiers, par exemple 101011100-> 1,1,3. Pour chaque entrée reçue, il effectue les opérations suivantes: (1) permute la liste des piles en fonction de la valeur. Laissez la valeur entière en question être appelée un . Si a est inférieur à 10, il effectue la permutation u . Si a est compris entre 9 et 30 (non inclus), il effectue la permutation d . Sinon, il fait la permutation r . (2) Il pousse ensuite unsur la pile qui est en premier dans la liste. Notez que je ne veux pas dire stack1(bien que cela puisse être le cas qui stack1est en premier dans la liste). Les permutations sont définies ci-dessous. Depuis cinpushest la seule façon d'obtenir l' entrée d'utilisateur , il doit apparaître dans toute solution.

• mov value registerLa movcommande est essentiellement une affectation de variable. Il assigne valueà register. valuepeut prendre plusieurs formes: il peut s'agir (1) d' un entier, par exemple 47 (2) du nom d'un registre différent, par exemple Hans (3) de l'index d'une pile suivi de "s", par exemple 4s. Notez qu'il s'agit de l'index dans la liste et non du numéro de la pile. En tant que tel, le nombre ne doit pas dépasser 24.

  Quelques movexemples:

  mov 4s Hans 
  mov Hans ShabbySam
  mov 9999 Gertrude
  

• movfs index registerCela signifie "déplacer de la pile". C'est similaire à la movcommande. Il existe pour que vous puissiez accéder à une pile indexée par un registre. Par exemple, si précédemment, vous définissez Hans sur 4 ( mov 4 Hans), vous pouvez movfs Hans Gertrudedéfinir Gertrude sur le haut de la pile 4. Ce type de comportement n'est pas accessible simplement à l'aide de mov.

• inc register augmente la valeur du registre de 1.
• dec register diminue la valeur du registre de 1.
• compg value value registerCela signifie «comparer plus grand». Le registre est égal à la plus grande des deux valeurs. valuepeut être un entier, un registre ou un index de pile suivi de 's', comme ci-dessus.
• compl value value register 'compare less' comme ci-dessus, à l'exception de la valeur la plus petite.
• gte value1 value2 registerVérifie si value1 >= value2la valeur booléenne (telle que 1 ou 0) est ensuite placée dans register.
• POP!! indexapparaît en haut de la pile indexée par indexdans la liste des piles.
• jmp labelsaute inconditionnellement à l'étiquette label. C'est un bon moment pour parler des étiquettes. Une étiquette est un mot suivi de ':'. L'interprète effectue une pré-analyse des étiquettes afin que vous puissiez passer à la fois aux étiquettes et inversement.
• jz value labelsaute à labelsi valueest zéro.

• jnz value labelsaute à labelsi valueest différent de zéro.

  Exemples d'étiquettes et de sauts:

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

• "shuffle" permutationVoici la commande de lecture aléatoire. Cela vous permet de permuter la liste des piles. Il y a trois permutations valides qui peuvent être utilisés comme arguments, l, f, et b.

• print registerCeci vérifie si toutes les piles sont dans leurs positions initiales, c'est-à-dire que la pile i est à l'index i dans la liste des piles. Si tel est le cas, il affiche la valeur à registerunaire. Sinon, une mauvaise erreur est imprimée. Comme vous pouvez le constater, pour pouvoir générer quoi que ce soit, les piles doivent toutes se trouver aux bons endroits.
• done!cela indique au programme de quitter sans erreur. Si le programme se termine sans done!, il imprimera sur la console le numéro au-dessus de chaque pile suivi du numéro de la pile. L'ordre dans lequel les piles sont imprimées correspond à l'ordre dans lequel elles apparaissent dans la liste des piles. Si une pile est vide, elle sera omise. Ce comportement est à des fins de débogage et ne peut pas être utilisé dans une solution.
• print-d valueCeci affiche la valeur de la pile, du registre ou de l’entier donné (pour accéder à la pile i , passer isen argument, comme expliqué ci-dessus). Il s’agit d’un outil de débogage qui ne fait pas partie du langage. En tant que tel, il n’est pas autorisé dans une solution.

-> Voici le code de l'interprète

Tout l'analyse se passe dans la fonction principale. C'est ici que vous trouverez l'analyse de commandes spécifiques.

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

-> Permutations Les permutations permutent les éléments de la liste de pile de la manière suivante:

Où signifie que

(Celles-ci apparaissent également dans le code de l'interprète. En cas de divergence, l'interprète est correct.)

-> Exemple simple

Ces deux programmes simples impriment les nombres de 24 à 1 (unaire) sans espace.

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!

Ils sont le même programme.

Explication et solution:

Martin a également une bonne explication dans sa réponse .

Comme Martin l'a découvert, ce langage a été inspiré par le cube de poche (alias 2x2 Rubik's cube). Les 24 piles sont comme les 24 carrés individuels du cube. Les permutations sont les mouvements de base autorisés: haut, bas, droite, gauche, avant, arrière.

La principale difficulté ici est que, lorsque les valeurs sont poussées, seuls trois mouvements sont utilisés: haut, bas et droit. Cependant, vous n'avez pas accès à ces mouvements lorsque vous "mélangez" les piles. Vous n'avez que les trois autres mouvements.

Il s’avère que les deux séries de trois mouvements s’appliquent à l’ensemble du groupe (c’est-à-dire qu’il s’agit de générateurs), ce qui permet de résoudre le problème. Cela signifie que vous pouvez réellement résoudre n'importe quel cube de Rubik 2x2 en utilisant 3 des mouvements.

Tout ce qui reste à faire est de trouver comment annuler les mouvements haut, bas et droit en utilisant les trois autres. À cette fin, j'ai employé un système de calcul formel appelé GAP .

Après avoir annulé les permutations, trouver le troisième plus grand nombre est assez 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 , fissuré par cardboard_box

Je suis intriguée depuis un certain temps par l’idée d’un langage de programmation dans lequel deux programmes interagissent (probablement inspiré de ROCB ). Ce défi était une bonne incitation à aborder enfin ce concept tout en essayant de garder le moins de langage possible. Les objectifs de conception étaient de rendre le langage Turing-complet, alors que chacune de ses parties ne le sont pas individuellement. En outre, même les deux ne devraient pas être complets avec Turing sans faire appel à la manipulation du code source. Je pense y être parvenu, mais je n’ai encore prouvé formellement aucune de ces choses. Alors sans plus tarder, je vous présente ...

Les protagonistes

Brian et Chuck sont deux programmes ressemblant à Brainfuck. Un seul d'entre eux est exécuté à un moment donné, à commencer par Brian. Le problème, c'est que la bande mémoire de Brian est également le code source de Chuck. Et la bande mémoire de Chuck est aussi le code source de Brian. En outre, la tête de lecture de Brian est également le pointeur d'instructions de Chuck et inversement. Les bandes sont semi-infinies (c'est-à-dire infinies à droite) et peuvent contenir des entiers signés de précision arbitraire, initialisés à zéro (sauf indication contraire du code source).

Le code source étant également une bande mémoire, les commandes sont définies techniquement par des valeurs entières, mais elles correspondent à des caractères raisonnables. Les commandes suivantes existent:

• ,( 44): Lit un octet de STDIN dans la cellule de mémoire en cours. Seul Brian peut le faire. Cette commande est un non-op pour Chuck.
• .( 46): Écrivez la cellule de mémoire actuelle, modulo 256, sous forme d'octet dans STDOUT. Seul Chuck peut le faire. Cette commande est un non-op pour Brian.
• +( 43): Incrémente la cellule de mémoire actuelle.
• -( 45): Décrémente la cellule de mémoire actuelle.
• ?( 63): Si la cellule de mémoire actuelle est à zéro, il s'agit d'un no-op. Sinon, passez le contrôle à l'autre programme. La tête de la bande sur le programme qui utilise ?restera sur le ?. La tête de bande de l'autre programme déplacera une cellule vers la droite avant d'exécuter la première commande (de sorte que la cellule utilisée comme test n'est pas exécutée elle-même).
• <( 60): Déplacez la tête de la cassette d'une cellule vers la gauche. Ceci est une opération impossible si la tête de la cassette est déjà à l'extrémité gauche de la bande.
• >( 62): Déplacez la tête de la cassette d'une cellule vers la droite.
• {( 123): Déplacez à plusieurs reprises la tête de la bande vers la gauche jusqu'à ce que la cellule actuelle atteigne zéro ou que l'extrémité gauche de la bande soit atteinte.
• }( 125): Déplacez à plusieurs reprises la tête de la bande vers la droite jusqu'à ce que la cellule en cours devienne zéro.

Le programme se termine lorsque le pointeur d'instructions du programme actif atteint un point où il n'y a plus d'instructions à sa droite.

Le code source

Le fichier source est traité comme suit:

• Si le fichier contient la chaîne ```, le fichier sera divisé en deux parties autour de la première occurrence de cette chaîne. Tous les espaces blancs de début et de fin sont supprimés et la première partie est utilisée comme code source pour Brian et la deuxième partie pour Chuck.
• Si le fichier ne contient pas cette chaîne, la première ligne du fichier sera utilisée comme source pour Brian et la deuxième partie pour Chuck (à l'exception de la nouvelle ligne de délimitation, aucun espace n'est supprimé).
• Toutes les occurrences de _dans les deux programmes sont remplacées par des octets NULL.
• Les deux bandes de mémoire sont initialisées avec les codes de caractères correspondant à la chaîne résultante.

Par exemple, le fichier source suivant

  abc
```
0_1
23

Donnerait les bandes initiales suivantes:

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

L'interprète

L'interprète est écrit en rubis. Il faut deux indicateurs de ligne de commande qui ne doivent être utilisés par aucune solution (car ils ne font pas partie de la spécification de langue actuelle):

• -d: Avec ce drapeau, Brian et Chuck comprennent deux autres commandes. !imprimera une représentation sous forme de chaîne des deux bandes de mémoire, le programme actif étant répertorié en premier (un ^marque les têtes de bande actuelles). @fera également cela, mais mettra immédiatement fin au programme. Parce que je suis paresseux, aucune de ces méthodes ne fonctionne si elles sont la dernière commande du programme. Si vous souhaitez les utiliser ici, répétez-les ou écrivez un no-op à leur suite.
• -D: Ceci est le mode de débogage détaillé. Il imprimera les mêmes informations de débogage !qu'après chaque tick. @fonctionne également dans ce mode.

Voici le code:

# coding: utf-8

class Instance
    attr_accessor :tape, :code, :ip

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

    OPERATORS.default = :nop

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

        @ip = 0
    end

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

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

        move_right if result != :toggle

        return result
    end

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

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

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

    def get
        @code[@ip]
    end

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

    def input() end
    def output() end

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

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

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

class BrianChuck

    class ProgramError < Exception; end

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

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

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

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

        chuck ||= ""

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

        brian.tape = chuck
        chuck.tape = brian

        @instances = [brian, chuck]
    end

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

        loop do
            result = current.tick

            toggle if result == :toggle

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

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

    private

    def current
        @instances[0]
    end

    def toggle
        @instances.reverse!
    end
end

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

if debug_level > 0
    ARGV.shift
end

BrianChuck.run(ARGF.read, debug_level)

Voici ma propre solution (manuscrite) au problème:

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

Ce code est exécutable tel quel, car toutes les annotations utilisent no-ops et sont ignorées par {et }.

L'idée de base est:

1. Ajoutez un nouvel élément zéro à la liste (à la fin de la bande de Chuck) et augmentez la longueur de la liste de 1.
2. Pendant que nous lisons 1s, incrémentons cet élément.

3. Quand on lit un 0, fais un peu de ménage. Si le nombre résultant était supérieur à zéro, revenez à 1.

   Nous avons maintenant une liste des numéros saisis à la fin de la bande de Chuck et nous connaissons la longueur de la liste.

4. Soustrayez 2 de la longueur de la liste (pour que les étapes suivantes ignorent les deux éléments les plus grands), appelez ceci N.

5. Pendant que N > 0, incrémentez un total cumulé, puis décrémentez tous les éléments de la liste. Chaque fois qu'un élément de la liste atteint zéro, décrémentez N.

   A la fin de cela, le total en cours d' exécution contiendra le troisième plus grand nombre dans l'entrée, M.

6. Ecrire des Mcopies de .la fin de la bande de Chuck.

7. Sur Chuck, recherchez une 1cassette de Brian, puis exécutez celles générées .à la fin.

Après avoir terminé ceci, j'ai réalisé que je pouvais le simplifier beaucoup à certains endroits. Par exemple, au lieu de garder une trace de ce compteur et de l'écrire .sur la bande de Chuck, je pourrais simplement en imprimer un 1immédiatement, chaque fois avant de décrémenter tous les éléments de la liste. Cependant, apporter des modifications à ce code est assez pénible, car il propage d'autres modifications dans tous les sens, je ne me suis donc pas soucié d'apporter ces modifications.

Le point intéressant est de savoir comment garder une trace de la liste et comment la parcourir. Vous ne pouvez pas simplement stocker les numéros dos à dos sur la bande de Chuck, car si vous voulez vérifier une condition sur l'un des éléments de la liste, vous risquez d'exécuter le reste de la liste qui pourrait contenir du code valide. Vous ne savez pas non plus combien de temps la liste sera longue, vous ne pouvez donc pas simplement réserver un espace devant le code de Chuck.

Le problème suivant est que nous devons quitter la liste pour la décrémenter Npendant que nous la traitons et que nous devons retourner au même endroit que nous étions auparavant. Mais {et }juste passer la liste complète.

Nous devons donc écrire du code de manière dynamique sur Chuck. En fait, chaque élément de la liste ia la forme suivante:

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

1est un marqueur que nous pouvons mettre à zéro pour indiquer où nous en sommes restés au traitement de la liste. Son but est de rattraper {ou }qui ne fera que passer le code et le i. Nous utilisons également cette valeur pour vérifier si nous sommes à la fin de la liste pendant le traitement. Par conséquent, si ce n’est pas le cas, ce sera le cas 1et le conditionnel ?basculera le contrôle sur Chuck. Code Aest utilisé pour gérer cette situation et déplacer l'IP sur Brian en conséquence.

Maintenant, lorsque nous décrémentons, inous devons vérifier si iest déjà égal à zéro. Bien que ce ne soit pas le cas, nous ?allons encore changer de contrôle, il en Code Best de même pour gérer cela.

HPR, écrit en Python 3 ( fissuré par TheNumberOne )

HPR (le nom ne veut rien dire) est un langage de traitement de listes d'entiers. Il est conçu pour être minimaliste , extrêmement limité et exempt de restrictions "artificielles" . Programmer en HPR est pénible, non pas parce que vous devez résoudre un casse-tête pour empêcher l'interprète de vous crier dessus, mais parce qu'il est difficile de faire en sorte qu'un programme fasse quelque chose d'utile. Je ne sais pas si HPR est capable de quoi que ce soit de beaucoup plus intéressant que de calculer le troisième plus gros élément d'une liste.

Spécification de la langue

Un programme HPR est exécuté dans un environnement , qui est un ensemble d’entiers non négatifs non négatifs et de listes d’entiers non négatifs. Initialement, l'environnement ne contient que la liste d'entrées (l'interpréteur les analyse pour vous). Il existe trois commandes et deux opérateurs de "flux de contrôle" modifiant l'environnement:

• *supprime le premier élément de chaque liste non vide de l'environnement et le place dans l'environnement. Les listes vides ne sont pas affectées. Par exemple, cela transforme

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

• -décrémente tous les nombres de l’environnement, puis supprime les éléments négatifs. Par exemple, cela transforme

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

• $fait pivoter chaque liste de l'environnement d'un pas vers la gauche. Par exemple, cela transforme

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

• !(A)(B), où Aet Bsont des programmes, est fondamentalement une whileboucle. Il exécute "l'action" Ajusqu'à ce que le "test" Bdonne un environnement vide. Cela peut produire une boucle infinie.
• #(A)(B), où Aet Bsont des programmes, s’appliquent Aet Bà l’environnement actuel et prend la différence symétrique des résultats.

Les commandes sont exécutées de gauche à droite. A la fin, la taille de l'environnement est imprimée en unaire.

L'interprète

Cet interpréteur comporte la commande debug ?, qui affiche l' environnement sans le modifier. Il ne devrait apparaître dans aucune solution à la tâche. Tous les caractères sauf *-$!#()?sont simplement ignorés, vous pouvez donc écrire des commentaires directement dans le code. Enfin, l'interprète reconnaît l'idiome !(A)(#(A)())comme "exécuter Ajusqu'à ce que le résultat ne change plus" et l'optimise pour une vitesse supplémentaire (j'en avais besoin pour que ma solution se termine en moins d'une heure sur le dernier cas de test).

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

Ma solution

Ma solution de référence est longue de 484 octets, donc assez courte par rapport au programme de 3271 octets de TheNumberOne. Ceci est probablement dû au système de macros sophistiqué et impressionnant développé par TheNumberOne pour la programmation en HPR. L'idée principale dans nos deux programmes est similaire:

1. Découvrez comment produire le maximum d'éléments d'une liste.
2. Pour supprimer le maximum d'éléments, faites pivoter la liste jusqu'à ce que le premier élément soit égal au maximum, puis faites-la apparaître.
3. Supprimez le maximum deux fois, puis imprimez le nouvel élément maximum.

Toutefois, pour autant que je sache, les détails de la mise en œuvre exacte sont assez différents. Voici ma solution:

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

Et voici le programme Python commenté qui le produit (rien d'extraordinaire ici, juste une manipulation de base des chaînes pour se débarrasser de toutes les répétitions):

# 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 (Pour tuer le dragon, vous avez besoin d'une épée) - Cracked by Martin Büttner

EDIT: J'ai ajouté ma solution et explication ci-dessous le post principal.

Contexte

Dans cette langue, vous prenez le contrôle d'un vaillant guerrier qui a été chargé de tuer un terrible dragon. Le dragon vit dans un labyrinthe souterrain, plein de périls et de dangers, et jusqu'à présent, personne n'a été capable de le cartographier et de survivre. Cela signifie que vous devez vous diriger vers le dragon dans l'obscurité, sans autre intuition et courage que de vous guider.

...

Pas tout à fait. Vous avez apporté une quantité presque illimitée de sbires jetables avec vous et ils sont prêts à vous devancer pour découvrir la voie sûre. Malheureusement, elles sont toutes aussi épaisses que deux planches courtes et ne feront que ce que vous leur dites. C’est à vous de trouver une méthode astucieuse pour que vos sbires découvrent le bon chemin.

Quelques détails supplémentaires

Le repaire du dragon se présente sous la forme d'une grille 10x10. Entre certains points adjacents de la grille, il y a une passerelle étroite; entre les autres, il y a un gouffre profond et une mort certaine. Un exemple de mise en page pour une grille 4x4 pourrait être le suivant:

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

Vous savez qu'il existe toujours un moyen d'aller d'un point à un autre, mais rien de plus que cela ne vous a été révélé.

Pour réussir à vaincre le dragon, vous devez d’abord rassembler des objets que vous pourrez combiner pour créer une lame magique qui tue les dragons. De manière pratique, toutes les pièces de cette arme ont été dispersées dans le repaire du dragon. Vous devez simplement les collecter.

Le problème, c’est que chaque pièce de l’arme a été piégée. À chaque collecte, la disposition des allées change. Des chemins auparavant sûrs pourraient maintenant mener à une mort certaine et vice-versa.

Les commandes

Il n'y a que 5 commandes valides.

• < - Faites un pas à gauche

• > - Faites un pas à droite

• ^ - Faites un pas en avant

• v - Faites un pas en bas

• c- Ramassez tous les objets qui traînent à votre position actuelle. S'il y avait des éléments présents, la disposition du repaire change. Avec les positions numérotées en rangées comme ci-dessus, prenez votre position modulo 10. Il existe 10 mises en page codées en dur dans l'interpréteur, et la mise en page devient la mise en page correspondante. Par exemple, si vous êtes en position 13, la mise en page devient:layouts[3]

Les présentations telles qu'elles apparaissent dans l'interpètre ont été codées en entiers de la manière suivante:

• La disposition vide est codée à zéro.

• Pour chaque bord de la mise en page, prenons xla plus petite des deux positions qu’elle joint.

  • Si le pas est horizontal, ajoutez 2^(2*x)à l'encodage (c'est puissant, pas XOR)

  • Si le pas est vertical, ajoutez 2^(2*x + 1)à l'encodage.

Flux d'exécution

L'interpréteur est exécuté avec le nom d'un fichier source en tant qu'argument de ligne de commande.

Lorsque l’interprète est exécuté, l’utilisateur est invité à fournir une quête. Cette entrée doit être sous la forme décrite dans la question et déterminer les emplacements dans le repaire des composants de l'arme. Plus précisément, chaque entier entré est pris modulo 100 et placé à l'emplacement correspondant dans le repaire.

Chaque programme source est composé de plusieurs lignes, chaque ligne étant composée d’une séquence des 5 caractères valides ci-dessus. Ces lignes représentent vos sbires. Vous, le guerrier, suivez une séquence d'actions connues pour être sûres. Au début, vous ne savez rien du repaire, cette séquence est donc vide. En prenant chaque séide à tour de rôle, on procède comme suit, à partir de la position 0:

• Le séide est chargé d'exécuter toutes les actions connues pour être sûres, suivies des actions dans sa propre ligne de code.

  • Si le séide meurt à un moment donné, vous en êtes averti et le repaire rétablit sa configuration initiale. Tous les articles sont remplacés et les allées reprennent leur position de départ.

  • Si, à la place, le séide survit, vous le vaporisez quand même - ce n'est qu'un séide, après tout. Comme auparavant, cela déclenche la réinitialisation du repaire à son état initial, mais cette fois-ci, vous ajoutez les actions de la ligne de code du séide à la séquence d'actions connues pour être sûres.

Une fois que tous les sbires ont été épuisés, vous, le guerrier, effectuez toutes les actions connues pour être sûres, toujours à partir de la position 0. Deux résultats sont possibles:

• Vous collectez toutes les pièces de l'arme - dans ce cas, vous réussissez à tuer le dragon et un message de victoire excitant est émis. Ce message de victoire contiendra, parmi d'autres caractères, nceux où, nest le troisième plus grand nombre fourni en entrée.

• Vous n'avez pas réussi à récupérer certaines pièces de l'arme. Dans ce cas, le dragon continue à vivre et votre quête a échoué.

Code interprète (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()

Bonne chance, vaillant guerrier.

Ma solution et explication

Voici un script Python qui génère du code source pour résoudre le problème. À titre d’intérêt, le code source final de Martin est environ 5 fois plus petit que le code produit par mon script. D'autre part, mon script pour générer le code est environ 15 fois plus petit que le programme 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')

Structure basique

Cela génère 990 lignes de code source, regroupées par groupe de 10. Les 10 premières lignes contiennent toutes des instructions qui tentent de déplacer un séide de position 0en position 1, puis de collecter un élément - un ensemble pour chaque mise en page possible. Les 10 lignes suivantes contiennent toutes des instructions qui tentent de déplacer un séide de position 1en position 2, puis de récupérer un objet. Et ainsi de suite ... Ces chemins sont calculés avec la pathfonction dans le script - il effectue simplement une recherche en profondeur d'abord.

Si nous pouvons nous assurer que, dans chaque groupe de 10, précisément un séide réussit, nous aurons résolu le problème.

Le problème avec l'approche

Il se peut que pas exactement un sous-marin du groupe des 10 réussisse - par exemple, un séide conçu pour passer d’une position 0à une autre 1pourrait accidentellement réussir à passer d’une position 1à une autre 2(en raison des similitudes dans les dispositions), et que les erreurs de calcul se propagent, entraînant potentiellement une défaillance.

Comment le réparer

Le correctif que j'ai utilisé était le suivant:

Pour chaque séide qui essaie de se déplacer de position nen position n+1, faites-le d'abord marcher de position nen position 0(le coin supérieur gauche) et inversement, puis de position nen position 99(le coin inférieur droit), et inversement. Ces instructions ne peuvent être exécutées en toute sécurité que depuis une position n. Toute autre position de départ et le séide marchera sur le bord.

Ces instructions supplémentaires empêchent donc les sbires d’aller accidentellement aux sbires où ils ne sont pas censés aller, ce qui garantit qu’un séide de chaque groupe de 10 réussit. Notez que ce n'est pas nécessairement le séide que vous attendez - il se peut que le séide qui pense être dans la disposition 0 réussisse, même si nous sommes vraiment dans la disposition 7 - mais dans tous les cas, le fait maintenant changé de position signifie que tous les autres membres du groupe mourront nécessairement. Ces étapes supplémentaires sont calculées par la assert_atfonction, qui safe_pathretourne un chemin qui est la concaténation de ces étapes supplémentaires avec le chemin ordinaire.

Firetype, fissuré par Martin Büttner

Un mélange vraiment étrange de BF et CJam. Et qui sait quoi d'autre! Je suis sûr que ce sera facile, mais c'était amusant quand même. Pour votre information, le nom fait référence à Vermillion Fire de Final Fantasy Type-0 .

REMARQUE : Veuillez me pardonner pour toute ambiguïté dans cette description. Je ne suis pas le meilleur écrivain ...: O

Martin a craqué ça très vite! C'était mon programme original pour résoudre le problème:

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











`
~
+
|
%

_
=

\
@
-
-
!
<
>
>
>

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

Syntaxe

Un script Firetype est essentiellement une liste de lignes. Le premier caractère de chaque ligne est la commande à exécuter. Les lignes vides sont essentiellement des NOP.

Sémantique

Vous avez un tableau d'entiers et un pointeur (pensez BF). Vous pouvez déplacer les éléments à gauche et à droite ou "pousser" des éléments sur le tableau.

Poussant

Lorsque vous "poussez" un élément et que vous êtes à la fin du tableau, un élément supplémentaire sera ajouté à la fin. Si vous n'êtes pas à la fin, l'élément suivant sera remplacé. Quoi qu'il en soit, le pointeur sera toujours incrémenté.

Les commandes

_

Poussez un zéro sur le tableau.

+

Incrémenter l'élément au pointeur actuel.

-

Décrémente l'élément au pointeur actuel.

*

Doublez l'élément au pointeur actuel.

/

Réduisez de moitié l'élément au pointeur actuel.

%

Prenez l'élément au pointeur actuel et avancez de plusieurs lignes, puis déplacez le pointeur vers la gauche. Si la valeur est négative, sautez à la place.

=

Prenez l'élément au pointeur actuel et passez à la ligne + 1. Par exemple, si l'élément en cours est 0, cela passera à la ligne 1. Cela déplace également le pointeur vers la gauche.

,

Lire un caractère de l’entrée standard et indiquer sa valeur ASCII.

^

Prenez l'élément au niveau du pointeur actuel, interprétez-le comme la valeur ASCII d'un caractère et convertissez-le en entier. Par exemple, si la valeur actuelle est 49 (la valeur ASCII de 1), l'élément du pointeur actuel sera défini sur l'entier 1.

.

Écrivez le numéro actuel à l'écran.

!

Prenez l'élément au pointeur actuel et répétez la ligne suivante à plusieurs reprises. Déplace également le pointeur vers la gauche.

<

Déplacez le pointeur à gauche. Si vous êtes déjà au début, une erreur est générée.

>

Déplacez le pointeur vers la droite. Si vous êtes déjà à la fin, une erreur est générée.

~

Si l'élément en cours est différent de zéro, remplacez-le par 0; sinon, remplacez-le par 1.

|

Place l'élément actuel.

@

Définissez l'élément actuel sur la longueur du tableau.

`

Dupliquer l'élément actuel.

\

Triez les éléments devant et avant le pointeur.

#

Annulez l'élément actuel.

L'interprète

Aussi disponible chez 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 !! (sûr)

C'est baack ...

... et, espérons-le, définitivement plus résistant aux échappatoires.

J'ai déjà lu les Acc! spec. Comment va Acc !! différent?

En Acc !! , les variables de boucle sortent de la portée lorsque la boucle se ferme. Vous ne pouvez les utiliser que dans la boucle. À l'extérieur, vous obtiendrez une erreur "le nom n'est pas défini". Autre que ce changement, les langues sont identiques.

Les déclarations

Les commandes sont analysées ligne par ligne. Il existe trois types de commande:

1. Count <var> while <cond>

Compte <var>à partir de 0 tant que <cond>non nul, équivalent à C ++ for(int <var>=0; <cond>; <var>++). Le compteur de boucle peut être n'importe quelle lettre minuscule. La condition peut être n'importe quelle expression, n'impliquant pas nécessairement la variable de boucle. La boucle s'arrête lorsque la valeur de la condition devient 0.

Les boucles nécessitent des accolades à la K & R (en particulier la variante Stroustrup ):

Count i while i-5 {
 ...
}

Comme mentionné ci-dessus, les variables de boucle ne sont disponibles que dans leurs boucles ; tenter de les référencer par la suite provoque une erreur.

2. Write <charcode>

Renvoie un seul caractère avec la valeur ASCII / Unicode donnée sur stdout. Le charcode peut être n'importe quelle expression.

3. Expression

Toute expression indépendante est évaluée et attribuée à l'accumulateur (qui est accessible en tant que _). Ainsi, par exemple, 3est une déclaration qui définit l'accumulateur sur 3; _ + 1incrémente l'accumulateur; et _ * Nlit un caractère et multiplie l'accumulateur par son charcode.

Remarque: l'accumulateur est la seule variable pouvant être affectée directement. variables de boucle et Npeut être utilisé dans les calculs mais pas modifié.

L'accumulateur est initialement 0.

Expressions

Une expression peut inclure des littéraux entiers, des variables de boucle ( a-z), _pour l'accumulateur, ainsi que la valeur spéciale N, qui lit un caractère et passe à son code de caractère chaque fois qu'il est utilisé. Remarque: cela signifie que vous ne pouvez lire qu'un seul coup par personnage; la prochaine fois que vous utiliserez N, vous lirez le prochain.

Les opérateurs sont:

• +, une addition
• -, soustraction; négation unaire
• *, multiplication
• /, division entière
• %, modulo
• ^, exponentiation

Les parenthèses peuvent être utilisées pour imposer la priorité des opérations. Tout autre caractère dans une expression est une erreur de syntaxe.

Espaces et commentaires

Les espaces et les lignes vides sont ignorés. Les espaces blancs dans les en-têtes de boucle doivent être exactement comme indiqué, avec un seul espace entre l'en-tête de la boucle et l'accolade ouverte également. Les espaces dans les expressions sont facultatifs.

# commence un commentaire d'une seule ligne.

Entrée sortie

Acc !! attend une seule ligne de caractères en entrée. Chaque caractère saisi peut être extrait en séquence et son code de caractères traité N. Essayer de lire après le dernier caractère de la ligne provoque une erreur. Un caractère peut être généré en transmettant son charcode à l' Writeinstruction.

Interprète

L'interprète (écrit en Python 3) traduit Acc !! code en Python et execc'est tout.

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

Solution

La chute de l'original Acc! étaient des variables de boucle qui restaient accessibles en dehors de leurs boucles. Cela a permis d’enregistrer des copies de l’accumulateur, ce qui a rendu la solution beaucoup trop facile.

Ici, sans ce trou de boucle (désolé), nous n’avons que l’accumulateur pour stocker des données. Pour résoudre cette tâche, nous devons toutefois stocker quatre valeurs arbitrairement grandes. ¹ La solution: entrelacez leurs bits et stockez le numéro de combinaison obtenu dans l'accumulateur. Par exemple, une valeur d'accumulateur de 6437 stockerait les données suivantes (en utilisant le bit de poids faible comme indicateur à un bit):

1100100100101  Binary representation of accumulator
321032103210F  Key

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

Nous pouvons accéder à n’importe quel bit d’un nombre quelconque en divisant l’accumulateur par la puissance appropriée de 2, mod 2. Ceci permet également de définir ou de retourner des bits individuels.

Au niveau macro, l'algorithme boucle sur les nombres unaires de l'entrée. Il lit une valeur dans le nombre 0, puis effectue une passe de l'algorithme de tri à bulles pour le placer dans la position appropriée par rapport aux trois autres nombres. Enfin, il supprime la valeur qui reste dans le nombre 0, car il s’agit du plus petit des quatre et ne peut jamais être le troisième. Lorsque la boucle est terminée, le numéro 1 est le troisième plus grand. Nous ignorons donc les autres et les sortons.

La partie la plus difficile (et la raison pour laquelle j'avais des variables globales de boucle dans la première incarnation) consiste à comparer deux nombres pour savoir s'il faut les échanger. Pour comparer deux bits, nous pouvons transformer une table de vérité en une expression mathématique; ma percée pour Acc !! Nous avons trouvé un algorithme de comparaison allant des bits de poids faible aux bits de poids fort, car sans variables globales, il est impossible de parcourir en boucle les bits d’un nombre de gauche à droite. Le bit de poids faible de l'accumulateur stocke un indicateur qui indique s'il faut échanger les deux nombres actuellement à l'étude.

Je soupçonne que Acc !! Turing-complete, mais je ne suis pas sûr de vouloir prendre la peine de le prouver.

Voici ma solution avec des commentaires:

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

_{¹ Selon la spécification de la question, seules les valeurs inférieures à 1 million doivent être prises en charge. Je suis heureux que personne n’en ait profité pour trouver une solution plus facile, même si je ne suis pas tout à fait sûr de savoir comment vous feriez les comparaisons.}

Picofuck (sûr)

Picofuck est similaire à Smallfuck . Il fonctionne sur une bande binaire qui est non liée à droite et liée à gauche. Il a les commandes suivantes:

• > déplace le pointeur vers la droite

• <déplacez le pointeur à gauche. Si le pointeur tombe de la bande, le programme se termine.

• * retourner le bit au pointeur

• (si le point au pointeur est 0, saute au suivant)

• )ne faites rien - les parenthèses dans Picofuck sont des ifblocs, pas des whileboucles.

• .écrivez sur stdout le bit au pointeur en tant qu'ascii 0ou 1.

• ,lire à partir de stdin jusqu'à ce que nous rencontrions un 0ou 1, et stocker cela dans le bit au pointeur.

Le code Picofuck se termine - une fois que la fin du programme est atteinte, elle continue depuis le début.

De plus, Picofuck interdit les parenthèses imbriquées. Les parenthèses apparaissant dans un programme Picofuck doivent alterner entre (et ), en commençant par (et en terminant par ).

Interprète

Écrit en Python 2.7

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

Solution

Le programme python 2.7 suivant présente ma solution, que vous pouvez trouver ici.

Je pourrai éditer ce post plus tard avec une explication plus détaillée de la façon dont cela fonctionne, mais il s'avère que Picofuck est Turing-complete.

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 - Safe! / Solution fournie

Les bases

Toutes les instructions impliquées ont quatre opérandes d'adresse de mémoire:

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

Où vest la taille de la mémoire dans les quatuors.

Pᵢ, Qᵢ, Rᵢ, SᵢSont signés entiers dans la taille native de votre machine (par exemple 16, 32 ou 64 bits) que nous appellerons mots.

Pour chaque quartet i, l'opération implicite, avec []indication d'indirection, est la suivante:

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

Notez que Subleq est un sous-ensemble de PQRS .

Subleq a été prouvé complet, donc PQRS devrait l'être aussi!

Structure du programme

PQRS définit un en-tête initial comme suit:

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

H₀ H₁ H₂ H₃est toujours la première instruction P₀ Q₀ R₀ S₀. H₀avoir H₃besoin d'être défini au moment du chargement.

PQRS a des E / S rudimentaires, mais suffisantes pour le challenge.

H₄ H₅: au démarrage du programme, il lit un maximum de H₅caractères ASCII à partir de l'entrée standard et enregistre les mots à H₄partir de l' index . H₄et H₅doivent être définis au moment du chargement. Après la lecture, H₅sera défini sur le nombre de caractères lus (et mots sauvegardés).

H₆ H₇: à la fin du programme, à partir de l'index H₆, il affiche tous les octets contenant les H₇mots à la sortie standard en caractères ASCII. H₆et H₇doivent être définis avant la fin du programme. Les octets nuls '\0'dans la sortie seront ignorés.

Résiliation

La résiliation est obtenue en établissant Sᵢdes limites i < 0ou i ≥ v.

Des trucs

Il Pᵢ Qᵢ Rᵢ Sᵢn'est pas nécessaire que les quatuors soient alignés ou séquentiels, des ramifications sont autorisées à des intervalles inférieurs au quartet.

PQRS étant indirectionnel, contrairement à Subleq, la flexibilité est suffisante pour implémenter des sous-programmes.

Le code peut être auto-modifiable!

Interprète

L'interprète est écrit en C:

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

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

// Recommend optimized!
#define OPTIMIZED

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

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

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

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

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

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

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

    // Done
    free(M);

    return 0;
}

Pour l'utiliser, enregistrez ce qui précède sous pqrs.c puis compilez:

gcc -o pqrs pqrs.c

Exemple de programme

Les échos peuvent contenir jusqu'à 40 caractères, précédés de «PQRS-».

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

Pour exécuter, enregistrez ce qui précède sous echo.pqrs, puis:

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

Exécuter les cas de test:

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

Tous les scénarios de test fonctionnent extrêmement rapidement, par exemple <500 ms.

Le défi

Le PQRS pouvant être considéré comme stable, le défi commence le 2015-10-31 13:00 et se termine le 2015-11-08 13:00, au format UTC.

Bonne chance!

Solution

Le langage est assez similaire à celui utilisé dans "Baby" - le premier appareil numérique électronique à programme enregistré au monde. Sur cette page se trouve un programme permettant de trouver le facteur le plus élevé d’un entier en moins de 32 mots de mémoire (CRT!)!

J'ai trouvé que l'écriture de la solution conformément aux spécifications n'était pas compatible avec le système d'exploitation et la machine que j'utilisais (un dérivé de Linux Ubuntu sur un matériel légèrement plus ancien). Il demandait simplement plus de mémoire que disponible et une sauvegarde de base. Sur les systèmes d'exploitation dotés d'une gestion avancée de la mémoire virtuelle ou sur des machines disposant d'au moins 8 Go de mémoire, vous pouvez probablement exécuter la solution selon les spécifications. J'ai fourni les deux solutions.

Il est très difficile de coder directement dans PQRS , ce qui revient à écrire du langage machine, peut-être même du microcode. Au lieu de cela, il est plus facile d’écrire dans une sorte de langage assembleur que de le "compiler". Vous trouverez ci-dessous un langage d'assemblage annoté pour la solution optimisée pour l'exécution des scénarios de test:

; 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

Ce qu'il fait est d'analyser l'entrée en convertissant unaire en binaire, puis un tri en bulle sur les nombres avec les valeurs dans l'ordre décroissant, puis finalement la troisième valeur la plus grande en convertissant le binaire en unaire.

Notez que INC(incrément) est négatif et DEC(décrément) est positif! Où il utilise L#ou L#+1as P-ou Q-OPs, ce qui se passe, c'est qu'il met à jour les pointeurs: incrémentation, décrémentation, permutation, etc. L'assembleur a été compilé à la main dans PQRS en substituant les étiquettes aux décalages. Voici la solution optimisée 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

Le code ci-dessus peut être enregistré challenge-optimized.pqrspour exécuter les cas de test.

Pour être complet, voici la source par spécifications:

; 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

Et solution:

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

Pour exécuter ce qui précède, vous aurez besoin de commenter #define OPTIMIZEDet ajouter #define PER_SPECSdans pqrs.cet recompiler.

C'était un grand défi - j'ai vraiment apprécié l'entraînement mental! M'a ramené à mes vieux jours d'assembleur 6502 ...

Si je devais implémenter PQRS en tant que «vrai» langage de programmation, j'ajouterais probablement des modes supplémentaires pour l'accès direct et doublement indirect, en plus de l'accès indirect, ainsi que de la position relative et de la position absolue, tous deux avec des options d'accès indirect pour la branche!

Zinc, fissuré! par @Zgarb

Egalement disponible sur GitHub .

Vous avez besoin de Dart 1.12 et Pub. Il suffit de lancer pub getpour télécharger la seule dépendance, une bibliothèque d'analyse.

En espérant que cela dure plus de 30 minutes! : O

La langue

Le zinc est axé sur la redéfinition des opérateurs. Vous pouvez facilement redéfinir tous les opérateurs de la langue!

La structure d'un programme de zinc typique ressemble à ceci:

let
<operator overrides>
in <expression>

Il n'y a que deux types de données: les entiers et les ensembles. Il n'existe pas de littéral d'ensemble, et les ensembles vides sont interdits.

Expressions

Les expressions suivantes sont valides dans le zinc:

Littéraux

Le zinc prend en charge tous les littéraux entiers normaux, comme 1et -2.

Variables

Le zinc a des variables (comme la plupart des langues). Pour les référencer, utilisez simplement le nom. Encore comme la plupart des langues!

Cependant, il existe une variable spéciale appelée Squi se comporte un peu comme celle de Pyth Q. Lorsque vous l'utilisez pour la première fois, il lit une ligne à partir d'une entrée standard et l'interprète comme un ensemble de chiffres. Par exemple, la ligne d’entrée 1234231deviendrait l’ensemble {1, 2, 3, 4, 3, 2, 1}.

NOTE IMPORTANTE!!! Dans certains cas, un littéral à la fin d'une substitution d'opérateur est analysé de manière incorrecte. Vous devez donc l'entourer de parenthèses.

Opérations binaires

Les opérations binaires suivantes sont supportées:

• Addition par +: 1+1.
• Soustraction via -: 1-1.
• MULTIPLICATION via *: 2*2.
• Division par /: 4/2.
• Égalité avec =: 3=3.

De plus, l'opération unaire suivante est également prise en charge:

• Longueur avec #: #x.

La préséance est toujours droite associative. Vous pouvez utiliser des parenthèses pour remplacer ceci.

Seules l'égalité et la longueur travaillent sur les décors. Lorsque vous essayez d'obtenir la longueur d'un entier, vous obtenez le nombre de chiffres dans sa représentation sous forme de chaîne.

Compréhension d'ensemble

Afin de manipuler les ensembles, le zinc a des compréhensions définies. Ils ressemblent à ceci:

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

Une clause est une clause When ou une clause Sort.

Une clause quand ressemble ^<expression>. L'expression qui suit le curseur doit donner un entier. L'utilisation de la clause when ne prend que les éléments de l'ensemble pour lesquels expressionest non nul. Dans l'expression, la variable _sera définie sur l'index actuel de l'ensemble. C'est à peu près équivalent à ce Python:

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

Une clause de tri , qui ressemble à $<expression>, trie l'ensemble décroissant par la valeur de <expression>. C'est égal à ce Python:

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

Voici quelques exemples de compréhension:

• Ne prenez que les éléments de jeu ségaux à 5:

  {x:s^x=5}
  

• Triez l'ensemble spar la valeur si ses éléments sont carrés:

  {x:s$x*x}
  

Les dérogations

Les remplacements d’opérateurs vous permettent de redéfinir les opérateurs. Ils ressemblent à ceci:

<operator>=<operator>

ou:

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

Dans le premier cas, vous pouvez définir un opérateur égal à un autre opérateur. Par exemple, je peux définir +de soustraire réellement via:

+=-

En faisant cela, vous pouvez redéfinir un opérateur en opérateur magique . Il y a deux opérateurs de magie:

• joinprend un ensemble et un entier et joint le contenu de cet ensemble. Par exemple, rejoindre {1, 2, 3}avec 4donnera le nombre entier 14243.

• cutprend également un ensemble et un entier et le partitionnera à chaque occurrence de cet entier. Utiliser cutsur {1, 3, 9, 4, 3, 2}et 3créera {{1}, {9, 4}, {2}}... MAIS tous les ensembles à élément unique sont aplatis, le résultat sera donc réel {1, {9, 4}, 2}.

Voici un exemple qui redéfinit l' +opérateur comme suit join:

+=join

Dans ce dernier cas, vous pouvez redéfinir un opérateur à l'expression donnée. À titre d'exemple, cela définit l'opération plus d'ajouter les valeurs, puis d'ajouter 1:

x+y=1+:x+:y

Mais quoi +:? Vous pouvez ajouter les deux points :à un opérateur pour toujours utiliser la version intégrée. Cet exemple utilise le +via intégré +:pour additionner les nombres, puis ajoute un 1 (rappelez-vous que tout est associatif à droite).

Remplacer l'opérateur de longueur ressemble un peu à:

#x=<expression>

Notez que presque toutes les opérations internes (à l'exception de l'égalité) utiliseront cet opérateur de longueur pour déterminer la longueur de l'ensemble. Si vous l'avez défini comme étant:

#x=1

chaque partie du zinc qui fonctionne sur des ensembles sauf =n'agit que sur le premier élément de l'ensemble qui lui a été attribué.

Plusieurs substitutions

Vous pouvez remplacer plusieurs opérateurs en les séparant par des virgules:

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

Impression

Vous ne pouvez rien imprimer directement dans le zinc. Le résultat de l'expression suivante insera imprimé. Les valeurs d'un ensemble seront concaténées avec séparateur. Par exemple, prenez ceci:

let
...
in expr

Si exprest défini {1, 3, {2, 4}}, 1324sera imprimé à l'écran une fois le programme terminé.

Mettre tous ensemble

Voici un programme de zinc simple qui semble s’ajouter 2+2mais qui donne 5 comme résultat:

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

L'interprète

Cela va dans 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());
}

Et cela entre pubspec.yaml:

name: zinc
dependencies:
  parsers: any

Solution envisagée

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

Compass Soup ( cracked by cardboard_box )

Interprète: C ++

Compass Soup est un peu comme une machine de Turing avec une bande infinie en 2 dimensions. Le problème principal est que la mémoire d'instructions et la mémoire de données se trouvent dans le même espace et que le programme génère le contenu complet de cet espace.

Comment ça fonctionne

Un programme est un bloc de texte en 2 dimensions. L'espace programme commence par l'intégralité du code source placé avec le premier caractère à (0,0). Le reste de l'espace de programme est infini et est initialisé avec des caractères nuls (ASCII 0).

Deux indicateurs peuvent se déplacer dans l'espace du programme:

• Le pointeur d'exécution a un emplacement et une direction (nord, sud, est ou ouest). Chaque tick, l'instruction sous le pointeur d'exécution est exécutée, puis le pointeur d'exécution se déplace dans sa direction actuelle. Le pointeur d'exécution commence à se déplacer vers l'est (x positif), à l'emplacement du !personnage ou à (0,0) s'il n'existe pas.
• Le pointeur de données n'a qu'un emplacement. Il est proposé avec les instructions x, X, y, et Y. Cela commence à l'emplacement du @personnage ou à (0,0) s'il n'existe pas.

Contribution

Le contenu de stdin est imprimé dans l’espace programme en commençant par l’emplacement du >caractère ou par (0,0) s’il n’existe pas.

Sortie

Le programme se termine lorsque le pointeur d'exécution est irrémédiablement hors limites. La sortie représente tout le contenu de l’espace de programmation à ce moment. Il est envoyé à stdout et 'result.txt'.

Instructions

• n - redirige le pointeur d'exécution Nord (y négatif)
• e - redirige le pointeur d’exécution Est (x positif)
• s - redirige le pointeur d'exécution Sud (y positif)
• w - redirige le pointeur d’exécution Ouest (x négatif)
• y - déplace le pointeur de données vers le nord (y négatif)
• X - déplace le pointeur de données Est (positif x)
• Y - déplace le pointeur de données vers le sud (y positif)
• x - déplace le pointeur de données Ouest (négatif x)
• p- écrit le caractère suivant rencontré par le pointeur d'exécution au niveau du pointeur de données. Ce personnage n'est pas exécuté comme une instruction.
• j- vérifie le caractère suivant rencontré par le pointeur d'exécution par rapport au caractère situé sous le pointeur de données. Ce personnage n'est pas exécuté comme une instruction. S'ils sont identiques, le pointeur d'exécution saute par-dessus le caractère suivant.
• c - écrit le caractère nul sur le pointeur de données.
• * - point d'arrêt - provoque simplement la rupture de l'interprète.

Tous les autres caractères sont ignorés par le pointeur d'exécution.

Interprète

L'interpréteur prend le fichier source comme argument et entrée sur stdin. Il a un débogueur steppable, que vous pouvez appeler avec une instruction de point d'arrêt dans le code ( *). Lorsqu'il est interrompu, le pointeur d'exécution est représenté par ASCII 178 (bloc ombré plus foncé) et le pointeur de données est représenté par ASCII 177 (bloc ombré plus clair).

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