Skip to content

Instantly share code, notes, and snippets.

@TWal

TWal/1.bf

Last active January 2, 2016 06:19
Show Gist options
  • Save TWal/8262259 to your computer and use it in GitHub Desktop.
Save TWal/8262259 to your computer and use it in GitHub Desktop.
Download ZIP
Les qualifications du prologin 2014 répondues brainfuck | 2014 prologin qualifications answered in brainfuck | http://prologin.org/training/challenge/qcm2014 | SimpleBrainfuck : https://github.com/TWal/SimpleBrainfuck
Raw
1.bf
;; +>+<[>>>>>>++++++[>++++++++<-]<+[-<[>++++++++++<-]>[<+>-]+>
;; [<<+> >-],> [<->>+ <-] >[<+>-]<<<->[>>+> +<
;; <<-]> >[<<+ >>-]++ +++ +++++[->>+<[>-] >[
;; << <<< +>> >>>->]<<-<]>[- ]<<<<]
;; >[ -]> [-] <<<<+<<[>>>[<< <<+>>>>
;; -] <-< <-] >>[-<[>+>>>+<< <<-]>[<+
;; >-]>[ <+>>> >+<<<- ]<[ >+<-]<<+[->[ >>[<
;; <<+>> >[>+< -]]>[< +>- ]<<< [>+<
;; -]]>[ <+>-] >-<<-< ]>+ [-]>> +[>>[-]>
;; [< +>- ]<< <[-]]> >>[- ]<[<<<<+
;; >> >>-]<<<]<< <-]>>>+ <[>- <[>>+<<-
;; ]] >>[ <<+ >>-]<[ ++++ +[>+++++
;; +++<- ]>.[- ]<]<[> +<- ]>[>+ ++++++++
;; +<[-> -[>+> >]>[+[ <+> -]>+>> ]<<<<<]>
;; [-]++++++[<++++++++>-]>[<<+>>-]>[<<+>>-]<<]<[.<]++++++++++.
;; Le code est à passer dans un `sed 's/;;.*//'` afin d'enlever tous les commentaires
;; Implémentation similaire de l'algorithme en python :
;; def myMax(a, b):
;; acpy = a
;; bcpy = b
;; while a != 0 and b != 0:
;; a -= 1
;; b -= 1
;; if a != 0:
;; return acpy
;; else:
;; return bcpy
;;
;; def vantardise(deltas, n):
;; currentMax = 0
;; for d in deltas:
;; currentMax = myMax(d, currentMax)
;; return currentMax
;; Schéma de variables :
;; nb temp0 max temp1 currentInt temp2 maxDup cintDup
;; * nb est le nombre de tuyaux à traiter
;; * temp{0,1,2} sont des variables temporaires. temp0 est un flag disant si on doit lire nb ou un tuyau
;; * max est la longueur maximum trouvée
;; * currentInt est la longueur du tuyau courante
;; * maxDup est une variable temporaire contenant la copie de max
;; * cintDup est un variable temporaire contenant la copie de currentInt
;; On met temp0 à 1 (on doit lire nb)
> +
;; Tant qu'il reste des chiffres à traiter, on les traite (on ajoute 1 pour entrer dans la boucle)
< + [
;; On lit l'entrée dans currentInt
;; Le schéma mémoire pour la lecture de nombre est la suivante :
;; output continueReading input ascii0 temp1 temp2 temp3 temp4
;; * output est la sortie
;; * continueReading est un flag disant si on doit continuer de lire
;; * input est la variable où est lue l'input
;; * ascii0 est une variable contenant la valeur ascii de 0
;; * temp{1,2,3,4} sont des variables temporaires
>>>>
;; On met 48 dans ascii0 en utilisant input comme variable temporaire
>>++++++ [- >++++++++ <]
;; while(continueReading)
<+ [
;; continueReading = 0 (on va l'utiliser comme variable temporaire)
-
;; On multiplie output par 10
<[- >++++++++++ <]
>[<+ >-]
;; continueReading = 1
+
;; output += input
>[<<+ >>-]
;; On lit l'input
,
;; input -= ascii0 et temp1 = ascii0
>[<- >>+ <-]
;; On restaure ascii0
>[<+ >-]
;; continueReading = 0 (oui, on l'a mis à 1 un peu plus haut sans l'utiliser, mais j'ai la flemme de corriger ça dans tous les exercices :-D)
<<<-
;; On va vérifier si l'input qu'on a eu est un nombre ou pas
;; On copie input dans temp2 en utilisant temp1 comme variable temporaire
>[>>>+ <+ <<-]
>>[ <<+ >>-]
;; temp1 = 10, while(temp1 != 0)
++++++++++ [
;; temp1 -= 1
-
;; On va faire continueReading += (temp2 == 0)
;; temp3 = 1
>>+
;; On va à temp2
<[ >- ] > [ <
;; Si on est ici, c'est que temp2 = 0
;; continueReading += 1
<<<<+>>>>
;; On sort de la boucle
>->
] <<
;; Et ici on est retourné à temp2
-
;; On va à temp1
<
]
;; temp2 = 0 (par contre, ça peut wrapper, c'est dommage)
>[-]
;; On retourne à continueReading
<<<<
]
;; On vide input (ça peut aussi wrapper)
>[-]
;; On vide ascii 0
>[-]
;; On va à output
<<<
;; Ce code sera réutilisé dans tous les autres algorithmes et ne sera pas re-commenté
;; if(temp0) (on utilise temp1 pour le else)
< +
<< [
;; On bouge currentInt dans nb
>>>[<<<<+ >>>>-]
;; On met temp1 et temp0 à 0
< -
<< -
]
;; if(temp1) donc else
>> [ -
;; on copie max dans maxDup et currentInt dans cintDup en utilisant temp1 comme variable temporaire
<[>>>>+ <<<+ <-]
>[ <+ >-]
>[>>>+ <<<<+ >-]
<[ >+ <-]
;; on effectue la comparaison de max et currentInt
;; temp0 est un flag disant si on doit continuer la boucle de comparaison
<< + [ -
;; if(max !=0 && currentInt != 0) (on utilise temp2 comme variable temporaire pour sortir de la boucle)
> [
>> [
;; Si on arrive ici, c'est qu'on doit continuer, on met temp0 à 1
<<< +
>>>[>+ <-]
] >[<+ >-]
<<<[>+ <-]
] >[<+ >-]
;; max -= 1 et currentInt -= 1
< - >> -
<<<
]
;; Maintenant, soit max est à -1 soit currentInt est à -1
;; On met max à 0 (le + avant est là pour ne pas wrapper)
> + [-]
;; Si on entre dans la boucle, alors currentInt != 0 et donc max < currentInt
>> + [
;; On vide maxDup
>> [-]
;; On bouge cintDup dans maxDup
>[<+ >-]
;; On va dans currentInt et on le vide
<<< [-]
]
;; On vide cintDup
>>> [-]
;; On bouge maxDup dans le maximum max
<[<<<<+ >>>>-]
;; Et on va dans temp1
<<<
]
;; nb -= 1
<<< -
]
;; On affiche max
>>
;; Schéma mémoire de l'affichage :
;; n d newDigit newN
;; * n est le nombre à afficher
;; * d est la base dans laquelle on affiche le nombre (10)
;; * newDigit est le nombre à afficher après division
;; * newN est le nouveau n sur lequel continuer l'algorithme
;; On va vérifier que la variable n'est pas à 0
;; On va utiliser d comme flag. d = 1
>+
;; if(n != 0)
<[
;; d = 0
>-
;; On sort de la boucle en utilisant newDigit
<[>>+ <<-]
] >>[<<+ >>-]
;; if(d != 0)
<[ -
;; On fait newDigit = 48 en utilisant d comme variable temporaire
++++++ [>++++++++;<-]
;; On affiche newDigit et newDigit = 0
>. [-]
;; On retourne à d
<
]
;; On commence la partie intéressante. On décale se décale à droite afin d'avoir une case à 0, et qu'en faisant [.<] on n'aille pas dans des cases à indice négatif
<[>+ <-]
;; while(n != 0)
>[
;; d = 10
>++++++++++
;; divMod
;; Avant : n d 0 0
<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
;; Après : 0 n-n%10 newDigit newN
;; On vide d
>[-]
;; On ajoute 48 à newDigit
++++++ [<++++++++ >-]
;; On le bouge bouge newDigit deux cases à gauche
>[<<+ >>-]
;; Idem pour newN
>[<<+ >>-]
;; On va à newN
<<
]
;; On affiche le tout
<[.<]
;; Ce code pourra varier très légèrement dans les prochains exercices (parfois il n'y aura pas de vérification par rapport à l'affichage de 0, parfois il y aura des instructions qui videront les cases qui seront utilisées par l'algorithme d'affichage)
;; Il ne sera désormais plus commenté, puisque il est quasiment identique à chaque fois
;; Newline
++++++++++ .
Raw
1.sbf
#include(utils.sbf)
#variables(PreList; zero; blah; firstFlag; max)
#variables(List; flag; pnb; zero; max; temp; maxDup; pnbDup)
#variables(Vars; nb; temp0; max; temp1; currentInt; temp2; maxDup; cintDup)
#_variables(Vars; temp0; nb; max; currentInt; temp1; temp2; maxDup; cintDup)
@Vars@nb; =temp0; +
=nb; + [
=currentInt;
@ReadInt@output; _readInt() =output; @Vars@currentInt;
=temp1; +
=temp0; [
_moveTo(currentInt; nb)
=temp1; -
=temp0; -
]
=temp1; [ -
_copy(max; maxDup; temp1)
_copy(currentInt; cintDup; temp1)
=temp0; + [ -
=max; [
=currentInt; [
=temp0; +
_moveTo(currentInt; temp2)
=currentInt;
] _moveTo(temp2; currentInt)
_moveTo(max; temp1)
=max;
] _moveTo(temp1; max)
=max; - =currentInt; -
=temp0;
]
=max; + [-]
=currentInt; + [
=maxDup; [-]
_moveTo(cintDup; maxDup)
=currentInt; [-]
] =cintDup; [-]
_moveTo(maxDup; max)
=temp1;
]
=nb; -
]
=max; _printInt(yes; no; no)
_add(10) .
Raw
2.bf
;; >>>>>+[->>>++++++[>++++++++<-]<+[-<[>++++++++++<-]>[<+>-]+>[<<+>>-],>[<->>+<-]
;; >[< +>-]<<<->[>>+>+<<<-]>>[<<+>>-]++++++++++[->>+<[>-]>[<<<<<+> >>
;; >>-> ]<<-<]>[-]<<<<]>[-]>[-]<<<[<<+>>-]>+<<<<[>>>+>-<<<<-]>>>[ <<<
;; +>>>- ]+>[<<<[>+<-]<+>>+>->-]<[-<[>>+<<-]+>> >]<]<< -<<-
;; >[>[>> ]+>>>+>++>++>>+++++[<<+++>+++++++++ +++ +>-],
;; >+++[<< [>-<-]>>>+<<[>>-<<[<+>-]]<[>+<-]> > >[<<<<
;; [<]>[<+> -]>[>]>>>[-]]<<<<[<]<+>>[>]>[<+> -]>[<+>
;; -]<-]<[-] <[-]<[-]<<[<<]>->+<]>[<+>-]+<-< <<[<< ] >>->>[
;; >>]>>[>>]+ [<<]>>-<[>[>>]>[-[<<<[<<]<<[<< ]>[<< <[ <<]<+
;; >>+>[>>]>-] <<<[<<]<[>>>[>>]>+<<<[<<]<-]> >[>[> >]+ >>-[
;; +<<[<<]>>-]< <[<<]>-]>[>>]>>[>>]>>[>>]>[< +>-]> -<]+ >[<
;; <<<[<<]<<[<<] +<<-[+>>[>>]<<-]>>[>>]>>[>> ]>>-] <[
;; <+>-]]<[>+<-]> >[<<<<[<<]<<[<<]+>>-[+<<[< <]>>-]>>[>>]>>
;; [>>]>>-]<<+<<[< <]>-]<<<[<<]+[-<<[<<]>+>[> >]+<<]>>[-]>[-]
;; >[-]>[-]>[-]<<<< +<[>-<[>>+<<-]]>>[<<+>>-]<[ +++++[>++++++++<-
;; ]>.[-]<]<[>+<-]>[>[-]>[ -]>[-]>[-]>[-]<<<<++++++++++<
;; [->-[>+>>]>[+[<+>-]>+>> ]<<<<<]>[-]++++++[<++++++++>-
;; ]>[<<+>>-]>[<<+>>-]<<]<[.<]++++++++++.[-]>+<[<<+>>----->>>-[<<<->>]+>+<---<++]
;; Le code est à passer dans un `sed 's/;;.*//'` afin d'enlever tous les commentaires
;; Implémentation similaire de l'algorithme en python :
;; def sabotage(deltas, n, directions, directions_len):
;; pos = 0
;; for d in directions:
;; if d == "A":
;; pos += 1
;; if pos == n:
;; pos = 0
;; elif d == "R":
;; if pos == 0:
;; pos = n
;; pos -= 1
;; elif d == "T":
;; for i in xrange(deltas[pos]):
;; pos += 1
;; if pos == n:
;; pos = 0
;; return pos + 1
;; _ _ _ _
;; | | ___ ___| |_ _ _ _ __ ___ __| | ___ ___ | |_ _ _ _ _ __ _ _ ___ __
;; | | / _ \/ __| __| | | | '__/ _ \ / _` |/ _ \/ __| | __| | | | | | |/ _` | | | \ \/ /
;; | |__| __/ (__| |_| |_| | | | __/ | (_| | __/\__ \ | |_| |_| | |_| | (_| | |_| |> <
;; |_____\___|\___|\__|\__,_|_| \___| \__,_|\___||___/ \__|\__,_|\__, |\__,_|\__,_/_/\_\
;; |___/
;; Schéma mémoire avant le tableau des tuyaux :
;; temp zero counter firstFlag
;; * temp est une variable temporaire
;; * zero est une variable à zéro pour parcourir le tableau
;; * counter est une variable temporaire
;; * firstFlag est le premier flag du tableau
;; Schéma mémoire d'une élément du tableau des tuyaux :
;; flag pipe nflag
;; * flag est un flag utilisé pour se souvenir de notre position dans le tableau
;; * pipe est la longueur du tuyau
;; * nflag est le flag du tuyau suivant
;; On lit la longueur des tuyaux
;; Schéma mémoire de lecture des tuyaux :
;; flag output nflagnb temp1 temp2
;; * flag est le flag courant de la liste
;; * output est la sortie de la lecture
;; * nflagnb est le nombre d'entrées restant à lire, et le prochain flag de la liste
;; * temp1 et temp2 sont des variables temporaires
>>>
;; while(nflag != 0)
>>+ [ -
;; On lit un nombre dans temp1
>
>>++++++ [- >++++++++ <]
<+ [
-
<[- >++++++++++ <]
>[<+ >-]
+
>[<<+ >>-]
,
>[<- >>+ <-]
>[<+ >-]
<<<-
>[>>>+ <+ <<-]
>>[ <<+ >>-]
++++++++++ [ -
>>+
<[ >- ] > [ <
<<<<+
>>>>>->
] <<
-
<
]
>[-]
<<<<
]
>[-]
>[-]
;; On bouge temp1 dans output
<<<[<<+ >>-]
;; On va vérifier si on nous a donné le nombre de tuyaux ou si on nous a donné une longueur de tuyau
;; On nous a donné le nombre de tuyaux si flag = 0
;; On va faire temp2 = !flag
;; On va utiliser temp1 pour sortir de la boucle
;; temp2 = 1
>+
;; if(flag != 0)
<<<<[
;; temp1 = 1
>>>+
;; temp2 = 0
>-
;; flag = 0
<<<<-
]
;; On restaure flag
>>>[<<<+ >>>-]
;; On va faire un if(temp2), et utiliser temp1 pour le else
;; temp1 = 1
+
;; if(temp2)
>[
;; On bouge output dans nflagnb
<<<[>+ <-]
;; Quelque chose de spécifique à cet exercice : on incrément nflagnb pour qu'on lise aussi le nombre d'instructions
>+
;; flag = 1
<<+
;; temp1 = 0
>>>-
;; temp2 = 0
>-
]
;; if(temp1) donc else
<[ -
;; On décale nflagnb deux cases à droite
<[
>>+
<<-
]
;; nouveauFlag = 1
+
;; on va au nouveau temp1 (deux cases à droite de temp1)
>>>
]
;; On va à nflagnb
<
]
;; On met à 0 le dernier flag il est en trop
<<- <<
;; Spécifique à cet exercice : on enlève encore un autre flag car on a aussi lu le nombre d'instructions à lire
-
;; Le code pour lire une liste d'entier ne sera pas commenté dans les autres exercices car le code sera indentique (mis à part ce qui a été marqué comme spécifique à cet exercice)
;; _ _ _ _ _ _ _
;; | | ___ ___| |_ _ _ _ __ ___ __| | ___ ___ (_)_ __ ___| |_ _ __ _ _ ___| |_(_) ___ _ __ ___
;; | | / _ \/ __| __| | | | '__/ _ \ / _` |/ _ \/ __| | | '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \/ __|
;; | |__| __/ (__| |_| |_| | | | __/ | (_| | __/\__ \ | | | | \__ \ |_| | | |_| | (__| |_| | (_) | | | \__ \
;; |_____\___|\___|\__|\__,_|_| \___| \__,_|\___||___/ |_|_| |_|___/\__|_| \__,_|\___|\__|_|\___/|_| |_|___/
;; Schéma mémoire avant la liste des instructions :
;; zero nb firstFlag
;; * zero est une variable toujours à 0
;; * nb est le nombre d'instructions à lire
;; * firstFlag est le premier flag du tableau
;; Schéma mémoire de la lecture des instructions :
;; flag instr zero1 zero2 d0 d1 d2 input counter nflag
;; * flag est le flag du tableau
;; * instr est le code de l'instructions qu'on est en train de lire
;; * zero1 et zero2 sont des variables à 0 (mais parfois à 1)
;; * d0, d1, d2 sont des variables respectivement à 2, 17, et 65, puisque 65 = 'A', 65+17 = 'R' et 65+17+2 = 'T'. "dn" désignera par la suite une des trois variables
;; * input est la variable où est stoquée l'entrée
;; * counter est une variable utilisée pour savoir à quel dn on est
;; * nflag est un flag utilisé pour faire les "sinon"
> [
;; On va à l'instruction que l'on doit lire
> [>>]
;; On met son flag à 1
+
;; on met zero2 à 1, d0, d1 et d2 aux valeurs qu'elles doivent avoir (on utilise input comme variable temporaire)
>>> + > ++ > ++
>> +++++ [< +++++++++++++ < +++ >> -]
;; On lit l'input
,
;; >>> On exécute 3 fois la boucle de lecture d'instruction (3 va dans la variable counter) <<<
> +++ [
;; On enlève à input le dn au quel on est
<< [> - < -]
;; nflag = (input == 0) (on utilise dn comme variable temporaire)j
;; nflag = 1
>>> +
;; if(input)
<< [
;; nflag = 0
>> -
;; On sort de la boucle en utilisant dn
<<[<+ >-]
] <[>+ <-]
;; if(nflag) (if(input == 0)) alors on met zero2 0 à zero1 à 1
>>> [
;; On va à zero1
<<<< [<]
;; On bouge zero2 dans zero1
>[<+ >-]
;; On retourne là où on était
> [>]
;; nflag = 0
>>> [-]
]
;; >>> instr += 1 <<<
;; On va à zero
<<<< [<]
;; On augmente instr
< +
;; On retourne là où on était
>> [>]
;; >>> Shift <<<
;; On bouge input à dn et counter à input, et on se décale
>[<+ >-]
>[<+ >-]
<-
]
;; >>> On fait le ménage <<<
;; input = 0
< [-]
;; zero2 = 0
< [-]
;; zero1 = 0
< [-]
;; On va au début de la liste
<< [<<]
;; On enlève 1 à nb et on rajoute 1 à firstFlag, pour conserver nb
>> +
< -
]
;; On bouge firstFlag dans nb
>[<+ >-]
;; On enlève 1 à nb pour avoir le bon nombre d'entrées, et on met firstFlag à 1
< - > +
;; _____ _ _ _ _ _ _ _
;; | ____|_ _____ ___ _ _| |_(_) ___ _ __ __| | ___ ___ (_)_ __ ___| |_ _ __ _ _ ___| |_(_) ___ _ __ ___
;; | _| \ \/ / _ \/ __| | | | __| |/ _ \| '_ \ / _` |/ _ \/ __| | | '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \/ __|
;; | |___ > < __/ (__| |_| | |_| | (_) | | | | | (_| | __/\__ \ | | | | \__ \ |_| | | |_| | (__| |_| | (_) | | | \__ \
;; |_____/_/\_\___|\___|\__,_|\__|_|\___/|_| |_| \__,_|\___||___/ |_|_| |_|___/\__|_| \__,_|\___|\__|_|\___/|_| |_|___/
;; On met le premier flag du tableau des tuyaux à 0
<< <<[<<] >> -
>>[>>]
;; On met le flag après la dernière instruction à 1 (dans le code qui suit, on suppose que le flag de l'instruction suivante est à 1)
>>[>>]+[<<]
;; On met le premier flag à 0
>> -
;; Tant qu'il reste des instructions à traiter, on les traite
;; while(nb != 0)
< [
;; On va à l'instruction courante
> [>>]
;; >>> switch(instr) <<<
> [
;; Ici, instr > 0
- [
;; Ici, instr > 1
;; >>> On suppose que instr == 2 et on exécute l'opération T <<<
;; On va dans le tableau des tuyaux
<<<[<<]<<[<<]
;; >>> On copie la valeur du tuyaux dans counter (en utilisant temp comme variable temporaire) <<<
;; while(pipe != 0)
> [
;; temp += 1
<<<[<<]
< +
;; counter += 1
>> +
;; pipe -= 1
>[>>]
> -
]
<<<[<<]
;; while(temp != 0)
< [
;; pipe += 1
>>>[>>]
> +
;; temp -= 1
<<<[<<]
< -
]
;; >>> On décale le flag du tableau counter fois <<<
;; while(counter != 0)
>> [
;; On va au flag courant
>[>>]
;; On le décale
+>>- [ +
;; Si on est ici, c'est que le flag suivant était déjà à 0, ça veut dire qu'on est au bout du tableau
;; On revient au tout début du tableau et on met le premier flag à 0
<<[<<]
>> -
]
;; counter -= 1
<<[<<]
> -
]
;; On retourne dans la liste d'instructions
>[>>] >>[>>]>>[>>]
;; On utilise flag comme variable temporaire pour sortir de la condition, et on met nflag à 0
>[<+ >-] > - <
]
;; Si nflag != 0 alors on doit exécuter R. Le code du décalage du flag est quasiment à celui dans l'exécution de l'opération T
+ > [
;; On va dans la liste des tuyaux
<<<<[<<]<<[<<]
;; On décale le flag
+<<- [ +
>>[>>] <<-
]
;; On revient dans la liste des instructions
>>[>>]>>[>>]
;; On met nflag à 0
>> -
]
;; On utilise flag comme variable temporaire pour sortir de la boucle
<[<+ >-]
] <[>+ <-]
;; Si nflag est à 1, alors c'est que instr == 0. Le code est quasiment identique à l'exécution de l'opération R
>> [
;; On va dans la liste des tuyaux
<<<<[<<]<<[<<]
;; On décale le flag
+>>- [ +
<<[<<] >> -
]
;; On revient dans la liste des instructions
>>[>>]>>[>>]
;; On met nflag à 0
>> -
]
;; Puis on le remet à 1 (sa valeur initiale avant le switch)
+
;; On passe à l'instruction suivante (flag = 1 et nflag = 0)
<< + >> -
;; On retourne au début du tableau et on fait nb -= 1
<< << [<<]
> -
]
;; On va décaler le flag en incrémentant counter jusqu'à qu'on atteigne un flag déjà à 0
<<<[<<]
+ [ -
<<[<<]
;; counter += 1
> +
>[>>]
;; On va au flag suivant
+ <<
]
;; On va à counter
>
;; Et on l'affiche
>[-]>[-]<<
>+ <[
>-
<[>>+ <<-]
] >>[<<+ >>-]
<[ -
++++++ [>++++++++;<-]
>. [-]
<]
<[>+ <-]
>[
>[-]>[-]>[-]>[-]>[-]<<<<<
>++++++++++
<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
>[-] ++++++ [<++++++++ >-]
>[<<+ >>-]
>[<<+ >>-]
<<]
<[.<]
;; Newline
++++++++++ .
Raw
2.sbf
#include(utils.sbf)
#variables(PrePipe; temp; zero; counter; firstFlag)
#variables(Pipe; flag; pipe; nflag)
#variables(PreInstr; zero; nb; firstFlag)
#variables(Instr; flag; instr; nflag)
#variables(InstrDec; flag; instr; zero1; zero2; d0; d1; d2; input; counter; nflag)
#variables(InstrDecFinal; flag; instr; zero1; zero2; input; counter)
#_ -----------------------------------------------------------
#_ -------------------INSTRUCTION READING---------------------
#_ -----------------------------------------------------------
#_ A R T
#_ 65 82 84
#_ 65 17 2
#_ 0 1 2
#_ d2 d1 d0
@PrePipe@temp;
=firstFlag;
_readIntList(1)
@PreInstr@zero;
-
=nb; [
=firstFlag; [>>]
@InstrDec@flag; +
=zero2; + =d0; ++ =d1; ++
=input; _add(5) [=d2; _add(13) =d1; _add(3) =input; -]
=input; ,
=counter; _add(3) [
=d2; [=input; - =d2; -]
=nflag; +
#_ nflag = !input
=input; [
=nflag; -
_moveTo(input; d2)
=input;
] _moveTo(d2; input)
#_ if nflag then zero2 -> zero1
=nflag; [
=d1; [<]
@InstrDec@zero1;
_moveTo(zero2; zero1)
=d0; [>]
@InstrDec@d2;
=nflag; [-]
]
#_ ++instr
=d1; [<]
@InstrDec@zero1;
=instr; +
=zero2; [>]
@InstrDec@d2;
#_ Shift
_moveTo(input; d2)
_moveTo(counter; input)
=counter; <-
]
@InstrDecFinal@counter;
=input; [-]
=zero2; [-]
=zero1; [-]
=flag; [<<]
@PreInstr@zero;
=firstFlag; +
=nb; -
]
_moveTo(firstFlag; nb)
=nb; - =firstFlag; +
#macro(pipeToInstr;;
=flag; >>[>>]>>[>>]
@Instr@flag;
)
#macro(instrToPipe;;
=flag; <<[<<]<<[<<]
@Pipe@flag;
)
#macro(pipeToPrepipe;;
=flag; <<[<<]
@PrePipe@zero;
)
#macro(pipeToPreinstr;;
=flag; >>[>>]
@PreInstr@zero;
)
#macro(prepipeToPipe;;
=firstFlag; [>>]
@Pipe@flag;
)
#macro(preinstrToPipe;;
=zero; <<[<<]
@Pipe@flag;
)
#_ -----------------------------------------------------------
#_ -------------------INSTRUCTION EXECUTION-------------------
#_ -----------------------------------------------------------
=zero; <<[<<] @PrePipe@zero;
=firstFlag; - >>[>>] @PreInstr@zero;
>>[>>]+[<<]
=firstFlag; -
=nb; [
=firstFlag; [>>]
@Instr@flag;
=instr; [
#_ instr > 0
- [
#_ instr > 1
#_ EXEC T
_instrToPipe()
#_ copy the current pipe value to PrePipe@counter
=pipe; [
_pipeToPrepipe()
=temp; + =counter; +
_prepipeToPipe()
=pipe; -
]
_pipeToPrepipe()
=temp; [
_prepipeToPipe()
=pipe; +
_pipeToPrepipe()
=temp; -
]
=counter; [
_prepipeToPipe()
=flag; +>>- [ +
_pipeToPrepipe()
=firstFlag; -
@Pipe@flag;
]
_pipeToPrepipe()
=counter; -
]
_prepipeToPipe() _pipeToInstr()
_moveTo(instr; flag) =nflag; - =instr;
] + =nflag; [
#_ instr == 1
#_ EXEC R
_instrToPipe()
=flag; +<<- [ + #_ if I enter in this loop, then I'm at PrePipe@zero
_pipeToPreinstr()
=zero; <<-
@Pipe@flag;
]
_pipeToInstr()
=nflag; -
] _moveTo(instr; flag) =instr;
] _moveTo(flag; instr)
=nflag; [
#_ instr == 0
#_ EXEC A
_instrToPipe()
=flag; +>>- [ + #_ if I enter in this loop, then I'm at PreInstr@zero
_pipeToPrepipe()
=firstFlag; -
@Pipe@flag;
]
_pipeToInstr()
=nflag;
-
] +
=flag; + =nflag; -
=flag; << [<<]
@PreInstr@zero;
=nb; -
]
_preinstrToPipe()
=flag; + [ -
<<[<<] @PrePipe@zero;
=counter; +
_prepipeToPipe()
=flag; + <<
]
@PrePipe@zero;
=counter; _printInt(yes; yes; no)
#_ \n
_add(10) .
Raw
3.bf
;; >>>>+>+>+<<[ >>>>>>>+++++ +[>++++++++<
;; -]<+[-<[>+++ +++ +++ +<-]>[<+>-]+
;; >[<<+>>-],>[ <- >> +<-]>[<+>-]<
;; <<->[>>+>+<< < -]>> [ <<+>>-]+++++
;; +++++[->>+<[ > -]>[ < <<<<+>>>>>->
;; ]<<-<]>[-]<< < <]>[ - ]>[-]<<<<<+<
;; <[>>>>[<<<<< <+ >+ >>>>>-]<<-<<
;; -]>>[<<<<<[> >>+ >>> >+<<<<<<<-]>
;; >>[<<<+>>>-] <<<+>[>>+>>> >>+<<<<<<<-]
;;
;; >>[<<+>>-]>> >>[->-[>+>]> [+[<+>-]>>]<
;; <<<]>[-]>[<< +>>-]<<<<<[> >>[ <<<
;; <<<<<<+>>>>> >>>+>-]<<-<- ]> [-
;; >>[<<+>>>+<- ]<<[>>+<<-]+ [ ->>[ <
;; [<+>[<<+>>-] ]<<[>>+<<-]> > >[<< <
;; +>>>-]]<<<[> >>+<<<-]>>-> - <<]> >
;; +[-]<+[<<<<< <<+>>>>>>>[- ]] <]
;; >>>[<<+>>-]< <<]<<<-]<<<< [>> >>+
;; <<<<-]>>>>>> >>[<<<+>>>-] <<<<<[-]+<[-
;;
;; ]<[-[>>-<<[- ]]>>[>>>+[-< <[>[>+<[>>+<
;; <-] ]>> [<< +>> -]< <<[
;; >> >+ << <- ]] >>
;; > [<<< + > >>-] < < -<-> >
;; ] <<+[ - ] +>+[ < - >[-] ]
;; < [<<< < + >>>> - ] <-]< <
;; [- ]] >> [< << +>
;; >>- ]<< +++ +++ [<+ +++
;; ++++>-]<.>++ ++++++++.[-] >+<[+[+<<+]]
;; Le code est à passer dans un `sed 's/;;.*//'` afin d'enlever tous les commentaires
;; Implémentation similaire de l'algorithme en python :
;; # Retourne (a > b)
;; def gt(a, b):
;; while a != 0 and b != 0:
;; a -= 1
;; b -= 1
;; return a != 0
;;
;; def croissance(deltas, n):
;; deltas = [(x+y)%n for (x, y) in zip(deltas, xrange(n))]
;; bad = 0
;; for i in xrange(n-1):
;; if gt(deltas[i], deltas[i+1]):
;; bad += 1
;;
;; if bad > 1:
;; return 0
;; elif bad == 1:
;; if not gt(deltas[-1], deltas[0]):
;; return 1
;; else:
;; return 0
;; else:
;; return 1
;; Schéma mémoire :
;; firstVal badnb idNb nbCopy nb temp0 temp1 temp2 prevValue value vcopy
;; * firstVal contient la première valeur donnée
;; * badnb contient le nombre de comparaisons mauvaises
;; * idNb contient l'indice de l'élément courant
;; * nbCopy contient le nombre d'éléments (reste constant)
;; * nb contient le nombre d'éléments restant à traiter
;; * temp0 est une variable temporaire. Elle est au début à 1 jusqu'à que nb soit lu
;; * temp1 est une variable temporaire. Elle est au début à 1 jusqu'à que le premier tuyau soit lu
;; * temp2 est une variable temporaire
;; * prevValue est la longueur du tuyau précédent
;; * value est la longueur du tuyau courant
;; * vcopy est une variable temporaire contenant une copie de value
;; On met temp0 et temp1 à 1
>>>>> + > +
;; Tant qu'on a des entrées à traiter
<< + [
;; On lit le nombre courant dans value
>>>>>
>>++++++ [- >++++++++ <]
<+ [
-
<[- >++++++++++ <]
>[<+ >-]
+
>[<<+ >>-]
,
>[<- >>+ <-]
>[<+ >-]
<<<-
>[>>>+ <+ <<-]
>>[ <<+ >>-]
++++++++++ [ -
>>+
<[ >- ] > [ <
<<<<+
>>>>>->
] <<
-
<]
>[-]
<<<<]
>[-]
>[-]
<<<
;; temp2 = 1
<< +
;; si temp0 != 0, alors on vient de lire nb
<< [
;; On bouge value dans nb et nbCopy
>>>> [<<<<<< + > + >>>>> -]
;; temp2 = 0 et temp0 = 0
<< -
<< -
]
;; si temp2 != 0 alors on doit traiter une longueur de tuyau
>> [
;; On ajoute idNb dans value en utilisant temp0 comme variable temporaire
<<<<<[>>>>>>>+ <<<<+ <<<-]
>>>[ <<<+ >>>-]
;; idNb += 1
<<< +
;; On copie nbCopy dans vcopy en utilisant temp0 comme variable temporaire
>[>>>>>>>+ <<<<<+ <<-]
>>[ <<+ >>-]
;; On mod value par vcopy
>>>> [->-[>+>]>[+[-<+>]>>]<<<<]
>[-]>[<<+>>-]<<
;; Maintenant, value = value % nbCopy
;; Si temp1 != 0 alors on vient d'obtenir la première valeur
<<< [
;; On bouge value dans prevValue et firstVal
>>> [< + <<<<<<<< + >>>>>>>>> -]
;; temp2 = 0 et temp1 = 0
<< -
< -
]
;; Si temp2 != 0, alors on doit effectuer une comparaison
> [ -
;; On copie value dans vcopy en utilisant temp2 comme variable temporaire
>>[>+ <<<+ >>-]
<<[ >>+ <<-]
;; On compare value en prevValue
;; temp2 est un flag disant si on a besoin de continuer la boucle de comparaisons
+ [ -
>> [
< [
;; Si on arrive ici, c'est qu'on doit continuer, on met alors temp2 à 1
< +
;; Et on sort des deux boucles en utilisant temp1 comme variable temporaire
>[<<+ >>-]
] <<[>>+ <<-]
>>>[<<<+ >>>-]
] <<<[>>>+ <<<-]
;; value -= 1 et prevValue -= 1
>>> - < -
<
]
;; On vide value (le + est là pour ne pas wrapper)
>> + [-]
;; if(prevValue != 0) donc prevValue > value
< + [
;; badNb += 1
<<<<<<< +
;; On vide prevValue
>>>>>>> [-]
]
<
]
;; On bouge vcopy dans prevValue
>>>[<<+ >>-]
<<<
]
;; nb -= 1
<<< -
]
;; Changement de schéma mémoire :
;; output badnb temp nflag firstVal lastVal temp2 temp3
;; * output est la sortie (0 ou 1)
;; * badnb est la même chose quand dans le schéma précédent
;; * temp est une variable temporaire
;; * nflag est un flag servant à effectuer le switch
;; * firstVal est la première valeur de la liste donnée
;; * lastVal est la dernière valeur de la liste donnée
;; * temp2 et temp3 sont des variables temporaires
;; Réorganisation de la mémoire
;; On bouge l'ancien firstVal dans le nouveau firstVal
<<<<[>>>>+ <<<<-]
;; On bouge l'ancien prevValue dans le nouveau lastValue
>>>>>>>>[<<<+ >>>-]
;; nflag = 1
<<<<< [-] +
;; temp = 0
< [-]
;; switch(badnb)
< [
;; Ici, badnb > 0
- [
;; Ici, badnb > 1
;; On laisse output à 0
;; on met nflag à 0 et badnb aussi
>> -
<< [-]
] >> [
;; Ici, badnb == 1
;; On doit vérifier si lastVal <= firstVal (on fait en réalité !(lastVal > firstVal))
;; La comparaison est similaire à celle du dessus : on utilise temp2 comme flag pour continuer, et temp3 pour sortir des boucles
>>> + [ -
<< [
> [
> +
<[>>+ <<-]
] >>[<<+ >>-]
<<<[>>>+ <<<-]
] >>>[<<<+ >>>-]
<<< - > -
>
]
;; firstVal = 1 (on va l'utiliser comme flag pour faire un else
<< + [-] +
;; if(lastVal) (donc if(lastVal > firstVal))
> + [
;; firstVal = 0
< -
;; lastVal = 0
> [-]
]
;; if(firstVal) (donc else)
< [
;; output = 1
<<<< +
;; firstVal = 0
>>>> -
]
;; nflag = 0
< -
]
;; badnb = 0
<< [-]
]
;; Si nflag != 0 alors badnb == 0
>> [
;; On met output à 1
<<< +
;; Et nflag à 0
>>> -
]
;; On ajoute 48 à output
<< ++++++ [< ++++++++ > -]
;; On l'affiche
< .
;; Newline
> ++++++++++ .
Raw
3.sbf
#include(utils.sbf)
#variables(Vars; firstVal; badnb; idNb; nbCopy; nb; temp0; temp1; temp2; prevValue; value; vcopy)
@Vars@firstVal;
=temp0; + =temp1; +
=nb; + [
=value;
@ReadInt@output; _readInt() =output; @Vars@value;
=temp2; +
#_ if nb was given
=temp0; [
=value; [=nbCopy; + =nb; + =value; -]
=temp2; -
=temp0; -
]
=temp2; [
#_ add the index
_copy(idNb; value; temp0)
=idNb; +
#_ mod nb
_copy(nbCopy; vcopy; temp0)
=value; _mod()
>[-]>[<<+>>-]<<
#_ if the first value was given
=temp1; [
=value; [=prevValue; + =firstVal; + =value; -]
=temp2; -
=temp1; -
]
#_ if we actually have to check a value
=temp2; [ -
#_ temp2 = continue
_copy(value; vcopy; temp2)
=temp2; + [ -
=value; [
=prevValue; [
=temp2; +
_moveTo(prevValue; temp1)
=prevValue;
] _moveTo(temp1; prevValue)
_moveTo(value; temp1)
=value;
] _moveTo(temp1; value)
=value; - =prevValue; -
=temp2;
]
=value; + [-]
=prevValue; + [
#_ value < prevValue
=badnb; +
=prevValue; [-]
]
=temp2;
]
_moveTo(vcopy; prevValue)
=temp2;
]
=nb; -
]
_moveTo(firstVal; nb) _moveTo(prevValue; temp0)
=nbCopy; [-] + =idNb; [-]
=badnb;
#variables(Vars2; output; badnb; temp; nflag; firstVal; lastVal; temp2; temp3)
@Vars2@badnb;
=badnb; [
#_ badnb > 0
- [
#_ badnb > 1
=nflag; -
=badnb; [-]
] =nflag; [
#_ badnb == 1
#_ Check if lastVal <= firstVal
=temp2; + [ -
=firstVal; [
=lastVal; [
=temp2; +
_moveTo(lastVal; temp3)
=lastVal;
] _moveTo(temp3; lastVal)
_moveTo(firstVal; temp3)
=firstVal;
] _moveTo(temp3; firstVal)
=firstVal; - =lastVal; -
=temp2;
]
=firstVal; + [-] +
=lastVal; + [
=firstVal; -
=lastVal; [-]
]
=firstVal; [
=output; +
=firstVal; -
]
=nflag; -
]
=badnb; [-]
]
=nflag; [
#_ badnb == 0
=output; +
=nflag; -
]
=badnb; _add(6) [=output; _add(8) =badnb; -]
=output; . =badnb; _add(10) .
Raw
4.bf
;; >>>>+[->>>++++++[>++++++++<-]<+[-<[>++++++++++<-]>[<+>-]+>[<<+>>-],>[<->>+<-]>[<+>-]<<<->[>>+>+<<<-]>>[<<+>>-]+++
;; +++++++[->>+<[>-]>[<<<<<+>>>>>->]<<-<]>[-]<<<<]>[-]>[-]<<<[<<+>>-]>+<<<<[>>>+>-<<<<-]>>>[<<<+>>>-]+>[<<<[>+<-]<+>
;; >>->-]<[-<[>>+<<-]+>>>]<]<<-<<[<<]>>[->>[>>]>>>>>+<<<<+<<<[<<]+>>]>>>++++++[<++++++++>-]<.[-]+<-[>>>>>>>+[<<<<<+>
;; >>>>>+> >-<<[<<<<<+<[>-<[<<<+>>>-]]<<<[>>>+<<<-]>>>>+>>>>>>[>>>]>--[<<<<[<<<]<<<->>>>>>[>>>]>++++[<+>-]<--
;; -->]<++ +[>+<-]<<<[<<<] +<<<[>>+>->>>[<<<<->>>>[>>>]>>[-]<+[-]<<<<-< < <[<<<]<<
;; <<+>>>> >>>[<<<+>>>-]] <<<[>> >+<<<-]<[>>>>>[-]-<<-<<<-]<<[- ] ]>>>[<<<
;; <->>>>- >>>[>>>]>>[>+ >>+<<< -]>[<+>-]+<<[-[>>>>[<<<<<<<<[ < <<]<+>>>
;; >[>>>]>> >>>-]<<<<<<<< [<<<]<< <<<<<<<[<<]>>->>[>>]>>>>>>[< < <<<<<<[<
;; <]+>>->> [>>]> >>>>>-] <<<<<<<< [<<]>[>[>>] >>>> >> +<<+<<<<
;; <<[<<]>- ]>[ >>]>>>>[<<<<<<[<<]>+>[ >>]>>>>-]< <<< << [<<]<<[>
;; >>>[>>]> > >>>>+<<<<<<<<[<<] +<<-<<]>> +[ >> ]>>>>>>[
;; >>>>[>>> ]>>>>>+<<<<<<<<[<< <]<-]<[>+>>>>[>>> ]> >> >>>+<<<<
;; <<<<<[<< <]<< -]>[<+>-]>>>>[>>> ]>>>>>[->-[ >+ >] >[+[<+>-
;; ]>>]<<<< ]>[-] >[<<+>>-]<<<<<<[ <+>-]>>-<< ]+ >> [>>[<<->
;; >[<+>-]] <[>+< - ]<[<<<<<<[<<<]<<[>+>> >>[>>>]>>> >> +< <<<<<<<[
;; <<<]<<-] >[<+> - ]>>>>[>>>]>>>-]>>-<< ]<<[<+>-]] <[>+ <- ]> >>[>>+<<
;; -<<<<<<[ <<<]<<[>+>>>>[>>>] >>>>+<<<<<< <[<< < ]<<-]>[
;; <+>-]>>> > [>>>]>>>>[<+>>-<- ]>[<<[>>+<<- ] >>[<+>-
;; ]]<[>+<- ]< [-]]<<<+>>>>->[<<<<<[<<<]<+>>>>[>>>]> >-]<<<<
;; <[<<<]<< <<< [>>>>->+<<<<<-]>>+>>>>-<<[<<->>>[<<<<< +> >>>+>-]
;; <[>>+<<-]]>>[<<+>>-]<[<<<<<+>>>>+>-]>+<<[>>>>[>>>]>>+<<<<<[<<<]<-]<<[>>>>->-<<<<<-]>>>]>>]<]>>[>>>]+[[<<<]<<<<+>>
;; >>>>>[>>>]<[-]<+[-]<-<<<]<<<<->>>>>++++[>++++++++<-]>.[-]<<<<<<[>>>>>>+<<<<<<-]>>>>>>[>+<-]>[>++++++++++<[->-[>+>
;; >]>[+[<+>-]>+>>]<<<<<]>[-]++++++[<++++++++>-]>[<<+>>-]>[<<+>>-]<<]<[.<]>[>]<[[-]<]<<<<<<<+<-]++++++++++.[-]>+<[>]
;; Le code est à passer dans un `sed 's/;;.*//'` afin d'enlever tous les commentaires
;; Implémentation similaire de l'algorithme en python :
;; def solve(deltas, n, toGo):
;; if toGo == 0:
;; return 0
;; bound = 0
;; cont = 1
;; while cont:
;; bound += 1
;; stack = [(0, -1)]
;; smallCont = 1
;; while smallCont:
;; pos, nextMove = stack[-1]
;; nextMove += 1
;; stack[-1] = (pos, nextMove)
;; if bound == 0 or nextMove == 3:
;; # Backtrack
;; if len(stack) == 1:
;; smallCont = 0
;; else:
;; stack.pop()
;; bound += 1
;; else:
;; # Advance
;; bound -= 1
;; newPos = 0
;; if nextMove == 0:
;; newPos = (pos+1)%n
;; elif nextMove == 1:
;; newPos = (pos-1)%n
;; elif nextMove == 2:
;; newPos = (pos+deltas[pos])%n
;; stack.append((newPos, -1))
;; if newPos == toGo:
;; smallCont = 0
;; cont = 0
;; return bound + len(stack) - 1
;;
;; def hate(deltas, n):
;; return map(lambda pos: solve(deltas, n, pos), xrange(n))
;; On fait la recherche de solutions avec un IDDFS
;; J'aurais probablement pu faire un BFS pour ne faire qu'un parcours de graphe pour trouver toutes les solutions,
;; mais j'avais la flemme...
;; Un désavantage du BFS est aussi qu'il va tout le temps falloir se décaler à droite (on a une queue, plus une pile),
;; et que selon les interpréteurs, on risque d'atteindre les limites de la mémoire
;; Lecture des tuyaux
>>
>>+ [ -
>
>>++++++ [- >++++++++ <]
<+ [
-
<[- >++++++++++ <]
>[<+ >-]
+
>[<<+ >>-]
,
>[<- >>+ <-]
>[<+ >-]
<<<-
>[>>>+ <+ <<-]
>>[ <<+ >>-]
++++++++++ [ -
>>+
<[ >- ] > [ <
<<<<+
>>>>>->
] <<
-
<
]
>[-]
<<<<
]
>[-]
>[-]
<<<[<<+ >>-]
>+
<<<<[
>>>+
>-
<<<<-
]
>>>[<<<+ >>>-]
+
>[
<<<[>+ <-] >
<<+
>>>-
>-
]
<[ -
<[
>>+
<<-
] +
>>>
]
<
]
<<- <<
[<<]
;; Schéma mémoire avant la liste des tuyaux :
;; zero temp firstFlag
;; * zero est une variable toujours à 0
;; * temp est une variable temporaire
;; * firstFlag est le premier flag de la liste
;; Schéma mémoire d'un élément de la liste des tuyaux :
;; flag pipe
;; * flag est le flag
;; * pipe est la longueur du tuyau
;; Schéma mémoire avant la liste des positions (c'est une pile)
;; lastFlag lastPipe zero1 remaining objective bound mustBacktrack nb temp zero2 continue smallContinue firstFlag firstNextMove firstPos
;; * lastFlag et le dernier flag de la liste des tuyaux
;; * lastPipe est la dernière longueur de tuyau de la liste des tuyaux
;; * zero1 est un 0
;; * remaining est le nombre de positions restant à traiter
;; * objective est la position du tuyau à laquelle nous devons aller
;; * bound est la limite de profondeur de la recherche
;; * mustBacktrack est un flag disant si on doit backtrack ou pas
;; * nb est le nombre total de tuyaux
;; * temp est une variable temporaire
;; * zero2 est un 0
;; * continue est un flag disant si on doit continuer la recherche
;; * smallContinue est un flag disant si on doit continuer la recherche avec le bound courant
;; * firstFlag est le premier flag de la liste des positions
;; * firstNextMove et firstPos sont les premiers nextMove et pos de la liste des positions
;; Schéma mémoire d'un élément de la liste des positions :
;; flag nextMove pos nflag nnextMove npos
;; * flag est le flag
;; * nextMove est le numéro du mouvement qui a été utilisé pour générer la position suivante
;; * pos est la position où l'on est (le numéro du tuyau)
;; On va initialiser nb et remaining à leur bonne valeur : le nombre total de tuyaux
;; On itère sur la liste des tuyaux
>> [ -
;; On va incrémenter nb et remaining
>> [>>]
>>>>> + <<<< +
;; On revient
<<< [<<]
;; Et on passe à la valeur suivante
+ >>
]
;; On est maintenant à zero1. On va afficher un 0, puisque il faut 0 mouvements pour aller du premier tuyau à partir du premier tuyau
;; On va ajouter 48 à objective en utilisant bound comme variable temporaire
>>> ++++++ [ < ++++++++ > - ]
;; On l'affiche
< .
;; objective = 1
[-] +
;; while(remaining != 0)
< - [
;; continue = 1; while(continue)
>>>>>>> + [
;; bound += 1
<<<<< +
;; firstNextMove = -1
>>>>>>>> -
;; smallContinue = 1; while(smallContinue)
<< + [
;; >>> mustBacktrack = (bound == 0)
;; mustBacktrack = 1
<<<<< +
;; if(bound != 0)
< [
;; mustBacktrack -= 1
> -
;; On sort de la boucle en utilisant zero1 comme variable temporaire
<[<<<+ >>>-]
] <<<[>>>+ <<<-]
;; mustBacktrack += (nextMove+1 == 3)
;; if(nextMove+1 == 3) then mustBacktrack += 1
;; mustBacktrack += 1
>>>> +
;; On va à la position courante
>>>>>>[>>>]
;; nextMove += 1
> +
;; if(nextMove == 3)
--- [
;; On va décrémenter mustBacktrack
<<<<[<<<]
<<< -
;; On revient voir nextMove
>>>>>>[>>>]
;; On sort de la boucle en utilisant flag comme variable temporaire
;; Les ++++ et ---- sont là pour ne pas wrapper
> ++++
[<+ >-]
< ----
>
] < +++ [>+ <-]
;; On retourne du côté de mustBacktrack
<<<[<<<]
;; if(mustBactrack) (on utilise zero2 pour faire le else)
;; zero2 = 1
+
;; if(mustBacktrack)
<<< [
;; ____ _ _ _
;; | __ ) __ _ ___| | _| |_ _ __ __ _ ___| | __
;; | _ \ / _` |/ __| |/ / __| '__/ _` |/ __| |/ /
;; | |_) | (_| | (__| <| |_| | | (_| | (__| <
;; |____/ \__,_|\___|_|\_\\__|_| \__,_|\___|_|\_\
;; zero2 = 0
>>> -
;; if(firstFlag != 0) (on utilise temp pour faire le else)
;; temp = 1
< +
;; if(firstFlag)
>>>> [
;; >>> On doit backtrack <<<
;; temp = 0
<<<< -
;; On va à la position courante
>>>>[>>>]
;; pos = 0
>> [-]
;; nextMove = 0 (le + est là pour ne pas wrapper)
< +[-]
;; On me le flag d'avant à 0
<<<< -
;; On retourne au début de la liste
<<<[<<<]
;; On incrémente bound
<<<< +
;; On sort de la liste en utilisant zero2 comme variable temporaire
>>>>>>>[<<<+ >>>-]
] <<<[>>>+ <<<-]
;; if(temp) donc else
< [
;; >>> On a tout exploré avec ce bound, on va continuer la recherche avec un plus grand <<<
;; firstNextMove = -1
>>>>> [-]-
;; smallContinue = 0
<< -
;; temp = 0
<<< -
]
;; mustBacktrack = 0
<< [-]
]
;; if(zero2) donc else
>>> [ -
;; _ _
;; / \ __| |_ ____ _ _ __ ___ ___
;; / _ \ / _` \ \ / / _` | '_ \ / __/ _ \
;; / ___ \ (_| |\ V / (_| | | | | (_| __/
;; /_/ \_\__,_| \_/ \__,_|_| |_|\___\___|
;; bound -= 1
<<<< -
;; On va à la position courante
>>>>>>>[>>>]
;; On copie pos dans npos en utilisant nflag comme variable temporaire
>>[>>>+ <<+ <-]
>[ <+ >-]
;; On va utiliser nflag pour faire un switch
;; nflag = 1
+
;; >>> switch(nextMove) <<<
<< [
;; Ici, nextMove > 0
- [
;; Ici, nextMove > 1
;; On suppose que nextMove == 2, et on exécute l'opération T
;; _____
;; |_ _|
;; | |
;; | |
;; |_|
;; On bouge npos dans temp
>>>> [
;; temp += 1
<<<<<<<<[<<<] < +
;; npos -= 1
>>>>[>>>] >>>>> -
]
;; >>> On va bouger le flag du tuyau au bon endroit <<<
;; firstFlag = 0 (firstFlag de la liste des tuyaux)
<<<<<<<<[<<<]
<<<<<<<<< [<<]
>> -
;; On retourne après la liste des tuyaux
>>[>>]
;; while(temp != 0)
>>>>>> [
;; On va au flag du tuyau courant
<<<<<<<<[<<]
;; On le décale
+ >> -
;; temp -= 1
>>[>>]
>>>>>> -
]
;; >>> On bouge la longueur du tuyau dans temp, on la bouge aussi dans mustBacktrack pour pouvoir la restaurer <<<
;; On va au tuyau courant
<<<<<<<<[<<]
;; while(pipe)
> [
;; mustBacktrack += 1
>[>>]
>>>> +
;; temp += 1
>> +
;; pipe -= 1
<<<<<<<<[<<]
> -
]
;; On restaure la valeur initiale de pipe
>[>>]
;; while(mustBacktrack != 0)
>>>> [
;; pipe += 1
<<<<<<[<<]
> +
;; mustBacktrack -= 1
>[>>]
>>>> -
]
;; >>> On remet le flag de la liste des tuyaux à 1, tout en restaurant la valeur initiale de npos (sachant qu'on ne travaille pas dans npos mais dans temp) <<<
;; On va au tuyau courant
<<<<<<[<<]
;; Cette fois, on itère différemment, de manière à ce que si on est au 1er tuyau, alors on itère 0 fois, si on est au 2ème, on itère 1 fois, si on est au n-ième, on itère n-1 fois
<< [
;; temp += 1
>> >>[>>]
>>>>>> +
;; On retourne au flag et on le décale
<<<<<<<<[<<]
+<<-<<
]
;; firstFlag = 1
>> +
;; On retourne après la liste des tuyaux
[>>]
;; On bouge temp dans npos
;; while(temp != 0)
>>>>>> [
;; npos += 1
>>>>[>>>]
>>>>> +
;; temp -= 1
<<<<<<<<[<<<]
< -
]
;; On va faire npos %= nb
;; On copie nb juste après npos en utilisant temp comme variable temporaire
;; while(nb != 0)
< [
;; temp += 1
> +
;; laCaseJusteAprèsNpos += 1
>>>>[>>>]
>>>>> >+<
;; nb -= 1
<<<<<<<<[<<<]
<< -
]
;; On bouge temp dans nb
>[<+ >-]
;; On va à npos
>>>>[>>>] >>>>>
;; On fait le modulo
[->-[>+>]>[+[-<+>]>>]<<<<]
>[-]>[<<+>>-]<<
;; On utilise flag comme variable temporaire pour sortir de la boucle, et on met nflag à 0
<<<<[<+ >-] >> - <<
]
;; Si nflag != 0 alors on doit exécuter R
+ >> [
;; ____
;; | _ \
;; | |_) |
;; | _ <
;; |_| \_\
;; >>> if(npos == 0) on va utiliser nflag comme flag <<<
;; if(npos != 0)
>> [
;; nflag = 0
<< -
;; On utilise nnextMove pour sortir de la boucle
>>[<+ >-]
] <[>+ <-]
;; if(nflag) donc if(npos == 0)
< [
;; >>> On va copier nb dans npos (en utilisant temp comme variable temporaire) <<<
<<<<<<[<<<]
;; while(nb != 0)
<< [
;; temp += 1
> +
;; npos += 1
>>>>[>>>]
>>>>> +
;; nb -= 1
<<<<<<<<[<<<]
<< -
]
;; On bouge temp dans nb
>[<+ >-]
;; nflag = 0
>>>>[>>>]
>>> -
]
;; npos -= 1 (on exécute enfin ce que le R est sensé faire)
>> -
;; On va à nflag (il est déjà à 0)
<<
]
;; On utilise flag comme variable temporaire pour sortir de la boucle
<<[<+ >-]
]
;; On bouge flag dans nextMove pour restaurer sa valeur initiale
<[>+ <-]
;; Si nflag est à 1, c'est que nextMove = 0, on doit donc exécuter un A
>>> [
;; _
;; / \
;; / _ \
;; / ___ \
;; /_/ \_\
;; npos += 1
>> +
;; On met nflag à 0 pour l'utiliser comme variable temporaire
<< -
;; Si npos == nb, alors on va faire en sorte que npos = 0
;; >>> On copie nb dans nnextMove en utilisant temp comme variable temporaire <<<
<<<<<<[<<<]
;; while(nb != 0)
<< [
;; temp += 1
> +
;; nnextMove += 1
>>>>[>>>]
>>>> +
;; nb -= 1
<<<<<<<[<<<]
<< -
]
;; On bouge temp dans nb
>[<+ >-]
;; On revient à la position courante
>>>>[>>>]
;; >>> On va faire npos -= nb (donc npos -= nnextMove), et nflag = nb (donc nflag = nnextMove) <<<
;; while(nnextMove != 0)
>>>> [
;; npos -= 1
> -
;; nflag += 1
<< +
;; nnextMove -= 1
> -
]
;; if(npos != 0)
> [
;; >>> Si on arrive ici, npos est négatif, donc on fait npos += nb (c'est à dire npos += nflag) <<<
;; npos += nflag
<<[>>+ <<-]
;; On sort de la boucle en utilisant nnextMove comme variable temporaire
>>[<+ >-]
] <[>+ <-]
;; nflag = 0
< [-]
]
;; nnextMove = -1
> -
;; flag = 1
<<<< +
;; >>> On va vérifier si on a trouvé la solution <<<
;; On bouge npos dans temp
;; while(npos != 0)
>>>>> [
;; temp += 1
<<<<<[<<<]
< +
;; npos -= 1
>>>>[>>>]
>> -
]
<<<<<[<<<]
;; >>> On va regarder si objective == npos (donc si objective == temp) <<<
;; On fait temp -= objective, et zero2 = objective
;; while(objective != 0)
<<<<< [
;; zero2 += 1
>>>>> +
;; temp -= 1
< -
;; objective -= 1
<<<< -
]
;; On va faire mustBacktrack = (npos == 0)
;; mustBacktrack = 1
>> +
;; On va utiliser continue comme variable temporaire, continue = 0
>>>> -
;; if(temp != 0)
<< [
;; mustBacktrack = 0
<< -
;; On restaure la valeur de temp et de objective maintenant pour ne pas wrapper en sortant de la boucle
>>> [ < + <<<< + >>>>> -]
;; On sort de la boucle en utilisant continue comme variable temporaire
<[>>+ <<-]
] >>[<<+ >>-]
;; On restaure la valeur de temp et de objective
< [ < + <<<< + >>>>> -]
;; On restaure la valeur de continue
> +
;; On restaure la valeur de npos
;; while(temp != 0)
<< [
;; npos += 1
>>>>[>>>]
>> +
;; temp -= 1
<<<<<[<<<]
< -
]
;; if(mustBacktrack)
<< [
;; On a trouvé la solution \o/
;; smallContinue = 0
>>>>> -
;; continue = 0
< -
;; mustBacktrack = 0
<<<< -
]
;; On va à zero2 (c'est là qu'on était au début de la boucle)
>>>
]
;; On va à smallContinue
>>
]
;; On va à continue
<
]
;; >>> On va effacer toute la liste, et restaurer bound <<<
>>[>>>]
+ [
;; bound += 1
[<<<]
<<<< +
;; pos = 0
>>>>>>> [>>>] <<<
>> [-]
;; nextMove = 0 (le + est là pour ne pas wrapper)
< +[-]
;; flag = 0 et on passe au suivant
< - <<<
]
;; La boucle ci-dessus a trop incrémenté bound, bound -= 1
<<<< -
;; On affiche un espace, on met 32 dans smallContinue en utilisant continue comme variable temporaire
>>>>> ++++ [ > ++++++++ < - ]
> . [-]
;; On bouge bound dans smallContinue pour ne pas gêner les autres variable en affichant bound
<<<<<<[>>>>>>+ <<<<<<-]
;; On affiche bound (on peut enlever une partie du code habituel car bound ne sera jamais égal à 0)
>>>>>>
[>+ <-]
>[
>++++++++++
<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
>[-] ++++++ [<++++++++ >-]
>[<<+ >>-]
>[<<+ >>-]
<<]
<[.<]
;; On fait le ménage
>[>]<[[-]<]
;; objective += 1
<<<<<<< +
;; remaning -= 1
< -
]
;; Newline
++++++++++ .
Raw
4.sbf
#include(utils.sbf)
#variables(PrePipe; zero; temp; firstFlag)
#variables(Pipe; flag; pipe; nflag)
#variables(PrePos; lastFlag; lastPipe; zero1; remaining; objective; bound; mustBacktrack; nb; temp; zero2; continue; smallContinue; firstFlag; firstNextMove; firstPos)
#variables(Pos; flag; nextMove; pos; nflag; nnextMove; npos)
#macro(preposToPos;; =firstFlag; [>>>] @Pos@flag;)
#macro(posToPrepos;; =flag; <<<[<<<] @PrePos@zero2;)
#macro(prepipeToPipe;; =firstFlag; [>>] @Pipe@flag;)
#macro(pipeToPrepipe;; =flag; <<[<<] @PrePipe@zero;)
#macro(pipeToPrepos;; =flag; >>[>>] @PrePos@zero1;)
#macro(preposToPipe;; =lastFlag; [<<] @Pipe@flag;)
@PrePipe@zero;
=firstFlag;
_readIntList(0)
@Pipe@flag;
[<<] @PrePipe@zero;
=firstFlag; [ -
@Pipe@flag;
=nflag; [>>] @PrePos@zero1;
=nb; + =remaining; +
=lastFlag; [<<]
+ >>
]
@PrePos@zero1;
=bound; _add(6) [ =objective; _add(8) =bound; - ]
=objective; . [-] +
=remaining; - [
=continue; + [
=bound; +
=firstNextMove; -
=smallContinue; + [
#_ if bound == 0 then mustBacktrack = 1
=mustBacktrack; +
=bound; [
#_# BT BECAUSE OF BOUND
=mustBacktrack; -
_moveTo(bound; zero1)
=bound;
] _moveTo(zero1; bound)
#_ increment nextMove
=mustBacktrack; +
_preposToPos()
=nextMove; +
#_ if nextMove == 3 then mustBacktrack = 1
=nextMove; --- [
#_# BT BECAUSE OF NEXTMOVE
_posToPrepos()
=mustBacktrack; -
_preposToPos()
=nextMove; ++++
_moveTo(nextMove; flag)
=flag; ----
=nextMove;
] =flag; +++ _moveTo(flag; nextMove)
_posToPrepos()
#_ if mustBacktrack (mustAdvance = zero2)
=zero2; +
=mustBacktrack; [
#_ backtrack
=zero2; -
=temp; +
=firstFlag; [
=temp; -
#_ rewind
_preposToPos()
=pos; [-]
=nextMove; +[-]
=flag; <<< -
_posToPrepos()
=bound; +
_moveTo(firstFlag; zero2)
=firstFlag;
] _moveTo(zero2; firstFlag)
=temp; [
#_ end
=firstNextMove; [-]-
=smallContinue; -
=temp; -
]
=mustBacktrack; [-]
]
=zero2; [ -
#_ advance
=bound; -
_preposToPos()
_copy(pos; npos; nflag)
=nflag; +
=nextMove; [
#_ nextMove > 0
- [
#_ nextMove > 1
#_ EXEC T
#_ move npos to temp
=npos; [
_posToPrepos()
=temp; +
_preposToPos()
=npos; -
]
#_ move the pipe flag at the right place
_posToPrepos()
=lastFlag; [<<] @PrePipe@zero;
=firstFlag; -
@Pipe@flag; _pipeToPrepos()
=temp; [
_preposToPipe()
=flag; + >> -
_pipeToPrepos()
=temp; -
]
#_ add the pipe value to the pos (temp), copy to mustBacktrack
_preposToPipe()
=pipe; [
_pipeToPrepos()
=mustBacktrack; +
=temp; +
_preposToPipe()
=pipe; -
]
#_ restore pipe
_pipeToPrepos()
=mustBacktrack; [
_preposToPipe()
=pipe; +
_pipeToPrepos()
=mustBacktrack; -
]
#_ remove the pipe flag and restore the initial npos value
_preposToPipe()
=flag; << [
>> _pipeToPrepos()
=temp; +
_preposToPipe()
+<<-<<
] @PrePipe@zero;
=firstFlag; + [>>] @PrePos@zero1;
#_ move temp to npos
=temp; [
_preposToPos()
=npos; +
_posToPrepos()
=temp; -
]
#_ npos %= nb
#_ copy nb just after npos
=nb; [
=temp; +
_preposToPos()
=npos; >+<
_posToPrepos()
=nb; -
] _moveTo(temp; nb)
#_ perform the modulo
_preposToPos()
=npos; _mod()
>[-]>[<<+>>-]<<
_moveTo(nextMove; flag) =nflag; - =nextMove;
] + =nflag; [
#_ nextMove == 1
#_ EXEC R
#_ if npos == 0 then npos = nb
=npos; [
=nflag; -
_moveTo(npos; nnextMove)
=npos;
] _moveTo(nnextMove; npos)
=nflag; [
_posToPrepos()
=nb; [
=temp; +
_preposToPos()
=npos; +
_posToPrepos()
=nb; -
] _moveTo(temp; nb)
_preposToPos()
=nflag; -
]
#_ npos -= 1
=npos; -
=nflag;
] _moveTo(nextMove; flag) =nextMove;
] _moveTo(flag; nextMove)
=nflag; [
#_ nextMove == 0
#_ EXEC A
#_ increment npos
=npos; +
#_ setup nflag to use it as a temporary var
=nflag; -
#_ take the modulo by n (if pos == n then pos = 0)
_posToPrepos()
#_ copy nb to nnextMove
=nb; [
=temp; +
_preposToPos()
=nnextMove; +
_posToPrepos()
=nb; -
]
_moveTo(temp; nb)
_preposToPos()
#_ npos -= nb
=nnextMove; [
=npos; -
=nflag; +
=nnextMove; -
]
#_ if pos != 0 then it must be negative, pos += nb
=npos; [
_moveTo(nflag; npos)
_moveTo(npos; nnextMove)
=npos;
] _moveTo(nnextMove; npos)
=nflag; [-]
]
=nnextMove; -
=flag; +
#_ check if the solution was found
#_ move the last pos to temp
=npos; @Pos@pos; [
_posToPrepos()
=temp; +
_preposToPos()
=pos; -
]
_posToPrepos()
#_ check if objective == temp
=objective; [
=zero2; +
=temp; -
=objective; -
]
=mustBacktrack; +
=continue; - #_ use continue as a temp var
=temp; [
#_ objective != temp
=mustBacktrack; -
=zero2; [ =temp; + =objective; + =zero2; -]
_moveTo(temp; continue)
] _moveTo(continue; temp)
=zero2; [ =temp; + =objective; + =zero2; -]
=continue; + #_ restore continue
#_ restore pos
=temp; [
_preposToPos()
=pos; +
_posToPrepos()
=temp; -
]
=mustBacktrack; [
#_ found a solution
=smallContinue; -
=continue; -
=mustBacktrack; -
]
=zero2;
]
=smallContinue;
]
=continue;
]
_preposToPos()
=flag; + [
[<<<] @PrePos@zero2;
=bound; +
=firstFlag; [>>>] <<< @Pos@flag;
=pos; [-]
=nextMove; +[-]
=flag; - <<<
]
@PrePos@zero2;
=bound; -
=continue; _add(4) [ =smallContinue; _add(8) =continue; - ]
=smallContinue; . [-]
_moveTo(bound; smallContinue)
=smallContinue; _printInt(no; no; yes)
@PrePos@smallContinue;
=objective; +
=remaining; -
] _add(10) .
Raw
5.bf
;; >>>>+[->>>++++++[>++++++++<-]<+[-<[>++++++++++<-]>[<+>-]+>[<<+>>-],>[<->>+<-]>[<+>-
;; ]<<<->[>>+>+<<<-]>>[<<+>>-]++++++++++[->>+<[>-]>[<<<<<+>>>>>->]<<-<]>[-]<<<<]>[-]>[
;; -]< <<[<<+>>-]>+<<<<[>>>+>-<<<<-]>>>[<<<+>> > -]+>[<<<[>+<-]<+>>>->-]<[-<[>>
;; +<<- ]+>>> ]<]<< -<<<< [<<]> >[->> [>> ]>>>>> [>>>] +>+<[ <<<]< <<<[<<]+
;; >>]>> >>>[ >>>]+ [<<<] >>>-< <<<<< <[< <]>>[-> [>[> >]>>> >+<<< +<<<[<<]
;; >-]>[> > ] > > > > [<<<<<<[ < < ] >+>[>>
;; ]>>>> -]>[ >>>]> -<<<< [<<<] <[>>> >>[ >>>]+>> >-[+ <<<[< <<]>> >-]<<<[<
;; <<]< <-]>> >>>[> >>]+> +<[<< <]>>[ >>> ]+>>>- <<<[< <<]<< <<[<< ]+>>]>>>
;; >>[ >>[<->[-]]<[<-<<<[<<<]<[-]+>>>>[>>>]+>- ] >>]<<<[-<<<]+<[>-<-]+>[<->++++
;; [<+++++++++>>++<-]<.++++.[-]>>.[-]<]<[-<<<[<<]>>[->>[>>]>>>>>>>>+>>>>[>>>]+>+>+<<[<
;; <<]<<<<<<<<<<<[<<]+>>]>>>+>>>>+<<<<[>+>-<[>>+>[< ->[> >+<<-]]>>[<<+>> -]<<<+<--[
;; ++++> -<[>> >>+<< <<-]> >>>-- --<<< <]>>> >+++ [<<< <+>>> >-]+ <<<[>>>-<
;; <<<<< <<<+> >[<<- >>>>> >>>>> >>[>> >]<< <[>> [-]<- <-<<< ]<[-] <[-]<[-]
;; <+[ - ] < - < - <-<< <<<[ < <<]< <<<<<<[
;; <+>-] ]<[>+ <-]<[ >>>>- <<<<- ]>>>> >>[- ]]>> >[-<[ >>>+> [>>>] >>>>>>>>
;; +<<<< <<<<< <<[<< <]<-] >>>[< <<+>> >-]<< <<<+ <[-[ >>>>> >>[- >>>[>>>]>
;; >>>>>>>>>>>[>>>]+>+<[<<<]<<<<<<<<<<<<[<<<]+>>>]> >>>> >>>>>>>-<<<<<<< <<<<<<<<[<
;; <<]>>>>-<<<<<<<<<<<[<<<<<[<<<]<<<<<<<]<<<<[<<]>>[->>[>>]>>>>>>>>>>>>[>>>]>>[>>>>>>>
;; >>>[>>>]>>] >>>>>> > > >>[>>>]>-<<<<[<<<]<<<<<<<<<<<<[<<<]<<<<<<<[<
;; <<<<[<<<]<<<<<< <]<<<< [<<]> [>[>>] >>>>>>>>>>>+>[>>>]>>[>>>> >>>>> >[>>>]>>]
;; >>>>>>>>>>>[>>> ]+>>>- [+<<< [<<<]>> >-]<<<[<<<]<<<<<<<<<<<<< [<<<] <<<<<<<[<
;; <<< <[<<< ] < <<<<< <]<<<<[< < ] >-]>[ > >]>>>>>
;; >>>>>>[<<<<<<<< < < <<<[< <]>+>[> >]>>>>>>>>>>>-]>[>>>]>>[ >>>>> >>>>>[>>>
;; ]>>]<<<<<[<<<]> >> >[ >>>]< ->>[<< +>>>>[>>>]>>>>>>>>> >>> [>>>] >+<<<<[<<
;; <]<<<<<<<<< < <<[ < < <]>-]<<[>>+<<-]+>+>> >-<[>>>]>>>>>>>>>>>>[
;; >>>]+>>>-<<<[<<<]>>>>[>>>]+[<<<]<<<<<<<<<<<<<[<<<]<<<<<<<[<<<<<[<<<]<<<<<<<]<<<<[<<
;; ]+> >]>>>>>>>>>>>> [>>> ]>>[>>>>> > >>>>[>>>]>>]>>>>>>>>>>[ >>>] <<<
;; +<<< [<<<] <<<<< <<<+ <<<<[<<<]<<<<[ << <<+>> >>-]>-<]+>[>>>>> >[- >>>[>>>
;; ]>>>> >>>> >>>> [>>> ]+>+<[<<<]<<<<< <<< <<<< [<<<]>>[>[>>>]>+> >> >>>>>>>
;; >[>>>] < + <<[< <<]< <<<<< <<<< < <[<<< ]>>- ] >[>>>]>
;; [<<<< [<<< ]>>+ >[>> >]>-]<<<<[<<<]+ >>> ]>>> >>>>>>>>>[>>[<<<+ >> >-]>]<<
;; <[<< <]>>[ >[>>> ]<+< <[<<<]>>-]<<<< << <<<<< <<< [<<<]<<<-] <[< <<<+>>>
;; >-] ]<<<<[>>>>+<<< <-]> >>>>[>>>> > >[->>>[>>>] >>>>>>>>> >>>[ >>>
;; ]+>+<[<<<]<<<<<<<<<<<<[<<<]>>[>[>>>]>+>>>>>>>>>>>[>>>]<+<<[<<<]<<<<<<<<<<<<[<<<]>>-
;; ]>[>>> ]>[<< <<[<<<]>>+>[ >>>] >-]< <<<[<< <]+> >>]>>>>>>>>>>>>[>>>]
;; <<<[> >[>>>+< <<-]<<<<<]>>>[> >>] >>[< <<<<[<<<]>> >>> +<<[>>>]>>-]<<<<<[<<<
;; ]<<< <<<<<<<<< [<<<]<<<-]>>>> >> [>>> ]>>>>>-<+<+< +< <<<<[<<<]<<-[>>>>+>[>>
;; >]> >>>>>>+<<<< < <<<<< [ <<<] <<-] +>>>> [ <<<<+>>>>-]>[>>>]>>>>>>
;; >>[> >+>>>>-<< <<<<-]>+>>>>>[ << <<<- >[< <+>>> >> >+<<<<-]>>>>[<<<+>>>-]
;; ]<<<[ >> >+ <<<-]<[<<+>>>>> >+< <<<- ]<[ <<<<<< ->- >> >>>-]]<<<<<]>+>>
;; +<<[-] < < ]<<<<<<[<<<] <<<< <<<[ < <<< <[<< < ]<<<<<<<]>>>>>>[
;; -]>[-]>[-]>[-]>[-]<<<<<[>+<-]>[>[-]>[-]>[-]>[-]>[-]<<<<++++++++++<[->-[>+>>]>[+[<+>
;; -]>+>>]<<<<<]>[-]++++++[<++++++++>-]>[<<+>>-]>[<<+>>-]<<]<[.<]++++++++++.[-]][-]>+>
;; Le code est à passer dans un `sed 's/;;.*//'` afin d'enlever tous les commentaires
;; Implémentation similaire de l'algorithme en python :
;; def impossible(deltas, n):
;; plumbers = map(lambda _:0, xrange(n))
;; for pos in xrange(n):
;; plumbers[(pos+deltas[pos])%n] += 1
;; for p in plumbers:
;; if p == 0:
;; return False
;; return True
;;
;; def repli(deltas, n):
;; if impossible(deltas, n):
;; return -1
;; cont = 1
;; stack = [([], -1, 0)]
;; while cont:
;; stack = [(map(lambda _:1, xrange(n)), -1, stack[0][2]+1)]
;; smallCont = 1
;; while smallCont:
;; plumbers, nextMove, bound = stack[-1]
;; nextMove += 1
;; stack[-1] = (plumbers, nextMove, bound)
;; if bound == 0 or nextMove == 3:
;; # Backtrack
;; if len(stack) == 1:
;; smallCont = 0
;; else:
;; stack.pop()
;; else:
;; # Advance
;; newPlumbers = []
;; if nextMove == 0:
;; newPlumbers = map(lambda i: plumbers[(i+1)%n], xrange(n))
;; elif nextMove == 1:
;; newPlumbers = map(lambda i: plumbers[(i-1)%n], xrange(n))
;; elif nextMove == 2:
;; newPlumbers = map(lambda _:0, xrange(n))
;; for i in xrange(n):
;; newPlumbers[(i+deltas[i])%n] += plumbers[i]
;; stack.append((newPlumbers, -1, bound-1))
;; if newPlumbers[0] == n:
;; smallCont = 0
;; cont = 0
;; return stack[0][2]
;; L'algorithme est un IDDFS
;; Comme les tuyaux conservent l'ordre, on doit probablement pouvoir faire en sorte de n'utiliser que deux nombres pour représenter
;; un noeud du graphe et non pas un tableau entier, puisque tous les plombiers entre deux plombiers A et B seront toujours entre A et B
;; après avoir utilisé un tuyau.
;; Un *jeu* de tuyaux est impossible à résoudre si il n'y a pas une position où on peut aller par deux tuyaux différents
;; Ceci est équivalent à mettre un plombier sur chaque tuyau, tous les faire passer dans leurs tuyau, et regarder s'il y a un tuyau où il n'y a plus personne
;; Lecture des tuyaux
>>
>>+ [ -
>
>>++++++ [- >++++++++ <]
<+ [
-
<[- >++++++++++ <]
>[<+ >-]
+
>[<<+ >>-]
,
>[<- >>+ <-]
>[<+ >-]
<<<-
>[>>>+ <+ <<-]
>>[ <<+ >>-]
++++++++++ [ -
>>+
<[ >- ] > [ <
<<<<+
>>>>>->
] <<
-
<
]
>[-]
<<<<
]
>[-]
>[-] <<<[<<+ >>-]
>+
<<<<[
>>>+
>-
<<<<-
]
>>>[<<<+ >>>-]
+
>[
<<<[>+ <-] >
<<+
>>>-
>-
]
<[ -
<[
>>+
<<-
] +
>>>
]
<
]
<<- <<
<<[<<]
;; __ __ _ __ _ _ _ _
;; \ \ / /__ _ __(_)/ _(_) ___ __ _| |_(_) ___ _ __ __| | ___
;; \ \ / / _ \ '__| | |_| |/ __/ _` | __| |/ _ \| '_ \ / _` |/ _ \
;; \ V / __/ | | | _| | (_| (_| | |_| | (_) | | | | | (_| | __/
;; \_/ \___|_| |_|_| |_|\___\__,_|\__|_|\___/|_| |_| \__,_|\___|
;;
;; _ _ _ _ _ _ _ _ _
;; | ( |_)_ __ ___ _ __ ___ ___ ___(_) |__ (_) (_) |_ ___ ___
;; | |/| | '_ ` _ \| '_ \ / _ \/ __/ __| | '_ \| | | | __/ _ \/ _ \
;; | | | | | | | | | |_) | (_) \__ \__ \ | |_) | | | | || __/ __/
;; |_| |_|_| |_| |_| .__/ \___/|___/___/_|_.__/|_|_|_|\__\___|\___|
;; |_|
;; Schéma mémoire avant la liste des tuyaux :
;; zero temp firstFlag
;; * zero est un 0
;; * temp est une variable temporaire
;; * firstFlag est le premier flag du tableau
;; Schéma mémoire d'un élément de la liste des tuyaux :
;; flag pipe
;; * flag est le flag
;; * pipe est la longueur du tuyau
;; Schéma mémoire avant la liste des positions
;; temp1 counter zero1 zero2 temp2 firstFlag1 firstFlag2
;; * temp1 est une variable temporaire (utilisée comme 0 la liste des tuyaux est juste avant elle)
;; * counter est une autre variable temporaire
;; * zero1, zero2 sont des 0
;; * temp2 est une autre variable temporaire
;; * firstFlag1 et firstFlag2 sont les deux premiers flags
;; Schéma mémoire d'un élément de la liste des positions
;; flag1 flag2 val :
;; * flag1 et flag2 sont deux flags
;; * val est le nombre de plombiers à ce tuyau
;; >>> On créé la liste des positions de départ : tous les flag1, flag2 <<<
;; On itère sur le tableau des tuyaux
>> [ -
;; On va à la position courante
>> [>>] >>>>> [>>>]
;; flag1 = 1, flag2 = 1
+>+<
;; On retourne au tuyau courant
[<<<] <<<< [<<]
;; On passe au tuyau suivant
+ >>
]
;; On va calculer le nombre de plombiers à chaque tuyau après que chaque plombier passe dans son tuyau
;; * Le flag de la liste des tuyaux pour représenter le tuyau de départ
;; * Le flag1 de la liste des plombiers représente le tuyau de départ
;; * Le flag2 de la liste des plombiers représente le tuyau d'arrivée
;; On met le flag1 juste après le dernier élément de la liste des positions à 1, il sera mis à 0 par la suite
>>>>>[>>>] + [<<<]
;; On met firstFlag1 à 1
>>> -
;; On va avant la liste des tuyaux
<<<<< <<[<<]
;; On itère sur les tuyaux
>> [ -
;; >>> On copie pipe dans counter (on utilise temp2 comme variable temporaire) <<<
;; while(pipe != 0)
> [
;; temp2 += 1
>[>>]
>>>> +
;; counter += 1
<<< +
;; pipe -= 1
<<<[<<]
> -
]
>[>>]
;; while(temp2 != 0)
>>>> [
;; pipe += 1
<<<<<<[<<]
> +
;; temp2 -= 1
>[>>]
>>>> -
]
;; >>> On positionne flag2 <<<
;; On va au flag1 courant
>[>>>]
;; flag2 = 0
> -
<<<<[<<<]
;; while(counter != 0)
< [
;; On va au flag2 courant
>>>>>[>>>]
;; On décale flag2
+ >>> - [
;; Si on entre dans cette boucle, ça veut dire que le flag2 auquel on a enlevé 1 était déjà à 0
;; On répare notre bêtise
+
;; On retourne au début du tableau
<<< [<<<]
;; On met le premier flag2 à 0 et on incrémente le premier val
>>> -
]
;; On retourne au début du tableau
<<<[<<<]
;; counter -= 1
<< -
]
;; On va au flag2 courant
>>>>>[>>>]
;; val += 1
> +
;; flag2 = 1, et on retourne au début de la liste
< + [<<<]
;; On va au flag1 courant, on le décale, et on revient
>>[>>>] + >>> - <<< [<<<]
;; On va au tuyau courant
<<<<[<<]
;; On décale le flag
+ >>
]
;; >>> On va vider le tableau des positions en regardant si un val est à 0 <<<
;; On va au premier flag
>>>>> [
;; if(val != 0)
>> [
;; flag2 = 0
< -
;; val = 0
> [-]
]
;; if(flag2) donc if(val == 0)
< [
;; flag1 = 0
< -
;; counter = 1
<<<[<<<]
< [-] +
;; flag1 = 1
>>>>[>>>]
+
;; flag2 = 0
> -
]
;; On va au flag1 suivant
>>
]
;; On retourne au début de la liste en effacant les flag1
<<< [- <<<]
;; Si counter == 0, alors l'entrée donnée est impossible. On utilise zero1 comme flag
;; zero1 = 1
+
;; if(counter != 0)
< [
;; zero1 = 0
> -
;; counter = 0
< -
]
;; Maintenant, on va utiliser counter comme flag pour savoir si on doit commencer la rercherche de solution, counter = 1
+
;; if(zero1 != 0) donc if(counter == 0)
> [
;; counter = 0
< -
;;
;; zero1 = 5 (on ajoute seulement 4 car il est déjà à 1), et on l'utilise pour mettre 45 dans counter, et 10 dans zero2
> ++++ [ < +++++++++ >> ++ < -]
;; On affiche un tiret (valeur ascii : 45)
< .
;; On affiche un 1 (valeur ascii : 49)
++++ .
;; counter = 0
[-]
;; On affiche un \n (valeur ascii : 10)
>> .
;; zero2 = 0
[-]
;; On retourne à zero1 qui est déjà à 0
<
]
;; ____ _ _
;; | _ \ ___ ___| |__ ___ _ __ ___| |__ ___
;; | |_) / _ \/ __| '_ \ / _ \ '__/ __| '_ \ / _ \
;; | _ < __/ (__| | | | __/ | | (__| | | | __/
;; |_| \_\___|\___|_| |_|\___|_| \___|_| |_|\___|
;;
;; _ _ _ _
;; __| | ___ ___ ___ | |_ _| |_(_) ___ _ __
;; / _` |/ _ \ / __|/ _ \| | | | | __| |/ _ \| '_ \
;; | (_| | __/ \__ \ (_) | | |_| | |_| | (_) | | | |
;; \__,_|\___| |___/\___/|_|\__,_|\__|_|\___/|_| |_|
;; Dans l'algorithme suivant, on va avoir une liste de liste
;; Schéma mémoire avant la liste des positions des plombiers :
;; lastFlag1 lastFlag2 lastVal zero1 zero2 bigFlag continue smallContinue nextMove mustBacktrack bound nbEnd zero3 zero3 temp firstFlag1 firstFlag2 firstVal
;; * lastFlag1 est le dernier flag1 de la liste des positions des plombiers précédente
;; * lastFlag2 est le dernier flag2 de la liste des positions des plombiers précédente
;; * lastVal est la dernière valeur de la liste des positions des plombiers précédente
;; * zero1 est un 0
;; * zero2 est un 0
;; * bigFlag est le flag de la "grande" liste (la liste qui contient les autres listes). Il est à 0 sur la première liste, et sur la liste qu'on est en train de construire
;; * continue est un flag disant si on doit continuer la recherche
;; * smallContinue est un flag disant si on doit continuer la recherche avec le bound courant
;; * nextMove est le numéro du mouvement qui a été utilisé pour générer la liste des positions d'après
;; * mustBacktrack est un flag disant si on doit backtrack ou non
;; * bound est la limite de profondeur de la recherche
;; * nbEnd est le nombre total de plombiers
;; * zero3 est un 0
;; * zero4 est un 0
;; * temp est une variable temporaire
;; * firstFlag1 est le premier flag1 de la liste des positions des plombiers courante
;; * firstFlag2 est le premier flag2 de la liste des positions des plombiers courante
;; * firstVal est la première valeur de la liste des positions des plombiers courante
;; Schéma mémoire d'un élément de la liste des positions des plombiers :
;; flag1 flag2 val nflag1 nflag2 nval
;; * flag1 est un flag
;; * flag2 est un flag
;; * val est le nombre de plombiers présents à cette case
;; * nflag1 est le prochain flag1
;; * nflag2 est le prochain flag2
;; * nval est le prochain val
;; if(counter != 0)
< [ -
;; On va avant la liste des tuyaux
< << [<<]
;; >>> On prépare la première liste de positions des plombiers, où ils sont tous à leur tuyau respectif <<<
;; On va aussi initialiser nbEnd
;; On itère sur la liste des tuyaux
>> [ -
;; nbEnd += 1
>>[>>]
>>>>>>>> +
;; On va au flag1 courant
>>>> [>>>]
;; flag1 = 1, flag2 = 1, val = 1
+ > + > +
;; On retourne au tuyau courant
<< [<<<]
<<<<<<<<< <<[<<]
;; On passe au tuyau suivant
+ >>
]
;; bound = 1
>>>>>>> +
;; continue = 1, while(continue)
<<<< + [
;; nextMove = -1
>> -
;; smallContinue = 1, while(smallContinue)
< + [
;; >>> mustBacktrack = (bound == 0) <<<
;; mustBacktrack = 1
>> +
;; if(bound != 0)
> [
;; mustBacktrack = 0
< -
;; On utilise zero3 pour sortir de la boucle
>[>>+ <<-]
] >>[<<+ >>-]
;; nextMove += 1
<<<< +
;; >>> mustBacktrack += (nextMove == 3) <<<
;; mustBacktrack += 1
> +
;; if(nextMove != 3)
< --- [
;; mustBacktrack -= 1
> -
;; On utilise zero3 pour sortir de la boucle (les ++++ et ---- sont là pour ne pas wrapper)
< ++++
[>>>>+ <<<<-]
>>>> ----
<<<<
] >>>> +++ [<<<<+ >>>>-]
;; if(mustBacktrack) (on utilise zero3 pour le else)
;; zero3 = 1
+
;; if(mustBacktrack)
<<< [
;; ____ _ _ _
;; | __ ) __ _ ___| | _| |_ _ __ __ _ ___| | __
;; | _ \ / _` |/ __| |/ / __| '__/ _` |/ __| |/ /
;; | |_) | (_| | (__| <| |_| | | (_| | (__| <
;; |____/ \__,_|\___|_|\_\\__|_| \__,_|\___|_|\_\
;; zero3 = 0
>>> -
;; zero1 = 1 (il servira à faire le else)
<<<<<<<<< +
;; if(bigFlag) -> on n'est pas à la première liste
>> [
;; zero1 = 0
<< -
;; On efface toute la liste
>>>>>>>>>>>> [>>>] <<<
[ >> [-] < - < - <<<]
;; On efface tous les flags et autres
< [-] < [-] < [-] < +[-] < - < - < -
;; On va avant la liste des positions précédente
<<<<< [<<<]
;; On sort de la boucle en utilisant zero2
<<<<<<<[<+ >-]
] <[>+ <-]
;; if(zero1) donc else
< [
;; On a tout exploré avec le bound courant, on doit sortir de la boucle et l'incrémenter
;; smallContinue = 0
>>>> -
;; zero1 = 0
<<<< -
]
;; mustBacktrack = 0
>>>>>> [-]
]
;; if(zero3) donc if(mustBacktrack == 0)
>>> [ -
;; _ _
;; / \ __| |_ ____ _ _ __ ___ ___
;; / _ \ / _` \ \ / / _` | '_ \ / __/ _ \
;; / ___ \ (_| |\ V / (_| | | | | (_| __/
;; /_/ \_\__,_| \_/ \__,_|_| |_|\___\___|
;; >>> On va copier nbEnd dans le prochain nbEnd en utilisant temp comme variable temporaire <<<
;; while(nbEnd != 0)
< [
;; temp + 1
>>> +
;; nbEnd += 1 (celui dans lequel on copie)
> [>>>]
>>>>>>>> +
;; nbEnd -= 1 (celui qui est copié)
<<<<<<<<<<< [<<<]
< -
]
;; On restaure la valeur initiale de nbEnd
>>>[<<<+ >>>-]
;; mustBacktrack = 1 (on va l'utiliser comme flag)
<<<<< +
;; >>> switch(nextMove) <<<
< [
;; Ici, nextMove > 0
- [
;; Ici, nextMove > 1
;; On suppose que nextMove == 2, on exécute l'opération T
;; _____
;; |_ _|
;; | |
;; | |
;; |_|
;; >>> On créé les flags de la nouvelle liste <<<
;; On itère sur le tableau de plombiers courant
>>>>>>> [ -
;; On va dans la nouvelle liste des plombiers à la position courante
>>> [>>>]
>>>>>>>>>>>> [>>>]
;; flag1 = 1 et flag2 = 1
+ > +
;; On revient à la liste des plombiers courante
< [<<<]
<<<<<<<<<<<< [<<<]
;; On décale le flag
+ >>>
]
;; >>> On va "tuyauter" les plombiers de l'ancienne liste <<<
;; On met le premier flag1 de la nouvelle liste à 0
>>>>>>>>>>>> -
;; On va au début de la liste des plombiers courante
<<<<<<<<<<<<<<<[<<<]
;; On met firstFlag2 à 0
>>>> -
;; while(bigFlag)
<<<<<<<<<<< [
;; On va au bigFlag de la liste précédente
<<<<<[<<<]
<<<<<<<
]
;; On est à la fin de la liste des tuyaux, on va au début
<< << [<<]
;; On itère sur la liste des tuyaux
>> [ -
;; >>> On va mettre le flag2 de la nouvelle liste des plombiers au bon endroit (comme dans la vérification de l'impossibilité) <<<
;; On va au début de la première liste des plombiers
>>[>>]
;; On va à la deuxième
>>>>>>>>>>>>[>>>]
;; while(bigFlag) { on va à liste suivante }
>>[ >>>>>>>>>>[>>>] >>]
;; Maintenant, on est à la liste des plombiers que l'on est en train de construire
;; On va au flag1 courant
>>>>>>>>>> [>>>]
;; flag2 = 0
> -
;; On retourne au début de la liste
< <<<[<<<]
;; On va à la liste précédente
<<<<<<<<<<<<[<<<]
;; while(bigFlag) { on va à la liste précédente }
<<<<<<<[ <<<<<[<<<] <<<<<<<]
;; On va au tuyau courant
<<<<[<<]
;; On va bouger le flag2 vers la droite pipe fois, et on va utiliser le temp de la première liste pour restaurer le pipe
;; while(pipe != 0)
> [
;; temp += 1
>[>>]
>>>>>>>>>>> +
;; On va à la liste des plombiers que l'on est en train de construire
>[>>>] >>[ >>>>>>>>>>[>>>] >>]
;; On va au flag2 courant
>>>>>>>>>>> [>>>]
;; On le décale
+ >>> -
[ +
;; Si on arrive ici, c'est qu'on est allé trop loin, on retourne au début de la liste
<<< [<<<]
;; Et on met le premier flag2 à 0
>>> -
]
;; On retourne au début de la liste
<<<[<<<]
;; pipe -= 1
<<<<<<<<<<<<<[<<<] <<<<<<<[ <<<<<[<<<] <<<<<<<]
<<<<[<<]
> -
]
;; On restaure la valeur initiale de pipe
>[>>]
;; while(temp != 0)
>>>>>>>>>>> [
;; pipe += 1
<<<<<<<<<<<<<[<<]
> +
;; temp -= 1
>[>>]
>>>>>>>>>>> -
]
;; On va à l'avant dernière liste des plombiers
>[>>>] >>[ >>>>>>>>>>[>>>] >>]
<<<<<[<<<]
;; On va au flag2 courant de la liste des plombiers que l'on "tuyaute"
>>>> [>>>]
;; On met le flag1 à 0 pour l'utiliser comme variable temporaire pour restaurer val
< -
;; while(val != 0)
>> [
;; flag1 += 1
<< +
;; val += 1 (celui où est le flag2 courant de la liste que l'on construit)
>>>> [>>>]
>>>>>>>>>>>> [>>>]
> +
;; val -= 1 (celui de la liste que l'on "tuyaute"
< <<<[<<<]
<<<<<<<<<<<< [<<<]
> -
]
;; On restaure la valeur de val
<<[>>+ <<-]
;; flag1 = 1
+
;; On passe au flag2 suivant
> + >>> -
;; On décale le flag1 de la liste que l'on est en train de construire
< [>>>]
>>>>>>>>>>>> [>>>] + >>> - <<< [<<<]
;; On met le flag2 courant de la liste que l'on est en train de construire à 1
>>>> [>>>] + [<<<]
;; On va à la première liste des plombiers
<<<<<<<<<<<<<[<<<] <<<<<<<[ <<<<<[<<<] <<<<<<<]
;; On va au tuyau courant
<<<<[<<]
;; On décale le flag
+ >>
]
;; On va à la liste des plombiers que l'on est en train de construire
>>>>>>>>>>>>[>>>] >>[ >>>>>>>>>>[>>>] >>]
;; Après le dernier flag1 de la nouvelle liste, il y a un flag1 à -1, on le remet à 0
>>>>>>>>>> [>>>] <<< + <<< [<<<]
;; zero2 est à -1, on fait zero2 = 0
<<<<<<<< +
;; On va au nextMove sur lequel on est en train de faire le switch
<<<< [<<<]
;; On sort de la boucle en utilisant zero2 comme variable temporaire, on met mustBacktrack à 0
<<<<[<<<<+ >>>>-] > - <
]
;; if(mustBacktrack != 0) alors nextMove = 1
+ > [
;; On exécute l'opération R
;; ____
;; | _ \
;; | |_) |
;; | _ <
;; |_| \_\
;; >>> On va copier la liste des plombiers courante dans la nouvelle (à l'identique) <<<
;; On itère sur la liste des plombiers courante
>>>>>> [ -
;; >>> On créé les flags de la nouvelle liste <<<
;; On va au flag1 courant (de la nouvelle liste)
>>> [>>>]
>>>>>>>>>>>> [>>>]
;; flag1 = 1 et flag2 = 1
+ > +
;; On retourne au flag1 courante (de l'ancienne liste)
< [<<<]
<<<<<<<<<<<< [<<<]
;; >>> On copie val (on va utiliser zero2 comme variable temporaire) <<<
;; while(val != 0)
>> [
;; zero2 += 1
> [>>>]
> +
;; val += 1 (la copie)
>>>>>>>>>>> [>>>]
< +
;; val -= 1 (la copiée)
<< [<<<]
<<<<<<<<<<<< [<<<]
>> -
]
;; On restaure val
> [>>>]
;; while(zero2 != 0)
> [
;; val += 1
<<<< [<<<]
>> +
;; zero2 -= 1
> [>>>]
> -
]
;; On retourne au flag1 courant de la liste copiée
<<<< [<<<]
;; On décale le flag
+ >>>
]
;; >>> Maintenant, on va décaler toutes les valeurs à gauche (effectuer l'opération R) <<<
;; On va au premier flag
>>>>>>>>>>>> [
;; On décale val vers la gauche
>> [
<<< +
>>> -
]
;; On passe au flag suivant
>
] <<< [<<<]
;; Maintenant, la valeur qui doit aller dans la dernière case est dans temp
;; while(temp != 0)
>> [
;; On va à la fin du tableau
> [>>>]
;; val += 1
< +
;; temp -= 1
<< [<<<]
>> -
]
;; On retourne à notre mustBacktrack du début
<<<<<<<<<<<<<<[<<<]
;; mustBacktrack = 0
<<< -
]
;; On sort de la boucle en utilisant zero2 comme variable temporaire
<[<<<<+ >>>>-]
] <<<<[>>>>+ <<<<-]
;; Si mustBacktrack est encore à 1, c'est que nextMove = 0
>>>>> [
;; On exécute l'opération A
;; _
;; / \
;; / _ \
;; / ___ \
;; /_/ \_\
;; >>> On copie la liste des plombiers comme dans R <<<
;; Ce code ne sera pas commenté car il est strictement identique au code de R ci-dessus
>>>>>> [ -
>>> [>>>]
>>>>>>>>>>>> [>>>]
+ > +
< [<<<]
<<<<<<<<<<<< [<<<]
>> [
> [>>>]
> +
>>>>>>>>>>> [>>>]
< +
<< [<<<]
<<<<<<<<<<<< [<<<]
>> -
]
> [>>>]
> [
<<<< [<<<]
>> +
> [>>>]
> -
]
<<<< [<<<]
+ >>>
]
;; >>> On va décaler toutes les valeurs vers la droite <<<
;; On va à la fin du tableau, et on itère dessus à l'envers
>>>>>>>>>>>> [>>>]<<<
[
;; On décale la valeur vers la droite
>>[>>>+ <<<-]
;; On passe au flag précédent
<< <<<
]
;; Maintenant, la valeur devant être dans la première case de la liste est tout à la fin, on va corriger ça
>>> [>>>]
;; while(valDeLaFin != 0)
>> [
;; valDuDébut += 1
<< <<<[<<<]
>>>>> +
;; valDeLaFin -= 1
<< [>>>]
>> -
]
;; On retourne à la liste précédente
<< <<<[<<<]
<<<<<<<<<<<<[<<<]
;; mustBacktrack = 0
<<< -
]
;; On va au nouveau tableau
>>>>>>[>>>]
;; bigFlag = 1, continue = 1, smallContinue = 1, nextMove = -1
>> + > + > + > -
;; On va copier bound - 1 dans le nouveau bound (on utilise temp comme variable temporaire)
<<<<<<<<[<<<]
;; while(ancienBound - 1 != 0)
<< - [
;; temp += 1
>>>> +
;; nouveauBound += 1
>[>>>]
>>>>>>> +
;; ancienBound -= 1
<<<<<<<<<<[<<<]
<< -
] +
;; On restaure la valeur initiale de bound
>>>>[<<<<+ >>>>-]
>[>>>]
;; >>> On va regarder si on a trouvé une solution <<<
;; On a trouvé une solution si nbEnd == firstVal
;; firstVal -= nbEnd, zero4 = nbEnd
;; while(nbEnd != 0)
>>>>>>>> [
;; zero4 += 1
>> +
;; firstVal -= 1
>>>> -
;; nbEnd -= 1
<<<<<< -
]
;; zero3 = (firstVal == 0)
;; zero3 = 1
> +
;; if(firstVal != 0)
>>>>> [
;; zero3 = 0
<<<<< -
;; On restaure nbEnd et firstVal (pour ne pas wrapper après)
> [ << + >>>>>> + <<<< - ]
;; On sort de la boucle en utilisant temp
>>>>[<<<+ >>>-]
] <<<[>>>+ <<<-]
;; On restaure nbEnd et firstVal
< [ << + >>>>>> + <<<< - ]
;; if(zero3)
< [
;; On a trouvé une solution \o/
;; continue = 0
<<<<<< -
;; smallContinue = 0
> -
;; zero3 = 0
>>>>> -
]
;; On est déjà à zero3
]
;; On va à smallContinue
<<<<<
]
;; bound += 1
>>> +
;; nextMove = 0
<< +[-]
;; On va à continue
<<
]
;; On va à la première liste de plombiers
<<<<<<[<<<] <<<<<<<[ <<<<<[<<<] <<<<<<<]
;; On affiche bound (qui est différent de 0)
>>>>>
>[-]<
[>+ <-]
>[
>[-]>[-]>[-]>[-]>[-]<<<<<
>++++++++++
<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
>[-] ++++++ [<++++++++ >-]
>[<<+ >>-]
>[<<+ >>-]
<<
]
<[.<]
;; Newline
++++++++++ .
[-]
]
Raw
5.sbf
#include(utils.sbf)
#variables(PrePipe; zero1; zero2; firstFlag)
#variables(Pipe; flag; pipe; nflag)
#_ ICheck = Impossible Check
#variables(PreICheck; temp1; counter; zero1; zero2; temp2; firstFlag1; firstFlag2)
#variables(ICheck; flag1; flag2; val; nflag1; nflag2; nval)
#macro(pipeToPrepipe;; =flag; <<[<<] @PrePipe@zero1;)
#macro(prepipeToPipe;; =firstFlag; [>>] @Pipe@flag;)
#macro(pipeToIcheck1;; =flag; >>[>>]>>>[>>>] @ICheck@flag1;)
#macro(Icheck1ToPipe;; =flag1; <<<[<<<]<<[<<] @Pipe@flag;)
#macro(pipeToIcheck2;; =flag; >>[>>]>>>>[>>>] @ICheck@flag2;)
#macro(Icheck2ToPipe;; =flag2; <<<[<<<]<<<[<<] @Pipe@flag;)
#macro(pipeToPreicheck;; =flag; >>[>>] @PreICheck@temp1;)
#macro(preicheckToPipe;; =temp1; <<[<<] @Pipe@flag;)
#macro(preicheckToIcheck1;; =firstFlag1; [>>>] @ICheck@flag1;)
#macro(icheck1ToPreicheck;; =flag1; <<<[<<<] @PreICheck@zero1;)
#macro(preicheckToIcheck2;; =firstFlag2; [>>>] @ICheck@flag2;)
#macro(icheck2ToPreicheck;; =flag2; <<<[<<<] @PreICheck@zero2;)
@PrePipe@zero1;
=firstFlag;
_readIntList(0)
@Pipe@flag;
_pipeToPrepipe()
#_ ----------------------------------------------------------------------------
#_ ------------------------------IMPOSSIBLE CHECK------------------------------
#_ ----------------------------------------------------------------------------
=firstFlag; [ -
>> [>>] >>>>> [>>>] +>+<
[<<<] <<<< [<<]
+ >>
] @PreICheck@temp1;
_preicheckToIcheck1()
=flag1; +
[<<<] @PreICheck@zero1;
=firstFlag1; -
=temp1; <<[<<] @PrePipe@zero1;
=firstFlag; @Pipe@flag; [ -
#_ copy pipe to counter
=pipe; [
_pipeToPreicheck()
=temp2; +
=counter; +
_preicheckToPipe()
=pipe; -
]
_pipeToPreicheck()
=temp2; [
_preicheckToPipe()
=pipe; +
_pipeToPreicheck()
=temp2; -
]
_preicheckToIcheck1()
=flag2; -
_icheck1ToPreicheck()
=counter; [
_preicheckToIcheck2()
=flag2; + =nflag2; -
=nflag2; [
+
=flag2; [<<<] @PreICheck@zero2;
=firstFlag2; -
@ICheck@flag2;
=flag2;
]
_icheck2ToPreicheck()
=counter; -
]
_preicheckToIcheck2()
=val; +
=flag2; + [<<<] @PreICheck@zero2;
_preicheckToIcheck1() =flag1; + =nflag1; - =flag1; [<<<] @PreICheck@zero1;
_preicheckToPipe()
+ >>
]
@PreICheck@temp1;
=firstFlag1; @ICheck@flag1; [
=val; [
=flag2; -
=val; [-]
]
=flag2; [
=flag1; - _icheck1ToPreicheck()
=counter; [-] +
_preicheckToIcheck1()
=flag1; + =flag2; -
]
=nflag1;
]
<<< [- <<<]
@PreICheck@zero1; +
=counter; [
=zero1; -
=counter; -
] +
=zero1; [
#_ Impossible!
=counter; -
=zero1; _add(4) [ =counter; _add(9) =zero2; _add(2) =zero1; -]
=counter; . _add(4) . [-]
=zero2; . [-]
=zero1;
]
#variables(Plumber; flag1; flag2; val; nflag1; nflag2; nval)
#variables(PrePlumber; lastFlag1; lastFlag2; lastVal; zero1; zero2; bigFlag; continue; smallContinue; nextMove; mustBacktrack; bound; nbEnd; zero3; zero4; temp; firstFlag1; firstFlag2; firstVal)
#_variables(PrePlumber; lastFlag1; lastFlag2; lastVal; zero1; zero2; bigFlag; continue; smallContinue; nextMove; mustBacktrack; bound; nbEnd; zero3; zero4; temp; firstFlag1; firstFlag2; firstVal)
#_variables(PrePlumber; lastFlag1; lastFlag2; lastVal; zero1; zero2; bigFlag; continue; smallContinue; nbEnd; nextMove; mustBacktrack; bound; zero3; zero4; temp; firstFlag1; firstFlag2; firstVal)
#macro(toNextPreplumber;; =firstFlag1; [>>>] @PrePlumber@zero1;)
#macro(toPrevPreplumber;; =lastFlag1; [<<<] @PrePlumber@zero3;)
#macro(toFirstPreplumber;; _toPrevPreplumber() =bigFlag; [ _toPrevPreplumber() =bigFlag;])
#macro(toLastPreplumber;; _toNextPreplumber() =bigFlag; [ _toNextPreplumber() =bigFlag;])
#macro(preplumberToPipe;; =zero1; <<[<<] @Pipe@flag;)
#macro(pipeToPreplumber;; =flag; >>[>>] @PrePlumber@zero1;)
#_ Alg:
#_ while(continue) {
#_ while(bigFlag) {
#_ if(bound == 0) {
#_ backtrack()
#_ }
#_ nextMove += 1
#_ if(nextMove not existing) {
#_ backtrack()
#_ }
#_ advance()
#_ if(firstVal == n) {
#_ bigFlag = 0
#_ continue = 0
#_ }
#_ }
#_ bound += 1
#_ }
=counter; [
=counter; -
=temp1;
<< [<<]
@PrePipe@zero1;
#_ SETUP
=firstFlag; [ -
>>[>>] @PrePlumber@zero1;
=nbEnd; +
=firstFlag1;
[>>>] <<< @Plumber@flag1;
=nflag1; + =nflag2; + =nval; +
=nflag1; [<<<] @PrePlumber@zero3;
=zero1; <<[<<] @Pipe@flag;
+ >>
] @PrePlumber@zero1;
=bound; +
=continue; + [
#_ LOOP
=nextMove; -
=smallContinue; + [
#_ if bound == 0 then mustBacktrack = 1
=mustBacktrack; +
=bound; [
=mustBacktrack; -
_moveTo(bound; zero3)
=bound;
] _moveTo(zero3; bound)
=nextMove; +
#_ if nextMove == 3 then mustBacktrack = 1
=mustBacktrack; +
=nextMove; --- [
=mustBacktrack; -
=nextMove; ++++
_moveTo(nextMove; zero3)
=zero3; ----
=nextMove;
] =zero3; +++ _moveTo(zero3; nextMove)
#_ if mustBacktrack (zero3 = mustAdvance)
=zero3; +
=mustBacktrack; [
#_ backtrack
=zero3; -
#_ if bigFlag = 0 then zero1 = 1
=zero1; +
=bigFlag; [
=zero1; -
#_ rewind
=firstFlag1; [>>>] <<< @Plumber@flag1;
[ =val; [-] =flag2; - =flag1; - <<<]
@PrePlumber@zero3;
=nbEnd; [-] =bound; [-] =mustBacktrack; [-] =nextMove; +[-] =smallContinue; - =continue; - =bigFlag; - =lastFlag1; [<<<]
@PrePlumber@zero3;
_moveTo(bigFlag; zero2)
=bigFlag;
] _moveTo(zero2; bigFlag)
=zero1; [
#_ end
=smallContinue; -
=zero1; -
]
=mustBacktrack; [-]
]
=zero3; [ -
#_ advance
#_ copy nb
=nbEnd; [
=temp; +
=firstFlag1; [>>>] @PrePlumber@zero1;
=nbEnd; +
=lastFlag1; [<<<] @PrePlumber@zero3;
=nbEnd; -
]
_moveTo(temp; nbEnd)
#_ use mustBacktrack as a flag
=mustBacktrack; +
=nextMove; [
#_ nextMove > 0
- [
#_ nextMove > 1
#_ T
#_ set up flags
=firstFlag1; [ -
@Plumber@flag1;
=nflag1; [>>>] @PrePlumber@zero1;
=firstFlag1; [>>>] @Plumber@flag1;
=flag1; + =flag2; +
=flag1; [<<<] @PrePlumber@zero3;
=lastFlag1; [<<<] @Plumber@flag1;
+ >>>
] @PrePlumber@zero1;
=firstFlag1; -
#_ bigFlag = 0
_toPrevPreplumber()
=firstFlag2; -
=bigFlag; [
_toPrevPreplumber()
=bigFlag;
]
=zero1; << [<<] @PrePipe@zero1;
=firstFlag; [ -
#_ set up flag2
@Pipe@flag;
_pipeToPreplumber()
_toLastPreplumber()
=firstFlag1; [>>>] @Plumber@flag1;
=flag2; -
=flag1; <<<[<<<] @PrePlumber@zero3;
_toFirstPreplumber()
_preplumberToPipe()
#_ move flag2
=pipe; [
_pipeToPreplumber()
=temp; +
_toLastPreplumber()
=firstFlag2; [>>>] @Plumber@flag2;
+ >>> - [ +
<<< [<<<] @PrePlumber@zero4;
=firstFlag2; -
@Plumber@flag2;
]
=flag2; <<<[<<<] @PrePlumber@zero4;
_toFirstPreplumber()
_preplumberToPipe()
=pipe; -
]
#_ restore pipe
_pipeToPreplumber()
=temp; [
_preplumberToPipe()
=pipe; +
_pipeToPreplumber()
=temp; -
]
#_ copy the value at the right cell
_toLastPreplumber()
_toPrevPreplumber()
=firstFlag2; [>>>] @Plumber@flag2;
=flag1; -
=val; [
=flag1; +
=nflag2; [>>>] @PrePlumber@zero2;
=firstFlag2; [>>>] @Plumber@flag2;
=val; +
=flag2; <<<[<<<] @PrePlumber@zero4;
=lastFlag2; [<<<] @Plumber@flag2;
=val; -
]
_moveTo(flag1; val)
=flag1; +
#_ move the flags
=flag2; + =nflag2; -
=nflag1; [>>>] @PrePlumber@zero1;
=firstFlag1; [>>>] + >>> - <<< [<<<] @PrePlumber@zero3;
=firstFlag2; [>>>] + [<<<] @PrePlumber@zero4;
_toFirstPreplumber()
_preplumberToPipe()
=flag; + >>
] @PrePlumber@zero1;
_toLastPreplumber()
=firstFlag1; [>>>] <<< + <<< [<<<] @PrePlumber@zero3;
=zero2; +
=lastFlag1; [<<<] @PrePlumber@zero3;
_moveTo(nextMove; zero2) =mustBacktrack; - =nextMove;
] + =mustBacktrack; [
#_ nextMove == 1
#_ R
=firstFlag1; [ -
@Plumber@flag1;
#_ set up the flags
=nflag1; [>>>] @PrePlumber@zero1;
=firstFlag1; [>>>] @Plumber@flag1;
=flag1; + =flag2; +
=flag1; [<<<] @PrePlumber@zero3;
=lastFlag1; [<<<] @Plumber@flag1;
#_ copy the value
=val; [
=nflag1; [>>>] @PrePlumber@zero1;
=zero2; +
=firstFlag1; [>>>] @Plumber@nflag1;
=val; +
=flag1; [<<<] @PrePlumber@zero3;
=lastFlag1; [<<<] @Plumber@flag1;
=val; -
]
=nflag1; [>>>] @PrePlumber@zero1;
=zero2; [
=lastFlag1; [<<<] @Plumber@flag1;
=val; +
=nflag1; [>>>] @PrePlumber@zero1;
=zero2; -
]
=lastFlag1; [<<<] @Plumber@flag1;
=flag1; + >>>
]
@PrePlumber@zero1;
#_ shift values
=firstFlag1; @Plumber@flag1; [
=val; [
<<< +
>>> -
]
=flag1; >>>
] <<< [<<<] @PrePlumber@zero3;
=temp; [
=firstFlag1; [>>>] @Plumber@nflag1;
=val; +
=flag1; [<<<] @PrePlumber@zero3;
=temp; -
]
_toPrevPreplumber()
=mustBacktrack; -
] _moveTo(nextMove; zero2) =nextMove;
] _moveTo(zero2; nextMove)
=mustBacktrack; [
#_ nextMove == 0
#_ A
=firstFlag1; [ -
@Plumber@flag1;
#_ set up the flags
=nflag1; [>>>] @PrePlumber@zero1;
=firstFlag1; [>>>] @Plumber@flag1;
=flag1; + =flag2; +
=flag1; [<<<] @PrePlumber@zero3;
=lastFlag1; [<<<] @Plumber@flag1;
#_ copy the value
=val; [
=nflag1; [>>>] @PrePlumber@zero1;
=zero2; +
=firstFlag1; [>>>] @Plumber@nflag1;
=val; +
=flag1; [<<<] @PrePlumber@zero3;
=lastFlag1; [<<<] @Plumber@flag1;
=val; -
]
=nflag1; [>>>] @PrePlumber@zero1;
=zero2; [
=lastFlag1; [<<<] @Plumber@flag1;
=val; +
=nflag1; [>>>] @PrePlumber@zero1;
=zero2; -
]
=lastFlag1; [<<<] @Plumber@flag1;
=flag1; + >>>
]
@PrePlumber@zero1;
#_ shift values
=firstFlag1; [>>>]<<< @Plumber@flag1;
[
_moveTo(val; nval)
=flag1; <<<
] @PrePlumber@zero3;
=firstFlag1; [>>>] @Plumber@flag1;
=val; [
=flag1; <<<[<<<] @PrePlumber@zero3;
=firstVal; +
=firstFlag1; [>>>] @Plumber@flag1;
=val; -
]
=flag1; <<<[<<<] @PrePlumber@zero3;
_toPrevPreplumber()
=mustBacktrack; -
]
#_ finish advance
#_ set up misc flags
_toNextPreplumber()
=bigFlag; + =continue; + =smallContinue; + =nextMove; -
_toPrevPreplumber()
#_ copy bound
=bound; - [
=temp; +
_toNextPreplumber()
=bound; +
_toPrevPreplumber()
=bound; -
] +
_moveTo(temp; bound)
_toNextPreplumber()
#_ check if the solution was found
=nbEnd; [
=zero4; + =firstVal; -
=nbEnd; -
]
=zero3; +
=firstVal; [
#_ nbEnd != firstVal
=zero3; -
=zero4; [ =nbEnd; + =firstVal; + =zero4; - ]
_moveTo(firstVal; temp)
] _moveTo(temp; firstVal)
=zero4; [ =nbEnd; + =firstVal; + =zero4; - ]
=zero3; [
=continue; -
=smallContinue; -
=zero3; -
]
=zero3;
]
=smallContinue;
]
=bound; +
=nextMove; +[-]
=continue;
]
_toFirstPreplumber()
=bound;
_printInt(no; yes; no)
_add(10) .
[-]
]
Raw
utils.sbf
#cmacro(add;
int i;
int nb = atoi(argv[0]);
if(nb < 0) {
for(i = 0; i < -nb; ++i) {
push("-");
}
} else {
for(i = 0; i < nb; ++i) {
push("+");
}
}
)
#macro(moveTo; v1; v2;;
=v1; [=v2; + =v1; -]
)
#macro(copy; v1; v2; temp;;
=v1; [=v2; + =temp; + =v1; -]
=temp; [ =v1; + =temp; -]
)
#variables(ReadInt; output; continueReading; input; ascii0; temp1; temp2; temp3; temp4)
#macro(readInt;;
#_ ascii0 = 48
=input; _add(6) [- =ascii0; _add(8) =input;]
=continueReading; + [
#_ multiply by 10 output
=continueReading; - #_ use it as a temp variable
=output; [- =continueReading; _add(10) =output;]
_moveTo(continueReading; output)
=continueReading; + #_ restore it
#_ add the new number to output
_moveTo(input; output)
#_ read input
=input; ,
#_ subtract 48 to it
=ascii0; [=input; - =temp1; + =ascii0; -]
_moveTo(temp1; ascii0)
#_ check if it is a number or not (if 0 <= input < 10)
=continueReading; -
_copy(input; temp2; temp1)
=temp1; _add(10) [ -
#_ if temp2 == 0 then continueReading = 1
=temp3; +
=temp2; [ >- ] > [ <
=continueReading; +
=temp2; >->
] <<
=temp2; -
=temp1;
]
=temp2; [-]
=continueReading;
]
=input; [-]
=ascii0; [-]
)
#variables(ReadIntList; flag; output; nflagnb; temp1; temp2)
#macro(readIntList; delta;;
@ReadIntList@flag;
=nflagnb; + [ -
=temp1;
@ReadInt@output;
_readInt();
=output;
@ReadIntList@temp1;
_moveTo(temp1; output)
=temp2; +
=flag; [
=temp1; +
=temp2; -
=flag; -
]
_moveTo(temp1; flag)
=temp1; +
=temp2; [
#_ Number of elements in the list given
_moveTo(output; nflagnb) =nflagnb; _add(delta)
=flag; +
=temp1; -
=temp2; -
]
=temp1; [ -
=nflagnb; [
@ReadIntList@flag;
=nflagnb; +
=flag; -
] +
=nflagnb;
=temp1;
]
=nflagnb;
]
=flag; - @ReadIntList@nflagnb; =flag;
)
#_ before: n d
#_ after: 0 d-n%d n%d n/d
#macro(divMod;;
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
)
#_ before: n d
#_ after: 0 d-n%d n%d
#macro(mod;;
[->-[>+>]>[+[-<+>]>>]<<<<]
)
#variables(PrintInt; n; d; newDigit; newN)
#macro(printIntZeroyes;;
=d; + =n; [
=d; -
_moveTo(n; newDigit)
] _moveTo(newDigit; n)
=d; [ -
_add(6) [=newDigit; _add(8); =d; -]
=newDigit; . [-]
=d;
]
)
#macro(printIntZerono;; )
#macro(printIntCrushyes;; >[-]>[-]>[-]>[-]>[-]<<<<<)
#macro(printIntCrushno;; )
#macro(printIntCleanupyes;; >[>]<[[-]<])
#macro(printIntCleanupno;; )
#macro(printInt; mustHandle0; mustCrushEverything; mustCleanup;;
@PrintInt@n;
_printIntCrushmustCrushEverything()
_printIntZeromustHandle0()
_moveTo(n; d)
=d; @PrintInt@n; [
_printIntCrushmustCrushEverything()
=d; _add(10)
=n; _divMod()
#_ Now n = 0, and d is useless, put the ascii '0' in d
=d; [-] _add(6) [=n; _add(8) =d; -]
_moveTo(newDigit; n)
_moveTo(newN; d)
=d;
]
<[.<]
_printIntCleanupmustCleanup()
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment