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]

Advertisements

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";
      }
      

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: