Enigmatic Code

Programming Enigma Puzzles

Tantalizer 475: League table

From New Scientist #1026, 11th November 1976 [link]

Here is what is left of the league table pinned in our local church door at the end of the season. It shows the number of goals scored in each match rather than the mere result. Each side played each [other side] once and there were no ties in the “points” list.

You would think that the Anvils, having scored more than half the goals scored in the entire competition, must have done pretty well. But in fact, as you see, they came bottom. The Bears beat the Eagles and drew with the Furies. At least one team drew more games than the Casuals. The Dynamos — but that’s enough information.

Can you fill in the table?

[tantalizer475]

One response to “Tantalizer 475: League table

  1. Jim Randell 16 August 2017 at 9:59 am

    Instead of writing a program to solve the problem I expressed it as a set of MiniZinc constraints:

    %#! mzn-chuffed -a
    
    include "globals.mzn";
    
    % the teams
    set of int: Teams = 1..6;
    int: A = 1;
    int: B = 2;
    int: C = 3;
    int: D = 4;
    int: E = 5;
    int: F = 6;
    
    % the table
    array[Teams, Teams] of var 0..19: x;
    
    % teams don't play themselves
    constraint forall (i in Teams) (x[i, i] = 0);
    
    % figures given in the table
    constraint x[A, B] = 3;
    constraint x[A, C] = 3;
    constraint x[A, D] = 3;
    constraint x[A, E] = 3;
    constraint x[A, F] = 10;
    constraint x[F, A] = 2;
    
    % total number of goals scored by team i
    function var int: goals(var int: i) = sum (j in Teams where j != i) (x[i, j]);
    
    % A scored more than half the goals in the match
    constraint goals(A) > sum (i in Teams where i != A) (goals(i));
    
    % number of matches won by team i
    function var int: win(var int: i) = sum (j in Teams where j != i) (x[i, j] > x[j, i]);
    
    % number of matches drawn by team i
    function var int: draw(var int: i) = sum (j in Teams where j != i) (x[i, j] = x[j, i]);
    
    % points for team i (2 points for a win, 1 for a draw)
    function var int: points(var int: i) = 2 * win(i) + draw(i);
    
    % there are no ties in the points list
    constraint all_different (i in Teams) (points(i));
    
    % A came bottom
    constraint forall (i in Teams where i != A) (points(A) < points(i));
    
    % B beat E
    constraint x[B, E] > x[E, B];
    
    % B drew with F
    constraint x[B, F] = x[F, B];
    
    % at least one team drew more games than C
    constraint exists (i in Teams where i != C) (draw(i) > draw(C));
    
    solve satisfy;
    

    The [[ mzn-chuffed ]] solver executes this model in 287ms.

    And here is a Python program that uses the minizinc.py wrapper to format the output from MiniZinc into the appropriate table.

    from enigma import compare, printf
    from minizinc import MiniZinc
    
    # map team index to name
    teams = dict(enumerate("ABCDEF", start=1))
    
    # row format
    fmt = "{t:>1} {A:>3} {B:>3} {C:>3} {D:>3} {E:>3} {F:>3}  {pts:>3}"
    for (x,) in MiniZinc("tantalizer475.mzn").solve(result="x", solver="mzn-chuffed -a"):
      # output the header
      d = dict((x, x) for x in "A B C D E F pts".split())
      printf(fmt, t='', **d)
      for (k, t) in teams.items():
        # calculate points
        pts = sum([0, 1, 2][compare(x[k][i], x[i][k]) + 1] for i in teams.keys() if i != k)
        # remaining values in the table
        d = dict((teams[i], s) for (i, s) in x[k].items())
        d[t] = '-'
        # output the row
        printf(fmt, pts=pts, **d)
      printf()
    

    Solution: The full table is given below:

    Assuming 2 points for a win and 1 to each side for a draw. (The published solution gives 1 point for a win and a half point to each side for a draw).

    If, however, we were to assume 3 points for a win and 1 for a draw then there would be multiple solutions, so really the puzzle should explicitly state the scoring system.

    The scores in the matches are:

    AvB = 3-4, AvC = 3-4, AvD = 3-4, AvE = 3-4, AvF = 10-2
    BvC = 0-0, BvD = 0-0, BvE = 1-0, BvF = 0-0
    CvD = 0-0, CvE = 1-0, CvF = 1-0
    DvE = 0-0, DvF = 0-0
    EvF = 0-0

    As we see, A scored 22 goals, and all the other teams scored 21 goals between them. C drew two matches (BvC, CvD), and B and F drew 3 matches (BvC, BvD, BvF and BvF, DvF, EvF) and D drew four matches (BvD, CvD, DvE, DvF).

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: