# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1522: Real in the lead

From New Scientist #2684, 29th November 2008 [link]

In the group stage of the European Champions League each of the four teams plays each of the others in both home and away matches, gaining 3 points for a win and 1 point for a draw. Each team has already played five matches. In one group Real is currently in first position, Sporting second, Twente third and United fourth, and these positions will remain unchanged after the final week’s matches, since each of the last three teams will still have fewer points than the team above even if it wins its final match.

If I told you who beat whom in one of the matches already played you could deduce with certainty all the other matches that have been played and their results.

Who beat whom in that match, and how many points does each of these two teams currently have?

[enigma1522]

### 2 responses to “Enigma 1522: Real in the lead”

1. Jim Randell 13 August 2012 at 6:59 am

Here’s a Python program that runs in 63ms. Algorithmically it’s based on my original Perl program.

```from collections import defaultdict
from itertools import product
from enigma import sprintf, printf

# each team plays two matches against the other three teams
# so there are 6 pairs of opponents: RS RT RU ST SU TU
# each team has played 5 of their 6 matches
# so for each pair there are the following possibilites

# team1 vs. team2
games = ('w', 'd', 'l', 'ww', 'wd', 'wl', 'dd', 'dl', 'll')

# points for team1 and team2
p1 = dict(zip(games, (3, 1, 0, 6, 4, 3, 2, 1, 0)))
p2 = dict(zip(games, (0, 1, 3, 0, 1, 3, 2, 4, 6)))

# output format
fmt = "R={R} S={S} T={T} U={U} / RS={RS} RT={RT} RU={RU} ST={ST} SU={SU} TU={TU}"
# get a handle on the variables in our scope, it'll come in handy later
v = vars()

# accumulate overall outcomes by individual matches
match = defaultdict(list)

# choose three outcomes for R's opponents
for (RS, RT, RU) in product(games, repeat=3):
if len(RS + RT + RU) != 5: continue # there must be 5 games
R = p1[RS] + p1[RT] + p1[RU] # points for R

# outcomes for S's remaining opponents
for (ST, SU) in product(games, repeat=2):
if len(RS + ST + SU) != 5: continue # must be 5 games
S = p2[RS] + p1[ST] + p1[SU] # points for S
if not(R > S and R - S > 3): continue # R leads S by >3 points

# outcomes for T's remaining opponent
for TU in games:
if len(RT + ST + TU) != 5: continue # must be 5 games
T = p2[RT] + p2[ST] + p1[TU] # points for T
if not(S > T and S - T > 3): continue # T leads S by >3 points

# outcomes for U
if len(RU + SU + TU) != 5: continue # must be 5 games
U = p2[RU] + p2[SU] + p2[TU] # points for U
if not(T > U and T - U > 3): continue # U leads T by >3 points

# record the overall outcomes by individual matches
s = sprintf(fmt)
for p in ('RS', 'RT', 'RU', 'ST', 'SU', 'TU'):
for g in v[p]:
match[(p, g)].append(s)

for ((p, g), v) in match.items():
if len(v) != 1: continue # result must be unique
if g == 'd': continue # we don't want draws
printf("{p}:{g} [{v[0]}]")
```

Solution: Twente beat Sporting. Sporting has 9 points. Twente has 5 points.

• Jim Randell 20 August 2012 at 8:06 am

Here’s my original Perl program. It runs in 324ms, although moving the rejection tests as early as possible (as I did in the Python code) brings this down to 43ms.

```use strict;

# there are six ways of combining the teams, each happens twice
my (\$RS, \$RT, \$RU, \$ST, \$SU, \$TU);

# possible scores
my @SCORES = (
# [ <matches played>, <points for>, <points against>, <label> ]
[ 2, 6, 0, 'ww' ],
[ 2, 4, 1, 'wd' ],
[ 2, 3, 3, 'wl' ],
[ 2, 2, 2, 'dd' ],
[ 2, 1, 4, 'dl' ],
[ 2, 0, 6, 'll' ],
[ 1, 3, 0, 'w' ],
[ 1, 1, 1, 'd' ],
[ 1, 0, 3, 'l' ],
);

my (\$R, \$S, \$T, \$U);

my %MATCH = ();
my \$x;

for \$RS (@SCORES) {
for \$RT (@SCORES) {
for \$RU (@SCORES) {
for \$ST (@SCORES) {
for \$SU (@SCORES) {
for \$TU (@SCORES) {
# each team has played 5 matches
next unless \$RS->[0] + \$RT->[0] + \$RU->[0] == 5;
next unless \$RS->[0] + \$ST->[0] + \$SU->[0] == 5;
next unless \$RT->[0] + \$ST->[0] + \$TU->[0] == 5;
next unless \$RU->[0] + \$ST->[0] + \$TU->[0] == 5;

\$R = \$RS->[1] + \$RT->[1] + \$RU->[1];
\$S = \$RS->[2] + \$ST->[1] + \$SU->[1];
next unless \$R > \$S and \$R - \$S > 3;
\$T = \$RT->[2] + \$ST->[2] + \$TU->[1];
next unless \$S > \$T and \$S - \$T > 3;
\$U = \$RU->[2] + \$SU->[2] + \$TU->[2];
next unless \$T > \$U and \$T - \$U > 3;

# one result should be a unique
\$x = "RS=\$RS->[3] RT=\$RT->[3] RU=\$RU->[3] ST=\$ST->[3] SU=\$SU->[3] TU=\$TU->[3] R=\$R S=\$S T=\$T U=\$U";
map { push @{\$MATCH{'RS' . \$_}}, \$x } split '', \$RS->[3];
map { push @{\$MATCH{'RT' . \$_}}, \$x } split '', \$RT->[3];
map { push @{\$MATCH{'RU' . \$_}}, \$x } split '', \$RU->[3];
map { push @{\$MATCH{'ST' . \$_}}, \$x } split '', \$ST->[3];
map { push @{\$MATCH{'SU' . \$_}}, \$x } split '', \$SU->[3];
map { push @{\$MATCH{'TU' . \$_}}, \$x } split '', \$TU->[3];
print "[\$x]\n";
}
}
}
}
}
}

my (\$k, \$v);
while ((\$k, \$v) = each %MATCH) {
next unless @{\$v} == 1;
next if \$k =~ /d\$/; # don't want draws
print "\$k \$v->[0]\n";
}
```