Tous les défis
Moyen 0 résolus 0 % de réussite

Trouver la règle du motif

Devinez la règle d'une famille de carrés de lettres à partir de ses premiers membres, puis construisez le membre pour n'importe quel n.

Ce que vous allez apprendre

  • Décrire une image par une règle sur les numéros de ligne et de colonne
  • Calculer un numéro d'anneau comme le maximum de deux distances
  • Associer un nombre à une lettre

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
                  CCCCC

Observez-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

Exemple 1
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"].

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.