Enigmatic Code

Programming Enigma Puzzles

Enigma 293: Red is not a colour

From New Scientist #1441, 31st January 1985 [link]

Yesterday, a red letter day in our local club, was the occasion for the single-frame final of our annual snooker tournament. This climactic “Battle of the Titans” began with much canny safety play — but there were no scores until a stunning table-length red opened the balls to a useful break. The suspense mounted thereafter as successive visits to the table resulted in breaks which totalled just one point more than the (opponent’s) preceding break. I remember that all 15 red balls (scoring one point each) were potted singly, and every red was successfully followed by a nominated coloured ball. No penalty points were incurred and the frame was not ceded prematurely.

Once again, Roland Cannon took the winner’s cup. Rusty Abacus, our referee and official marker, gave a little presentation speech; referring to the recent final, he remarked that all the coloured balls potted in association with red balls had been potted the same number of times as the points value of the particular coloured ball. Then the blue ball (say) would have been potted five times in all.

Roland also won the medal for the highest break of the tournament. This was his reward for a gallant 22-point clearance which snatched the victory in his quarter-final battle.

Note that the potting sequence/points value of the coloured balls is: yellow/2, green/3, brown/4, blue/5, pink/6 and black/7 points. Also, the club rules committee insists that when a player has a lead of eight points or more after the final pink has been potted, then the final black ball must not be played.

What was Roland’s total score in that final frame?

[enigma293]

Advertisements

2 responses to “Enigma 293: Red is not a colour

  1. Jim Randell 8 July 2015 at 9:23 am

    The first program I wrote to solve this problem didn’t come up with any answers, so here’s a slower Python 3 program which generates ascending sequences of break scores starting with a score between 3 (the smallest possible break) and 21 (the highest possible break in the final), and then applies the additional tests. It takes 53s to check all possible scores.

    from collections import Counter
    from enigma import irange, flatten, printf
    
    # generate breaks of a given value
    # v - the value
    # balls - the sequence of balls to play (1=red, is followed by a colour)
    # m - minimum value colour to choose
    # s - sequence of balls in break so far
    def generate(v, balls, m=2, s=[]):
      # are we done?
      if v == 0:
        yield (s, balls)
      elif balls:
        b = balls[0]
        if b == 1:
          # pot a red and choose a colour
          for c in irange(m, min(7, v - 1)):
            yield from generate(v - (b + c), balls[1:], c, s + [b, c])
        else:
          if not(b > v):
            yield from generate(v - b, balls[1:], m, s + [b])
    
    # check a sequence of breaks solves the problem
    def check(ss):
      # flatten the sequence of breaks
      balls = flatten(ss)
      # find the colours that follow a red
      cs = set(balls[1:31:2])
      # count all the balls
      c = Counter(balls)
      # check the colours that follow a red are potted their own number of times
      if any(c[x] != x for x in cs): return
      # calculate the scores for each break, and for each player
      ps = tuple(sum(s) for s in ss)
      # break scores are less than 22
      if not all(p < 22 for p in ps): return
      (p1, p2) = (sum(ps[0::2]), sum(ps[1::2]))
      # the final black is not played if the leader is more than 7 points ahead
      if not ((balls[-1] == 7 and abs(p1 - p2) < 8) or (balls[-1] == 6 and abs(p1 - p2) > 7)): return
      printf("[breaks = {ss}]")
      printf("[count = {c}]")
      printf("[scores = {ps}, total = {p1}, {p2}]")
      # return the total scores and the sequence of breaks
      return (p1, p2, ss)
    
    def solve(b, balls, ss=[]):
      if len(balls) < 2:
        r = check(ss)
        if r: yield r
      else:
        for (s, bs) in generate(b, balls):
          yield from solve(b + 1, bs, ss + [s])
    
    balls = ([1] * 15) + [2, 3, 4, 5, 6, 7]
    
    r = Counter()
    for b in irange(3, 21):
      printf("[trying initial break = {b} ...]")
      for (p1, p2, ss) in solve(b, balls):
        printf("[b={b}: ({p1}, {p2}) {ss}]")
        r[max(p1, p2)] += 1
    
    for (k, v) in r.most_common():
      printf("score = {k} [{v} solutions]")
    

    Solution: Roland’s total score in the final was 60 points.

    There are thirteen possible matches (sequences of balls) that correspond to this scenario. All of them involve breaks of 12, 13, 14, 15, 16, 17, 18 (to give total scores of 60 and 45). The final black is not played. The colours potted with the reds are: 1 yellow, 2 greens, 3 browns, 4 blues, 5 pinks. Player 2 pots the final red and then a yellow. Player 1 then pots the green, brown, blue and pink, and takes the frame without needing to pot the black. So overall (including the clearance) each coloured ball is potted its own number of times, with the exception of the black, which is not potted at all.

    One example match is:

    (1 4 1 6) (1 5 1 6) (1 6 1 6) (1 2 1 4 1 6) (1 3 1 5 1 5) (1 3 1 4 1 5 2) (3 4 5 6)

    (I don’t distinguish the order that the balls were potted in, so (1 4 1 6) could be red/brown/red/pink or red/pink/red/brown, without this restriction the program finds 3960 possible sequences).

    The next possible match with ascending sequence of break scores is breaks of (19, 20, 21, 22, 23) to give total scores of (63, 42) (again the final black is not played). But such a sequence is not a solution as the highest break in the tournament was 22, and it wasn’t in the final. Nevertheless here is an example sequence for this scenario:

    (1 3 1 3 1 4 1 5) (1 5 1 6 1 6) (1 6 1 6 1 6) (1 4 1 4 1 5 1 5) (1 2 2 3 4 5 6)

    • Jim Randell 9 July 2015 at 2:51 pm

      Here’s a faster program. It runs in 1.65s (using PyPy).

      from collections import Counter
      from enigma import compare, irange, printf
      
      # set up the balls
      reds = [1] * 15
      colours = [2, 3, 4, 5, 6, 7]
      black = colours[-1]
      
      # play the next ball
      # n - number of balls remaining to play
      # balls - the balls remaining (1 = red, is followed by a colour)
      # cs - count the colours potted with the reds
      # ss - completed breaks
      # s - current break
      # p - score in current break
      # t - target score
      # m - maximum break
      # p1 - total score for current player
      # p2 - total score for other player
      # r - count solutions by winning score
      def play(n, balls, cs, ss, s, p, t, m, p1, p2, r):
      
        # breaks cannot exceed the maximum allowed
        if t > m: return
      
        # are we done?
        if n == 0 or (n == 1 and abs(p1 - p2) > sum(balls)):
          # all breaks must be complete
          if len(s) > 0: return
          # if the black was potted with the reds, it must have been potted 7 times
          if black in cs and cs[black] != black: return
          printf("[breaks = {ss}, scores = {ps}, totals = {ts}]", ps=tuple(sum(s) for s in ss), ts=(p1, p2))
          # count the solutions by the winners score
          r[max(p1, p2)] += 1
          return
      
        # next ball
        b = balls[0]
      
        # is it a red?
        if b == 1:
          # highest colour potted so far in this break
          h = (0 if len(s) == 0 else max(s))
          # pair it with a colour
          for c in colours:
            # consider colours in order
            if c < h: continue
            # colours cannot exceed their points value
            if c in cs and (cs[c] == c - 1 or (c == black and cs[c] == c)): continue
            cs2 = cs + Counter([c])
            # can we extend (or complete) the current break?
            x = compare(p + b + c, t)
            if x == -1:
              # the current break can be extended
              play(n - 1, balls[1:], cs2, ss, s + [b, c], p + b + c, t, m, p1 + b + c, p2, r)
            elif x == 0:
              # this play completes the current break
              play(n - 1, balls[1:], cs2, ss + [s + [b, c]], [], 0, t + 1, m, p2, p1 + b + c, r)
            else:
              break
          return
      
        # reds are exhausted
        if b == colours[0]:
          # check the colour counts
          if not all(n == c - 1 or (c == black and n == c) for (c, n) in cs.items()): return
      
        # we're clearing the colours
        cs2 = (cs + Counter([b]) if b in cs else cs)
        # can we extend or complete the current break
        x = compare(p + b, t)
        if x == -1:
          # the current break can be extended
          play(n - 1, balls[1:], cs2, ss, s + [b], p + b, t, m, p1 + b, p2, r)
        elif x == 0:
          # this play completes the current break
          play(n - 1, balls[1:], cs2, ss + [s + [b]], [], 0, t + 1, m, p2, p1 + b, r)
      
      
      # play games with initial breaks from 3 to 21, maximum break = 21
      balls = reds + colours
      r = Counter()
      for b in irange(3, 21):
        printf("[trying initial break = {b} ...]")
        play(len(balls), balls, Counter(), [], [], 0, b, 21, 0, 0, r)
      
      # report solutions
      for (k, v) in r.most_common():
        printf("score = {k} [{v} solutions]")
      

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: