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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: