Enigmatic Code

Programming Enigma Puzzles

Enigma 397: All wrong again

From New Scientist #1547, 12th February 1987 [link]

In the following addition sum all the digits are wrong. But the same wrong digit stands for the same correct digit wherever it appears, and the same correct digit is always represented by the same wrong digit.

Find the correct addition sum.

[enigma397]

Tantalizer 481: Happy Christmas

From New Scientist #1032, 23rd December 1976 [link]

tantalizer-481

Oops! What the message is meant to say is of course:

HAPPY CHRISTMAS TO YOU FROM THE NEW SCIENTIST.

Perhaps you would like to put it right by sliding on word at a time along a line into a vacant oval. If you are not too saturated with Christmas pud, you should manage it in 26 moves.

[tantalizer481]

Enigma 1114: Christmas changes

From New Scientist #2270, 23rd December 2000

Christmas is said to change things and so this enigma is an old puzzle with some changes.

Problem: You have to assign a digit to each of the 10 letters in the sum here:

When you have decided on an assignment of digits to the 10 letters, then your assignment is a solution of the problem if it satisfies at least one of the following conditions:

• At least one digit is assigned to more than one letter.
• When the digits are put into the addition sum it is not correct.
• The digit assigned to “U” is smaller than the digit assigned to “H”.

You need to find an assignment of digits to the 10 letters which is NOT a solution of the problem.

What is the value of BLEAT in your assignment?

[enigma1114]

Bit Twiddling

Every so often I click on the Random Post link at the top right of the site, and have another look at a previously published problem. And sometimes I’ll think about attacking a problem in a different way than my original solution, and post an additional comment.

I recently revisited Enigma 69: Maximum Queen moves to see if I could think of a better algorithm to enable me to expand the analysis beyond a 5×5 board. As it happened I didn’t come up with a better algorithm, but I did refine the one I’d previously published to be more efficient. By eliminating symmetrically equivalent positions, using bit vectors to represent the board, and pre-computing moves I was able to get my program running about 150 times faster than my simple implementation. While this isn’t enough to rescue the pathologically slow nature of the algorithm as the size of the board increases, it does bring the solution for the 6×6 board into a feasible time frame.

After 14 hours of CPU time (less actual time, as we can run multiple copies of the program to consider different numbers of Queens) I was able to confirm that 128 moves was indeed maximal for the 6×6 board, with the Queens arranged in a “border” configuration (and I was able to do some analysis, but not an exhaustive treatment, of the 7×7, 8×8 and 9×9 boards).

As the board was now represented by a bit vector, I was looking for an efficient way to generate all k-bit patterns in an n-bit vector. And that was when I stumbled on the Bit Twiddling Hacks page. Right down at the end of the page is a section called “Compute the lexicographically next bit permutation”.

The page is primarily concerned with C (or C++) code, but the implementation in Python is as follows.

Suppose we start with the variable v holding an integer with k bits set when represented in binary. Then the following code fragment computes w, which is the next largest integer after v that also has k bits set in it’s binary representation.

t = (v | (v - 1)) + 1
w = t | ((((t & -t) // (v & -v)) >> 1) - 1)

So, if we want to generate all 8-bit numbers with exactly 2 bits set, we can simply start with the smallest number with 2 bits set (11 in binary, which is 3 in decimal), and keep applying the the code above until we exceed 255 (the largest 8-bit number).

v = 3
while v < 256:
  print(f"{v:08b} = {v}")
  t = (v | (v - 1)) + 1
  v = t | ((((t & -t) // (v & -v)) >> 1) - 1)

When run (under Python 3.6) we get the following result:

00000011 = 3
00000101 = 5
00000110 = 6
00001001 = 9
00001010 = 10
00001100 = 12
00010001 = 17
00010010 = 18
00010100 = 20
00011000 = 24
00100001 = 33
00100010 = 34
00100100 = 36
00101000 = 40
00110000 = 48
01000001 = 65
01000010 = 66
01000100 = 68
01001000 = 72
01010000 = 80
01100000 = 96
10000001 = 129
10000010 = 130
10000100 = 132
10001000 = 136
10010000 = 144
10100000 = 160
11000000 = 192

Which is a complete list of all 28 8-bit integers with exactly 2 bits set, in numerical order. And if we didn’t limit the numbers to 8-bits the program would continue generating integers with exactly 2 bits set indefinitely.

I might add this function to the enigma.py library (if I can think of a good name for it), but if you are trying to speed up a program it will probably be faster to just use the code fragment inline.

Enigma 396: The hostess’s problem

From New Scientist #1546, 5th February 1987 [link]

At a recent dinner party five men and their wives sat at the 10 places around the table. Men and women alternated around the table and no man sat next to his own wife. No man’s Christian name had the same initial as his surname.

Mrs Collins sat between Brian and David. Colin’s wife sat between Mr Briant and Mr Edwards. Mr Allen sat between Edward’s wife and Mrs Davidson. Brian’s wife sat next to Alan.

In the information which I’ve just given you, if two people were sitting next to each other then I have not told you about it more than once.

Which two men (Christian name and surname of each) sat next to Mrs Edwards?

[enigma396]

Tantalizer 482: Lapses from grace

From New Scientist #1033, 6th January 1977 [link]

An air of rare humility pervades the Common Room at St. Aletheia’s tonight. The seven inmates overdid the post-prandial gin and rashly confessed their sins to one another. Each owned to a different pair of the deadly ones and each sin turned out to have claimed a different pair of victims.

Constance, Emily and Flavia have no sin in common to any two of them. Beatrice, Deborah, Emily and Gertrude confessed to all seven between them. Alice and Gertrude admitted to sloth; Deborah and Emily to lust. Alice is not given to pride nor Beatrice to avarice nor Flavia to either pride or intemperance. Constance, who owned to anger, has a sin in common with Deborah, who did not.

Which pair has fallen prey to intemperance and which pair to envy?

[tantalizer482]

Enigma 1115: New Christmas star

From New Scientist #2270, 23rd December 2000

enigma-1115

Here is another “magical” Christmas star of twelve triangles, in which can be seen 
six lines of five triangles (two horizontal and two in each of the diagonal directions). Your task is to place a digit in each of the twelve triangles so that:

all six digits in the outermost “points” of the star are odd;

the total of the five digits in each line is the same,
 and it is the same as the total of the six digits in the points of the star;

each of the horizontal lines of digits, when read as a 5-digit number, is a perfect square.

What are those two perfect squares?

Thanks to Hugh Casement for providing the source for this puzzle.

[enigma1115]

Enigma 395: By Jove, it figures!

From New Scientist #1545, 29th January 1987 [link]

In the addition sum below, each of the digits from 0 to 9 has been replaced by a letter whenever it occurs. Different letters stand for different digits. You are asked to reproduce the original sum.

[enigma395]

Puzzle 73: A division sum. Find the missing digits

From New Scientist #1124, 12th October 1978 [link]

puzzle-73

[puzzle73]

Enigma 1116: United win at last

From New Scientist #2272, 6th January 2001

Albion, Borough, City, Rangers and United played a tournament in which each team played each of the other teams once. Two matches took place in each of five weeks, each team having one week without a match.

One point was awarded for winning in the first week, 2 points for winning in the second week, 3 points for winning in the third week, 4 points for winning in the fourth week and 5 points for winning in the fifth week. For a drawn match each team gained half the points it would have gained for winning it. At any stage, teams that had gained the same number of points were regarded as tying.

After the first week A led, with B tying for second place. After the second week B led, with C tying for second place. After the third week C led, with R tying for second place. After the fourth week R led, with U tying for second place. After the fifth week U had won the tournament with more points than any of the other teams.

(1) Which team or teams finished in second place after the fifth week?

(2) Give the results of Albion’s matches, listing them in the order in which they were played and naming the opponents in each match.

This completes the archive of Enigma puzzles from 2001. There are now 1065 Enigma puzzles on the site, the archive is complete from the beginning of Enigma in February 1979 to January 1987, and from January 2001 to the final Enigma puzzle in December 2013. Altogether there are currently 59.5% of all Enigmas published available on the site, which leaves 726 Enigmas between 1987 and 2000 left to publish.

[enigma1116]

Enigma 394: Unwinding

From New Scientist #1544, 22nd January 1987 [link]

Professor Kugelbaum was unwinding at the Maths Club with a cigar after lunch when a wild-looking man burst in and introduced himself thus:

“My name is TED MARGIN. Juggling with the letters of my name one obtains both GREAT MIND and GRAND TIME. But I digress. Each letter of my name stands for one digit exactly from 1 to 9 inclusive and vice versa. And, do you know,

(A × R × M) / (A + R + M) = 2,

MAD is greater than ART (though RAT is greater than either), and TED = MAR + GIN.

If, in addition, I were to tell you the digit which corresponds to M then you could deduce the one-to-one correspondence between the letters of my name and the digits 1 to 9″.

At this point a helpful butler removed the man, but Kugelbaum was amused to find that the information was quite consistent.

Write the digits 1 to 9 in the alphabetical order of the letters to which they correspond.

[enigma394]

Tantalizer 483: Thought for food

From New Scientist #1034, 13th January 1977 [link]

The food at Dotheboys Hall was always disgusting but that was no problem until the latest rise in the cost of ingredients. So last week Mr Squeers declared that in future it would have to be a great deal nastier.

He sampled it daily, marking it out of 25 for nutrition and out of 25 for expense. Monday was the first day and he awarded his highest total of points in the whole week. The cook was spoken to severely and, gratifyingly, the total awarded on each subsequent day fell daily.

When the totals are broken down under their two headings, things get less simple. Thus Monday was only 4th on each list, 26 points in total were awarded on Tuesday, Wednesday’s menu scored second highest for nutrition, Thursday’s scored 4 points for expense and Friday’s scored 8 for nutrition. Saturday’s was 5th for nutrition and scored 13 for expense. Sunday’s came 6th in the expense list.

There were no ties under either heading and the number of points given on Wednesday for nutrition also occurred somewhere in the expense column.

On which days were the school best nourished and fed at greatest expense?

[tantalizer483]

Enigma 1117: Reapply as necessary

From New Scientist #2273, 13th January 2001

Recently I read this exercise in a school book:

“Start with a whole number, reverse it and then add the two together to get a new number. Repeat the process until you have a palindrome. For example, starting with 263 gives:

leading to the palindrome 2662.”

I tried this by starting with a three-figure number. I reversed it to give a larger number, and then I added the two together, but my answer was still not palindromic. So I repeated the process, which gave me another three-figure number which was still not palindromic. In fact I had to repeat the process twice more before I reached a palindrome.

What number did I start with?

[enigma1117]

Enigma 393: Decode the sum

From New Scientist #1543, 15th January 1987 [link]

In the following addition sum, different letters stand for different digits and the same letter stands for the same digit throughout.

Decode the sum.

[enigma393]

Puzzle 74: Football (three teams, old method)

From New Scientist #1125, 19th October 1978 [link]

Three football teams (AB and C) are to play each other once. After some — or perhaps all — the matches had been played, a table giving some details of goals, and so on, looked like this:

puzzle-74

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

Find the score in each match.

[puzzle74]

Enigma 1118: 2001 – A specious oddity

From New Scientist #2274, 20th January 2001

George is planning to celebrate the new millennium — the real one — by visiting Foula, the most remote of the Shetland Islands. It is one of the few places in the world where the inhabitants still live by the old Julian calendar rather than the now almost universal Gregorian calendar.

In order to correct the drift of the Julian calendar against the seasons, Pope Gregory decreed that in 1582, Thursday 4th October (Julian) should be immediately followed by Friday 15th October (Gregorian), and in order to prevent a recurrence of the drift, years divisible by 100 would henceforth only be leap years if divisible by 400. Previously all years divisible by four were leap years. Catholic countries obeyed immediately, others — apart from Foula — fell into line in later centuries.

While planning his visit George programmed his computer to print 12-month calendars for the required year, showing weekdays, under both Julian and Gregorian styles. But when he ran the program he was surprised to find that the two printouts were identical.

He then realised that he had entered the wrong year number — the Julian and Gregorian calendars for the year 2001 are not the same.

What is the first year after 1582 for which they are the same?

[enigma1118]

Tantalizer 484: Blockwork

From New Scientist #1035, 20th January 1977 [link]

Someone gave my small son a bag of 1in cubes for Christmas and he was soon busy stacking them. First he built a rectangular wall one brick thick. Then he used the rest of the bricks to build another rectangular block, using 140 bricks more than the other. Then he got bored.

But I didn’t, as I spotted an intriguing fact. The sum of the lengths of the twelve edges on each construction was the same. So were the total surface areas of the two constructions (including the faces standing on the carpet). All the six dimensions involved were different.

How many bricks had he been given?

[tantalizer484]

Enigma 392: Nothing written right

From New Scientist #1542, 8th January 1987 [link]

In the following addition sum all the digits are wrong. But the same wrong digit stands for the same correct digit wherever it appears, and the same correct digit is always represented by the same wrong digit.

Find the correct addition sum.

[enigma392]

Puzzle 75: C is silent

From New Scientist #1126, 26th October 1978 [link]

The four tribes seem now, for better or worse, to be firmly established on the Island of Imperfection. They are the Pukkas, who always tell the truth; the Wotta-Woppas, who never tell the truth; the Shilla-Shallas, who make statements which are alternately true and false or false and true; and the Jokers, whose rules for truth-telling in making three statements are any rules that are different from those of any of the other three tribes.

In the story which I have to tell about ABC and D there is one member of each tribe. C, I am afraid, does not actually say anything. Can he just be fed-up? I don’t blame him. The other three speak as follows:

A: B is a Pukka;
B: C is a Shilla-Shalla;
D: A is a Pukka;
D: I am a Shilla-Shalla or a Wotta-Woppa;
D: B is a Joker.

Find the tribes to which ABC and D belong.

[puzzle75]

Enigma 1119: Six primes

From New Scientist #2275, 27th January 2001

I invite you to select a three-digit prime number such that if you reverse the order of its digits you form a larger three-digit prime number. Furthermore the first two digits and the last two digits of these two three-digit prime numbers must themselves be four two-digit prime numbers, each one different from all the others.

Which three-digit prime number should you select?

[enigma1119]