Enigmatic Code

Programming Enigma Puzzles

Enigma 344: Five-nations championship

From New Scientist #1493, 30th January 1986 [link]

England, Scotland, Wales, Ireland and France took part in the Rugby union five-nations championship, each country playing each other country once. Two match points were awarded for a win and one match point for a draw, and the total number of match points gained by each country was: England 7, Scotland 6, Wales 4, Ireland 2, France 1.

No two matches had the same score and no country scored more than six points in any match; but each country scored exactly the same number of points in the championship as each other country, and Wales also had this number of points scored against them.

Those not familiar with the point scoring system of rugby union merely need to know that it is not possible for a side to score one, two or five points in a match.

What were the results and scores of Wales’s matches in the championship?

[enigma344]

Advertisements

2 responses to “Enigma 344: Five-nations championship

  1. Jim Randell 13 May 2016 at 7:30 am

    This Python 3 program uses the Football.substituted_table() function from the enigma.py library to find possible match outcomes. Then it uses a recursive function to allocate scores to the matches that satisfy the goals (match points) for / against conditions. It runs in 133ms.

    from collections import Counter
    from enigma import Football, diff, printf
    
    # scoring system
    football = Football(games='wdl', points={ 'w': 2, 'd': 1 }, )
    
    # possible scorelines
    scores = {
      # wins
      'w': ((3, 0), (4, 0), (4, 3), (6, 0), (6, 3), (6, 4)),
      # draws
      'd': ((0, 0), (3, 3), (4, 4), (6, 6)),
    }
    # losses
    scores['l'] = ((b, a) for (a, b) in scores['w'])
    
    # labels for the teams
    (E, S, W, I, F) = (0, 1, 2, 3, 4)
    
    # generate possible scores for a team given the match outcomes
    # scores in all matches are different
    # ms - match outcomes
    # ts - indices in ms for the team we are interested in
    # xs - excluded scores
    # f - goals for
    # a - goals against
    # ss - scores accumulated so far
    # returns: (list of <scores>, <goals for>, <goals against>)
    def generate_scores_team(ms, ts, xs=set(), f=0, a=0, ss=[]):
      if not ms:
        yield (ss, f, a)
      else:
        (m, t) = (ms[0], ts[0])
        for s in scores[m]:
          if s not in xs and s[::-1] not in xs:
            yield from generate_scores_team(ms[1:], ts[1:], xs.union([s]), f + s[t], a + s[t ^ 1], ss + [s])
    
    # update a dictionary with keys, values
    def update(d, ks, vs):
      d = dict(d)
      d.update(zip(ks, vs))
      return d
    
    # generate scores for each match in matches
    # teams - specifies the order the teams are processed in
    # check - check function for the goals_for / goals_against values
    # scores - scores in matches
    # goals_for, goals_against - goals for / goals against values for the teams
    # returns: (scores, goals_for, goals_against)
    def generate_scores(matches, teams, check, scores=dict(), goals_for=[], goals_against=[]):
      if not teams:
        yield (scores, goals_for, goals_against)
      else:
        t = teams[0]
        # matches for team t
        ms = list(m for m in matches.keys() if t in m)
        # matches with scores
        ss = list(m for m in ms if m in scores)
        # goals for/against in matches with scores
        (f, a) = football.goals((scores[m] for m in ss), (m.index(t) for m in ss))
        # find scores for the remaining unscored matches
        rs = diff(ms, ss)
        for (s, f, a) in generate_scores_team(list(matches[m] for m in rs), list(m.index(t) for m in rs), set(scores.values()), f, a):
          (gf, ga) = (goals_for + [f], goals_against + [a])
          if check(gf, ga):
            yield from generate_scores(matches, teams[1:], check, update(scores, rs, s), gf, ga)
    
    # function to check all goals for are the same as the first goals against
    def check(goals_for, goals_against):
      a = goals_against[0]
      return all(x == a for x in goals_for)
    
    # record Wales matches
    r = Counter()
    
    # solve the table
    for (ms, _) in football.substituted_table({ 'points': '76421' }, d={ '1': 1, '2': 2, '4': 4, '6': 6, '7': 7 }):
      # generate scores that satisfy check()
      for (ss, f, a) in generate_scores(ms, teams=[W, E, S, I, F], check=check):
        # output the results
        football.output_matches(ms, ss, teams='ESWIF')
        # record Wales matches
        r[(ss[(E, W)], ss[(S, W)], ss[(W, I)], ss[(W, F)])] += 1
    
    # output solutions
    for ((EW, SW, WI, WF), n) in r.most_common():
      printf("EW={EW} SW={SW} WI={WI} WF={WF} [{n} solutions]")
    

    Solution: The scores in Wales’ matches are: England vs. Wales = 3-0; Scotland vs. Wales = 3-3; Wales vs. Ireland = 4-4; Wales vs. France = 6-3.

    Each team scored 13 points overall.

    There are 6 different ways to assign the scores, but the scores in the England vs. Scotland, England vs. Wales, Scotland vs. Wales, Wales vs. Ireland, Wales vs. France, and Ireland vs. France matches are always the same.

    The scores in the matches that don’t involve Wales are:

    England vs. Scotland = 0-0;
    England vs. Ireland = 4-0 or 4-3 or 6-0;
    England vs. France = 6-0 or 6-4 or 4-0;

    Scotland vs. France = 6-4 or 6-0 or 4-0;
    Scotland vs. Ireland = 4-3 or 4-0 or 6-0;

    Ireland vs. France = 6-6.

  2. Jim Randell 13 May 2016 at 7:31 am

    Here’s a declarative solution in MiniZinc. It runs in 86ms.

    include "globals.mzn";
    
    % possible scores:
    
    % goals for / against
    %                        |      losses     |  draws   |      wins       |
    %                         1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
    array[1..16] of int: F = [0, 0, 3, 0, 3, 4, 0, 3, 4, 6, 3, 4, 4, 6, 6, 6];
    array[1..16] of int: A = [3, 4, 4, 6, 6, 6, 0, 3, 4, 6, 0, 0, 3, 0, 3, 4];
    
    % points for team 1 in a match (1 for a draw, 2 for a win)
    function var int: points1(var int: m) = (m > 6) + (m > 10);
    
    % points for team 2 in a match
    function var int: points2(var int: m) = 2 - points1(m);
    
    % scores for each match
    var 1..16: ES;
    var 1..16: EW;
    var 1..16: EI;
    var 1..16: EF;
    var 1..16: SW;
    var 1..16: SI;
    var 1..16: SF;
    var 1..16: WI;
    var 1..16: WF;
    var 1..16: IF;
    
    % constraints:
    
    % all scores are different
    constraint all_different([ES, EW, EI, EF, SW, SI, SF, WI, WF, IF]);
    
    % England has 7 points
    constraint points1(ES) + points1(EW) + points1(EI) + points1(EF) == 7;
    
    % Scotland has 6 points
    constraint points2(ES) + points1(SW) + points1(SI) + points1(SF) == 6;
    
    % Wales has 4 points
    constraint points2(EW) + points2(SW) + points1(WI) + points1(WF) == 4;
    
    % Ireland has 2 points
    constraint points2(EI) + points2(SI) + points2(WI) + points1(IF) == 2;
    
    % France has 1 point
    constraint points2(EF) + points2(SF) + points2(WF) + points2(IF) == 1;
    
    % all "goals for" are the same, as is "goals against" for Wales
    constraint all_equal([
      F[ES] + F[EW] + F[EI] + F[EF], % goals for England
      A[ES] + F[SW] + F[SI] + F[SF], % goals for Scotland
      A[EW] + A[SW] + F[WI] + F[WF], % goals for Wales
      A[EI] + A[SI] + A[WI] + F[IF], % goals for Ireland
      A[EF] + A[SF] + A[WF] + A[IF], % goals for France
      F[EW] + F[SW] + A[WI] + A[WF], % goals against Wales
    ]);
    
    % solve it
    solve satisfy;
    
    % output the scores
    output [
    % "E v S: " ++ show([F[ES], A[ES]]) ++ "\n" ++
      "E v W: " ++ show([F[EW], A[EW]]) ++ "\n" ++
    % "E v I: " ++ show([F[EI], A[EI]]) ++ "\n" ++
    % "E v F: " ++ show([F[EF], A[EF]]) ++ "\n" ++
      "S v W: " ++ show([F[SW], A[SW]]) ++ "\n" ++
    % "S v I: " ++ show([F[SI], A[SI]]) ++ "\n" ++
    % "S v F: " ++ show([F[SF], A[SF]]) ++ "\n" ++
      "W v I: " ++ show([F[WI], A[WI]]) ++ "\n" ++
      "W v F: " ++ show([F[WF], A[WF]]) ++ "\n" ++
    % "I v F: " ++ show([F[IF], A[IF]]) ++ "\n" ++
      ""
    ];
    

    If you want to see the six possible solutions you can remove the comments in the output clause to show all the scores.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: