C'est un drôle d'accident que ce monde ne possède qu'une seule dimension temporelle, mais il ne doit pas nécessairement en être ainsi. Il est facile d'imaginer des mondes avec 2 dimensions temporelles ou plus, et dans ces mondes, vous pourriez construire des ordinateurs et exécuter des logiciels dessus, comme dans celui-ci.
Le système
Voici un système pour exécuter les programmes Brainf * ck en deux dimensions temporelles:
Les deux dimensions temporelles sont x et y. Chaque programme Brainf * ck comprend un demi-programme x et un demi-programme ay, par exemple, un programme
x: +>+
y: [-]
Les deux demi-programmes ont chacun leur propre pointeur de programme, mais ils partagent un seul pointeur de bande (c'est-à-dire qu'ils fonctionnent tous les deux sur la même cellule de la bande).
Le temps est bidimensionnel, il est donc constitué d'une grille de moments:
En se déplaçant le long de la dimension x, le demi-programme x exécute un pas de temps. En se déplaçant le long de la dimension y, le demi-programme y exécute un pas de temps.
Ainsi, par exemple, supposons que la bande commence comme [0] 0 0( []représente le pointeur de bande) et que les programmes x / y sont +et ->-. L'exécution de ce programme ressemblerait à ceci:
x y tape x-action y-action
0 0 [ 0] 0 0 + at 0 - at 0
1 0 [ 1] 0 0 (done) - at 0
0 1 [-1] 0 0 + at 0 move >
1 1 [ 0] 0 0 (done) move >
Notez que, lorsque le temps se déplace dans la direction y, le demi-programme x continue de faire la même chose encore et encore, car son temps ne progresse pas.
La bande à chaque instant inclut l'effet cumulatif de toutes les actions qui y alimentent (chaque action compte une fois). Ainsi, par exemple, la bande au moment (2, 1) contient l'effet cumulatif de:
- l'action x de (0, 0)
- l'action x de (1, 0)
- l'action x de (0, 1)
- l'action x de (1, 1)
- l'action y de (0, 0)
- l'action y de (1, 0)
- l'action y de (2, 0)
Cumul signifie:
- Tous les incréments et décréments d'une somme de cellules ensemble.
- Tous les mouvements vers la gauche (-1) et la droite (+1) vers le pointeur de bande totalisent ensemble.
Les pointeurs d'instructions ne s'accumulent pas. Chaque demi-programme obtient son pointeur d'instruction à partir du moment précédent dans sa dimension. Autrement dit, les pointeurs de programme x progressent uniquement dans la dimension x et les pointeurs de programme y progressent uniquement dans la dimension y. Ainsi, par exemple, dans le programme ( [], +) à partir de [0] 0 0, l'exécution serait
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 0 0 0 + at 0 0 0
1 0 0 0 0 + at 0 2 (from jump) 0
0 1 1 0 0 0 1
1 1 2 0 0 1 (from NO jump) 1
Quelques autres moments de la simulation ci-dessus ( +, ->-) sont:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
2 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 > 0 1
1 1 [ 0] 0 0 > 1 1
2 1 [-1] 0 0 > 1 1
0 2 -1 [ 0] 0 + at 1 - at 1 0 2
1 2 0 1 [ 0] - at 2 1 2
2 2 [-1] 1 0 - at 0 1 2
Les opérateurs Brainf * ck autorisés sont les suivants (ils ont leur signification standard):
+,-: incrémenter, décrémenter;[,]: boucle jusqu'à zéro (le traitement d'un[ou]prend un pas de temps, comme dans Brainf * ck standard);<,>: déplacez-vous vers la gauche / droite sur la bande.
Exemple complexe
Pour le programme ( >, +) commençant par [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > + at 0 0 0
1 0 0 [ 0] 0 + at 1 1 0
0 1 [ 1] 0 0 > 0 1
1 1 1 1 [ 0] 1 1
Pour ( +, -) commençant par [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 0 1
1 1 [ 0] 0 0 1 1
Notez que la bande se termine comme [0] 0 0chacun +et -se produit deux fois, en additionnant à 0.
Pour le programme ( >+, [-]) commençant par [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > 0 0
1 0 0 [ 0] 0 + at 1 1 0
2 0 0 [ 1] 0 2 0
0 1 [ 0] 0 0 > 0 3
1 1 0 0 [ 0] + at 2 1 3
2 1 0 1 [ 1] - at 2 2 1
0 2 [ 0] 0 0 > 0 3
1 2 [ 0] 0 0 + at 0 1 3
2 2 [ 1] 1 0 2 2
Diagramme avec des flèches
Le diagramme ci-dessous montre comment calculer les actions et la bande:
Le puzzle
Écrivez un programme 2D Brainf * ck (avec un demi-programme x et un demi-programme ay) à exécuter sur une bande à 3 cellules, qui remplit les deux conditions suivantes:
- Si la bande commence comme
[0] 0 0, au moment (5, 5), elle a un0dans la cellule zéro. - Si la bande commence comme
[1] 0 0, au moment (5, 5), elle a un0dans la cellule zéro.
Le programme le plus court répondant aux exigences l'emporte.
+et>? Si c'est1 1 [0](assez fou mais c'est ce que la spécification semble suggérer), comment les pointeurs d'instructions se combinent-ils? Si les deux threads sont+et[], alors1 2la bande de données serait[3], mais le deuxième pointeur d'instruction est-il à l'intérieur de la boucle ([]+chemin), ou à l'extérieur ([+]chemin) ou même illégal (+[])?+,>) pour voir si j'obtiens le même résultat que vous.(1,1)travers l'un(1,0)ou l' autre(0,1), mais si un programme commence par>et l'autre commence par+, alors leur ordre relatif est-il important?Réponses:
4 octets au total: (
[-],>)J'ai écrit un brute-forcer pour trouver le plus petit programme de ce type.
Voici les schémas de ce programme en action. Ces grilles sont disposées de manière similaire à la grille de la spécification, avec (0,0) le coin inférieur gauche, le temps x le long de l'axe x et le temps y le long de l'axe y. Le coin supérieur droit contient le résultat.
Tout d'abord, avec une bande de
0 0 0:Maintenant avec une bande de
1 0 0:Il y avait quelques choses qui n'étaient pas clairement expliquées dans la spécification, comme le fait que la bande à 3 cellules s'enroule.
En bonus, voici la visualisation de l' exemple (
>+,[-]):Et l'un des exemples (
>+,+>):Notez que le coin supérieur droit est différent de ce que vous avez répertorié, je pense que c'est une erreur dans votre exemple car mon code correspond à tous les autres exemples que j'ai essayés.
la source