Enigmatic Code

Programming Enigma Puzzles

Tantalizer 464: Pentathlon

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

2 responses to “Tantalizer 464: Pentathlon

  1. Jim Randell 3 January 2018 at 8:34 am

    The initial letters of the events are all different, so we can just use C, F, H, P, S to refer to the events.

    I started with a MiniZinc model 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 Tantalizer puzzles 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 ]

    from itertools import permutations, combinations
    from collections import Counter
    from enigma import join, printf
    
    # the events
    events = "CFHPS"
    
    # check sequences <ss> satisfy the conditions
    def check(ss):
    
      # consider the choices by day
      for (i, d) in enumerate(zip(*ss)):
    
        # count the events requested for this day
        c = Counter(d)
    
        # "No day was picked for any event by more than two entrants"
        if any(v > 2 for v in c.values()): return False
    
        # Mon: "swimming was the only event which no one wished to tackle"
        if i == 0:
          if not(c['S'] == 0): return False
          if not all(c[e] > 0 for e in events if e != 'S'): return False
    
        # Tue: "there was just one request for horse-riding, ... fencing and ... swimming"
        elif i == 1:
          if not(c['H'] == 1 and c['F'] == 1 and c['S'] == 1): return False
    
        # Wed: "there were two bids for cross-country, ... and two for pistol-shooting"
        elif i == 2:
          if not(c['C'] == 2 and c['P'] == 2): return False
    
        # Thu: "two entrants proposed cross-country and just one wanted fencing"
        # (originally: "just one wanted horse-riding")
        elif i == 3:
          if not(c['C'] == 2 and c['F'] == 1): return False
          
        # Fri: "was more sought after for swimming than for fencing"
        elif i == 4:
          if not(c['S'] > c['F']): return False
    
      # looks OK
      return True
    
    # choose an actual ordering for the events
    for s in permutations(events):
    
      # find all orderings that match s in exactly 2 places
      ps = list(p for p in permutations(events) if sum(a == b for (a, b) in zip(s, p)) == 2)
    
      # choose 5 of these orderings for the entrants
      for ss in combinations(ps, 5):
        if check(ss):
          printf("    Mo Tu We Th Fr")
          for (i, x) in enumerate(ss, start=1):
            printf("{i}:  {x}", x=join(x, sep="  "))
          printf("    -------------\n    {s}", s=join(s, sep="  "))
          printf()
    

    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 MiniZinc model 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.

    include "globals.mzn";
    
    % the 5 entrants
    set of int: Entrants = 1..5;
    
    % the events
    set of int: Events = 1..5;
    int: C = 1; % Cross Country
    int: F = 2; % Fencing
    int: H = 3; % Horse Riding
    int: P = 4; % Pistol Shooting
    int: S = 5; % Swimming
    
    % the days of the week
    set of int: Days = 1..5;
    int: Mon = 1;
    int: Tue = 2;
    int: Wed = 3;
    int: Thu = 4;
    int: Fri = 5;
    
    % x[i, j] = preferred event for entrant i on day j
    array[Entrants, Days] of var Events: x;
    
    % each entrant gives a different day for each event
    constraint forall (i in Entrants) (all_different([x[i, day] | day in Days]));
    
    % how many bids for <event> on <day>?
    function var int: bids(var int: day, var int: event) = sum (i in Entrants) (x[i, day] = event);
    
    % "No day was picked for any event by more than two entrants"
    constraint forall (day in Days, event in Events) (bids(day, event) < 3);
    
    % Mon: "Swimming was the only event which no one wished to tackle"
    constraint bids(Mon, S) = 0;
    constraint forall (e in Events where e != S) (bids(Mon, e) > 0);
    
    % Tue: "there was just one request for horse-riding, ... for fencing and ... for swimming"
    constraint bids(Tue, H) = 1 /\ bids(Tue, F) = 1 /\ bids(Tue, S) = 1;
    
    % Wed: "there were two bids for cross-country running and two for pistol-shooting"
    constraint bids(Wed, C) = 2 /\ bids(Wed, P) = 2;
    
    % Thu: "two entrants proposed cross-country and just one wanted fencing"
    constraint bids(Thu, C) = 2 /\ bids(Thu, F) = 1;
    
    % Fri: "was more sought after for swimming than for fencing"
    constraint bids(Fri, S) > bids(Fri, F);
    
    
    % the actual order of events
    array[Events] of var Days: day;
    
    % each event occurs on a different day
    constraint all_different(day);
    
    % each entrant has exactly 2 events on the day they requested
    constraint forall (i in Entrants) (sum (j in Days) (x[i, j] = day[j]) == 2);
    
    
    solve satisfy;
    

    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.py library to format the output in a more readable format.

    from enigma import join, printf
    from minizinc import MiniZinc
    
    # load the model
    p = MiniZinc("tantalizer464.mzn")
    
    # turn a dictionary into a sequence
    def events(d):
      return tuple(d[k] for k in sorted(d.keys()))
    
    # format a sequence of event indices
    def fmt(x):
      return join(("?CFHPS"[k] for k in x), sep="  ")
    
    # solve the puzzle, and output solutions
    for (x, day) in p.solve(solver="mzn-chuffed", result="x day"):
      # order the bids in the table
      x = sorted(events(d) for d in x.values())
      printf("    Mo Tu We Th Fr")
      for (i, e) in enumerate(x, start=1):
        printf("{i}:  {fmt(e)}")
      printf("    -------------\n    {fmt(events(day))}")
      printf()
    
  2. Hakan Kjellerstrand 5 January 2018 at 7:03 pm

    @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”:

    solve :: int_search(array1d(x), anti_first_fail, indomain_min, complete) 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:

    constraint increasing([x[e,1] | e in Entrants]);
    

    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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: