### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

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

### Site Stats

- 175,242 hits

Advertisements

Programming Enigma Puzzles

3 January 2018

Posted by on **From New Scientist #1015, 26th August 1976** [link]

The Pentathlon at the West Wessex Olympics is a Monday-to-Friday affair with a different event each day. Entrants specify which day they would prefer for which event — a silly idea, as they never agree.

This time, for instance, there were five entrants. Each handed in a list of events in his preferred order. No day was picked for any event by more than two entrants. Swimming was the only event which no one wished to tackle on the Monday. For the Tuesday there was just one request for horse-riding, just one for fencing and just one for swimming. For the Wednesday there were two bids for cross-country running and two for pistol-shooting. For the Thursday two entrants proposed cross-country and just one wanted horse-riding. The Friday was more sought after for swimming than for fencing.

Still, the organisers did manage to find an order which gave each entrant exactly two events on the day he had wanted them.

In what order were the events held?

I don’t think there is a solution to this puzzle as it is presented. Instead I would change the condition for Thursday to:

For Thursday two entrants proposed cross-country and just one wanted

fencing.

This allows you to arrive at the published answer.

[tantalizer464]

Advertisements

%d bloggers like this:

The initial letters of the events are all different, so we can just use

C, F, H, P, Sto refer to the events.I started with a

MiniZincmodel for the original puzzle, but it said the set of constraints I wrote was unsatisfiable. So I wrote a Python program to play around with the puzzle. It works by selecting the final ordering for the events (there 120 possible orderings (= 5!)), and for each of these orderings there are 20 possible entrant orderings that match on exactly two of the events. We can choose 5 of these orderings to create a table, which we can then check against the conditions given in the puzzle text.If found that by eliminating the condition for Thursday I got 3 answers that matched the published solution, and I chose the one of these where both swimming and fencing were requested for Friday (which makes the Friday condition more satisfying). Then the simplest change to the Thursday condition to satisfy this solution was to change the requirement for 1 entrant to request horse riding, to 1 entrant requesting fencing. With this change there is only one table that satisfies all the conditions, and it matches the published answer.

I don’t know if this was the puzzle the setter had in mind. All the later

Tantalizerpuzzles are on the site, and I didn’t come across a correction when transcribing them.The following Python program runs in 4.6s using PyPy, but takes longer with the standard CPython implementations. We get a faster execution time if we do the checks for each day before the “no day was picked for any event by more than two entrants” check, but the code is presented in the order the tests are described in the puzzle text.

Run:[ @repl.it ]Solution:The order of events is: Mon = Fencing; Tue = Pistol shooting; Wed = Cross-country running; Thu = Swimming; Fri = Horse riding.The table of the entrants bids is given below:

The bottom row shows the actual order of events, and the events that take place on the requested days are highlighted in the entrants rows (2 corresponding events for each entrant).

I have taken the text “they never agree” to literally mean that the orderings provided by the entrants must all be different, but we can allow for entrants submitting the same orderings by using [[

itertools.combinations_with_replacement()]] instead of [[itertools.combinations()]]. This just gives us more cases to check, but there are no further solutions with this relaxed condition.You can change the [[

'F']] at line 36 to [['H']] to see there are no solutions to the original puzzle text.Here is a

MiniZincmodel that finds the solution to the modified problem. It runs in 130ms using the [[mzn-chuffed]] solver. I haven’t used the [[-a]] flag, as (unlike the Python program) there are no ordering constraints on the entrants bids. When using the [[-a]] flag we get 120 solutions, but these are just all the permutations of entrants bids in the single solution produced by the Python code.Similarly to above, you can change the [[

F]] on line 45 to [[H]] to find that the original puzzle text is not satisfiable.Here is a Python 3.6 wrapper program for it that uses the

minizinc.pylibrary to format the output in a more readable format.@Jim Randell Nice MiniZinc model!

Regarding the solution time of the model: If you want to make it somewhat faster for the first solution you can try this search annotation/heuristic instead of “solve satisfy”:

The "anti_first_fail" and "indomain_min" tweaks the search in the search tree a bit.

It’s a magnitude or two faster on my machine: Gecode takes 0.012s (vs 0.138s); it’s the time Gecode reported so the flattening time is excluded. Chuffed without the -f flag (i.e. ignoring the search annotation) seems also be faster with this search annotation as well (though Chuffed is generally faster with the -f flag).

I tried to find a simple symmetry breaking constraint that only showed a single solution, but did not come up with any one right now. This one generates only two solutions instead of 120:

When adding the symmetry breaking, it’s faster when showing all the solutions (the -a flag) but slower for just the first solution; which is not so surprising since the symmetry breaking constraint then seems to “clash” with the search tree tweaking.