Enigmatic Code

Programming Enigma Puzzles

Tantalizer 441: Luck of the draw

From New Scientist #992, 18th March 1976 [link]

Dopey confessed that he had never learnt to play chess and was appointed umpire. The other six dwarves settled down to play a five-round tournament. Grumpy drew with everyone but Sneezy and finished equal bottom with Doc, whom he had played in the first round. Sneezy drew with Doc, Happy and Sleepy. Bashful drew with Sleepy. There were no other draws.

There was at least one draw in each round and each dwarf drew in at least two consecutive rounds. The two equal winners did not play each other in the second round.

What were the pairings in the final round?

[tantalizer441]

One response to “Tantalizer 441: Luck of the draw

  1. Jim Randell 14 November 2018 at 8:05 am

    As Dopey sits out we can use two letter abbreviations for the dwarves (also assuming the dwarf whose name is not given in the puzzle is “Bashful”).

    I opted for a declarative approach to this puzzle, as my imperative Python code [link] was getting a bit messy (although it was a bit faster).

    Here is a MiniZinc model for the problem.

    %#! mzn-gecode -a
    
    include "globals.mzn";
    
    % labels for the 6 players
    set of int: Players = 1..6;
    int: Ba = 1;
    int: Do = 2;
    int: Gr = 3;
    int: Ha = 4;
    int: Sl = 5;
    int: Sn = 6;
    
    % in which round does each pair meet?
    array[Players, Players] of var 0..5: round;
    
    % no-one plays themselves
    constraint forall (i in Players) (round[i, i] = 0);
    
    % but players play each other
    constraint forall (i, j in Players where i < j) (round[i, j] = round[j, i]);
    
    % different players in different rounds
    constraint forall (i in Players) (all_different([round[i, j] | j in Players]));
    constraint forall (j in Players) (all_different([round[i, j] | i in Players]));
    
    % points in each game (2 for a win, 1 for a draw)
    array[Players, Players] of var 0..2: points;
    
    % no one plays themselves
    constraint forall (i in Players) (points[i, i] = 0);
    
    % 2 points are awarded in each game
    constraint forall (i, j in Players where i < j) (points[i, j] + points[j, i] = 2);
    
    % total points for player i
    var int: total(var int: i) = sum (j in Players where j != i) (points[i, j]);
    
    % additional constraints:
    
    % "Grumpy drew with everyone but Sneezy"
    constraint points[Gr, Ba] = 1;
    constraint points[Gr, Do] = 1;
    constraint points[Gr, Ha] = 1;
    constraint points[Gr, Sl] = 1;
    constraint points[Gr, Sn] != 1;
    
    % "Grumpy finished equal bottom with Doc"
    var int: bottom;
    constraint bottom = total(Gr);
    constraint bottom = total(Do);
    constraint forall (i in [Ba, Ha, Sl, Sn]) (total(i) > bottom);
    
    % "Grumpy played Doc in round 1"
    constraint round[Gr, Do] = 1;
    
    % "Sneezy drew with Doc, Happy and Sleepy"
    constraint points[Sn, Do] = 1;
    constraint points[Sn, Ha] = 1;
    constraint points[Sn, Sl] = 1;
    
    % "Bashful drew with Sleepy"
    constraint points[Ba, Sl] = 1;
    
    % there were no other draws
    constraint points[Sn, Ba] != 1;
    constraint points[Do, Ha] != 1;
    constraint points[Do, Sl] != 1;
    constraint points[Do, Ba] != 1;
    constraint points[Ha, Sl] != 1;
    constraint points[Ha, Ba] != 1;
    
    % there was at least one draw in each round
    constraint forall (k in 1..5) (exists (i, j in Players) (round[i, j] = k /\ points[i, j] = 1));
    
    % each player drew in at least two consecutive rounds
    constraint forall (i in Players) (exists (k in 1..4) (
      (exists (j in Players) (round[i, j] = k /\ points[i, j] = 1)) /\
      (exists (j in Players) (round[i, j] = k + 1 /\ points[i, j] = 1))
    ));
    
    % the two equal winners did not play each other in the second round
    var int: top;
    var Players: w1;
    var Players: w2;
    constraint w1 < w2;
    constraint total(w1) = top;
    constraint total(w2) = top;
    constraint forall (i in Players) (not(i = w1 \/ i = w2) -> total(i) < top);
    constraint round[w1, w2] != 2;
    
    solve satisfy;
    

    And here is a Python program to format the output (using the minizinc.py wrapper). Overall execution time is 281ms.

    from itertools import combinations
    from enigma import irange, join, sprintf as f, printf
    from minizinc import MiniZinc
    
    # labels to output the solutions
    players = irange(1, 6)
    label = "?? Ba Do Gr Ha Sl Sn".split(" ")
    win = 'ldw' # 0 = lose, 1 = draw, 2 = win
    
    # the MiniZinc model
    p = MiniZinc("tantalizer441.mzn", use_shebang=1)
    
    # solve the puzzle an extract the tables
    for (r, p) in p.solve(result="round points"):
      # consider each round
      for k in irange(1, 5):
        # find (i, j) pairings in round k
        ps = list((i, j) for (i, j) in combinations(players, 2) if r[i][j] == k)
        printf("round {k}: {ps}", ps=join((f("{i}-{j} ({w})", i=label[i], j=label[j], w=win[p[i][j]]) for (i, j) in ps), sep=", "))
      # find the total points for each player
      printf("total points: {pts}", pts=join((f("{i} = {n}", i=label[i], n=sum(p[i].values())) for i in players), sep=", "))
      printf()
    

    Solution: The matches in the final round were: Bashful vs. Sneezy; Doc vs. Sleepy; Grumpy vs. Happy.

    There is only one possible arrangement for the matches:

    Round 1: Bashful vs. Happy; Doc vs. Grumpy; Sleepy vs. Sneezy.
    Round 2: Bashful vs. Grumpy; Doc vs. Sneezy; Happy vs. Sleepy.
    Round 3: Bashful vs. Sleepy; Doc vs. Happy; Grumpy vs. Sneezy.
    Round 4: Bashful vs. Doc; Grumpy vs. Sleepy; Happy vs. Sneezy.
    Round 5: Bashful vs. Sneezy; Doc vs. Sleepy; Grumpy vs. Happy.

    But there are three possible outcomes:

    Round 1: lose, draw, draw.
    Round 2: draw, draw, lose.
    Round 3: draw, lose, lose.
    Round 4: win, draw, draw.
    Round 5: win, win, draw.

    Round 1: lose, draw, draw.
    Round 2: draw, draw, win.
    Round 3: draw, win, lose.
    Round 4: win, draw, draw.
    Round 5: win, lose, draw.

    Round 1: win, draw, draw.
    Round 2: draw, draw, win.
    Round 3: draw, lose, lose.
    Round 4: lose, draw, draw.
    Round 5: win, lose, draw.

    Assuming 2 points for a win, and 1 point to each player in a draw:

    The joint winners, with 6 points each, are Bashful and Happy.
    The joint losers, with 4 points each, are Doc and Grumpy.
    And in the middle, with 5 points each, are Sleepy and Sneezy.

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: