Besoin d'explications ? Je suis un lien cliquable qui donne du contexte
Introduction au puzzle
Plier une feuille de papier est une activité à la portée de tous. Le premier constat après avoir plié une feuille de papier est que le nombre de couches de papier a doublé. Cependant, selon le côté sur lequel on se positionne, le nombre de couches peut être différent. En effet, en se plaçant du côté par lequel le pli a été réalisé, une seule couche sera visible. Les autres côtés afficheront deux fois plus de couches.
Un pli est donc comparable à une opération qui, du point de vue d'un côté donné, modifie le nombre de couches :
- Soit double le nombre de couches, si le pli a été effectué latéralement
- Soit fixe à un le nombre, si le pli a été effectué vers le côté opposé
- Soit ajoute le nombre de couches du côté opposé, si le pli a été effectué à partir du côté opposé
Le problème en langage C à traiter est donc de déterminer, selon un côté et une séquence de plis donnés, combien de couches sont visibles après la séquence de pli en se plaçant du côté donnée.
Les données auxquelles nous disposons sont donc :
- Une séquence de plis sous forme de chaîne de caractères où chaque caractère représente une direction R(ight), L(eft), U(p), D(own)
- Un caractère R, L, U, D qui sera la direction par lequel la feuille sera observée
Dans un souci de réalisme, une feuille de papier ne sera pas pliée plus de 8 fois.
Les données à renvoyer sont donc :
- Le nombre de couches de papier visibles depuis la position donnée
Résolution du puzzle
Résumé de la méthode
On va utiliser la même méthode qu'un humain pourrait utiliser. À chaque pli, selon le type de pli (vu plus haut), on modifie le nombre de couches visibles.
Transposition en langage C
On commence par définir le côté par lequel la feuille sera observée après la séquence de plis en assignant un nombre à chaque direction
On créé un tableau qui contiendra la séquence de plis sous forme de nombres (le nombre désigne le côté à partir duquel le pli est réalisé).
Et on réalise une boucle qui va parcourir le tableau créé :
- Si le pli est latéral, le nombre de couches du côté assigné et de son côté opposé est doublé.
- Si le pli est effectué vers le côté opposé, le nombre de couches du côté assigné est ajouté au nombre de couches du côté opposé, tandis que le nombre de couches du côté assigné revient à 1
- Si le pli est effectué à partir du côté opposé, le nombre de couches du côté opposé est ajouté au nombre de couches du côté assigné, tandis que le nombre de couches du côté opposé revient à 1
Code en langage C de la résolution
int folds = 1, dir = 0, length = 0, back_folds = 1;
int folding_order[9];
Les variables sont initialisées. folds est le nombre de plis visibles et back_folds est le nombre de plis du côté opposé
dir est le côté assigné sous forme d'entier, length est le nombre de plis dans la séquence (car le nombre de plis peut varier, pas la taille du tableau tableau, c'est un tableau à taille fixe, bienvenue en C ^^)
Enfin, folding_order est le tableau d'entiers qui continedra la séquence de plis sous forme... d'entiers.
char order[9];
scanf("%[^\n]", order); fgetc(stdin);
char side[6];
scanf("%[^\n]", side);
Ici, order est la chaîne de caractères représentant la séquence de plis et side sera le côté assigné sous forme de caractère.
switch(side[0]) {
case 'R':
dir = 0;
break;
case 'U':
dir = 1;
break;
case 'L':
dir = 2;
break;
case 'D':
dir = 3;
break;
}
Ce bloc d'instruction permet d'assigner le côté assigné en entier. Remarquez que les côtés opposés sont à une distance de 2. Cela permettra de faciliter les calculs quand il s'agira de réaliser la séquence de plis.
switch permet d'établir plusieurs cas en fonction des valeurs prises et case donne les instructions à réaliser en fonction du cas.
Nous pouvons maintenant faire de même pour la séquence de plis, grâce au bloc d'instructions suivant qui parcourt la chaîne de caractères donnée plus tôt :
for (int i = 0; i < 9; i++) {
switch(order[i]) {
case 'R':
folding_order [i] = 0;
length ++;
break;
case 'U':
folding_order [i] = 1;
length ++;
break;
case 'L':
folding_order [i] = 2;
length ++;
break;
case 'D':
folding_order [i] = 3;
length ++;
break;
}
}
length ++; permet d'ajouter 1 à la longueur de la séquence, donnant une longueur dynamique à la séquence de plis.
La boucle principale est la suivante :
for (int i = 0; i < length; i++) {
if (folding_order[i] == dir) {
back_folds += folds;
folds = 1;
}
else if (folding_order[i] == dir+2 || folding_order[i] == dir-2) {
folds += back_folds;
back_folds = 1;
}
else {
folds *= 2;
back_folds *= 2;
}
}
3 cas se présentent ici :
- Si le pli part du côté assigné (donc que le nombre assigné au pli est celui assigné à la direction), alors, comme dit précédemment, le nombre de plis visibles revient à 1 et celui des plis opposés est augmenté
- Sinon, si le pli part du côté opposé (donc que le nombre assigné au pli est à une distance de 2 du côté assigné), la situation inverse par rapport à la précédente se produit.
- Sinon, le pli est latéral, et le nombre de plis visibles et opposés est doublé.
Comparaison avec un autre Codingamer
Le code donné par l'utilisateur Hellfire91 sur Codingame suit une méthode qui diffère par l'ordre des actions réalisées notamment.
Là où, pour le code étudié plus haut le côté assigné était d'abord pris en compte, ce code traite la séquence de plis pour tous les côtés, puis donne en sortie le côté demandé.
Ainsi, tous les côtés auront un pli différent d'un autre en prenant en compte le pli réalisé dans la séquence.
Voici le code :
int main()
{
char order[9];
scanf("%[^\n]", order); fgetc(stdin);
char side[6];
scanf("%[^\n]", side);
char sides[4] = { 'U', 'R', 'D', 'L' };
int count[4] = { 1, 1, 1, 1 };
int s = 0;
for (int ind = 0; ind < 9 && order[ind] != 0; ind++)
{
for (s = 0; s < 4; s++)
{
if (sides[s] == order[ind])
break;
}
count[(s + 1) % 4] *= 2;
count[(s + 2) % 4] += count[s];
count[(s + 3) % 4] *= 2;
count[s] = 1;
}
for (s = 0; s < 4; s++)
{
if (sides[s] == side[0])
break;
}
printf("%d\n", count[s]);
return 0;
}
Cette stratégie reprend le fait d'espacer de 2 les côtés opposés pour faciliter les calculs
Ce code est plutôt clair, il permet d'être compris par un humain comprenant le langage C, tout en restant court et efficace.
Bilan
La réalisation de ce puzzle améliore la capacité de visualiser des situations comme une séquence de plis d'une feuille de papier, et d'en tirer des propriétés afin de le transposer en programme. Cela permet de travailler sur des situations plus concrètes que des problèmes numériques.