Enigmatic Code

Programming Enigma Puzzles

Enigma 359: Neat odd quad

From New Scientist #1508, 15th May 1986 [link]

Enigma 359

I call ABCD an odd cyclic quadrilateral, or “odd quad” for short. It has four corners A, B, C, D, and four straight sides AB, BC, CD, DA, so it’s a quadrilateral. The corners lie on a circle, so it’s cyclic. And it’s odd because — well, what is its area? I have decided to define that as what the sides cut off from the outside world, that is, the sum of the shaded areas.

neat odd quad has the lengths of its four sides all different positive whole numbers and its area is a whole number too.

Can you find a neat odd quad with an area less than 30? What are the lengths of:

(a) The sides AB, CD, which don’t cross?
(b) The crossing sides BC, AD?

[enigma359]

Enigma 1153: Luconacci numbers

From New Scientist #2309, 22nd September 2001

In the Fibonacci sequence the first two terms are 1 and 1, and each subsequent term is the sum of the previous two terms; so the sequence starts 1, 1, 2, 3, 5. Less well known is the Lucas sequence, whose first two terms are 1 and 3, and each subsequent term is the sum of the previous two terms; so the sequence starts 1, 3, 4, 7, 11. In the Tribonacci sequence (so named by Mark Feinberg) the first three terms are 1, 1 and 2, as in the Fibonacci sequence, and each subsequent term is the sum of the previous three terms; so it starts 1, 1, 2, 4, 7.

Harry, Tom and I were looking to find a 2-digit Fibonacci number, a 2-digit Lucas number and a 2-digit Tribonacci number that used six different digits. We each found a different solution; our three Fibonacci numbers were all different from each other; our three Lucas numbers were all different from each other; and our three Tribonacci numbers were all different from each other. None of the numbers in my solution appeared in either Harry’s or Tom’s solution.

List in ascending order the numbers in my solution.

[enigma1153]

Enigma 358: Add up the scores

From New Scientist #1507, 8th May 1986 [link]

In the following football table and addition sum letters have been substituted for digits (from 0 to 9). The same letter stands for the same digit wherever it occurs and different letters stand the different digits.

The four teams are eventually going to play each other once – or perhaps they have already done so. The score in each match is different.

Enigma 358 - Table

(Two points are given for a win and one point to each side in a drawn match).

Enigma 358 - SUM

Find the scores in the football matches and write the addition sum out with numbers substituted for letters.

[enigma358]

Enigma 1154: Funny money

From New Scientist #2310, 29th September 2001

After the Apathy Party swept into power in the General Election, George, its founder, realised one of the hazards of government: impractical proposals are liable to become law because no one has properly assessed the consequences. The latest is so bizarre that even the Apathy Party must reject it?

The Chancellor of the Exchequer thinks it would be fun to abolish the current coinage and mint just one denomination of coin and one of note. He has proposed an absurd pair of values, each a whole number of pence. George realises that although a large sum of money, such as £999.99, can be paid exactly in several different ways, there are precisely 10,000 amounts that can each be paid exactly using only one combination of the proposed notes and coins. Worse, there is a smaller, but still substantial, number of amounts that cannot be paid exactly using any combination of one or both of the denominations.

How many different amounts cannot be paid exactly?

See also Enigma 1194.

Thanks to Hugh Casement for providing a transcript of this puzzle.

[enigma1154]

Enigma 357: Present and correct

From New Scientist #1506, 1st May 1986 [link]

There were six boys in the tutorial group and they had five different teachers. Each teacher knew some of the boys by Christian name and the rest by surname. Here is how four of the teachers referred to the group:

1. Andy, Bob, Charlie, Thompson, Underwood, Vardy;

2. Andy, Bob, Smith, Thompson, Underwood, Vardy;

3. Charlie, Dave, Eddie, Smith, Thompson, Wilkinson;

4. Andy, Charlie, Dave, Smith, Thompson, Underwood.

The fifth teacher was still learning their names but already knew at least two, namely the Dave in the group and the Vardy in the group.

Name the six boys (Christian name and surname each).

[enigma357]

Enigma 1155: Ending up with numbers

From New Scientist #2311, 6th October 2001

To test my nephew’s arithmetic I get him to write down a three-figure number and then to write down the next twenty consecutive numbers as well. Then he has to “reverse” each of the numbers (so that 237 would become 732, and 540 would become 45, and so on). So, for example, if his starting number was 185 then the twenty-one numbers he would get would be: 581, 681, 781, 881, 981, 91, 191, 291, 391, 491, 591, 691, 791, 891, 991, 2, 102, 202, 302, 402 and 502.

I then ask him to cross out all those numbers which are divisible by 2, then from what’s left to cross out all those numbers divisible by 3, then from what’s left to cross out all those numbers divisible by 5, then from what’s left to cross out all those numbers divisible by 7, and finally from what’s left to cross out all those numbers divisible by 11. So, for example, if he started with 185 (as above) then he would end up with just the six numbers 881, 191, 391, 491, 691 and 991.

On one occasion recently he chose his three-figure starting number, carried out the above process and when he had finished he was left with 14 numbers. By some neat logic you can work out what the starting number was.

What was it?

[enigma1155]

Enigma 356: Counting house

From New Scientist #1505, 24th April 1986 [link]

“My fortune,” said the king to his vizier, “consists of a number of identical gold pieces. I remember their number by a set of peculiar numerical circumstances. I do not speak their number openly, as there are spies and eavesdroppers at court. Instead I shall tell you indirectly.”

“My fortune cannot be divided equally among my sons without splitting gold pieces. Nor could it be so divisible, unless the number of my sons were to run into thousands. My three youngest sons live in the palace, and of the other 15 some have perished in the late wars against the heathen.”

“Now the number of pieces of gold in my fortune has the following curious property: if one multiplies it by the number of my sons living, one obtained a 10-digit number in which all the digits from 0 to 9 appear, with one exception. If any number of digits be cut off the right of this number, the remaining digits form a number which is divisible without remainder by the number of digits cut off. You have a reputation of being a calculator, and so will know the number I mean, and thus the number of gold pieces in my counting house.”

The vizier bowed and reached for his pen case and parchment.

How many sons and how many gold pieces did the king possess?

[enigma356]

Enigma 1156: The tax process

From New Scientist #2312, 13th October 2001

The people on the island of Fairshare have their own tax process. If A is the average income for the people on the island then only people earning more than A pay tax. If a person earns P, which is more than A, then that person pays tax (P−A)²/P.

When all the tax has been collected, then it is shared between the people earning less than A, in proportion to the amounts their incomes fall short of A.

There are 10 people on the island, C, D, E, F, G, H, I, J, K and L. Their final incomes after the tax process were:

C = F£117,
D = F£112,
E = F£103-58,
F = F£90,
G = F£60-47,
H = F£53-52,
I = F£51-15,
J = F£46-57,
K = F£44-20,
L = F£41-99 (that is to say 41 Fairshare pounds and 99 pence, where there are 116 pence to the Fairshare pound).

What were the original incomes of E, H and K?

See also Enigma 1253.

[enigma1156]

Enigma 355: Diffy-dist

From New Scientist #1504, 17th April 1986 [link]

Enigma 355

Diffy-dist is a game for two, played on a regular 6 × 6 square array of points, numbered as in the picture. Each player marks a point at each turn, the only restrictions being that the distance between any pair of marked points must be different from the distance between any other pair. Suppose, for instance, points 1 and 5 and 23 have been marked. Now 9 cannot be marked, because 9 – 1 and 9 – 5 are equidistant; nor 35, because 35 – 5 and 1 – 23 are equidistant.

The result of a recent game was unusual. We ended with six points marked. Of their numbers, one was prime, two were odd, three were consecutive, and four were multiples of 3.

What were the six numbers?

[enigma355]

Enigma 1157: Never the same result

From New Scientist #2313, 20th October 2001

Albion, Borough, City, Rangers and United have played another tournament. This time each team played each of the other teams twice. The two matches that any two teams played against each other had different results, even in the case of City, which did not draw any of its matches.

Two points were awarded for a win and one point for a draw. After each team had played each of the other teams once, United was in the lead, one point ahead of Rangers, which was one point ahead of City, which was one point ahead of Borough, which was one point ahead of Albion.

But by the end of the tournament the positions were completely the opposite: Albion finished one point ahead of Borough, which was one point ahead of City, which was one point ahead of Rangers, which was one point ahead of United.

If you knew the results of the first match between Borough and United you could deduce with certainty the results of all the other matches played.

Give the result of the first match Borough played against each of the other four teams, naming the opponents in each match.

[enigma1157]

Enigma 354: Football again… and why, why, why?

From New Scientist #1503, 10th April 1986 [link]

In the following football table and addition sum letters have been substituted for digits (from 0 to 9). The same letter stands for the same digit wherever it appears and different letters stand for different digits.

The three teams are eventually going to play each other once — or perhaps they have already done so.

Enigma 354 - Table

(Two points are given for a win and one point to each size in a drawn match).

Enigma 354 - Sum

Find the scores in the football matches and write the addition sum out with numbers substituted for letters.

[enigma354]

Enigma 1158: Anti-Magic

From New Scientist #2314, 27th October 2001

George quickly solved the popular magic square puzzle which asks you to arrange the numbers 1 to 16 in a 4 × 4 grid so that the four rows. the four columns and the two diagonals all have the same sum — so he tried to be different. He has now found an “Anti-Magic Square”, using the numbers 1 to 16, but the ten totals are all different. They are in fact ten consecutive numbers, but in no particular sequence in relation to the square grid.

One of the diagonals in George’s square contains four consecutive numbers and the other contains four prime numbers, each in ascending numerical order from top to bottom.

One row contains four numbers in ascending numerical order from left to right.

What are those four numbers?

Enigma 8 was also about anti-magic squares.

[enigma1158]

Enigma 353: Up the polls

From New Scientist #1502, 3rd April 1986 [link]

When electing a mayor, our town councillors each vote for one of the candidates, and if a candidate obtains over half the votes in this first count he is elected. If this fails to happen, then the candidate with the least votes “donates” his votes entirely to one of the remaining candidates and takes no further part of the procedure.

The new totals are then calculated and if one candidate has over half the votes, or if a candidate has been first in the two counts, then he is elected. If both those fail to happen, then again the candidate with fewest votes in the second count donates his votes to one of the remaining candidates and retires. This continues until someone has over half the votes or has been top in any two counts.

When the current mayor was elected the 31 counsellors each voted for their choice of one of the five candidates, and each candidate received a different number (but less than half) of the votes. So the candidate with fewest votes donated his and retired. The second count gave a new clear leader, but it was still indecisive. The third account gave a new clear leader, but it too was still indecisive. At last, on the fourth count, the mayor was elected, and in none of the counts had he been placed second.

How many votes did that mayor get in the very first vote?

[enigma353]

Enigma 1159: Measure for measure

From New Scientist #2315, 3rd November 2001 [link]

I bought a few yards of expensive material recently and I suspected that I had been short-measured. So I took it to the local trading standards officer who measured it exactly in inches. She did not tell me the exact length but she did tell me that it involved two decimal places.

She then told me what the length was to the nearest inch (where exact halves are rounded up) and this did equal the whole number of yards which I had purchased.

Also, as required by a European directive, she changed her exact measurement in inches to centimetres (1 inch = 2.54 centimetres) and she told me the length of the material to the nearest centimetre.

From the things which she told me I was in fact able to work out the exact length of the material in inches and to see that I had actually been sold slightly more material than I had asked for.

How many yards of material had I asked for?

[enigma1159]

Enigma 352: In the bag

From New Scientist #1501, 27th March 1986 [link]

Yesterday, I was presented with an unusual box containing 13 painted Easter eggs. Each egg was either red, white or blue and there was at least one egg of each colour. If I had been in a dark room, the minimum number of eggs I would have had to withdraw from the box to be certain of picking at least three eggs of the same colour was the same as the number of blue eggs in the box.

Being superstitious, I decided against leaving 13 eggs in the box and transferred a number to a black bag. This bag may not have been empty before I added the coloured eggs. If it wasn’t, then it contained one or more black eggs and nothing else. However, two things are certain. One is that if I were in a dark room, the minimum number of eggs I would now have to withdraw from the box to be sure of having at least three eggs of the same colour is the same as the number of blue eggs in the bag. The second is that the chances of picking out a white egg from the bag with one attempt are the same as the chances of picking out a white egg from the box with one attempt.

But I am in a dark room. Trying to deduce the contents of that black back without turning the light on and looking is keeping me awake late into the night.

How many red, white, blue and black (if any) eggs are there in the bag?

[enigma352]

Enigma 1160: Sum logic

From New Scientist #2316, 10th November 2001 [link]

Enigma 1160

Joe made this puzzle for his son. It consists of nine small squares in a square tray. As shown, one square is marked with a plus sign and the rest numbered 1 to 8. The puzzle involves removing the plus sign and then sliding a square into the space left by the plus sign.

From then on each move consists of sliding a square into a vacant space and finally replacing the plus sign in its original position. As shown the numbers do not add up. 123 + 45 does not equal 678. The object of the puzzle is to finish so the numbers do add up.

In how many different ways can this be achieved?

[enigma1160]

Enigma 351: Four flies

From New Scientist #1500, 20th March 1986 [link]

Four unfriendly flies are sitting watching the cricket. Each is on the boundary of the ground, which is perfectly circular. Their names, in order round the edge, are At, Bet, Cot and Dut.

The length of each of the straight lines At-Bet, Bet-Cot, Cot-Dut and Dut-At is an exact whole number of flymins (this is, the flies’ unit of distance). Two of those lines actually have the same length. Furthermore, the total of these four lengths is precisely the same number as the area (in square flymins) of the quadrilateral At-Bet-Cot-Dut.

If I tell you that that area does not include the pitch (which is at the centre of the ground), can you tell me the four lengths?

[enigma351]

Solving Alphametics with Python, Part 2

In my previous article (Solving Alphametics with Python) I explored some possibilities for improving on the speed of a simple algorithm for solving general Alphametic expressions using Python’s eval() function. I implemented a way of solving Alphametics without calling eval() for every potential letter-to-digit assignment, and also a way of reducing the number of possibilities we need to consider in the common case of expressions involving equality.

That article received a comment from Arthur Vause, in which he shared his own program that addresses the problem of repeated calls to eval() by writing code that generates a program that considers the possibilities, and then getting Python to execute that.

I’ve taken this idea a bit further and instead of having code that generates a relatively short program, instead it can generate a series of nested loops and if statements with all the logic of the valid/invalid assignments built into the structure of the generated program itself. This gives us something that may not look elegant, but executes quickly, (and can be handled by PyPy without problems).

So, for a problem like Enigma 1530:

TOM × 13 = DALEY

my code produces a program like this:

def solve():
  for T in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
    for O in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
      if O != T:
        for M in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
          if M != T and M != O:
            TOM = M + O*10 + T*100
            x = TOM * 13
            (x, Y) = divmod(x, 10)
            if Y != T and Y != O and Y != M:
              (x, E) = divmod(x, 10)
              if E != T and E != O and E != M and E != Y:
                (x, L) = divmod(x, 10)
                if L != T and L != O and L != M and L != Y and L != E:
                  (x, A) = divmod(x, 10)
                  if A != T and A != O and A != M and A != Y and A != E and A != L:
                    (x, D) = divmod(x, 10)
                    if D != T and D != O and D != M and D != Y and D != E and D != L and D != A and D != 0 and x == 0:
                      yield { 'A': A, 'D': D, 'E': E, 'L': L, 'M': M, 'O': O, 'T': T, 'Y': Y }

(This is a slightly simplified version, but you get the idea).

Firstly, this code isn’t elegant. But we don’t really care about that in this instance. No-one is going to look at it, it’s just going to be executed. (I know I have asked you to look at it in this post).

Here’s an explanation of how the generated program works:

(Lines 2-6)

In this example, the only letters we need to consider the values of are T, O, and M, and instead of using itertools.permutations() and rejecting assignments with invalid digits we don’t need to generate possibilities with invalid assignments in the first place.

For example, we don’t need to consider the possibility of T being zero (because leading zeros are not allowed), so we don’t put 0 in the possible values of T. Any other invalid digits assignments can be removed in the same way.

(Lines 7-8)

Once we have the values of T, O, M, we construct the value of TOM and calculate the left-hand side of the expression (TOM × 13).

(Lines 9-18)

We then try and match this result to the value we are looking for (DALEY), by repeatedly examining the final digit. For each digit we examine we either match it an existing assignment (if it is a letter we have already seen), or we check that it is a new assignment (if it is a letter we haven’t already seen).

In this case, all the letters are new, so we just need to check that their values don’t reuse any of the digits we have already assigned. When we get to the leading digit (D) we also need to check that it is non-zero, and that we have used up all the digits of the result.

(Line 19)

If we make it through all that we have found a solution, so we return a dictionary mapping the letters to the digit values.

This approach can easily deal with multiple expressions in a single program — once we have finished with one expression we just generate the code for the next one until all expressions are exhausted. If we reach the end when the code is executed all the expressions are satisfied, and we can return the dictionary for the solution.

I’ve implemented this approach in the enigma.py library (from version 2016-06-25), as the function substituted_expression() and changed the SubstitutedExpression() solver to use this.

Comparative timings are given in the table below, using the examples from the previous article.

The columns are:

1 = Raymond Hettinger’s code, using repeated calls eval() for a single expression, multiple expressions are chained together using “and”. The code is modified so that single digit 0 values are allowed. Note: This can’t deal with expressions in bases other than 10.

2 = The previous version of the enigma.py code, as described in the previous article. It uses a single call to eval() for a single expression, but can chain individual expression solutions together to solve problems involving multiple expressions.

3 = The current version of the enigma.py code, as described in this article. Multiple expressions can be evaluated in a single call to eval().

4 = The SubstitutedSum() solver form the enigma.py library. This can only deal with expressions that are simple sums (but can chain expressions together, operate in different bases and allow initial assignments and invalid assignments).

    1      2      3      4    test
 94.4s   4.6s   0.32s  0.19s  (LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL)
 75.0s   0.44s  0.07s  0.07s  (HMPDM + BHPHM = RCDHA) (RBAD + PQHD = AADD)
 92.7s   4.2s   0.37s  ----   (SAND + SUN + SEX + SEA = IBIZA) (SAND > SUN > SEX > SEA)
  2.6s   0.93s  0.11s  ----   (PAY + ASP + YES + ERR + RYE + SPA = YAPS) (P < A < Y < E < R < S)
 32.0s   0.22s  0.04s  ----   (TOM * 13 = DALEY)
 45.7s   0.26s  0.04s  ----   (CUT + UTC + TCU = MEDS) ((RIO + IOR + ORI) * MEDS = OMTTOUI)
 47.0s   1.1s   0.14s  ----   ((ENI * GMA) % 1000 = MES) (ENI + GMA = SUM) (I > 2 * U)
109.2s   8.6s   0.99s  ----   (ALPHA + BETA + GAMMA = DELTA) (ALPHABET % 26 = 0) (ALPHABET % 24 = 0) (GAMMA % 3 = 0)
 85.3s   0.19s  0.04s  ----   (ENIG * MA == AM * gIne) (E - N - M == M - n - e) (N == n + n) (IN == nI + nI)
 ----    7.6s   0.55s  0.31s  (GOLD + DALEY = THOMAS) [base=11]
 ----	55.6s	0.96s  0.08s  (FAREWELL + FREDALO = FLINTOFF) [base=11]
107.9s   2.9s   0.40s  0.07s  (ELGAR + ENIGMA = NIMROD) [O=0]
134.6s   1.3s   0.24s  0.09s  (WILKI + NSON = JONNY) [no digit is 9]
 87.2s   0.48s  0.05s  0.08s  (1939 + 1079 = 6856) [digits cannot stand for themselves]
 78.4s   0.55s  0.08s  ----   (BRAIN + STRAIN + AGAIN = ENIGMA) (is_cube(ATE))
 74.1s   2.6s   0.16s  ----   (ETA + BETA + THETA = DELTA) (is_prime(PHI)) (is_prime(PSI))
109.6s   0.72s  0.05s  ----   (SEVEN - THREE = FOUR) (is_prime(SEVEN)) (is_prime(FOUR)) (is_prime(RUOF)) (is_square(TEN))
 55.5s   0.44s  0.06s  ----   (M * TIMES = ENIGMA)
 92.0s  12.7s   0.61s  0.10s  (SAINT + GEORGE = DRAGON) (E % 2 = 0)
 59.0s   0.45s  0.06s  ----   (AB * CDE = FGHIJ) (AB + CD + EF + GH + IJ = CCC)

As we see, the approach described in this article is generally hundreds of times faster than the repeated eval() approach, and in some tests more than 2000× faster. It is also generally tens of times faster than the approach described in the previous article. In fact it solves each of the example problems in less than 1s and can solve all of the given example Alphametics in less than 6s total runtime.

If you want to see the actual code that is generated by the solver for a particular problem you can pass a value of 3 or more to the verbose parameter of the solver. e.g.:

% python enigma.py Alphametic -v3 "TOM * 13 = DALEY"
...

And the code (as well as some other debugging information) will be output before the solutions.

Thanks for reading.

Enigma 1161: Shifty division

From New Scientist #2317, 17th November 2001 [link]

In a previous Enigma, George asked you to find the smallest number which can be multiplied by four simply by moving the last digit to the front. The answer is 102564 × 4 = 410256. In fact, 102564 is the smallest number which can be multiplied by any integer by moving its last digit to the front.

George is now trying to find numbers which can be divided exactly by some integer (any integer greater than one) simply by moving the last digit (which must not be zero) to the front. He has found two solutions to this puzzle and checked them on his eight-digit calculator. He is now looking for another.

What is the smallest number which George has not yet found which can be divided by some factor using this trick?

[enigma1161]

Enigma 350: Oh, careless pen!

From New Scientist #1499, 13th March 1986 [link]

Four football teams (A, B, C and D) are to play each other once. After some of the matches had been played a table was drawn up giving some details of the matches played, won, lost and so on.

Unfortunately, not only had the digits been replaced by letters, but also (Uncle Bungle and his careless pen again!) one of the letters was wrong on one of the occasions on which it appeared — if it appeared more than once.

The table looked like this:

Enigma 350

(Two points are given for a win, and one point to each side in a drawn match).

Which letter was wrong? What should it be? Find the score in each match.

[enigma350]

Follow

Get every new post delivered to your Inbox.