Enigmatic Code

Programming Enigma Puzzles

Puzzle 70: Football five teams: new method

From New Scientist #1121, 21st September 1978 [link]

The new method of rewarding goals scored in football matches goes from strength to strength. In this method 10 points are given for a win, 5 points for a draw and 1 point for each goal scored. Once can get some idea of the success of the method from the fact that in the latest competition between 5 teams, when some of the matches had been played, each team had scored at least 1 goal in every match. They are eventually going to play each other once.

The points were as follows:

A   11
B    8
C   12
D    5
E   43

Not more than 9 goals were scored in any match.

What was the score in each match?

[puzzle70]

Advertisements

8 responses to “Puzzle 70: Football five teams: new method

  1. Jim Randell 12 July 2017 at 12:15 pm

    See also: Puzzle 78 and Enigma 239.

    Here I’ve used a simple MiniZinc model to solve this problem. The mzn-g12fd solver executes it in 110ms.

    %#! mzn-g12fd -a
    
    % points for team X in match X vs Y given goals scored
    % (we use 0-0 to mean a match is not played)
    function var int: points(var int: X, var int: Y) =
      if X = 0 /\ Y = 0
        then 0
        else X + 10 * (X > Y) + 5 * (X = Y)
      endif;
    
    % goals for each side in each game
    var 0..8: AB; var 0..8: BA;
    var 0..8: AC; var 0..8: CA;
    var 0..8: AD; var 0..8: DA;
    var 0..8: AE; var 0..8: EA;
    var 0..8: BC; var 0..8: CB;
    var 0..8: BD; var 0..8: DB;
    var 0..8: BE; var 0..8: EB;
    var 0..8: CD; var 0..8: DC;
    var 0..8: CE; var 0..8: EC;
    var 0..8: DE; var 0..8: ED;
    
    % at least one goal is scored in each played match
    constraint AB = 0 <-> BA = 0;
    constraint AC = 0 <-> CA = 0;
    constraint AD = 0 <-> DA = 0;
    constraint AE = 0 <-> EA = 0;
    constraint BC = 0 <-> CB = 0;
    constraint BD = 0 <-> DB = 0;
    constraint BE = 0 <-> EB = 0;
    constraint CD = 0 <-> DC = 0;
    constraint CE = 0 <-> EC = 0;
    constraint DE = 0 <-> ED = 0;
    
    % not more than 9 goals were scored in any match
    constraint AB + BA < 10;
    constraint AC + CA < 10;
    constraint AD + DA < 10;
    constraint AE + EA < 10;
    constraint BC + CB < 10;
    constraint BD + DB < 10;
    constraint BE + EB < 10;
    constraint CD + DC < 10;
    constraint CE + EC < 10;
    constraint DE + ED < 10;
    
    % points for each team
    constraint points(AB, BA) + points(AC, CA) + points(AD, DA) + points(AE, EA) = 11;
    constraint points(BA, AB) + points(BC, CB) + points(BD, DB) + points(BE, EB) = 8;
    constraint points(CA, AC) + points(CB, BC) + points(CD, DC) + points(CE, EC) = 12;
    constraint points(DA, AD) + points(DB, BD) + points(DC, CD) + points(DE, ED) = 5;
    constraint points(EA, AE) + points(EB, BE) + points(EC, CE) + points(ED, DE) = 43;
    
    solve satisfy;
    
    output [
     "AvB = " ++ show([AB, BA]) ++ "\n" ++
     "AvC = " ++ show([AC, CA]) ++ "\n" ++
     "AvD = " ++ show([AD, DA]) ++ "\n" ++
     "AvE = " ++ show([AE, EA]) ++ "\n" ++
     "BvC = " ++ show([BC, CB]) ++ "\n" ++
     "BvD = " ++ show([BD, DB]) ++ "\n" ++
     "BvE = " ++ show([BE, EB]) ++ "\n" ++
     "CvD = " ++ show([CD, DC]) ++ "\n" ++
     "CvE = " ++ show([CE, EC]) ++ "\n" ++
     "DvE = " ++ show([DE, ED])
    ];
    

    Solution: The scores in the played matches are: AvB = 2-2; AvE = 4-5; BvE = 1-3; CvD = 2-1; DvE = 4-5. The remaining matches are not yet played.

  2. hakank 12 July 2017 at 9:18 pm

    Here’s another MiniZinc model, using a matrix for the scores (which seemed more natural for me).

    % include "globals.mzn"; 
    
    int: n = 5;
    array[1..n] of int: points = [11,8,12,5,43];
    
    % decision variables
    % a match between a and b: a got scores[a,b] points and b got scores[b,a] points
    array[1..n,1..n] of var 0..9: scores; % max 9 scores. 0's for not played matches
    
    % var 0..(n+(n+1)) div 2: num_matches = sum([scores[i,j] > 0 | i,j in 1..n ]) div 2;
    
    % solve satisfy;
    solve :: int_search(array1d(scores), first_fail, indomain_split, complete) satisfy;
    
    constraint
      forall(i in 1..n) (
         scores[i,i] = 0 % a team don't play against itself
         /\ 
         % the possible matches
         forall(j in 1..n where i < j) (
           % a match not yet played: scores 0 
           if scores[i,j] = 0 then scores[j,i] = 0 else true endif 
           /\ 
           % each teams scored at least 1 goal in every match: scores > 0
           if scores[i,j] > 0 then scores[j,i] > 0 else true endif
           /\ % no more than 9 goals was scored in each match
           scores[i,j] + scores[j,i] <= 9
         )
      )
      /\ % the points
      forall(i in 1..n) (
        points[i] = sum([ 10*(scores[i,j] > scores[j,i]) + 5*(scores[i,j] = scores[j,i] /\ scores[i,j] > 0)
                          + scores[i,j]
                        | j in 1..n where i != j])
    
      )
    ;
    
    output 
    % ["num_matches: \(num_matches)\n"] ++
    [
      if j = 1 then "\n" else "" endif ++
        show(scores[i,j]) ++ " "
      | i,j in 1..n
    ]
    ++ ["\n\n"] ++
    [
     if fix(scores[i,j]) > 0 then 
       "\(i) vs \(j): \(scores[i,j]) - \(scores[j,i])\n"
     else 
       ""
     endif 
     | i,j in 1..n where i < j
    ]
    ;
    
    • Jim Randell 13 July 2017 at 9:35 am

      @hakank: Thanks for your post. Sorry you had problems (at one time I hoped that WordPress.com would allow the ability to edit (or even preview) comments, but it never happened).

      I took the code from the link you posted and incorporated it into the original comment, using:

      [code language="text"]...[/code]

      tags to preserve the code. (See [ https://en.support.wordpress.com/code/posting-source-code/ ] for a list of supported languages). I deleted the followup comments where you were trying to sort it out. Hope that’s OK.

      • hakank 13 July 2017 at 11:24 am

        @jim Thanks for this. And sorry for messing things up. I’ll try to remember that it should be “code” and not “pre” that I should use. And I’ll test it right away with a new comment on the Picat code. 🙂

  3. hakank 12 July 2017 at 10:52 pm

    And here’s the same approach in Picat: http://hakank.org/picat/football_five_teams_new_method.pi

    Solved in about 15millis.

  4. hakank 13 July 2017 at 11:26 am

    Here’s the Picat code mentioned above:

    import cp.
    
    main => go.
    
    go =>
      N = 5,
      Points = [11,8,12,5,43],
    
      % decision variables
      % a match between a and b: a got scores[a,b] points and b got scores[b,a] points
      Scores = new_array(N,N), 
      Scores :: 0..8, % max 8 goal per match (1+8). 0's for not played matches
    
      foreach(I in 1..N)
        Scores[I,I] #= 0, % a team don't play against itself
        foreach(J in 1..N, I < J)
           % a match not yet played: scores 0, 
           % also: each teams scored at least 1 goal in every match: scores > 0
           Scores[I,J] #= 0 #<=> Scores[J,I] #= 0,
    
           % no more than 9 goals was scored in each match
           Scores[I,J] + Scores[J,I] #<= 9
        end
      end,
      % the points
      foreach(I in 1..N)
        Points[I] #= sum([ 
                           10*(Scores[I,J] #> Scores[J,I]) + 
                           5*((Scores[I,J] #= Scores[J,I]) #/\ Scores[I,J] #> 0) +
                           Scores[I,J]
                         : J in 1..N, I != J])
      end,
    
      solve($[ff,split],Scores),
    
      foreach(I in 1..N, J in 1..N, I < J)
        if Scores[I,J] > 0 then
          printf("%d vs %d: %d - %d\n", I,J, Scores[I,J],Scores[J,I])
        end
      end,
      nl.
    
  5. hakank 21 July 2017 at 6:32 pm

    @jim: Yes, Picat is an interesting language. I’m kind of involved with Picat and co-authored the book “Constraint Solving and Planning with Picat” together with Neng-Fa Zhou (creator of Picat) and Jonathan Frumann in 2015. The book is now free to download: PDF via http://picat-lang.org/picatbook2015.html (I was the main author of the two Constraint Programming chapters). Here’s my Picat page with some programs in different areas of interest: http://hakank.org/picat/ .

    MiniZinc has better support for some type of constraints (e.g. element: z = x[y] where x, y, and z are all decision variables) and also has support for many different FlatZinc solvers, among them Picat. Picat, on the other hand, is a complete programming language where one can write traditional “imperative” loops (which MiniZinc don’t allow). So MiniZinc and Picat are both favourite languages, and nowadays I tend to implement models in both languages.

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: