Sunday Times Teaser 2765 – Prime Points

by John Owen

Published: 20 September 2015 (link)

In my fantasy football league each team plays each other once, with three points for a win and one point for a draw. Last season Aberdeen won the league, Brechin finished second, Cowdenbeath third, and so on, in alphabetical order. Remarkably each team finished with a different prime number of points. Dunfermline lost to Forfar.

In order, what were Elgin’s results against Aberdeen, Brechin, Cowdenbeath, and so on (in the form WWLDL…)?

One Comment Leave one →

Brian Gladman permalink


from itertools import combinations, permutations, product
from collections import defaultdict
from number_theory import Primes, frobenius_solve

# return unique permutations of an input sequence
def unique_permutations(x): 
  seen = set()
  for p in permutations(x):
    if p not in seen:
      seen.update([p])
      yield p

# compile match results that give a specified set of (win, draw, loss)
# values; for the list (in res) of (win, draw, loss) values for the 
# teams in order of their league positions (A, B, ...) allocate their
# wins, draws and losses as losses, draws and wins for the teams in 
# lower positions, permuting them to check all possible allocations;
# repeat this until all match scores have been allocated in this way; 
def compile_table(res, g):
  if len(res) == 0:
    # we have a compatible set of match scores - convert the results
    # in g to match results for each team 
    r = defaultdict(str)
    for a in range(len(g)):
      for b in range(a + 1, len(g)):
        r[chr(ord('A') + a)] += 'LDW'[g[a][b - a - 1]]
        r[chr(ord('A') + b)] += 'WDL'[g[a][b - a - 1]]
    yield g, r
  else:
    # convert the current team's wins, draws and losses into losses,
    # draws and wins for the lower placed teams (use indexes into 'WDL')
    t = [2] * res[0][0] + [1] * res[0][1] + [0] * res[0][2]
    # permute these results for allocation to the remaining teams
    for p in unique_permutations(t):
      # now compile the remaining wins, draws and losses after these 
      # results have been accounted for
      new_res = tuple(tuple(x[j] - (1 if j == y else 0) 
                  for j in (0, 1, 2)) for x, y in zip(res[1:], p))
      # ensure that the win, draw, loss values remain valid
      if all(x >= 0 for y in new_res for x in y):
        # proceed to the next team lower in the league and repeat
        yield from compile_table(new_res, g + [p])

# for saving possible solutions
psol = []
# Since teams each play (N - 1) matches, the maximum points for a team is
# 3N - 3; so N must be such that the N'th prime is <= 3N - 3, which means
# that N is less than 10 with a maximum prime of 23 
pr = Primes().list(0, 25)
# the number of teams
for teams in range(6, 10):
  # the number of matches
  matches = teams * (teams - 1) // 2
  for seq in combinations(pr, teams):
    # ensure that the sum of the points is valid (the minmum/maximum total
    # points are two/three times the number of matches)
    if not (2 * matches <= sum(seq) <= 3 * matches):
      continue
    # find all possible (win, draw, loss) combinations that give these numbers
    # of points (put higher scores first - i.e. in order of league position)
    for wd_l in product(*(frobenius_solve((1, 3), s) for s in reversed(seq))):
      # add in the losses for each team and check that they are not negative 
      wdl_l = [(d, w, teams - 1 - w - d) for w, d in wd_l if w + d < teams]
      # check we have (win, draw, loss) values for every team
      if len(wdl_l) == teams:
        # now compile the total wins, draws and losses
        w, d, l = (sum(x[0] for x in wdl_l), sum(x[1] for x in wdl_l),
                   sum(x[2] for x in wdl_l))
        # total wins must equal total losses and total draws must be even
        # team D must lose at least once and team F must win at least once 
        if w == l and d % 2 == 0 and wdl_l[3][2] and wdl_l[5][0] > 0:
          psol += [tuple(wdl_l)]

# for each set of (win, draw, loss) sequences for the teams, look for a set of
# compatible match results
for res in psol:
  first = True
  for g, r in compile_table(res, []):
    if first:
      print('WDL (A, B, ...):', *res)
      print('Results:')
      first = False
    # set a marker for any results where D loses to F
    s = ' ***' if r['D'][4] == 'L' else ''
    print('  ', tuple(x + ':' + r[x] for x in sorted(r.keys())), s)

from itertools import combinations, permutations, product

from collections import defaultdict

from number_theory import Primes, frobenius_solve

# return unique permutations of an input sequence

def unique_permutations(x):

seen = set()

for p in permutations(x):

if p not in seen:

seen.update([p])

yield p

# compile match results that give a specified set of (win, draw, loss)

# values; for the list (in res) of (win, draw, loss) values for the

# teams in order of their league positions (A, B, ...) allocate their

# wins, draws and losses as losses, draws and wins for the teams in

# lower positions, permuting them to check all possible allocations;

# repeat this until all match scores have been allocated in this way;

def compile_table(res, g):

if len(res) == 0:

# we have a compatible set of match scores - convert the results

# in g to match results for each team

r = defaultdict(str)

for a in range(len(g)):

for b in range(a + 1, len(g)):

r[chr(ord('A') + a)] += 'LDW'[g[a][b - a - 1]]

r[chr(ord('A') + b)] += 'WDL'[g[a][b - a - 1]]

yield g, r

else:

# convert the current team's wins, draws and losses into losses,

# draws and wins for the lower placed teams (use indexes into 'WDL')

t = [2] * res[0][0] + [1] * res[0][1] + [0] * res[0][2]

# permute these results for allocation to the remaining teams

for p in unique_permutations(t):

# now compile the remaining wins, draws and losses after these

# results have been accounted for

new_res = tuple(tuple(x[j] - (1 if j == y else 0)

for j in (0, 1, 2)) for x, y in zip(res[1:], p))

# ensure that the win, draw, loss values remain valid

if all(x >= 0 for y in new_res for x in y):

# proceed to the next team lower in the league and repeat

yield from compile_table(new_res, g + [p])

# for saving possible solutions

psol = []

# Since teams each play (N - 1) matches, the maximum points for a team is

# 3N - 3; so N must be such that the N'th prime is <= 3N - 3, which means

# that N is less than 10 with a maximum prime of 23

pr = Primes().list(0, 25)

# the number of teams

for teams in range(6, 10):

# the number of matches

matches = teams * (teams - 1) // 2

for seq in combinations(pr, teams):

# ensure that the sum of the points is valid (the minmum/maximum total

# points are two/three times the number of matches)

if not (2 * matches <= sum(seq) <= 3 * matches):

continue

# find all possible (win, draw, loss) combinations that give these numbers

# of points (put higher scores first - i.e. in order of league position)

for wd_l in product(*(frobenius_solve((1, 3), s) for s in reversed(seq))):

# add in the losses for each team and check that they are not negative

wdl_l = [(d, w, teams - 1 - w - d) for w, d in wd_l if w + d < teams]

# check we have (win, draw, loss) values for every team

if len(wdl_l) == teams:

# now compile the total wins, draws and losses

w, d, l = (sum(x[0] for x in wdl_l), sum(x[1] for x in wdl_l),

sum(x[2] for x in wdl_l))

# total wins must equal total losses and total draws must be even

# team D must lose at least once and team F must win at least once

if w == l and d % 2 == 0 and wdl_l[3][2] and wdl_l[5][0] > 0:

psol += [tuple(wdl_l)]

# for each set of (win, draw, loss) sequences for the teams, look for a set of

# compatible match results

for res in psol:

first = True

for g, r in compile_table(res, []):

if first:

print('WDL (A, B, ...):', *res)

print('Results:')

first = False

# set a marker for any results where D loses to F

s = ' ***' if r['D'][4] == 'L' else ''

print(' ', tuple(x + ':' + r[x] for x in sorted(r.keys())), s)

Sunday Times Teaser 2765 – Prime Points

by John Owen

Published: 20 September 2015 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta