Enigmatic Code

Programming Enigma Puzzles

Tantalizer 442: What’s the score?

From New Scientist #993, 25th March 1976 [link]

The usual five football teams entered our local cup and played the usual one game against each of the others. Exactly three of the games were won by the home side. No two teams won the same number of games. There were no drawn games. Each team played two games at home.

The Ayfield Aces won two games. The Barnley Bears were at home to the Aces and to the Cornfield Casuals. The Casuals were at home to the Aces. Ditching Dynamos were at home to the Eggplant Eagles.

What was the result in each of the ten games?

[tantalizer442]

2 responses to “Tantalizer 442: What’s the score?

  1. Jim Randell 31 October 2018 at 6:59 am

    I wrote a MiniZinc model to find the tables for home/away fixtures and win/lose outcomes.

    This model runs in 139ms.

    %#! mzn-gecode -a
    
    include "globals.mzn";
    
    % the five teams
    set of int: Teams = 1..5;
    int: A = 1;
    int: B = 2;
    int: C = 3;
    int: D = 4;
    int: E = 5;
    
    % table of home games
    array [Teams, Teams] of var 0..1: home;
    
    % no team plays itself
    constraint forall (i in Teams) (home[i, i] = 0);
    
    % if a team plays at home, the other team plays away
    constraint forall (i, j in Teams where i < j) (home[i, j] + home[j, i] = 1);
    
    % table of wins
    array [Teams, Teams] of var 0..1: win;
    
    % no team plays itself
    constraint forall (i in Teams) (win[i, i] = 0);
    
    % if one team wins, the other team loses
    constraint forall (i, j in Teams where i < j) (win[i, j] + win[j, i] = 1);
    
    
    % "exactly three of the games were won by the home side"
    constraint sum (i, j in Teams) (win[i, j] = 1 /\ home[i, j] = 1) = 3;
    
    % "no two teams won the same number of games"
    function var int: wins(var int: i) = sum (j in Teams where j != i) (win[i, j]);
    constraint all_different([wins(i) | i in Teams]);
    
    % "each team played two games at home"
    constraint forall (i in Teams) (sum (j in Teams) (home[i, j]) = 2);
    
    % "A won 2 games"
    constraint wins(A) = 2;
    
    % "B were at home to A and to C"
    constraint home[B, A] = 1 /\ home[B, C] = 1;
    
    % "C were at home to A"
    constraint home[C, A] = 1;
    
    % "D were at home to E"
    constraint home[D, E] = 1;
    
    solve satisfy;
    

    Solution: E won all four of their games (against A, B, C, D). D won their games against A, B, C (but lost to E). A won their games against B and C (and lost to D and E). C won their game against B (but lost to A, D, E). B lost all four of their games (against A, C, D, E).

    Here’s a table (1 = win, 0 = lose, yellow = home):

    So the three home wins were D at home to B, E at home to B and E at home to C.

    • Jim Randell 31 October 2018 at 4:47 pm

      I also wrote a Python program to solve this problem. It runs in 113ms.

      Run: [ @repl.it ]

      from itertools import product
      from enigma import irange, first, icount, unpack, seq_all_different, printf
      
      # labels for the teams
      (A, B, C, D, E) = irange(0, 4)
      
      # make a (k^2) table from a sequence of T(k) elements
      def table(s, k=5, invert=lambda x: 1 - x):
        s = iter(s)
        t = list()
        for i in irange(0, k - 1):
          # copy and invert elements before the diagonal
          r = list(invert(t[j][i]) for j in irange(0, i - 1))
          # add the diagonal entry
          r.append(0)
          # consume elements from the sequence
          r.extend(first(s, k - i - 1))
          # add the row
          t.append(r)
        return t
      
      # potential 5x5 tables for home and win
      tables = map(table, product((0, 1), repeat=10))
      
      # consider table for home games
      for home in tables:
      
        # "B were at home to A and C"
        if not(home[B][A] and home[B][C]): continue
      
        # "C were at home to A"
        if not(home[C][A]): continue
      
        # "D were at home to E"
        if not(home[D][E]): continue
      
        # "each team played 2 games at home"
        if not all(sum(r) == 2 for r in home): continue
      
        # consider table for wins
        for win in tables:
      
          # "A won 2 games"
          if not(sum(win[A]) == 2): continue
      
          # "no two teams won the same number of games"
          if not seq_all_different(map(sum, win)): continue
      
          # "exactly three of the games were won by the home side"
          fn = unpack(lambda i, j: win[i][j] and home[i][j])
          if not(icount(product((A, B, C, D, E), repeat=2), fn, 4) == 3): continue
      
          printf("home = {home}")
          printf("win  = {win}")
          printf()
      

      The interesting bit of code to write was the [[ table() ]] function that constructs a 5×5 table from the T(5 – 1) = 10 elements that form the upper right hand part.

      For each table there are 2^10 = 1024 possibilities before the conditions are applied.

      The information about the home games is sufficient that there is only a single “home” table by the time we get to line 39.

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: