Teaser 3192: In formation technology
From The Sunday Times, 26th November 2023 [link] [link]
Football formations are generally described by three or four nonzero whole numbers summing to 10 (the goalkeeper isn’t counted), representing, from defence to attack, the number of players in approximate lines across the pitch.
Last season we played a different formation every week, always using four lines, each with at most four players; the difference between one week and the next was that from one line two players moved, one to an adjacent line and the other to the line beyond that (e.g. 3-4-1-2 could only be followed by 3-2-2-3). Our number of fixtures was the largest it could have been, given these conditions. The first number in our formations was more often 3 than any other number; 3-1-3-3 gave us our worst result.
How many games did we play, and what were our first three formations?
[teaser3192]
Frits are discussing. 
GeoffR and 
Ender Aktulga are discussing. 
Hugo and 
S2T2 
Jim Randell 5:38 pm on 24 November 2023 Permalink |
This Python program runs in 68ms. (Internal runtime is 2.5ms).
Run: [ @replit ]
from enigma import (Accumulator, decompose, update, multiset, join, printf) # find possible formations fs = list(decompose(10, 4, increasing=0, sep=0, min_v=1, max_v=4)) # find possible transitions trans = dict() for s in fs: ts = set() # choose an index to donate 2 players for (i, n) in enumerate(s): if n < 3: continue # i -> j, k for d in [-1, +1]: j = i + d if j < 0 or j > 3 or s[j] > 3: continue k = j + d if k < 0 or k > 3 or s[k] > 3: continue ts.add(update(s, [(i, n - 2), (j, s[j] + 1), (k, s[k] + 1)])) trans[s] = ts # find paths in graph <adj> def paths(adj, ss): yield ss # try to extend the path s = ss[-1] for t in adj[s]: if t not in ss: yield from paths(adj, ss + [t]) # find maximal length paths r = Accumulator(fn=max, collect=1) for s in fs: for ss in paths(trans, [s]): r.accumulate_data(len(ss), ss) printf("max len = {r.value}") # consider maximal length paths for ss in r.data: # 3-1-3-3 must be present if (3, 1, 3, 3) not in ss: continue # 3 occurs most frequently as the first number m = multiset.from_seq(s[0] for s in ss) n3 = m.count(3) if not all(n3 > nk for (k, nk) in m.items() if k != 3): continue # output solution fmt = lambda x: join(x, sep='-') printf("{ss}", ss=join((fmt(x) for x in ss), sep=", ", enc="()"))Solution: There were 13 games. The first three formations were: 3-2-4-1, 4-3-2-1, 4-1-3-2.
The full list of formations is:
There are 4 weeks that begin with 3-, and 3 weeks that each start 1-, 2-, 4-.
LikeLike
Frits 5:05 pm on 1 December 2023 Permalink |
@Jim,
I noticed that you don’t see (among others ) 4-1-3-2 to 2-2-3-3 as a valid transition. I don’t consider “to the line beyond that” as the immediate adjacent line.
LikeLike
Jim Randell 5:12 pm on 1 December 2023 Permalink |
@Frits: Yes, it has to be adjacent (it is “the line beyond” not “a line beyond”). It would probably have been better expressed as “the next line beyond”.
I think there are many solutions to the puzzle where you allow transfers to non-adjacent lines. (I originally tried it with this interpretation).
And welcome back, it has been a while.
LikeLike