Mayan Calculation – CodinGame solution in C
Treat every Mayan digit as a block of H text rows and turn it into a single string key, so the 20 reference glyphs become a lookup table from key to value 0-19. Read each operand top to bottom as base-20 digits (most significant first) into a 64-bit integer with value = value*20 + digit, apply the operator, then repeatedly take result % 20 to print the answer back as glyphs, printing the zero glyph when the result is 0.
The problem
You receive the drawing of the twenty Mayan digits: H lines, each holding the 20 glyphs side by side, every glyph being L characters wide. Then come two numbers written in that script, given as a line count followed by that many lines of width L, stacked vertically with the most significant digit on top. A last line gives one operator among +, -, * and /.
Your program must compute the operation and print the result in the same Mayan glyphs, one digit block of H lines under another. Glyph sizes stay under 100 characters, and both operands and the result fit in a signed 64-bit integer; division is integer division.
Approach, step by step
- Build a glyph lookup tableSlice each of the H header lines into 20 chunks of L characters and append chunk d to the key of digit d. After the header, key[d] is the full drawing of digit d flattened into one string, and comparing two glyphs becomes a plain string comparison.
- Decode each operandThe number of lines S is always a multiple of H, so the operand has S / H digits. Read H lines at a time, concatenate them the same way, find the matching key and fold it into the value with value = value * 20 + digit, starting from the top block.
- Compute in 64-bit integersApply the operator on long long (C), long (Java) or Python ints. Use integer division for / so the result stays a whole number that can be written back in base 20.
- Encode the resultCollect result % 20 and divide by 20 until the value reaches zero, which gives the digits from least to most significant. Print them in reverse order, each as its H rows taken from the lookup table.
- Handle zero explicitlyA do/while loop (or a special case) guarantees that a zero result still prints one block: the zero glyph. A plain while loop prints nothing and fails the tests that subtract equal numbers or multiply by zero.
Complexity
O(H * L * (20 + D))O(H * L * 20)Reading the header and the operands touches every character once, and each of the D operand digits is compared against at most 20 keys. Base-20 conversion of the result needs at most 15 digits for a 64-bit value.
Solution code
Bug fixed in this version: The original C code works on small values but is not reliable. It calls pow() without including math.h, and more importantly it accumulates the operand with a double-precision pow(20, k): doubles only carry 53 bits of precision, so operands above roughly 9 * 10^15 are silently rounded and the printed result is off by a few units (reproduced with random 17-digit additions). It also reads lines with gets(), which was removed from C11 and no longer compiles on strict toolchains, and allocates rows of exactly W or 20*W bytes, leaving no room for the terminating null byte. The replacement below uses integer arithmetic only, bounded scanf reads and string keys.
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;
}
Common mistakes
- Floating-point powers of 20Computing digit * pow(20, k) goes through a double and loses precision once the operand passes 2^53. Horner's rule (value = value * 20 + digit) stays in integers and is simpler.
- Printing nothing for zeroConverting with while (n > 0) produces an empty output when the result is 0. The expected answer is the zero glyph, so either special-case it or use a do/while loop.
- Reading digits in the wrong orderThe top block is the most significant digit, unlike the way you usually peel digits off with % 20. Mixing the two directions gives correct single-digit tests and wrong multi-digit ones.
- Comparing only the first row of a glyphSeveral Mayan digits share their top rows (the bars are at the bottom), so matching a glyph on its first line or on partial rows maps different digits to the same value. Compare the full H x L block.
- Off-by-one buffers in CA header line is exactly 20 * L characters, so the buffer needs 20 * L + 1 bytes for the null terminator. Undersized buffers often work locally and corrupt memory on the validator.
Going further
The lookup does not need to understand what a Mayan digit looks like: the puzzle is really "parse a positional numeral system whose digits are arbitrary pictures". Turning each glyph into a string key reduces decoding to a dictionary lookup, and in Python or Java you can literally use a HashMap<String, Integer> built from the header. That also makes the solution robust to the custom glyph sets used by some validators, where the dots and bars are replaced by other characters. A second point that rarely gets explained is the size budget: 20^14 is about 1.6 * 10^18, so every 64-bit answer fits in at most 15 Mayan digits, which is why a fixed array of 32 slots is plenty for the output digits.
FAQ
Can the result of Mayan Calculation be negative?
No. The tests are built so that subtraction never goes below zero and division is exact integer division, so you only ever encode a non-negative value.
Why does my answer fail only on the big-number test?
Most likely you used floating-point math (pow, Math.pow or float) somewhere in the conversion. Above 2^53 doubles round to even numbers and the last base-20 digit comes out wrong; stick to 64-bit integers.
Do I need BigInteger in Java?
No. Operands and results fit in a signed 64-bit long, so long arithmetic is enough as long as you avoid Math.pow.