Coding Solution

Mayan Calculation – solution CodinGame en C

Moyenbase conversionstring parsing2D character grids64-bit arithmeticMis à jour le
Réponse courte

On traite chaque chiffre maya comme un bloc de H lignes de texte qu'on aplatit en une seule chaîne clé : les 20 glyphes de référence deviennent une table de correspondance clé → valeur de 0 à 19. On lit chaque opérande de haut en bas comme des chiffres en base 20 (poids fort en premier) dans un entier 64 bits avec value = value*20 + digit, on applique l'opérateur, puis on extrait result % 20 à répétition pour réécrire la réponse en glyphes, sans oublier d'afficher le glyphe zéro quand le résultat vaut 0.

L'énoncé

On reçoit le dessin des vingt chiffres mayas : H lignes contenant chacune les 20 glyphes côte à côte, chaque glyphe faisant L caractères de large. Viennent ensuite deux nombres écrits dans cette numération, chacun donné par un nombre de lignes puis autant de lignes de largeur L, empilées verticalement avec le chiffre de poids fort en haut. Une dernière ligne donne un opérateur parmi +, -, * et /.

Le programme doit effectuer l'opération et afficher le résultat avec les mêmes glyphes, un bloc de H lignes sous l'autre. Les glyphes restent sous 100 caractères, les opérandes comme le résultat tiennent dans un entier signé 64 bits, et la division est entière.

La démarche, étape par étape

  1. Construire la table des glyphesOn découpe chacune des H lignes d'en-tête en 20 tranches de L caractères et on ajoute la tranche d à la clé du chiffre d. Après l'en-tête, key[d] contient le dessin complet du chiffre d aplati en une chaîne : comparer deux glyphes revient à comparer deux chaînes.
  2. Décoder chaque opérandeLe nombre de lignes S est toujours un multiple de H, donc l'opérande compte S / H chiffres. On lit H lignes à la fois, on les concatène de la même façon, on cherche la clé correspondante et on l'intègre avec value = value * 20 + digit, en partant du bloc du haut.
  3. Calculer en entiers 64 bitsOn applique l'opérateur sur des long long (C), long (Java) ou int Python. Pour /, on garde la division entière afin que le résultat reste un entier réécrivable en base 20.
  4. Encoder le résultatOn prélève result % 20 et on divise par 20 jusqu'à zéro, ce qui donne les chiffres du poids faible au poids fort. On les affiche dans l'ordre inverse, chacun sous la forme de ses H lignes prises dans la table.
  5. Gérer explicitement le zéroUne boucle do/while (ou un cas particulier) garantit qu'un résultat nul affiche quand même un bloc : le glyphe zéro. Un simple while n'affiche rien et échoue sur les tests qui soustraient deux nombres égaux ou multiplient par zéro.

Complexité

TempsO(H * L * (20 + D))
MémoireO(H * L * 20)

La lecture de l'en-tête et des opérandes touche chaque caractère une fois, et chacun des D chiffres d'opérande est comparé à au plus 20 clés. La conversion du résultat en base 20 demande au plus 15 chiffres pour une valeur 64 bits.

Code de la solution

Mayan Calculation – C

#include <stdio.h>
#include <string.h>

int L, H;
char glyph[20][10000];   /* glyph[d] = the H rows of digit d, concatenated */

/* Reads 'lines' rows of a Mayan number and returns its decimal value */
long long readNumber(void) {
    int lines;
    scanf("%d", &lines);
    long long value = 0;
    char key[10000], row[128];
    for (int k = 0; k < lines / H; k++) {
        key[0] = '\0';
        for (int r = 0; r < H; r++) {
            scanf("%127s", row);
            strcat(key, row);
        }
        int d = 0;
        while (d < 20 && strcmp(glyph[d], key) != 0) d++;
        value = value * 20 + d;   /* most significant digit comes first */
    }
    return value;
}

void printDigit(int d) {
    for (int r = 0; r < H; r++)
        printf("%.*s\n", L, glyph[d] + r * L);
}

int main(void) {
    scanf("%d %d", &L, &H);
    static char row[2048];
    for (int r = 0; r < H; r++) {
        scanf("%2047s", row);
        for (int d = 0; d < 20; d++)
            strncat(glyph[d], row + d * L, L);
    }
    long long a = readNumber();
    long long b = readNumber();
    char op;
    scanf(" %c", &op);

    long long res = op == '+' ? a + b : op == '-' ? a - b : op == '*' ? a * b : a / b;

    /* collect base-20 digits, least significant first */
    int digits[32], n = 0;
    do {
        digits[n++] = res % 20;
        res /= 20;
    } while (res > 0);
    for (int i = n - 1; i >= 0; i--)
        printDigit(digits[i]);
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

La table de correspondance n'a pas besoin de comprendre à quoi ressemble un chiffre maya : le puzzle revient à « analyser un système de numération positionnel dont les chiffres sont des images arbitraires ». Transformer chaque glyphe en chaîne clé réduit le décodage à une recherche dans un dictionnaire, et en Python ou en Java on peut littéralement utiliser une HashMap<String, Integer> construite à partir de l'en-tête. Cela rend aussi la solution robuste aux jeux de glyphes personnalisés de certains validateurs, où les points et les barres sont remplacés par d'autres caractères. Un second point rarement expliqué est le budget de taille : 20^14 vaut environ 1,6 * 10^18, donc toute réponse 64 bits tient en au plus 15 chiffres mayas, ce qui explique qu'un tableau fixe de 32 cases suffise largement pour les chiffres de sortie.

Questions fréquentes

Le résultat de Mayan Calculation peut-il être négatif ?

Non. Les tests sont construits pour que la soustraction ne passe jamais sous zéro et que la division soit une division entière exacte : on n'encode jamais qu'une valeur positive ou nulle.

Pourquoi ma réponse échoue-t-elle seulement sur le test avec de grands nombres ?

Très probablement à cause d'un calcul en flottant (pow, Math.pow ou float) quelque part dans la conversion. Au-delà de 2^53, les doubles arrondissent aux nombres pairs et le dernier chiffre en base 20 est faux ; il faut rester en entiers 64 bits.

Faut-il BigInteger en Java ?

Non. Opérandes et résultats tiennent dans un long signé 64 bits, donc l'arithmétique sur long suffit tant qu'on évite Math.pow.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome