Problème
Un livre d'énigmes montre les trois premiers membres d'une famille de motifs et demande de trouver la suite :
n = 1 n = 2 n = 3
A BBB CCCCC
BAB CBBBC
BBB CBABC
CBBBC
CCCCCObservez-les avant de lire la suite et essayez de formuler la règle vous-même. La voici, énoncée précisément. Le membre n est un carré de 2n − 1 lignes, chacune longue de 2n − 1 lettres, sans espace. Numérotez les lignes et les colonnes à partir de 0, le centre étant à la position n − 1. La case de la ligne r et de la colonne c contient la lettre située d rangs après A dans l'alphabet, où d = max(|r − (n − 1)|, |c − (n − 1)|) est le nombre d'anneaux qui séparent la case du centre. Le centre est donc A, l'anneau qui l'entoure est B, et le bord extérieur porte la n-ième lettre.
Implémentez decode_the_pattern(n).
Entrée
n : le numéro du membre de la famille à construire (au plus 26, pour ne jamais dépasser Z).
Sortie
Renvoyez les 2n − 1 lignes de haut en bas. Si n vaut 0, renvoyez une liste vide.
Contraintes
0 ≤ n ≤ 26
Exemples
Entrée :
n = 2
Sortie attendue :
expected = ["BBB", "BAB", "BBB"]
Entrée :
long long n = 2;
Sortie attendue :
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
Entrée :
long n = 2;
Sortie attendue :
string[] expected = new string[] {"BBB", "BAB", "BBB"};
Explication
Seul le centre (1, 1) est à 0 anneau, toutes les autres cases sont à 1 anneau : ["BBB", "BAB", "BBB"].
Entrée :
n = 4
Sortie attendue :
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
Entrée :
long long n = 4;
Sortie attendue :
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Entrée :
long n = 4;
Sortie attendue :
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Explication
Les cases du bord sont à 3 anneaux (D), et la ligne 3 est celle du milieu : ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Repérez le centre de chaque carré d'exemple et regardez comment les lettres changent quand on s'en éloigne.
Indice 2
Les cases d'un même anneau ont la même lettre, et le numéro d'anneau est la plus grande des deux distances au centre (en ligne et en colonne).
Indice 3
Vérifiez votre règle sur l'exemple n = 3 avant de construire un n quelconque.
Complexité attendue
temps O(n^2), espace supplémentaire O(n^2)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.