Enigmatic Code

Programming Enigma Puzzles

Enigma 530: Sudden death

From New Scientist #1682, 16th September 1989 [link]

There were eight players in the Greenchester Knock-Out Golf Championship. Unfortunately, due to rain, the whole competition had to be played on Saturday afternoon, and so it was decided to play the four first-round matches, the two semifinals and the final as sudden-death matches.

Thus in each match the two players played one hole and, if the scores were different, then the lower was the winner of that match. If the scores were equal then the played another hole with the same procedure applying, and so on, until the winner of that match was found.

After the competition the organiser listed each player’s scores for the holes (s)he had played, in order. Unfortunately he did not indicate the number of holes played in each round, but ran the scores together in a single list, as follows:

Anne: 3,3
Bern: 4,2,3,4
Chris: 4,2,3,3,3,3,3,3,2
Donald: 3,2,3,3,3
Eric: 4
Frances: 4,2,3,3,4
Grace: 3,2,3,4
Harriet: 4,2,3,3,2,4

Who beat whom in the semifinals?

[enigma530]

One response to “Enigma 530: Sudden death

  1. Jim Randell 16 December 2019 at 8:29 am

    This Python 3 program runs in 84ms.

    Run: [ @repl.it ]

    from enigma import partitions, join, printf
    
    # play the pairs off against each other
    # return a new map with the remaining scores
    def play(d, ps):
      d2 = dict()
      for (X, Y) in ps:
        # play X vs Y
        for (i, (x, y)) in enumerate(zip(d[X], d[Y]), start=1):
          if x < y:
            # win for X: Y is knocked out
            if i != len(d[Y]): return
            d2[X] = d[X][i:]
            break
          elif y < x:
            # win for Y: X is knocked out
            if i != len(d[X]): return
            d2[Y] = d[Y][i:]
            break
          # else move on to the next hole
        else:
          # ran out of holes with no winner
          return
      return d2
    
    # find possible tournaments
    def solve(d, s=[]):
      # have we got to the final?
      ks = list(d.keys())
      if len(ks) == 1:
        w = ks[0]
        if len(d[w]) == 0:
          yield (w, s)
      else:
        # choose the pairs to play
        for ps in partitions(ks, 2):
          d2 = play(d, ps)
          if d2 is None: continue
          yield from solve(d2, s + [ps])
    
    # the scores for each player
    d = dict(
      A=(3, 3),
      B=(4, 2, 3, 4),
      C=(4, 2, 3, 3, 3, 3, 3, 3, 2),
      D=(3, 2, 3, 3, 3),
      E=(4,),
      F=(4, 2, 3, 3, 4),
      G=(3, 2, 3, 4),
      H=(4, 2, 3, 3, 2, 4),
    )
    
    # format a tournament ("AvB CvD ... / ... / XvY")
    fmt = lambda s: join((join((x + "v" + y for (x, y) in r), sep=" ") for r in s), sep=" / ")
    
    # solve the puzzle
    for (w, s) in solve(d):
      printf("winner={w} [{s}]", s=fmt(s))
    

    Solution: In the semifinals Chris beat Grace and Donald beat Harriet.

    And in the final Chris beat Donald.

    There are two possible arrangements for the tournament:

    Q: A (3, 3) vs G (3, 2); B (4, 2, 3, 4) vs C (4, 2, 3, 3); D (3) vs E (4); F (4, 2, 3, 3, 4) vs H (4, 2, 3, 3, 2)
    S: C (3, 3) vs G (3, 4); D (2) vs H (4)
    F: C (3, 3, 2) vs D (3, 3, 3)

    Q: A (3, 3) vs G (3, 2); C (4, 2, 3, 3, 3) vs F (4, 2, 3, 3, 4); D (3) vs E (4); B (4, 2, 3, 4) vs H (4, 2, 3, 3)
    S: C (3, 3) vs G (3, 4); D (2, 3) vs H (2, 4)
    F: C (3, 2) vs D (3, 3)

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: