Sunday Times Teaser 2608 – Football Logic

by John Owen

Published: 16 September 2012 (link)

In the logicians’ football tournament, each of three teams (captained by Alf, Bert and Charlie) plays each other once, with three points for a win and one for a draw. In working out their order at the end of the tournament, “goals scored” are used to determine the order of teams with the same points total. Each captain only knows the scores in his own team’s games. At the end I asked the captains in turn whether they knew which position they had finished in. The replies were: Alf “no”; Bert “no”; Charlie “no”; Alf “yes”.

In which position did Charlie’s team finish, and what was the result in the game between the other two teams?

3 Comments Leave one →

Brian Gladman permalink

This one is a lot harder in Python than on pencil and paper! Here is my solution (the redundancy discussed below has now been removed):


from itertools import product
from collections import defaultdict

# The three outcomes in points for the two teams in a match
res = ( (3, 0), (1, 1), (0, 3) )

# The tournament  outcomes are a set of three matches encoded as
# (ap, bp, cp, ((a, b), (b, c), (c, a)))  in which ap, bp and cp
# are the  points for A's, B's and C's teams and the three games
# leading to these point scores is: ((a, b), (b, c), (c, a))).

# In each announcement round (A, B, C, A) we need to reflect the
# results from A, B or C's perspective  and see if they csn find
# their team's tournsament position  without knowing the results
# of the match in which they didn't take part.  Let X be A, B or
# C and Y, Z be the other two teams. For each point score for X,
# we  need to look at all Y, Z scores for this X score to see if
# X's tournament position depends on the Y, Z scores.

# indexes for X, Y and Z from a given X index
ixx = ( (0, 1, 2), (1, 2, 0), (2, 0, 1) )

def partition(c, m):
  xi, yi, zi = ixx[ord(c) - ord('A')]

  # list all the Y and Z results that give each of X's scores
  dx = defaultdict(list)
  for t in m:
    dx[t[xi]] += [(t[yi], t[zi], t[3])]

  # m1 and m2 are the results for which X can and can't declare
  # his team's position without knowing the Y, Z result
  m1, m2 = set(), set()

  # for each X point score
  for x in dx:

    # accumulate the results that produce this X point score
    # list l is used to put the results for X, Y, Z into the
    # correct positions in the output tuples
    mm, l = set(), [0] * 4
    l[xi] = x
    for y, z, t in dx[x]:
      l[yi], l[zi], l[3] = y, z, t
      mm |= set((tuple(l),))

    # check if the X is always in the same turnament position
    # irrespective of the result for Y playing Z
    if ( all(x > max(y, z) for y, z, t in dx[x]) or
         all(x < min(y, z) for y, z, t in dx[x]) or
         all(min(y, z) < x < max(y, z) for y, z, t in dx[x]) ):
      m1 |= mm
    else:
      m2 |= mm

  return m1, m2

# compile the set of the possible 'three match' outcomes
m = set()
for t in product(res, repeat=3):
  # tuples for each of the three matches
  ab, bc, ca = t
  # compute A's, B's and C's total point scores
  pa, pb, pc = ab[0] + ca[1], bc[0] + ab[1], ca[0] + bc[1]
  # if the result is not three draws
  if not (pa == pb == pc == 2):
    # compile the set of results
    m |= set(((pa, pb, pc, t),))

# remove any results where A, B and C can respectively
# declare in the first, second and third rounds
z, m = partition('A', m)
z, m = partition('B', m)
z, m = partition('C', m)
# now remove any results for which A _cannot_ declare
m, z = partition('A', m)

# now find C's position and the A vs B result in all
# results for which A knows his team's position
cc = set()
for pa, pb, pc, t in m:
  if pc not in (pa, pb):
    c_pos = sorted((pa, pb, pc)).index(pc)
    cc |= set(((c_pos, t[0]),))

# and output any results
fs = 'C's team is {:s} and the (A, B) score is {:s}.'
ff = ('first', 'second', 'third')
for c in cc:
  print(fs.format(ff[c[0]], c[1]))

from itertools import product

from collections import defaultdict

# The three outcomes in points for the two teams in a match

res = ( (3, 0), (1, 1), (0, 3) )

# The tournament outcomes are a set of three matches encoded as

# (ap, bp, cp, ((a, b), (b, c), (c, a))) in which ap, bp and cp

# are the points for A's, B's and C's teams and the three games

# leading to these point scores is: ((a, b), (b, c), (c, a))).

# In each announcement round (A, B, C, A) we need to reflect the

# results from A, B or C's perspective and see if they csn find

# their team's tournsament position without knowing the results

# of the match in which they didn't take part. Let X be A, B or

# C and Y, Z be the other two teams. For each point score for X,

# we need to look at all Y, Z scores for this X score to see if

# X's tournament position depends on the Y, Z scores.

# indexes for X, Y and Z from a given X index

ixx = ( (0, 1, 2), (1, 2, 0), (2, 0, 1) )

def partition(c, m):

xi, yi, zi = ixx[ord(c) - ord('A')]

# list all the Y and Z results that give each of X's scores

dx = defaultdict(list)

for t in m:

dx[t[xi]] += [(t[yi], t[zi], t[3])]

# m1 and m2 are the results for which X can and can't declare

# his team's position without knowing the Y, Z result

m1, m2 = set(), set()

# for each X point score

for x in dx:

# accumulate the results that produce this X point score

# list l is used to put the results for X, Y, Z into the

# correct positions in the output tuples

mm, l = set(), [0] * 4

l[xi] = x

for y, z, t in dx[x]:

l[yi], l[zi], l[3] = y, z, t

mm |= set((tuple(l),))

# check if the X is always in the same turnament position

# irrespective of the result for Y playing Z

if ( all(x > max(y, z) for y, z, t in dx[x]) or

all(x < min(y, z) for y, z, t in dx[x]) or

all(min(y, z) < x < max(y, z) for y, z, t in dx[x]) ):

m1 |= mm

else:

m2 |= mm

return m1, m2

# compile the set of the possible 'three match' outcomes

m = set()

for t in product(res, repeat=3):

# tuples for each of the three matches

ab, bc, ca = t

# compute A's, B's and C's total point scores

pa, pb, pc = ab[0] + ca[1], bc[0] + ab[1], ca[0] + bc[1]

# if the result is not three draws

if not (pa == pb == pc == 2):

# compile the set of results

m |= set(((pa, pb, pc, t),))

# remove any results where A, B and C can respectively

# declare in the first, second and third rounds

z, m = partition('A', m)

z, m = partition('B', m)

z, m = partition('C', m)

# now remove any results for which A _cannot_ declare

m, z = partition('A', m)

# now find C's position and the A vs B result in all

# results for which A knows his team's position

cc = set()

for pa, pb, pc, t in m:

if pc not in (pa, pb):

c_pos = sorted((pa, pb, pc)).index(pc)

cc |= set(((c_pos, t[0]),))

# and output any results

fs = 'C's team is {:s} and the (A, B) score is {:s}.'

ff = ('first', 'second', 'third')

for c in cc:

print(fs.format(ff[c[0]], c[1]))

tonysmith permalink

Brian – this week I can’t follow much that is not green! What would happen without line 084?

Reply
Brian Gladman permalink

Hi Tony,

The short answer is nothing. Its original purpose was to take account of the fact that the A, B and C elimination steps are not identical since B has a bit more information than A, and C has more information than both A and B.

Originally, I had separate solutions for A, B and C rather than using the common ‘partition’ subroutine. When I moved to use a common subroutine, I originally had to add the extra elimination step for C to account for eliminations that C could do but A and B could not. But I made a change in the partition subroutine that (I think) removes the need for this.

Reply

Sunday Times Teaser 2608 – Football Logic

by John Owen

Published: 16 September 2012 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta