Sunday Times Teaser 3192 – In Formation Technology

by BRG on November 24, 2023

by Colin Vout

Published Friday November 24 2023 (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 (eg, 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?

From → Uncategorized

7 Comments Leave one →

BRG permalink


# partition the integer <n> into <m> unordered positive parts
def partition(m, n, seq=()):
  if not m:
    if not n:
      yield seq
  else:
    for i in range(1, min(n, 4) + 1):
      yield from partition(m - 1, n - i, seq + (i, ))

# the possible arrangements of four lines  
games = set(partition(4, 10))

# find legal moves for each arrangement
t12 = [(1, 2), (2, 3), (1, 0), (2, 1)]
moves = dict()
for g in games:
  mvs = set()
  # the index of the line the two players are from
  for f, n in enumerate(g):
    # the line cannot be left empty
    if n > 2:
      t1, t2 = t12[f]
      # a maximumm  of four players per line
      if g[t1] < 4 and g[t2] < 4:
        ns = list(g)
        ns[f], ns[t1], ns[t2] = n - 2, g[t1] + 1, g[t2] + 1
        mvs.add(tuple(ns))
  moves[g] = mvs

# generate maximum length sequences using transitions
# that do not lead to repeated positions  
def paths(moves, seq):
  yield seq
  for np in moves[seq[-1]]:
    if np not in seq:
      yield from paths(moves, seq + [np])

# collect all possible sequences ordered on their length
seqs = sorted((p for ig in games for p in paths(moves, [ig])), key=len)
max_seqs = list(s for s in seqs if len(s) == len(seqs[-1]))

# consider all maximum length sequences ...
for seq in max_seqs:
  # ... that include the given worst result
  if (3, 1, 3, 3) not in seq:
    continue
  # count the number of times each number occurs in
  # the first line across all games in the season
  cnts = [0] * 5
  for g in seq:
    cnts[g[0]] += 1
  # 3 occurs more often than any other number
  if cnts.count(t := max(cnts)) == 1 and cnts.index(t) == 3:
    t = ' -> '.join('-'.join(str(n) for n in g) for g in seq[:3]) 
    print(f"{len(seq)} games: {t} ...")

# partition the integer <n> into <m> unordered positive parts

def partition(m, n, seq=()):

if not m:

if not n:

yield seq

else:

for i in range(1, min(n, 4) + 1):

yield from partition(m - 1, n - i, seq + (i, ))

# the possible arrangements of four lines

games = set(partition(4, 10))

# find legal moves for each arrangement

t12 = [(1, 2), (2, 3), (1, 0), (2, 1)]

moves = dict()

for g in games:

mvs = set()

# the index of the line the two players are from

for f, n in enumerate(g):

# the line cannot be left empty

if n > 2:

t1, t2 = t12[f]

# a maximumm of four players per line

if g[t1] < 4 and g[t2] < 4:

ns = list(g)

ns[f], ns[t1], ns[t2] = n - 2, g[t1] + 1, g[t2] + 1

mvs.add(tuple(ns))

moves[g] = mvs

# generate maximum length sequences using transitions

# that do not lead to repeated positions

def paths(moves, seq):

yield seq

for np in moves[seq[-1]]:

if np not in seq:

yield from paths(moves, seq + [np])

# collect all possible sequences ordered on their length

seqs = sorted((p for ig in games for p in paths(moves, [ig])), key=len)

max_seqs = list(s for s in seqs if len(s) == len(seqs[-1]))

# consider all maximum length sequences ...

for seq in max_seqs:

# ... that include the given worst result

if (3, 1, 3, 3) not in seq:

continue

# count the number of times each number occurs in

# the first line across all games in the season

cnts = [0] * 5

for g in seq:

cnts[g[0]] += 1

# 3 occurs more often than any other number

if cnts.count(t := max(cnts)) == 1 and cnts.index(t) == 3:

t = ' -> '.join('-'.join(str(n) for n in g) for g in seq[:3])

print(f"{len(seq)} games: {t} ...")

JohnZ permalink

Somewhat short on comments, primitive printout, but it works.


from itertools import product

# recursively go to next possible group of 4 lines
def chain(cumul):
  for k in links[cumul[-1]]:
    if k not in cumul: # stop if loop encountered
      yield from chain(cumul + (k,))
  yield cumul

# generate all possible line-ups
lines = tuple(x for x in product(range(1, 5), repeat = 4) if sum(x) == 10)

# dictionary of link from one line-up to the next
links = dict()

for L in lines:
  links[L] = []
  if L[0] > 2 and L[1] < 4 and L[2] < 4:
    links[L] += [(L[0] - 2, L[1] + 1, L[2] + 1, L[3])]
  
  if L[1] > 2 and L[2] < 4 and L[3] < 4:
    links[L] += [(L[0], L[1] - 2, L[2] + 1, L[3] + 1)]
    
  if L[2] > 2 and L[0] < 4 and L[1] < 4:
    links[L] += [(L[0] + 1, L[1] + 1, L[2] - 2, L[3])]

  if L[3] > 2 and L[1] != 4 and L[2] != 4:
    links[L] += [(L[0], L[1] + 1, L[2] + 1, L[3] - 2)]

# generate and sort season line-ups by number of line-ups (games)
seasons = sorted({x for L in lines for x  in chain((L,))},
                  key = lambda x : len(x), reverse = True)

maxl = len(seasons[0]) # max number of games played
for i in seasons:
  if len(i) == maxl:
    if (3, 1, 3, 3) in i:
      fcount = [0] * 5
      for j in i:
        fcount[j[0]] += 1
      if fcount[3] == max(fcount) and fcount.count(fcount[3]) == 1:
        print (maxl, 'games:', *i[::]) # change :: to :3 for first three games
  else: # less than max number of games
    break

from itertools import product

# recursively go to next possible group of 4 lines

def chain(cumul):

for k in links[cumul[-1]]:

if k not in cumul: # stop if loop encountered

yield from chain(cumul + (k,))

yield cumul

# generate all possible line-ups

lines = tuple(x for x in product(range(1, 5), repeat = 4) if sum(x) == 10)

# dictionary of link from one line-up to the next

links = dict()

for L in lines:

links[L] = []

if L[0] > 2 and L[1] < 4 and L[2] < 4:

links[L] += [(L[0] - 2, L[1] + 1, L[2] + 1, L[3])]

if L[1] > 2 and L[2] < 4 and L[3] < 4:

links[L] += [(L[0], L[1] - 2, L[2] + 1, L[3] + 1)]

if L[2] > 2 and L[0] < 4 and L[1] < 4:

links[L] += [(L[0] + 1, L[1] + 1, L[2] - 2, L[3])]

if L[3] > 2 and L[1] != 4 and L[2] != 4:

links[L] += [(L[0], L[1] + 1, L[2] + 1, L[3] - 2)]

# generate and sort season line-ups by number of line-ups (games)

seasons = sorted({x for L in lines for x in chain((L,))},

key = lambda x : len(x), reverse = True)

maxl = len(seasons[0]) # max number of games played

for i in seasons:

if len(i) == maxl:

if (3, 1, 3, 3) in i:

fcount = [0] * 5

for j in i:

fcount[j[0]] += 1

if fcount[3] == max(fcount) and fcount.count(fcount[3]) == 1:

print (maxl, 'games:', *i[::]) # change :: to :3 for first three games

else: # less than max number of games

break

John Z permalink

The recursive functon, ‘chain’, above generates a lot of ‘chaff’. The ‘seasons’ list has 1752 entries. As an analogy, let’s say it yielded (1, 2, 3, 4, 5). It would follow that up with:
(1, 2, 3, 4)
(1, 2, 3)
(1, 2)
(1)

By adding a few additional lines the function is more efficient, generating a ‘seasons’ list with only 843 entries. But it’s much less elegant:


# recursively go to next possible group of 4 lines
def chain(cumul):
  if len(cumul) > 1 and (cumul[-1] in cumul[:-1]): # stop loop
    yield cumul[:-1]
    
  elif links[cumul[-1]] == []: # dead end
    yield cumul
             
  else:
    for k in links[cumul[-1]]:
      yield from chain(cumul + (k,))

# recursively go to next possible group of 4 lines

def chain(cumul):

if len(cumul) > 1 and (cumul[-1] in cumul[:-1]): # stop loop

yield cumul[:-1]

elif links[cumul[-1]] == []: # dead end

yield cumul

else:

for k in links[cumul[-1]]:

yield from chain(cumul + (k,))

John Z permalink

Definitive version


from itertools import product

# recursively go to next possible group of 4 lines
def chain(cumul):
  for k in links[cumul[-1]]:
    if k not in cumul: # stop if loop encountered
      yield from chain(cumul + (k,))
  yield cumul

# generate all possible line-ups
lines = tuple(x for x in product(range(1, 5), repeat = 4) if sum(x) == 10)

# dictionary of links from one line-up to the next
links = dict()

for L in lines:
  links[L] = []

  # consider all possible line-up changes
  for c in ((-2, 1, 1, 0), (0, -2, 1, 1), (1, 1, -2, 0), (0, 1, 1, -2)):
    nl = tuple(L[j] + c[j] for j in range(4))
    
    # are all prospective new lines in a range from 1 through 4
    if all(1 <= x <= 4 for x in nl):

      # add new transition
      links[L] += [nl]

# generate and sort season line-ups by number of line-ups (games)
seasons = sorted((x for L in lines for x in chain((L,))),
                  key = lambda x : len(x), reverse = True)

maxg = len(seasons[0]) # max number of games played
for i in seasons:
  if len(i) == maxg and (3, 1, 3, 3) in i:

    # number of times the digits 1 -> 4 appear first
    fnum = [0] * 5
    for j in i:
      fnum[j[0]] += 1
      
    # was first number in formations more often 3 than any other number?
    if fnum[3] == max(fnum) and fnum.count(fnum[3]) == 1:
      print (maxg, 'games:', *i[::]) # change :: to :3 for first three games

from itertools import product

# recursively go to next possible group of 4 lines

def chain(cumul):

for k in links[cumul[-1]]:

if k not in cumul: # stop if loop encountered

yield from chain(cumul + (k,))

yield cumul

# generate all possible line-ups

lines = tuple(x for x in product(range(1, 5), repeat = 4) if sum(x) == 10)

# dictionary of links from one line-up to the next

links = dict()

for L in lines:

links[L] = []

# consider all possible line-up changes

for c in ((-2, 1, 1, 0), (0, -2, 1, 1), (1, 1, -2, 0), (0, 1, 1, -2)):

nl = tuple(L[j] + c[j] for j in range(4))

# are all prospective new lines in a range from 1 through 4

if all(1 <= x <= 4 for x in nl):

# add new transition

links[L] += [nl]

# generate and sort season line-ups by number of line-ups (games)

seasons = sorted((x for L in lines for x in chain((L,))),

key = lambda x : len(x), reverse = True)

maxg = len(seasons[0]) # max number of games played

for i in seasons:

if len(i) == maxg and (3, 1, 3, 3) in i:

# number of times the digits 1 -> 4 appear first

fnum = [0] * 5

for j in i:

fnum[j[0]] += 1

# was first number in formations more often 3 than any other number?

if fnum[3] == max(fnum) and fnum.count(fnum[3]) == 1:

print (maxg, 'games:', *i[::]) # change :: to :3 for first three games

John Z permalink

lines 39, 40, 41 which count what “The first number in our formations was” can be replaced by:

Python

fnum = tuple(tuple(j[0] for j in i).count(k) for k in range(5))

1
2
3

fnum = tuple(tuple(j[0] for j in i).count(k) for k in range(5))

squeezing the code down a bit further.

Reply
- John Z permalink
  
  or similarly:
  
  Python
  
  fnum = [list(zip(*i))[0].count(k) for k in range(5)]
  
  1
  2
  3
  
  fnum = [list(zip(*i))[0].count(k) for k in range(5)]
  
  Reply
  - John Z permalink
    
    Yes, it reduces the line count and looks elegant but is computationally inefficient as the ‘zip’ is executed in every iteration of the ‘for’ loop, in this case five times.
    A more efficient alternative is:
    
    Python
    
    fd = tuple(zip(*i))[0] fnum = [fd.count(k) for k in range(5)]
    
    1
    2
    3
    4
    
    fd = tuple(zip(*i))[0]
    fnum = [fd.count(k) for k in range(5)]
    
    Reply

Sunday Times Teaser 3192 – In Formation Technology

by Colin Vout

Published Friday November 24 2023 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta