### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,972 hits

Advertisements

Programming Enigma Puzzles

2 May 2012

Posted by on **From New Scientist #2863, 5th May 2012** [link]

A set of snooker balls contains six coloured and 15 red balls. From such a set Harry took some coloured balls and a larger number of reds and put them in his bag. From the remainder Tom took some coloured balls and some reds (more of each than Harry took) and put them into his bag.

Each of them calculated that if he drew two balls at random out of his own bag simultaneously there was a 1 in X chance that they would both be coloured, X representing the same number for each person.

How many coloured balls and how many red balls from the set were not taken by either of them?

This is probably the same Harry and Tom from **Enigma 1551**.

[enigma1696]

Advertisements

%d bloggers like this:

The following Python program runs in 40ms. You can write the same program without using objects, but I thought this would be a bit more readable. (Or I could have used the Python

namedtuplelibrary).Solution:1 coloured ball and 4 red balls were not taken.In Harry’s bag, there are 2C, 4R; in Tom’s bag 3C, 7R

and the same probability is 1/15

30ms run time

Of course, it’s easy to deduce that ch (the number of coloured balls taken be Harry) is 2 : it has to be more than 1 to allow the selection of 2 coloured balls, and less than 3 as Tom takes more coloured balls than Harry, so

25ms run time

This is very similar to (but more compact than) the solution I originally came up with. Although I also tested X to check it was an integer value (which I feel was subtly implied in the puzzle, rather than explicitly stated), although as it turns out there are no non-integer solutions for X anyway.

An issue that often arises in providing programs to solve teasers is that of deciding how much prior analysis should be exploited in the programmed solution.

In this case, for example, it is easy to see that Harry can only pick two of the ‘coloured’ balls, a constraint that gives a large speed gain in a program when compared with an unconstrained search.

Going a bit further with the analysis also provides a complete solution which then reduces to a few lines of Python.

Indeed. The Enigma Puzzle this week is not a great programming challenge.

But in cases like this where the search space is sufficiently small I feel most satisfied by a fully exhaustive search. I tried to come up with a more interesting programmed solution in my first post by approaching the puzzle from a slightly different angle (finding possible pairs for X and then applying the constraints, rather than starting with the constraints), and also playing around with objects to make the printing of the solution easier.

Agreed. The coding of the first line caused me a dilemma, as knowing that Harry takes at least 2 coloured balls,and less than half the coloured balls could be coded as

for ch in range(2,3):, which might as well be replaced by ch=2

Anyway, here is an alternative coding in SQL, run on an SQlite database in 2.7ms. (The table “numbers” contains the set of natural numbers > 0 )

That’s neat. I’ve had some exposure to SQL in the past, and it wouldn’t leap out as the first language I’d chose to implement Enigma puzzles!

Here’s my solution in BBC Basic (running under the BeebEm3 emulator):

Having been potty-trained on Fortran, I usually start my Basic programs with

defint i – n

Then if you choose your variable names accordingly you can do without those % symbols that don’t exactly improve the readability of a program. Turbo Basic also allows long integers of 32 bits.

And it does away with line numbers. A label can be any name starting with a letter(presumably not a reserved word or a name in use as a variable) followed by a colon and on a line by itself. That’s neater than numbering every line: those early dialects of Basic were basically horrid!

I’m not intending to publish any of my programs here, as I’m not particularly proud of them. They’re much longer than the Python equivalent, and I’m sure take longer to run. This old dog is not going to learn new tricks, but he usually gets there in the end.