Teaser 3146: Curling league [revised]
From The Sunday Times, 8th January 2023 [link] [link]
The number of teams in our curling league is more than 4, but less than 26. In a tournament each team plays each of the other teams once, and the teams are ranked according to the number of wins they achieve (draws are impossible). If any teams are tied on wins, ranking is only possible if those teams have different numbers of wins in their mutual games. For example, in a three-way tie if A beats B, B beats C and A beats C, the ranking is ABC, but if C beats A (or A has not yet played C), then ranking is impossible, as A and B have one win each.
At one point (when each team had played G games), ranking the teams as above was possible. However, if each team had played G−1 games, a ranking would not have been possible, irrespective of results. With one more team in the league, the minimum number of games needed to allow a ranking would be G+2.
How many teams are in the league and what was the value of G?
This is a revised version of the puzzle posted as Teaser 3146. The underlined text has been changed from the published version, to be in line with the intention of the setter.
[teaser3146]
Frits are discussing. 
Brian Gladman are discussing. 
GeoffR, 
Hugh Casement, 
Robert Brown are discussing. 
John Crabtree and 
S2T2 
Jim Randell 9:41 am on 9 January 2023 Permalink |
I solved the previous version of this puzzle with a fairly straightforward search [link]. And it came up with a solution quickly, without having to explore the entire solution space. Which was handy because that would have taken a long time.
So I looked at making my program more efficient. By looking at the number of wins achieved by each team we find there are only certain patterns of wins that are viable. Limiting the search to these patterns of wins, and doing more checks to reject candidate solutions early I was able to come up with a (more complicated) program that explores the entire solution space in a reasonable time, and constructively finds a single solution to the puzzle.
(This program can also be used to find both solutions to the puzzle as originally worded).
The following Python program runs in 7.6s.
from enigma import ( irange, group, item, div, subsets, multiset, rev, diff, filter2, seq_all_different, cache, printf ) # labels for <n> teams; 1..n teams = lambda n: irange(1, n) # a match is represented by (<winning-team>, <losing-team>) # check a set of matches for <n> teams is orderable for teams <ts> def orderable(ms, ts): # extract the winners (ws, _) = zip(*ms) # and count the number of wins for each team w = dict((t, ws.count(t)) for t in ts) # group teams with the same number of wins together g = group(w.items(), by=item(1), f=item(0), fn=sorted) # look for tied groups for (_, xs) in g.items(): if len(xs) < 2: continue # collect the mutual games amongst the group ws_ = list(x for (x, y) in ms if x in xs and y in xs) # and check they are all different if not seq_all_different(ws_.count(t) for t in xs): return False # looks good return True # allocate played matches for <n> teams, <k> matches per team, <p> matches in total, # from unallocated matches <ps> def allocate(n, k, p, ps, ws, t=1, ss=[]): # are we done? if t > n: yield ss else: # allocated games involving team <t> xs = list(x for x in ss if t in x) r = k - len(xs) if r < 0: return nw = ws[0] # number of allocated wins xw = sum(x == t for (x, y) in xs) if xw > nw: return # consider unallocated games involving team <t> (ts, ps_) = filter2((lambda x: t in x), ps) # select the remaining matches for team <t> for rs in subsets(ts, size=r): for js in subsets(irange(r), size=nw - xw, fn=set): # construct the new set of matches ss_ = ss + list(((t, x + y - t) if j in js else (x + y - t, t)) for (j, (x, y)) in enumerate(rs)) # check wins/losses are still viable for the remaining teams xws = multiset.from_seq(x[0] for x in ss_) xls = multiset.from_seq(x[1] for x in ss_) if any(xws.count(j) > w or xls.count(j) > k - w for (j, w) in zip(irange(t, n), ws)): continue # and check it is orderable for teams up to t if orderable(ss_, teams(t)): yield from allocate(n, k, p - r, ps_, ws[1:], t + 1, ss_) # decompose total played matches <p> into wins for <n> teams, each played <k> matches def decompose(p, n, k, w=0, ws=[]): if len(ws) == n: if p == 0: yield rev(ws) elif not (w > k): # choose number of teams with <w> wins for m in irange(min(w, k - w) + 1, 0, step=-1): if len(ws) + m > n or m * w > p: continue yield from decompose(p - m * w, n, k, w + 1, ws + [w] * m) # find orderable sets of wins for <n> teams, each having played <k> matches def wins(n, k): # calculate the number of played matches p = div(n * k, 2) if p is None: return # construct the possible matches ps = list(subsets(teams(n), size=2)) # construct possible wins for ws in decompose(p, n, k): # we can allocate matches between teams with the same number of wins g = group(enumerate(ws, start=1), by=item(1), f=item(0), fn=sorted) ss = list() for (_, vs) in g.items(): if len(vs) > 1: ss.extend(subsets(vs, size=2)) if len(ss) > p: continue # allocate the remaining matches yield from allocate(n, k, p - len(ss), diff(ps, ss), ws, 1, ss) @cache # check if <n> teams, each played <k> games is orderable def check(n, k): if not (n > k > 0): return None for r in wins(n, k): printf("[n={n} k={k} -> {r}]", r=sorted(r)) return True printf("[n={n} k={k} -> None]") return False # solve the puzzle def solve(start, stop): # n = number of teams in the league for n in irange(start + 1, stop + 1): # k = number of matches played by each team # look for minimum k that is orderable for k in irange(1, n - 1): # can we find an orderable set of wins? r = check(n, k) # find the smallest k that gives an orderable set if r: printf("-> n={n}: min_k = {k}") (T, G) = (n - 1, k - 2) # look to see if (T, G) is possible and (T, G - 1) is not possible if check(T, G) is True and check(T, G - 1) is False: # output solution printf("=> T = {T}; G = {G}") printf("##### SOLUTION FOUND -> league has {T} teams; games played = {G} #####") yield (T, G) break printf() # output solution summary for (T, G) in list(solve(5, 25)): printf("=> SOLUTION: league has {T} teams; games played = {G}")Solution: There are 16 teams in the league. G = 6.
For example, with teams A – P, each can play 6 games, and be orderable as follows:
And it is not possible for 16 teams to have each played 5 games and be orderable.
But it is possible for 17 teams, A – Q, to have each played 8 games and be orderable:
but not for any number of games less than 8.
Here are some notes on the refinements I used to eliminate cases from testing compared with my original program, that allows it to run in a reasonable time over the entire solution space…
Firstly we don’t care what order the teams are in, so we can assume team 1 is 1st in the order, team 2 is 2nd, and so on.
For a league with n teams, each having played k matches there are p = (n × k /2) matches played in total (each match involves 2 teams), so we can allocate these p wins among the n teams in a non-decreasing sequence of [0..k] wins. With team 1 having the largest number of wins, down to team n having the least wins.
Then looking at groups of teams with the same number of wins, these groups must be ordered according to the matches played amongst the teams involved. If team X has 0 wins there cannot be another team Y with 0 wins, as we can only order them with an X vs. Y match, which neither team can be allowed to win. So there can be at most 1 team with 0 wins, at most 2 teams with 1 wins, etc.
And by considering losses we get the same pattern coming down. There can be at most 1 team with k wins, at most 2 teams with (k – 1) wins, and so on.
So, I generated viable patterns of wins and then allocated matches according to these patterns by working through the list of wins and allocating appropriate matches for each team.
When allocating the remaining matches for each team I check after each allocation that we haven’t allocated too many wins (or losses) to one of the later occurring teams, and also after we have allocated the matches for a team the matches for that team and all earlier teams are fixed, so the set of matches restricted to just these teams must already be orderable (as they are not going to change later).
Also, it soon became obvious that using [[
enigma.decompose()]] to generate all possible decompositions and discarding those that were unsuitable was not very efficient as n increased, so I wrote a specific [[decompose()]] routine to do this for me.Then I realised that if we have groups of teams with the same number of wins, and we know the order that we want them to appear in, then we can allocate the wins involved between those teams immediately, before we start the general allocation of the remaining matches.
Together all these improvements let the program run in 10s or less (running under PyPy 7.3.11). This was hugely faster than my initial program for the original puzzle, and let the program examine the entire solution space, and construct orderings where they were possible.
LikeLike
Frits 4:41 pm on 9 January 2023 Permalink |
Using a different solve() is a bit faster. Basically we start with making a list of orderable set of wins (first item only) by calling decompose().
Only changes made to the code is to return a tuple in decompose() and to suppress printing in the check routine.
The “not found” branche is not further developed as it seems that all decompose() output is orderable.
def solve(start, stop): F = dict() # n = number of teams in the league for n in range(start, stop): # k = number of matches played by each team for k in range(1, n): if n % 2 and k % 2: continue # get first orderable set of wins lst = list(first(decompose(n * k // 2, n, k))) if lst: print((n, k), "-->", lst[0]) if not check(n, k, p=0): print("not found") else: F[n] = k break # check dictionary of first orderable set of wins for n, k in F.items(): if n - 1 in F: if F[n - 1] == k - 2: printf("=> SOLUTION: league has {n - 1} teams; games played = {k - 2}") elif k > 3 and F[n - 1] < k - 2: if check(n - 1, k - 2, p=0) and not check(n - 1, k - 3, p=0): printf("=> SOLUTION: league has {n - 1} teams; games played = {k - 2}")LikeLike
Jim Randell 9:46 pm on 9 January 2023 Permalink |
@Frits: I think most of the speed increase you are seeing comes from not checking the full range for n. If the number of teams can be up to 25 then we need to check up to n = 26. Otherwise it seems to be doing pretty much the same thing as my program, but finding solutions at the end rather than as it goes along.
The values generated by [[
decompose()]] all give an orderable set of matches when the program is run normally, but this is not the case in general. While playing around I found [[check(10, 8)]] (for example) needed to look at multiple decompositions before an orderable set was found.LikeLike
Frits 11:21 pm on 9 January 2023 Permalink |
@Jim, you are right, with range(start, stop + 2) the performance gain is minimal.
A bit surprising, your program calls check() 135 times and mine only 23 times (but these are all time consuming).
LikeLike
Jim Randell 11:28 pm on 9 January 2023 Permalink |
The [[
check()]] function is cached (via the [[@cache]] decorator), so we get access to previously computed values without recalculating them.LikeLike
Frits 11:34 pm on 9 January 2023 Permalink |
Removing @cache most of the time slightly improves the run time!
LikeLike
Jim Randell 9:36 am on 27 January 2023 Permalink |
Here is a non-constructive solution, that uses the pattern of wins given in my notes above.
Thinking about leagues of n teams where each team has played k matches, then if we start with a value for k we see the smallest possible value that n can be is (k + 1).
And when we think about allocating the p = (n.k / 2) matches among the n teams, then there can only be 1 team with 0 wins or k wins, 2 teams with 1 win or (k − 1) wins, etc.
So, if k is even (say 2x) we get a pattern of the form:
And if k is odd (say 2x + 1) we get a pattern of the form:
So by considering increasing values of k we can find a range of potentially viable n values and build up a set of viable (n, k) values. Note that no (n, k) value where both n and k are odd is viable, as a corresponding p value cannot be calculated, but we assume that all remaining (n, k) value will allow a viable ordering to be constructed. (In my program above this assumption is not made, and we don’t accept an (n, k) until an orderable scenario has been constructed. Removing this requirement significantly reduces the amount of work required to find a solution, and is the approach used in the setters’ own solution).
Once an appropriate set of (n, k) values has been constructed we can look for scenarios that provide a solution to the puzzle.
We are looking for a number of teams T and number of games G such that:
The Python program performs this search. It runs in 57ms. (Internal runtime is 534µs).
Run: [ @replit ]
from enigma import (irange, divc, tri, div, peek, printf) # for a given k value generate possible range of n values def nrange(k): lo = k + 1 # count maximum possible wins = number of matches h = divc(k, 2) t = k * tri(h) if k % 2 == 0: t += h * (h + 1) hi = div(2 * t, k) return (lo, hi) def solve(start, stop): ss = list() # possible number of teams t = 1 # record possible (n, k) values R = set() # consider increasing k values for k in irange(1, stop + 1): (lo, hi) = nrange(k) # fill out possible (n, k) values in R for n in irange(lo, hi): if k % 2 == 0 or n % 2 == 0: R.add((n, k)) # check possible teams while t + 1 < lo: t += 1 # find min_k for t min_k = peek(k for k in irange(1, t - 1) if (t, k) in R) printf("t={t} -> min_k={min_k}") # look for solutions (T, G) = (t - 1, min_k - 2) if T < start or T > stop: continue if (T, G) in R and (T, G - 1) not in R: printf("=> T = {T}; G = {G}") printf("##### SOLUTION FOUND -> league has {T} teams; games played = {G}") ss.append((T, G)) # output solution summary if ss: printf() for (T, G) in ss: printf("=> SOLUTION: league has {T} teams; games played = {G}") # solve the puzzle solve(5, 25)LikeLike