Enigmatic Code

Programming Enigma Puzzles

Enigma 886: Set square

From New Scientist #2041, 3rd August 1996 [link]

Last week I watched a thrilling five-set tennis match between the two top players, Pampas and Grassy. Pampas won the first set easily and the second in a tie-break. He then lost the next two sets and towards the end of the final set the scoreboard showing the games won looked like this:

Pampas then went on to win the next two games (and hence the match).

I remember on a previous occasion when they met the match also went to five sets. Towards the end of the match I looked at the scoreboard and each of the two rows of games won formed a five-figure perfect square. On that occasion Grassy then went on to win in two more games.

What did the score-board look like at the very end of that match?

[enigma886]

19 responses to “Enigma 886: Set square

  1. Jim Randell 23 July 2021 at 7:06 am

    This Python program generates possible final scores for the match, and then checks to see if the scoreboard would have shown two perfect squares before G won the final two games. It runs in 357ms.

    [Note: See below for an updated version of the code]

    Run: [ @replit ]

    from enigma import subsets, nconcat, is_square, update, printf
    
    # possible wins / tie-breaker in the final set
    wins = [(6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (7, 5), (7, 6)]
    final = [(6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (7, 5), (8, 6), (9, 7), (10, 8), (11, 9)]
    
    # choose scores for the first 4 sets
    for ss in subsets(wins, size=4, select="M", fn=list):
      if 0 in ss[0]: continue # no leading zeros
      ss.append(None) # slot for the final set
      # and invert two of them (P's wins)
      for (i, j) in subsets([0, 1, 2, 3], size=2):
        ss_ = update(ss, [i, j], [ss[i][::-1], ss[j][::-1]])
        # choose the final set
        for ss_[-1] in final:
          # collect digits for G and P
          (gds, pds) = map(tuple, zip(*ss_))
          # before G won the final 2 games, both give square numbers
          if not(is_square(nconcat(pds)) and is_square(nconcat(gds) - 2)): continue
          # output solution
          printf("P={pds}; G={gds}")
    

    Solution: Pampas = 7 2 3 6 1. Grassy = 5 6 6 4 6.

    So before Grassy won the final 2 games, the scoreboard showed:

    Pampas = 7 2 3 6 1 = 269²
    Grassy = 5 6 6 4 4 = 238²

    The program runs slightly faster with [[ is_square.cache_enabled = 1 ]].

    • Frits 23 July 2021 at 9:30 am

      @Jim, I think you have to expand “final” with (10, 8) and (11, 9) as fi. just before the end of the match it could have been 9 – 9 in the 5th set.

    • Jim Randell 23 July 2021 at 11:56 am

      An updated version of my code in light of the comments above. (The answer remains the same):

      from enigma import subsets, nconcat, is_square, update, printf
      
      # possible wins / tie-breaker in the final set
      wins = [(6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (7, 5), (7, 6)]
      final = [(6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (7, 5), (8, 6), (9, 7), (10, 8), (11, 9)]
      
      # check for a viable configuration of sets
      def check(pds, gds):
        (p, g) = map(nconcat, (pds, gds))
        # if G wins the the final 2 games
        if is_square(p) and is_square(g - 2): return True
        # if P wins the penultimate game
        (fp, fg) = (pds[-1], gds[-1])
        if fg == 6 and 0 < fp < 5 and is_square(p - 1) and is_square(g - 1): return True
        # not viable
        return False
      
      # choose scores for the first 4 sets
      for ss in subsets(wins, size=4, select="M", fn=list):
        if 0 in ss[0]: continue # no leading zeros
        ss.append(None) # slot for the final set
        # and invert two of them (P's wins)
        for (i, j) in subsets([0, 1, 2, 3], size=2):
          ss_ = update(ss, [i, j], [ss[i][::-1], ss[j][::-1]])
          # choose the final set
          for ss_[-1] in final:
            # collect digits for G and P
            (gds, pds) = map(tuple, zip(*ss_))
            # before the final 2 games, both give square numbers
            if check(pds, gds):
              # output solution
              printf("P={pds}; G={gds}")
      
    • Jim Randell 23 July 2021 at 2:17 pm

      And here is a faster version that starts from the squares, and then looks to see if they make a viable match. It runs in 56ms.

      from enigma import powers, nsplit, multiset, update, printf
      
      # possible wins / tie-breaker in the final set
      wins = { (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (7, 5), (7, 6) }
      finals = { (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (7, 5), (8, 6), (9, 7), (10, 8), (11, 9) }
      
      # the final score
      def score(gds, pds, dg, dp):
        if dg: gds = update(gds, [(-1, gds[-1] + dg)])
        if dp: pds = update(pds, [(-1, pds[-1] + dp)])
        return (gds, pds)
      
      # find possible final scores
      def final(gds, pds):
        wg = wp = 0
        for (i, (g, p)) in enumerate(zip(gds, pds)):
          if i < 4:
            # the first 4 sets
            if (g, p) in wins:
              wg += 1
            elif (p, g) in wins:
              wp += 1
            else:
              return
          elif wg == wp == 2:
            # the final set
            for (dg, dp) in [(2, 0), (1, 1)]:
              if (g + dg, p + dp) in finals:
                yield score(gds, pds, dg, dp)
      
      # 5 digit squares that could appear on the scoreboard
      sqs = list()
      for n in powers(100, 278, 2):
        ds = nsplit(n)
        # count the first 4 digits
        m = multiset.from_seq(ds[:4])
        # there must be 2 wins (6, 7) and no (8, 9)
        if m.count(7) <= 2 and m.count(6) + m.count(7) >= 2 and m.count(8) == m.count(9) == 0:
          sqs.append(ds)
      
      # choose G's square (final digit must be 4 to 9)
      for gds in sqs:
        if gds[-1] < 4: continue # G goes on to win
        # and P's square
        for pds in sqs:
          # check the sets
          for (gs, ps) in final(gds, pds):
            printf("P={ps}; G={gs}")
      
      • Frits 23 July 2021 at 3:40 pm

        @Jim, regarding line 37/38: four sixes for a player in the first 4 sets is not impossible.

        I am not sure whether you handle it or not but if it is an equal score in the final set (before the last 2 games) i think you should print 2 solutions.

        • Jim Randell 23 July 2021 at 4:09 pm

          OK. The new line 38 should sort that out. There are only 20 candidate squares selected, which makes the approach much faster. (Although this test could be omitted, as we check the digits against the sets of valid scores anyway, but it does perform some early rejection of impossible scores, making the code more efficient).

          Surely, if the score is equal before the last 2 games, then G must win them both to win the match. So there is only one solution in this scenario.

          You can probably tell I’m not a big tennis fan. (And definitely not a fan of the scoring system).

  2. Frits 23 July 2021 at 11:37 am

    This Python program runs in 3ms.

    lst = []      
    for i in range(100, 279):      # 9999 < i * i < 77700
      s = str(i * i)
      s4 = s[:-1]
      # skip when number of games is too high
      if any(x in s4 for x in "89"): continue
      # skip when we don't have 2 wins
      if s4.count('6') + s4.count('7') < 2: continue
      # skip if we have more than 2 games lost
      if any(s4.count(x) > 2 for x in "012345"): continue
      # skip if we have more than 2 games won
      if s4.count('7') > 2: continue
      
      lst.append(s)
    
    wins = [('6', '0'), ('6', '1'), ('6', '2'), ('6', '3'), ('6', '4'), 
            ('7', '5'), ('7', '6')] 
    set5 = {'40', '41', '44', '50', '51', '55', '66', '99'}
    set5 |= {x[::-1] for x in set5}    # add reverse scores
      
    for i, s1 in enumerate(lst[:-1]):
     s1_4 = s1[:-1]
     for s2 in lst[i + 1:]:
       foursets = list(zip(s1_4, s2[:-1]))
       # skip if scores are not legal set scores
       if any(x not in wins and x[::-1] not in wins for x in foursets): continue
       # skip if fifth set score is not 2 games of a legal 5th set win
       if s1[-1] + s2[-1] not in set5: continue
       
       print("Scoreboard:")
       if (s1[-1] == s2[-1]):   # equal score
         print(*(foursets + [(str(int(s1[-1]) + 2), s2[-1])]))
         print("or")
         print(*(foursets + [(s1[-1], str(int(s2[-1]) + 2))]))
       else:
         (hi, lo) = (s1[-1], s2[-1]) if s1[-1] > s2[-1] else (s2[-1], s1[-1])
         if hi == "4":
           print(*(foursets + [(str(int(hi) + 2), lo)]))
         else:
           print(*(foursets + [(str(int(hi) + 1), str(int(lo) + 1))]))
    
  3. Pingback: New Scientist Enigma 886 -Set Square | PuzzlingInPython

  4. Frits 29 July 2021 at 4:12 pm

    With a better check on 2 wins and 2 losses in the first 4 sets.

    Program has been optimized for PyPy.

     
    lst = []  
    
    (first6, first7, c) = (-1, -1, 0)
    # generate a list of viable squares 
    for i in range(100, 279):      # 9999 < i * i < 77700
      s = str(i * i)
      s4 = s[:-1]
      # skip when number of games is too high
      if any(x in s4 for x in "89"): continue
      # skip when we don't have 2 wins
      if s4.count('6') + s4.count('7') < 2: continue
      # skip if we have more than 2 wins
      if s4.count('7') > 2: continue
    
      lst.append(s)
      
      if 244 < i < 265 and first6 == -1: 
        first6 = c
    
      if i > 264 and first7 == -1: 
        first7 = c
    
      c += 1  
    
    wins = {"60", "61", "62", "63", "64", "75", "76"}         
    
    # skip 42, 43, 52, 53, 77 and 88 (because of square)
    set5 = {"40", "41", "44", "50", "51", "55", "66", "99"}
    set5 |= {x[::-1] for x in set5}    # add reverse scores
    
    if first6 == -1 and first7 == -1:
      print("no solution")
      exit()
    
    # we can choose the winner of the first set
    # so arrange that first set is won by player 2
    
    maxp1 = first7 if first7 != -1 else c
    for p1 in lst[:maxp1]:
      if p1[0] in "56":      # p2 must be '7'
        if first7 == -1:
          continue
        minp2 = first7
        maxp2 = c
      else:                  # p2 must be '6'
        if first6 != -1:
          continue
        minp2 = first6
        maxp2 = first7 if first7 != -1 else c
        
      for p2 in lst[minp2:maxp2]:
        # skip if fifth set score is not 2 games of a legal 5th set win
        if p1[-1] + p2[-1] not in set5: continue
       
        # skip if player 1 doesn't win 2 legal sets out of 3 sets in sets 2-4
        #   or if player 2 doesn't win 1 legal set out of 3 sets in sets 2-4
        if sum(x in wins for x in [p1[1]+p2[1], p1[2]+p2[2], p1[3]+p2[3]]) != 2 or \
           sum(x in wins for x in [p2[1]+p1[1], p2[2]+p1[2], p2[3]+p1[3]]) != 1: 
          continue      
    
        if (p1[-1] == p2[-1]):   # equal score
          print([p1[:-1] + str(int(p1[-1]) + 2), p2])
          print("or")
          print([p1, p2[:-1] + str(int(p2[-1]) + 2)])
        else:
          (hi, lo) = (p2, p1) if p1[-1] < p2[-1] else (p1, p2) 
          if hi[-1] == "4":
            print([hi[:-1] + '6', lo])
          else:
            print([hi[:-1] + '6', lo[:-1] + str(int(lo[-1]) + 1)])
    
  5. GeoffR 30 July 2021 at 11:26 am

    This posted code is not an exhaustive exploration of the solution space. I tried several scenarios for different match score patterns, but this was the only one that gave a viable answer,

    I also did not include game scores above 7-5, and allocated the two extra points in the fifth game to Grassy, as found previously.

    # GAMES played, in order, are A,B,C,D,E
    # GRASSY wins game E and two games from A,B,C,D
    # Game score points: p1, q1, r1, s1, t1 - for GRASSY
    # and                p2, q2, r2, s2, t2 - for PAMPAS
    
    from itertools import product
    from math import isqrt
    
    def is_sq(x):
      return isqrt(x) ** 2 == x
    
    # test for two squares for all game scores
    def two_sq(p1, p2, q1, q2, r1, r2, s1, s2, t1, t2):
      # form two squares from match scores
      # 5th game(Grassy) is formed on last digit for square before 2 points added
      num1 = 10000 * p1 + 1000 * q1 + 100 * r1 + 10 * s1 + (t1 - 2)
      num2 = 10000 * p2 + 1000 * q2 + 100 * r2 + 10 * s2 + t2
      if is_sq(num1) and is_sq(num2):
        return True
      return False
    
    # Test 4 - BCE are wins for GRASSY
    # L W W L W is winning game pattern
    for p2, q1, r1, s2, t1 in product(range(6, 8), repeat=5):
      for p1, q2, r2, s1, t2 in product(range(6), repeat=5):
        # check for invalid 2nd game scores if 1st score is 7
        if p2 == 7 and p1 < 5:continue
        if q1 == 7 and q2 < 5:continue
        if r1 == 7 and r2 < 5:continue
        if s2 == 7 and s2 < 5:continue
        if t1 == 7 and t2 < 5:continue
        # check this set of game points gives two squares
        if two_sq(p1, p2, q1, q2, r1, r2, s1, s2, t1, t2):
          print('Winning game score pattern(GRASSY) is L,W,W,L,W')
          print(f"Scoreboard - GRASSY: {p1},{q1},{r1},{s1},{t1}")
          print(f"Scoreboard - PAMPAS: {p2},{q2},{r2},{s2},{t2}")
    
    # Winning game score pattern (GRASSY) is L,W,W,L,W
    # Scoreboard - GRASSY: 5,6,6,4,6
    # Scoreboard - PAMPAS: 7,2,3,6,1
    
    # Other winning game pattern scores tested 
    # Test 1 - ABE - pattern W W L L W
    # Test 2 - ACE - pattern W L W L W
    # Test 3 - ADE - pattern W L L W W
    # Test 5 - BDE - pattern L W L W W
    
    
    
    • Frits 30 July 2021 at 3:38 pm

      @GeoffR, you allow for 6-5 as a set score.

      I guess you also tested Test 6 – CDE – pattern L L W W W.

  6. GeoffR 31 July 2021 at 8:17 am

    @Frits: I checked the game pattern “L L W W W”, but it did not produce a viable result.

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: