Codingame Solution: Mayan Calculation

The Goal

Upon discovering a new Maya site, hundreds of mathematics, physics and astronomy books have been uncovered.

The end of the world might arrive sooner than we thought, but we need you to be sure that it doesn't!

Thus, in order to computerize the mayan scientific calculations, you're asked to develop a program capable of performing basic arithmetical operations between two mayan numbers.

Rules

The mayan numerical system contains 20 numerals going from 0 to 19. Here's an ASCII example of their representation:

0	1	2	3	4	5	6	7	8	9
.oo. o..o .oo. ....	o... .... .... ....	oo.. .... .... ....	ooo. .... .... ....	oooo .... .... ....	.... ---- .... ....	o... ---- .... ....	oo.. ---- .... ....	ooo. ---- .... ....	oooo ---- .... ....
10	11	12	13	14	15	16	17	18	19
.... ---- ---- ....	o... ---- ---- ....	oo.. ---- ---- ....	ooo. ---- ---- ....	oooo ---- ---- ....	.... ---- ---- ----	o... ---- ---- ----	oo.. ---- ---- ----	ooo. ---- ---- ----	oooo ---- ---- ----

A mayan number is divided into vertical sections. Each section contains a numeral (from 0 to 19) representing a power of 20. The lowest section corresponds to 20⁰, the one above to 20¹ and so on.

Thereby, the example below is : (12 x 20 x 20) + (0 x 20) + 5 = 4805

To spice the problem up, the mayans used several dialects, and the graphical representation of the numerals could vary from one dialect to another.
 
The representation of the mayan numerals will be given as the input of your program in the form of ASCII characters. You will have to display the result of the operation between the two given mayan numbers. The possible operations are *, /, +, -

Game Input

Input

Line 1: the width L and height H of a mayan numeral.

H next lines: the ASCII representation of the 20 mayan numerals. Each line is (20 x L) characters long.

Next line: the amount of lines S1 of the first number.

S1 next lines: the first number, each line having L characters.

Next line: the amount of lines S2 of the second number.

S2 next lines: the second number, each line having L characters.

Last line: the operation to carry out: *, /, +, or -

Output

The result of the operation in mayan numeration, H lines per section, each line having L characters.

Constraints

0 < L, H < 100
0 < S1, S2 < 1000
The remainder of a division is always 0.
The mayan numbers given as input will not exceed 2⁶³.

Solution

This problem is a nice exercise for arbitrary large number handling. We use C here to implement the solution, which allows 64bit integers with long long int. The basic skeleton is this; we read in the alphabet into an array of strings, read the two numbers we need to calculate and finally read the operator. This allows us to implement the main routine like this:

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

int main() {

    int L, H;
    char M[20][2000];
    char OP;
    long long int N1, N2;

    scanf("%d%d", &L, &H);
    fgetc(stdin);

    readAlphabet(M, L, H);

    N1 = readNum(M, L, H);
    N2 = readNum(M, L, H);

    scanf("%c", &OP);
    fgetc(stdin);

    switch (OP) {
        case '+':
            printNum(M, L, H, N1 + N2);
            break;
        case '*':
            printNum(M, L, H, N1 * N2);
            break;
        case '-':
            printNum(M, L, H, N1 - N2);
            break;
        case '/':
            printNum(M, L, H, N1 / N2);
            break;
    }
    return 0;
}

Reading in the alphabet is quite easy. For each line we read the full string and cut it into L-sized pieces. After that, we append the slice to the map:

void readAlphabet(char M[20][2000], int L, int H) {

    for (int y = 0; y < H; y++) {

        char numeral[2048];
        scanf("%s", numeral);
        fgetc(stdin);

        for (int i = 0; i < 20; i++) {

            for (int x = 0; x < L; x++) {
                M[i][y * L + x] = numeral[i * L + x];
            }
        }
    }
}

Now the interesting part. We read in H lines S times. For each symbol we get this way, we need to lookup the symbol in the map. Since we appended the strings only, it's a string comparision to find the matching index. One tricky thing is the base-coeffitient. We need to start with a the largest power of 20 and successively reduce the base, since we read the data in reverse. This brings us to the following implementation:

long long int readNum(char M[20][2000], int L, int H) {

    char tmp[2000];
    long long int R = 0;
    int S;
    scanf("%d", &S);
    fgetc(stdin);

    long long int b = pow(20, S / H - 1);

    for (int i = 0; i < S;) {

        for (int y = 0; y < H; y++) {
            scanf("%s", (tmp + y * L));
            fgetc(stdin);
        }

        for (int j = 0; j < 20; j++) {

            if (0 == memcmp(M[j], tmp, H * L)) {
                R += b * j;
                break;
            }
        }
        b /= 20;
        i += H;
    }
    return R;
}

At the end, we need to print the result in the mayan alphabet again. That's simply the reverse of the read of the numbers. We divide the number into an array of base 20 and print the characters forming the final symbol from the map:

void printNum(char M[20][2000], int L, int H, long long int n) {

    long long int nums[16] = {0}; // log20(2^64)

    int i = 0;

    if (n == 0)
        i++;

    while (n) {

        long long int t = n / 20;
        long long int r = n - t * 20;

        nums[i++] = r;
        n = t;
    }

    while (i > 0) {

        n = nums[--i];

        for (int j = 0; j < L * H; j++) {

            printf("%c", M[n][j]);

            if ((j % L) == (L - 1)) {
                printf("\n");
            }
        }
    }
}

All images are copyright to Codingame