Enigmatic Code

Programming Enigma Puzzles

Enigma 1209: The league game

From New Scientist #2365, 19th October 2002 [link]

Lloyd and Owen have a new game. They imagine there is a football league with four teams, A, B, C and D. Each team plays every other team once, scoring 1 point for a draw and 2 for a win. The teams are ordered in their league by points and, where there are equal points, by goal difference.

At the start of their game, Lloyd has six cards in his hand, each with a different match on it, A v B, A v C, etc. The game consists of six rounds, numbered 1 to 6 in order. In each round Lloyd chooses one of the cards in his hand and lays it on the table. Owen writes a score on it, for example if the card was A v B, he might write A2 v B1. They then work out the league table for the matches played so far and see who is top. They also work out if it is certain that the team will be top after all the six matches have been played, whatever the scores of the remaining matches. If it is certain and it was not certain in the previous round then that round is called the “Decisive” round. That completes the round.

Lloyd plays so as to make the Decisive round as late as possible and Owen aims to make it as early as possible.

Question 1: If they both play as well as possible, what is the number of the Decisive round?

Question 2: If they change the rules so that a team gets 3 points for a win, what then is the number of the Decisive round?

[enigma1209]

Advertisements

One response to “Enigma 1209: The league game

  1. Jim Randell 19 August 2015 at 11:56 am

    I didn’t particularly like this puzzle. I’m not usually a fan of the “football league table”-type puzzle, and I found this one quite a tricky one to write a program for, and while it looks OK I’m not completely confident in it.

    This Python program examines the possible game play. It runs in 5.6s. The number of points for a win can be specified on the command line (default = 2).

    from enigma import Football, chunk, diff, printf
    
    # points for a win (2 or 3)
    import sys
    W = (2 if len(sys.argv) < 2 else int(sys.argv[1]))
    printf("[win = {W} points]")
    
    # scoring regime
    football = Football(points={ 'w': W, 'd': 1 })
    
    # teams and matches
    teams = 'ABCD'
    matches = ('AB', 'AC', 'AD', 'BC', 'BD', 'CD')
    
    # number of matches each team plays
    P = len(teams) - 1
    
    # marker for indecisive tournaments
    X = len(matches) + 1
    
    # construct the table for a sequence
    def table(s):
      t = list()
      # dictionary of matches
      d = dict(chunk(s, 2))
      # compute tables
      for x in teams:
        ms = tuple(k for k in d.keys() if x in k)
        t.append(football.table(tuple(d[k] for k in ms), tuple(k.index(x) for k in ms)))
      # sort it
      t.sort(key=lambda x: (x.points, x.w, x.d, x.l), reverse=True)
      return t
    
    # is the sequence decisive
    def is_decisive(s):
      t = table(s)
      # is there a leader?
      v = t[0].points
      vs = tuple(x for x in t if x.points == v)
      if len(vs) > 1:
        # if there are no wins we can't choose on goal difference
        if all(x.w == 0 for x in vs):
          return False
      # can anyone catch up with the leader?
      return all(x.points + W * (P - x.played) < v for x in t[1:])
    
    # play the game
    # return the number of the decisive round
    def play(s, ms):
    
      (n, r) = divmod(len(s), 2)
      if r == 0:
    
        # is this round decisive?
        if is_decisive(s):
          return n
    
        # are there any matches left?
        if not ms:
          return X
    
        # player 1: choose a match
        # try to make the decisive round as late as possible
        return max(play(s + [x], diff(ms, [x])) for x in ms)
    
      else:
    
        # player 2: choose an outcome for the match
        # try to make the decisive round as early as possible
        return min(play(s + [x], ms) for x in 'wdl')
    
    # play the game, starting with the first match
    n = play(list(matches[:1]), list(matches[1:]))
    printf("decisive round = {n}")
    

    Solution: Q1. With 2 points for a win the decisive round is round 6; Q2. With 3 points for a win the decisive round is round 5.

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: