Question for Allen

Exercise 1: cryptarithm.c (

3

marks)

A cryptarithm is a puzzle where digits have to be assigned to the letters of some words, different
letters being assigned different digits, and no word starting with 0, such that a number of conditions
are satisfied, that are naturally related to the meanings of the words when the words do have a
meaning. The program sample_cryptarithm.c that comes with this assignment provides you with
an example of a cryptarithm, where the task is to assign digits to the letters in three, four and
eight,

in such a way that:

• three is prime;

• four is a perfect square;

• eight is a perfect cube

It has a unique solution, namely,

4

2

611 for three, 70

5

6 for four, and 13824 for eight (so t is assigned
the digit 4, h is assigned the digit 2, etc.).

Write a program that assigns a digit to each letter that occurs in the words one, two, seven and
nine, distinct letters being assigned distinct digits, and the digit assigned to the first letter of each
of the three words being nonzero, such that:

• one + one = two;

• seven is prime;

• nine is a perfect square.

The output of your program, saved as cryptarithm.c, should be a line of the form

one = …, two = …, seven = ….. and nine = …. is a solution.

for each found solution, with of course every occurrence of . replaced by an appropriate digit.

Your program should not make any assumption on the actual solution(s), except obvious ones on
the ranges of some values.

For this exercise, the maximum number of indentations is set to 5 (use the style_sheet.txt file
and the mycstyle script to check that your program complies with this requirement).

If you use the function sqrt() from the standard library to compute the square root of a number,
do not forget to insert the line:

#include

2

Exercise 2: multiplication.c (3 marks)

A related kind of puzzle consists in assigning digits to stars so that some operation such as a mul-
tiplication or a division whose outline is given is satisfied, possibly together with other constraints.
The program sample_multiplication.c that comes with this assignment provides you with an
example of this kind of puzzle, where the aim is to solve the multiplication

* *

*

x

* * *

—

—-

* * * *

* * * *
* * * *

—

——

——-

*

* * * * *

in such a way that:

• each star stands for a digit, with the leftmost star on each line standing for a nonzero digit;

• all partial products are made up of the same digits;

• the first and second partial products are different;

• the orderings of digits in the second and third partial products are inverse of each other;

• the third partial product is the sum of the first two partial products.

Write a program that solves the multiplication

* * * *
x * * *
——-
* * * * *
* * * * *
* * * *
————-

* * * * * * *

where:

• all digits of the multiplicand are distinct and strictly positive, and

• all digits in the multiplier, partial products and final product occur in the multiplicand.

3

The output of your program, saved as multiplication.c, should be of the form

….

x …

—-

…..

…..
….
——-

…….

for each found solution, with of course every occurrence of . being replaced by an appropriate digit.

Your program should not make any assumption on the actual solution(s), except obvious ones on
the ranges of some values.

For this exercise, the maximum number of indentations is set to 4 (use the style_sheet.txt file
and the mycstyle script to check that your program complies with this requirement).

Exercise 3: quotient.c (3 marks)

Write a program that finds all fractions of the form n
d

such that n and d are positive integers with
no occurrence of 0, n

d
evaluates to 0.5, and every nonzero digit occurs once and only once in n or d.

To print out your solutions properly, your code should include a statement of the following form:

printf(“%d / %d = 0.5\n”, …, …);

for each found solution

and no other printf() statement.

Your program should be saved as quotient.c.

Your program should not make any assumption on the actual solution(s), except obvious ones on
the ranges of some values.
For this exercise, the maximum number of indentations is set to 4 (use the style_sheet.txt file
and the mycstyle script to check that your program complies with this requirement).
4

Exercise 4: square.c (more difficult, 1 mark)

Write a program that finds all possible ways of replacing stars with digits in

*
* * *
* * * * *

* * * * * * * * *

in such a way that:

• all resulting numbers, whether read horizontally or vertically, are perfect squares;

• numbers consisting of 2 digits or more do not start with 0;

• 0 can be one of the 1-digit numbers.

To print out your solutions properly, your code should include a sequence of statements of the
following form:

printf(“%5d\n”, …);

printf(“%6d\n”, …);

printf(“%7d\n”, …);

printf(“%d\n\n”, …);

and no other printf() statement.

Your program should not make any assumption on the actual solution, except obvious ones on the
ranges of some values.

Your program should be saved as square.c.

For this exercise, the maximum number of indentations is set to 6 (use the style_sheet.txt file
and the mycstyle script to check that your program complies with this requirement).

Your program should not make any assumption on the actual solution(s), except obvious ones on
the ranges of some values.

For this exercise, you will score 0.25 mark by automarking if your program outputs the solution(s)
in less than 1 second on my machine, and 0.5 mark if it outputs the solution(s) in less than 0.1
second.

If you use the function sqrt() or the function fmod() from the standard library to compute the
square root of a number or to compute the remainder of a floating point division, respectively, do
not forget to insert the line:

#include
5

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Description: Assigns a digit to each letter that occurs in the words *
* “three”, “four” and “eight”, distinct letters being assigned *
* distinct digits, and the digit assigned to the first letter *
* of each of the three words being nonzero, such that *
* – three is prime, *
* – four is a perfect square, and *
* – eight is a perfect cube. *
* *
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include
#include
#include
#include
/* The least possible value for eight is 10234,
* and the cubic root of 10234 is 21.71.
* The greatest possible value for eight is 98765,
* and the cubic root of 98765 is 46.22. */
#define MIN_EIGHT 22
#define MAX_EIGHT 46
/* The least possible value for four is 1023,
* and the square root of 1023 is 31.98.
* The greatest possible value for four is 9876,
* and the square root of 9876 is 99.38. */
#define MIN_FOUR 32
#define MAX_FOUR 99
bool is_prime(int);
int main(void) {
for (int n = MIN_EIGHT; n <= MAX_EIGHT; ++n) { int eight = n * n * n; int digits_eight[10] = {0}; int e = eight / 10000; /* three has to be prime hence e cannot be even. */ if (e % 2 == 0) continue; /* We memorise e. */ digits_eight[e] = 1; int i = eight / 1000 % 10; /* digits_eight[i] becomes equal to 1 if i has not been seen, and to 2 otherwise. */ if (++digits_eight[i] == 2) continue; int g = eight / 100 % 10; /* digits_eight[g] becomes equal to 1 if g has not been seen, and to 2 otherwise. */ if (++digits_eight[g] == 2) continue; int h = eight / 10 % 10; /* digits_eight[h] becomes equal to 1 if h has not been seen, and to 2 otherwise. */ if (++digits_eight[h] == 2) continue; int t = eight % 10; /* three does not start with 0. */ if (t == 0) continue; /* digits_eight[t] becomes equal to 1 if t has not been seen, and to 2 otherwise. */ if (++digits_eight[t] == 2) continue; for (int m = MIN_FOUR; m <= MAX_FOUR; ++m) { /* If the current attempt at setting four to a suitable value eventually fails * then we need to remember the current value of eight. */ int digits_eight_four[10]; for (int i = 0; i < 10; ++i) digits_eight_four[i] = digits_eight[i]; int four = m * m; int f = four / 1000; /* digits_eight_four[f] becomes equal to 1 if f has not been seen, and to 2 otherwise. */ if (++digits_eight_four[f] == 2) continue; int o = four / 100 % 10; /* digits_eight_four[o] becomes equal to 1 if o has not been seen, and to 2 otherwise. */ if (++digits_eight_four[o] == 2) continue; int u = four / 10 % 10; /* digits_eight_four[u] becomes equal to 1 if u has not been seen, and to 2 otherwise. */ if (++digits_eight_four[u] == 2) continue; int r = four % 10; if (digits_eight_four[r]) continue; int three = 10000 * t + 1000 * h + 100 * r + 10 * e + e; if (is_prime(three)) printf("three = %d, four = %d and eight = %d is a solution.\n", three, four, eight); } } return EXIT_SUCCESS; } bool is_prime(int n) { /* Returns false if n is even. */ if ((n % 2) == 0) return false; /* If n is not prime then it has a factor at most equal to its square root. */ const int max = sqrt(n); /* Returns false if n is divisible by an odd number. */ for (int k = 3; k <= max; k += 2) { if (n % k == 0) return false; } return true; }

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Description: Finds all multiplications of the form *
* * * * *
* x * * * *
* ——- *
* * * * * *
* * * * * *
* * * * * *
* —————- *
* * * * * * * *
* that satisfy the following conditions: *
* – each star stands for a digit, with the leftmost star *
* on each line standing for a nonzero digit; *
* – all partial products are made up of the same digits; *
* – the first and second partial products are different; *
* – the orderings of digits in the second and third *
* partial products are inverse of each other; *
* – the third partial product is the sum of the first two *
* partial products. *
* *
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include
#include
int main(void) {
for (int m = 100; m < 1000; ++m) for (int n = 100; n < 1000; ++n) { int product = m * n; if (product < 100000) continue; int partial_product1 = m * (n % 10); if (partial_product1 < 1000) continue; int partial_product2 = m * (n / 10 % 10); if (partial_product2 < 1000) continue; if (partial_product1 == partial_product2) continue; int partial_product3 = m * (n / 100); if (partial_product3 < 1000) continue; if (partial_product3 != partial_product1 + partial_product2) continue; /* Write first partial product as p11 p12 p13 p14. */ int p11 = partial_product1 / 1000; int p12 = partial_product1 / 100 % 10; int p13 = partial_product1 / 10 % 10; int p14 = partial_product1 % 10; /* Write second partial product as p21 p22 p23 p24. */ int p21 = partial_product2 / 1000; int p22 = partial_product2 / 100 % 10; int p23 = partial_product2 / 10 % 10; int p24 = partial_product2 % 10; /* Write third partial product as p31 p32 p33 p34. */ int p31 = partial_product3 / 1000; int p32 = partial_product3 / 100 % 10; int p33 = partial_product3 / 10 % 10; int p34 = partial_product3 % 10; /* Check that ordering of digits in second and third partial products * are inverse of each other. */ if (p21 != p34 || p22 != p33 || p23 != p32 || p24 != p31) continue; /* Set the p11-th, p12-th, p13-th and p14-th bits of digits_1 to 1. */ int digits_1 = 1 << p11; digits_1 |= 1 << p12; digits_1 |= 1 << p13; digits_1 |= 1 << p14; /* Set the p21-th, p22-th, p23-th and p24-th bits of digits_2 to 1. */ int digits_2 = 1 << p21; digits_2 |= 1 << p22; digits_2 |= 1 << p23; digits_2 |= 1 << p24; /* Check that first and second partial products, hence all partial products, * are made up of the same digits. */ if (digits_1 != digits_2) continue; printf("%6d\n x%4d\n", m, n); printf(" ---\n"); printf("%6d\n%5d\n%4d\n", partial_product1, partial_product2, partial_product3); printf("------\n"); printf("%d\n", product); } return EXIT_SUCCESS; }