Enigmatic Code

Programming Enigma Puzzles

Puzzle 52: Football on the Island of Imperfection

From New Scientist #1103, 18th May 1978 [link]

There has been a great craze for football recently on the Island of Imperfection and I have been fortunate enough to get some details of games played there.

There are three tribes on the Island — the Pukkas, who always tell the truth; the Wotta-Woppas, who never tell the truth; and the Shilli-Shallas, who make statements which are alternately true and false, or false and true.

Three teams, one from each tribe, have been having a competition, in which eventually they will play each other [once] — or perhaps they have already done this. The secretaries of the three teams have been asked to give details of the number of matches played, won, lost and drawn and they do this in accordance with the rules of their tribe — so that, for example, all the figures given by the secretary of the Wotta-Woppa team will be wrong.

The figures given are as follows (calling the teams AB and C in no particular order):

(In no instance did a team win by a majority of more than three goals).

Find the tribe to which each of the three teams belong, and the score in each match.

[puzzle52]

One response to “Puzzle 52: Football on the Island of Imperfection”

1. Jim Randell 21 March 2018 at 6:52 am

The following Python code runs in 102ms.

Run: [ @repl.it ]

```from itertools import permutations, product
from enigma import Football, irange, printf

# match values according to the tribes

# Pukka - all values match
def P(s, t):
return all(a == b for (a, b) in zip(s, t))

# Wotta Woppa - no values match
def W(s, t):
return all(a != b for (a, b) in zip(s, t))

# Shilli-Shalla - alternating matches/non-matching
def S(s, t):
(s0, s1) = (s[0::2], s[1::2])
(t0, t1) = (t[0::2], t[1::2])
return (P(s0, t0) and W(s1, t1)) or (W(s0, t0) and P(s1, t1))

# generate selections from a bunch of iterators
def iproduct(ss):
# initial lists of values
vs = tuple([] for _ in ss)
js = list(j for (j, _) in enumerate(ss))
ss = tuple(iter(s) for s in ss)
while js:
js2 = list(js)
# go through the lists of values
for j in js:
# add a new value to the list
try:
x = next(ss[j])
except StopIteration:
js2.remove(j)
continue
vs[j].append(x)
# generate selections using this value
yield from product(*((v[-1:] if i == j else v) for (i, v) in enumerate(vs)))
js = js2

# generators for possible (X, Y) scores in various types of matches X v Y
# subject to no team winnong by more than 3 goals

# unplayed matches
def scores_x():
yield None

# win for X against Y
def scores_w():
x = 1
while True:
for y in irange(0, x - 1):
if x - y > 3: continue
yield (x, y)
x += 1

# draw
def scores_d():
x = 0
while True:
yield (x, x)
x += 1

# win for Y against X
def scores_l():
for (x, y) in scores_w():
yield (y, x)

# generators for each type of match
scores = dict(x=scores_x, w=scores_w, d=scores_d, l=scores_l)

# find solutions for a specified 3 team table
def solve(table):
football = Football(games="wdlx")

# consider possible games outcomes
for (AB, AC, BC) in football.games(repeat=3):

# make the table
A = football.table([AB, AC], [0, 0])
B = football.table([AB, BC], [1, 0])
C = football.table([AC, BC], [1, 1])

# collect (played, w, l, d)
rows1 = tuple((t.played, t.w, t.l, t.d) for t in (A, B, C))

# choose an assignment of tribes to rows
for fns in permutations((P, W, S)):

# check the partial rows match the tribes
if not all(fn(r, t[:4]) for (fn, r, t) in zip(fns, rows1, table)): continue

# find the scores in each match (using the goals for/against values given)
for (sAB, sAC, sBC) in iproduct(list(scores[m]() for m in (AB, AC, BC))):

# compute goals for, goals against for each team
gA = football.goals([sAB, sAC], [0, 0])
gB = football.goals([sAB, sBC], [1, 0])
gC = football.goals([sAC, sBC], [1, 1])

# add in the "goals for", "goals against" columns
rows2 = tuple(r + x for (r, x) in zip(rows1, (gA, gB, gC)))

# and check the complete rows still match
if not all(fn(r, t) for (fn, r, t) in zip(fns, rows2, table)): continue

# return a solution (tribe functions, match outcomes, match scores)
yield (fns, (AB, AC, BC), (sAB, sAC, sBC))

# the table given (played, w, l, d, goals for, goals against)
table = (
(2, 1, 0, 1, 3, 2),
(1, 2, 2, 0, 4, 3),
(2, 2, 2, 1, 0, 2),
)

# solve the problem
for (fns, (AB, AC, BC), (sAB, sAC, sBC)) in solve(table):
# output solution
(tA, tB, tC) = (fn.__name__ for fn in fns)
printf("tribes: A={tA}, B={tB}, C={tC}")
printf("A vs B = ({AB}) {sAB[0]}-{sAB[1]}")
printf("A vs C = ({AC}) {sAC[0]}-{sAC[1]}")
printf("B vs C = ({BC}) {sBC[0]}-{sBC[1]}")
printf()
break # we only want the first solution
```

Solution: A are Pukkas, B are Wotta-Woppas, C are Shilli-Shallas. The scores in the matches are: A vs B = 2-2, A vs C = 1-0, B vs C = 3-0.

The `iproduct()` function takes a (bounded) sequence of (potentially unbounded) iterators and generates tuples corresponding to the Cartesian product of the tuples, every tuple would eventually appear, but if some of the iterables are unbounded the function will never finish (and will eventually run out of memory). The standard `itertools.product()` function does not operate on unbounded iterators.

The program stops after it finds the first solution, and in fact this is the only possible solution.

This site uses Akismet to reduce spam. Learn how your comment data is processed.