Teaser 2765: Prime points
From The Sunday Times, 20th 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…)?
[teaser2765]
Frits and 
Jim Randell 8:38 am on 24 November 2020 Permalink |
This Python program considers possible numbers of teams (up to a maximum of 26, as each team is named for a letter of the alphabet), and looks for possible sequences of primes that could correspond to the points. Once a candidate sequence is found we try to fill out a table of match outcomes (win, lose, draw) that gives the desired number of points for each team.
It runs in 49ms.
Run: [ @repl.it ]
from enigma import irange, T, Primes, subsets, express, update, join, printf points = { 'w': 3, 'd': 1 } # points for win, draw swap = { 'w': 'l', 'l': 'w', 'd': 'd' } # how a match went for the other team # complete the table by filling out row i onwards def complete(k, table, ps, i=0): # are we done? if not(i < k): yield table else: # collect: (total, empty squares) (t, js) = (ps[i], list()) for (j, x) in enumerate(table[i]): if x == ' ': js.append(j) else: t -= points.get(x, 0) # find ways to express t using 3 (= w) and 1 (= d) for (d, w) in express(t, (1, 3)): # and the remaining games are lost l = len(js) - d - w if l < 0: continue # look for ways to fill out the row for row in subsets('w' * w + 'd' * d + 'l' * l, size=len, select="mP"): # make an updated table t = update(table, [(i, update(table[i], js, row))]) for (j, x) in zip(js, row): t[j] = update(t[j], [(i, swap[x])]) # and solve for the remaining points yield from complete(k, t, ps, i + 1) # list of primes primes = Primes(75) # consider the number of teams in the league for k in irange(6, 26): # total number of matches n = T(k - 1) # maximum possible number of points m = 3 * (k - 1) # choose a set of k distinct primes for the points for ps in subsets(primes.irange(2, m), size=k): # calculate the total number of points scored t = sum(ps) # number of drawn and won/lost matches d = 3 * n - t w = n - d if d < 0 or w < 0 or d > n or w > n: continue # make the initial table table = list() for i in irange(k): row = [' '] * k row[i] = '-' table.append(row) # given data (D (= 3) lost to F (= 5)) for (r, c, v) in [(3, 5, 'l')]: table[r][c] = v table[c][r] = swap[v] # complete the table for the list of points for t in complete(k, table, ps[::-1]): # output the table printf("[{k} teams, {n} matches ({d} drawn, {w} won/lost)]") ts = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[:k] printf(" {ts}", ts=join(ts, sep=' ')) for (n, r) in zip(ts, t): p = sum(points.get(x, 0) for x in r) printf("{n}: {r} -> {p:2d} pts", r=join(r, sep=' ')) printf()Solution: Elgin’s results were: L L L L W D W.
The complete table looks like this:
LikeLike
Frits 11:48 am on 25 November 2020 Permalink |
from itertools import product P = [2, 3, 5, 7] P += [x for x in range(11, 100, 2) if all(x % p for p in P)] P += [x for x in range(101, 104, 2) if all(x % p for p in P)] SCORES = [0, 1, 3] LDW = "LD-W" LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" # determine the outcome of 0.5 * n * (n - 1) games def solve(n, i, pzl): if i < 0: yield pzl # determine number of unknown values cnt = sum(pzl[i][j] == -1 for j in range(n)) for p in product(SCORES, repeat=cnt): save = list(pzl[i]) x = 0 for j in range(n): if pzl[i][j] == -1: pzl[i][j] = p[x] pzl[j][i] = (1 if p[x] == 1 else abs(p[x] - 3)) x += 1 if sum(pzl[i]) == P[n - i - 1]: # correct total yield from solve(n, i - 1, pzl) # solve next team pzl[i] = save # backtrack # generate cumulative sum list of primes cumsum = [sum(P[:i+1]) for i in range(len(P))] nlist = [] # primes for teams must be minimal (2,3,5 ..) as otherwise the highest prime # exceeds the maximum score (n * 3) # # Dunfermline lost to Forfar so Forfar must have at least 3 points # and this can't happen in a league with 6 teams (6th team has 2 points) # so n > 6 print("teams games draws points max high reject reason") for n in range(7, 27): games = int(0.5 * n * (n - 1)) reason = "" if (n-1) * 3 - 1 == P[n-1]: reason = "high = max - 1" if (n-1) * 3 < P[n-1]: reason = "high > max" print(f"{n:<6} {games:<6} {games * 3 - cumsum[n-1]:<6} {cumsum[n-1]:<6} " f"{(n-1) * 3:<6} {P[n-1]:<6} {reason}") if reason == "": nlist.append(n) # solve and print table for n in nlist: # create matrix pzl = [[-1 for i in range(n)] for j in range(n)] pzl[3][5] = 0 # Dunfermline lost to Forfar pzl[5][3] = 3 # Forfor won from Dunfermline for i in range(n): pzl[i][i] = 0 # don't calculate x against x # solve which games have been played sol = solve(n, n-1, pzl) # print table print(f"\nnumber of teams: {n} \n") for s in sol: print(" " + " ".join(list(LETTERS[:n]))) # column header for i in range(len(s)): r = " " + " ".join(str(x) if k != i else "-" for k, x in enumerate(s[i])) print(LETTERS[:n][i], r) # row qualifier print("\nElgin's results:", " ".join([LDW[x] for k, x in enumerate(s[4]) if k != 4])) # teams games draws points max high reject reason # 7 21 5 58 18 17 high = max - 1 # 8 28 7 77 21 19 # 9 36 8 100 24 23 high = max - 1 # 10 45 6 129 27 29 high > max # 11 55 5 160 30 31 high > max # 12 66 1 197 33 37 high > max # 13 78 -4 238 36 41 high > max # 14 91 -8 281 39 43 high > max # 15 105 -13 328 42 47 high > max # 16 120 -21 381 45 53 high > max # 17 136 -32 440 48 59 high > max # 18 153 -42 501 51 61 high > max # 19 171 -55 568 54 67 high > max # 20 190 -69 639 57 71 high > max # 21 210 -82 712 60 73 high > max # 22 231 -98 791 63 79 high > max # 23 253 -115 874 66 83 high > max # 24 276 -135 963 69 89 high > max # 25 300 -160 1060 72 97 high > max # 26 325 -186 1161 75 101 high > max # # number of teams: 8 # # A B C D E F G H # A - 1 3 3 3 3 3 3 # B 1 - 3 1 3 3 3 3 # C 0 0 - 1 3 3 3 3 # D 0 1 1 - 3 0 3 3 # E 0 0 0 0 - 3 1 3 # F 0 0 0 3 0 - 1 1 # G 0 0 0 0 1 1 - 1 # H 0 0 0 0 0 1 1 - # # Elgin's results: L L L L W D WLikeLike