Question 2 of 8: Programming — Self-Describing Integers and a Crypto-Arithmetic Solver

Question 2: Programming — Self-Describing Integers and a Crypto-Arithmetic Solver (20 marks: (a) 10, (b) 10)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) A candidate integer, digit positions labeled left to right from 0. (b) An addition puzzle x + y = z written in letters, each letter a distinct digit 0–9, $x$ and $y$ at most 8 letters each.

Find. (a) Whether the entered number is self-describing. (b) Any assignment of digits to letters that makes the addition true.

Approach. (a) Read the number as a string, check every position $i$ against a direct count of how many digits equal $i$. (b) The puzzle has at most ten distinct letters (one per digit 0–9), so try every permutation of the ten digits over the letters actually used, rejecting a permutation the moment a leading letter would be zero or the sum fails — a brute force that is completely tractable at $10! = 3{,}628{,}800$ in the worst case.

(a) Self-describing integer checker (10 marks)

1. Restate the rule as a direct check, not a search. For an $n$-digit number with digits $d_0 d_1 \ldots d_{n-1}$, self-describing means $$d_i = \bigl|\{\,j : d_j = i\,\}\bigr| \qquad \text{for every } i = 0,\ldots,n-1$$ — "the value stored at position $i$ equals a count of digit $i$'s" translates directly into one counting pass per position.
2. Write the program. Reading the number as a character string (rather than as an int) sidesteps the need to re-extract digits and their count $n$ separately, exactly as the hint suggests.

   #include <stdio.h>
   #include <string.h>
   
   #define MAX_DIGITS 32
   
   int main(void)
   {
       char buf[MAX_DIGITS + 2];
       int  digit[MAX_DIGITS];
       int  n, i, j, count, ok = 1;
   
       printf("Enter a positive integer: ");
       if (scanf("%31s", buf) != 1) {
           printf("Invalid input.\n");
           return 1;
       }
       n = (int)strlen(buf);
   
       for (i = 0; i < n; i++) {
           if (buf[i] < '0' || buf[i] > '9') {
               printf("Invalid input.\n");
               return 1;
           }
           digit[i] = buf[i] - '0';
       }
   
       for (i = 0; i < n && ok; i++) {
           count = 0;
           for (j = 0; j < n; j++)
               if (digit[j] == i)
                   count++;
           if (count != digit[i])
               ok = 0;
       }
   
       printf("%s is %sself-describing.\n", buf, ok ? "" : "NOT ");
       return 0;
   }

3. Trace the paper's own examples. For 2020 ($n=4$): position 0 needs the count of 0's, which is 2 (positions 1, 3) — matches $d_0=2$; position 1 needs the count of 1's, which is 0 — matches $d_1=0$; position 2 needs the count of 2's, which is 2 (positions 0, 2) — matches $d_2=2$; position 3 needs the count of 3's, which is 0 — matches $d_3=0$. All four positions confirm, so 2020 passes, and the identical position-by-position check confirms 1210 and 3211000 as well. $$\boxed{\text{2020, 1210, 3211000 are self-describing; 1234, 9999 are not}}$$

(b) Crypto-arithmetic solver (10 marks)

1. Bound the search space. Collecting the distinct letters across $x$, $y$ and $z$ gives at most 10 letters (there are only 10 digits to assign), so a brute-force search tries every one-to-one mapping of digits 0–9 onto those letters, i.e. every permutation of 10 things taken $k$ at a time, $k \le 10$ — at most $10! = 3{,}628{,}800$ candidates, each checked in $O(\text{word length})$ time.
2. Write the program. std::next_permutation enumerates permutations of a fixed 10-element digit array in lexicographic order; only the first $k$ slots are read off for the $k$ letters actually used, which is equivalent to permutation-with-selection.

   #include <iostream>
   #include <string>
   #include <algorithm>
   using namespace std;
   
   long long wordValue(const string &w, const int assign[26])
   {
       long long v = 0;
       for (char c : w)
           v = v * 10 + assign[c - 'A'];
       return v;
   }
   
   int main()
   {
       string x, y, z;
       cout << "Enter puzzle as x y z (e.g. SEND MORE MONEY): ";
       cin >> x >> y >> z;
   
       bool used[26] = {false};
       char letters[10];
       int  nLetters = 0;
       for (const string &w : {x, y, z})
           for (char c : w)
               if (!used[c - 'A']) { used[c - 'A'] = true; letters[nLetters++] = c; }
   
       bool leading[26] = {false};
       leading[x[0] - 'A'] = leading[y[0] - 'A'] = leading[z[0] - 'A'] = true;
   
       int digits[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
       do {
           int assign[26];
           bool leadZero = false;
           for (int i = 0; i < nLetters; i++) {
               assign[letters[i] - 'A'] = digits[i];
               if (digits[i] == 0 && leading[letters[i] - 'A'])
                   leadZero = true;
           }
           if (leadZero) continue;
   
           if (wordValue(x, assign) + wordValue(y, assign) == wordValue(z, assign)) {
               cout << "Solution:";
               for (int i = 0; i < nLetters; i++)
                   cout << ' ' << letters[i] << '=' << assign[letters[i] - 'A'];
               cout << '\n';
               return 0;
           }
       } while (next_permutation(digits, digits + 10));
   
       cout << "No solution exists.\n";
       return 0;
   }

   Only the first nLetters entries of the permuted digits array are used per trial, and next_permutation still enumerates every distinct assignment because the remaining $10-\text{nLetters}$ digits are simply along for the ride. Each distinct assignment is in fact generated $(10-\text{nLetters})!$ times over — harmlessly, since the first match returns immediately — so the loop is exhaustive at the cost of that constant factor; enumerating only the $k$-permutations directly (a recursive assignment with a used[10] flag array) removes it.
3. Confirm the paper's example. Running the search over SEND + MORE = MONEY (8 distinct letters, so $10!/(10-8)! = 1{,}814{,}400$ candidates in the worst case, though the true solution is found well before the search is exhausted) returns exactly the assignment the paper quotes. $$\boxed{D{=}7,\ E{=}5,\ M{=}1,\ N{=}6,\ O{=}0,\ R{=}8,\ S{=}9,\ Y{=}2}$$ Substituting: $9567 + 1085 = 10652$, i.e. SEND=9567, MORE=1085, MONEY=10652, and $9567+1085=10652$ checks exactly.