Déplacer les pommes !

Eh oui, notre machine peut aussi transporter des fruits !

Soit une collection C={pomme, poire, raisin, =, blanc, X }.

Poser plusieurs pommes, poires et raisins consécutivement dans les cases, en prenant soin de les mélanger. Il ne doit pas y avoir de blanc entre les fruits. On termine la série par le signe =. La tête doit commencer sur le signe égal.

Objectif: déplacer toutes les pommes après le signe =.

À la fin, la tête doit s’arrêter sur le signe égal.

Si vous observez la collection, vous verrez le signe X en plus des autres. À quoi peut-il bien servir ? À vous de le découvrir…

Description du fonctionnement (cliquez pour voir, si vraiment vous n’y arrivez pas…)

La tête commence par se rendre à gauche. Si elle trouve une pomme, elle la remplace par un X, puis se déplace vers la droite jusqu’à la première case vide. Là, elle écrit une pomme, puis elle se rend sur le signe =, où elle recommence le processus. Si elle trouve une poire, un raisin ou un X, elle continue vers la gauche. Si elle finit par tomber sur une case vide, elle se déplace vers la droite et supprime tous les X au passage; elle s’arrête sur le signe =.

Compter un petit nombre de pommes !

Soit une collection C={pomme, =, ☐, X, [1-9]}.

Placer entre 1 et 9 pommes consécutivement sur la bande, suivies par le signe “=”. Au début et à la fin du traitement, la tête doit se trouver sur le signe =. À la fin du traitement, le nombre de pommes doit apparaître dans la case qui suit le signe =.

Description du fonctionnement

La tête se rend d’abord à gauche. Si elle tombe sur une pomme, elle la remplace par un X, se rend à droite du signe = et là, elle écrit un 1 si la case est vide, ou, si la case contient déjà un chiffre entre 1 et 8, elle l’incrémente. Puis elle recommence le processus. Si, en allant à gauche, la tête rencontre un X, elle continue à gauche. Si elle rencontre un blanc, elle retourne sur le signe = en transformant au passage tous les X en pommes. Là elle s’arrête. Pour réaliser une incrémentation, il suffit de remplacer le chiffre lu par le chiffre immédiatement supérieur : s’il y a un 1, on met un 2, s’il y a un 2, on met un 3, etc.

Incrémenter un nombre isolé sur la bande

Nous aurons souvent besoin de créer des compteurs. Aussi, ce défi est important, car il est le point de départ de problèmes plus complexes. Soit un entier naturel N posé sur la bande, à raison d’un chiffre par case. La tête est positionnée sur le chiffre des unités, donc le dernier à droite. A la fin du traitement, l’entier doit avoir la valeur N+1. La collection est C={[0-9],☐}. Peu importe l’emplacement d’arrêt.

Vous l’avez compris, la difficulté réside dans le passage des dizaines ! Alors, testez bien des nombres comme 9, 99, 999 ! Ce n’est pas très compliqué car on peut le réaliser dans un seul état !

Description du fonctionnement

Si la tête rencontre un chiffre de 0 à 8, elle le remplace par le chiffre immédiatement plus grand, et on s’arrête. Si elle lit un 9, elle le remplace par un 0, va à gauche et le processus recommence. Si elle lit un blanc, elle place un 1 et on s’arrête. Et voilà…

Incrémenter un nombre qui se trouve immédiatement à droite du signe =

Cette fois la tâche est un peu plus complexe. Souvent, nos compteurs se retrouvent juste à droite du signe “=”; c’est le cas du problème “compteur de pommes” précédent. Notre compteur doit être capable de s’incrémenter derrière le signe =, quel que soit le nombre de pommes. Or, lorsqu’il passe de 9 à 10, de 99 à 100, de 999 à 1000, etc, le nombre ne peut pas s’étendre vers la gauche, à cause du signe “=” et des pommes qui lui barrent le passage.

Votre tâche est de réaliser un programme universel d’incrémentation de nombre qui s’étend vers la droite. Situation de départ: sur le dernier chiffre du nombre. L’emplacement d’arrêt n’a pas d’importance. La collection est C={[0-9],☐}.  Ce programme doit traiter les cas particuliers de décalage vers la droite lorsque le nombre change de classe.  Notre “incrémenteur universel” nécessite seulement 3 états, ce n’est donc pas d’une grande complexité.

Exemples : =9 devient =10, =99 devient =100, =9999 devient =10000 etc, mais =7 devient =8, =299 devient =300…

Note: si vous voulez réutiliser la machine dans un autre programme, il vaut mieux que la position finale de la tête soit toujours la même.  Je suggère de s’arrêter toujours sur le signe =.

Bon courage.

Si vous n’y parvenez pas, voici le listage avec arrêt dans le nombre (spoiler !)

Machine : [IncrémenteurUniversel]
# Incrémente un entier naturel qui se trouve directement derrière le signe “=”.
# Début : sur la donnée la plus à droite
# Fin : sur une des données

État : q0
q0, 0 , 1 , stop
q0, 1 , 2 , stop
q0, 2 , 3 , stop
q0, 3 , 4 , stop
q0, 4 , 5 , stop
q0, 5 , 6 , stop
q0, 6 , 7 , stop
q0, 7 , 8 , stop
q0, 8 , 9 , stop
q0, ☐ , 1 , stop
q0, 9 , 0 , ← , q0
q0, ‘=’ , ‘=’ , → , q1

État : q1
q1, 0 , 1 , → , q2

État : q2
q2, 0 , 0 , → , q2
q2, ☐ , 0 , stop