Enigmatic Code

Programming Enigma Puzzles

Enigma 1059: Century break

From New Scientist #2215, 4th December 1999 [link]

At snooker a player scores 1 point for potting one of the 15 red balls, but scores better for potting any of the 6 coloured balls: 2 points for yellow, 3 for green, 4 for brown, 5 for blue, 6 for pink and 7 for black.

Davies potted his first red ball, followed by his first coloured ball, then his second red ball, and so on until he had potted all 15 red balls, each followed by a coloured ball.

After potting 15 red balls and 15 coloured balls, Davies had scored exactly 100 points; but it was interesting because in calling his score after each pot the referee had called every perfect square between 1 and 100.

Question 1: If in achieving this Davies had potted as few different colours as possible, which of the coloured balls would he have potted?

In fact Davies had brought a greater variety to the choice of coloured balls potted: for instance the 2nd, 5th, 8th, 11th and 14th coloured balls potted were all different and if I told you what they were you could deduce with certainty which ball was potted on each of his other pots.

Question 2: What (in order) were the 2nd, 5th, 8th, 11th and 14th coloured balls potted?

(In answering both questions give the colours).

[enigma1059]

2 responses to “Enigma 1059: Century break

  1. Jim Randell 4 June 2018 at 7:04 am

    This Python 3 program starts by working out possible combinations of colours that will go with the 15 reds in order to make a score of 100, and then examine sequences of red+colour pairs made from these combinations that have the required squares as a subsequence of the scores called in potting that sequence.

    From this list we can find the sequences that use the smallest number of different colours, and also sequences where the given balls are all different, and knowing their values gives a unique sequence.

    It runs in 1.36s.

    Run: [ @repl.it ]

    from collections import Counter, defaultdict
    from enigma import irange, distinct_values, filter_unique, printf
    
    # points for the colours
    colours = (2, 3, 4, 5, 6, 7)
    
    # perfect squares from 1 to 100
    squares = tuple(i * i for i in irange(1, 10))
    
    # make total t out of m multiples of the numbers in ns
    def multiples(t, ns, m, s=[]):
      k = len(ns)
      if k < 1: return
      n = ns[0]
      if k == 1:
        if t == m * n:
          yield tuple(s + [m])
      else:
        for d in irange(0, t // n):
          yield from multiples(t - n * d, ns[1:], m - d, s + [d])
    
    # create a red+colour sequence from the colours in cs
    # such that cumulative scores include ss as a subsequence
    def solve(cs, ss, s=[]):
      # are we done?
      if not cs:
        yield tuple(s)
      else:
        if len(s) % 2 == 0:
          # pot a red
          xs = [1]
        else:
          # pot a colour
          xs = cs.keys()
    
        for x in xs:
          t = sum(s) + x
          if t < ss[0]:
            yield from solve(cs - Counter([x]), ss, s + [x])
          elif t == ss[0]:
            yield from solve(cs - Counter([x]), ss[1:], s + [x])
        
    
    # record results by the collection of colours
    r = defaultdict(list)
    
    # there are 15 reds each worth 1 point, find colours to go with them to score 100
    for cs in multiples(100 - 15, colours, 15):
      # find sequences of red/colours whose scores include squares
      for s in solve(Counter(dict(zip(colours, cs))), squares):
        r[cs].append(s)
    printf("[found {c} colour combinations and {n} sequences]", c=len(r.keys()), n=sum(len(vs) for vs in r.values()))
    
    
    # part 1: find the smallest number of different colours used
    # (we find the largest number of unused colours)
    measure = lambda cs: cs.count(0)
    m = max(measure(k) for (k, vs) in r.items() if vs)
    
    printf("(1) min colours = {m}", m=len(colours) - m)
    
    # part 2: collect sequences where the required balls have distinct values
    # a function to select the required balls from a sequence
    select = lambda s: tuple(s[i] for i in (3, 9, 15, 21, 27))
    rs = list()
    
    # part 1: output sequences which use a minimal number of colours
    # part 2: collect sequences where the selected balls have distinct values
    for (k, ss) in r.items():
      x = measure(k)
      if x == m:
        # part 1: minimal number of colours
        printf("  colours = {k}")
        for s in ss:
          printf("  -> {s}")
      else:
        # part 2: larger number of colours, but selected balls have different values
        for s in ss:
          if distinct_values(select(s)):
            rs.append(s)
    
    # part 2: find sequences uniquely identified by the values of the selected balls
    (rs, _) = filter_unique(rs, select)
    
    # part 2: output solutions
    printf("(2) num sequences = {n}", n=len(rs))
    for s in rs:
      printf("  values = {k} -> {s}", n=len(rs), k=select(s))
    

    Solution: (1) It is possible to achieve this potting only 2 different colours – the green (3 points) and the black (7 points); (2) The specified balls are: blue, yellow, brown, black, green.

    For part 1:

    The green is potted 5 times (5 × 3 points = 15 points), and the black is potted 10 times (10 × 7 points = 70 points). Together these make 85 points, along with the 15 points for the reds this totals 100 points.

    The scoring sequence and total score is:

    red = 1 point
    + green = 4 points
    + red, green, red = 9 points
    + black = 16 points
    + red, black, red = 25 points
    + green, red, black = 36 points [*]
    + red, green, red, black, red = 49 points [*]
    + black, red, black = 64 points
    + red, black, red, black, red = 81 points
    + green, red, black, red, black = 100 points [*]

    The colours in the sections marked [*] can be potted in any order giving rise to 2×2×3 = 12 possible sequences.

    For part 2:

    The yellow is potted 2 times, the green 1 time, the brown 1 time, the blue 1 time, the pink 1 time, the black 9 times. 2×2 + 1×3 + 1×4 + 1×5 + 1×6 + 9×7 = 85 points.

    The sequence is:

    red = 1 point
    + yellow, red = 4 points
    + (blue) = 9 points
    + red, pink = 16 points
    + red, black, red = 25 points
    + (yellow), red, black, red = 36 points
    + black, red, (brown), red = 49 points
    + black, red, black = 64 points
    + red, (black), red, black, red = 81 points
    + black, red, (green), red, black = 100 points

    The 2nd, 5th, 8th, 11th and 14th colours are shown in parentheses.

    For part 2, there are 368 sequences of balls that use more than 2 different colours and have the required balls all different, but only one of these sequences is uniquely identified if the values of these balls are given.

  2. Brian Gladman 5 June 2018 at 3:08 pm

    My version requires my number theory library that I make available here.   It also requires either Jim’s enigma.py library or my partition_unique subroutine.

    from itertools import count, combinations
    from collections import Counter
    from number_theory import frobenius_solve
    try:
      from partition_unique import partition_unique
    except ImportError:
      from enigma import filter_unique as partition_unique
      
    # target (square) scores
    sqrs = [x * x for x in range(1, 11)]
    
    # play a break with target scores in <tgts> using
    # the 'coloured' balls in <balls>  
    def game(tgts, balls, score=0, pots=tuple()):
      if not tgts:
        yield pots
      else:
        # play a red
        score += 1
        # record any used target 
        i = 1 if score == tgts[0] else 0
        # the score needed for a 'colour'
        b = tgts[i] - score
        for x in balls.keys():
          if x <= b:
            # record any used target
            i += (1 if x == b else 0)
            yield from game(tgts[i:], balls - Counter([x]), score + x, pots + (1, x))
    
    # find snooker breaks using 'colours' in range lo .. hi-1 inclusive  
    def solve(lo, hi):
      for n in range(lo, hi):
        # select the colours to try
        for c in combinations(range(2, 8), n):
          # find ways of making 85 with combinations of these colours
          for f in frobenius_solve(c, 85):
            # we need at least some of each and a total of fifteen balls
            if all(x for x in f) and sum(f) == 15:
              balls = Counter(dict(zip(c, f)))
              # look for a solution
              for f in game(sqrs, balls):
                yield f, balls.items()
                
    # Q1: look for a break with a minimum number of different colours
    for f, q1s in solve(1, 7):
      break
    
    # Q2: the positions of the referenced colours in the break
    inx = [2 * i - 1 for i in (2, 5, 8, 11, 14)]
    
    # find possible breaks with five and six different colours
    sol = set()
    for f, b in solve(5, 7):
      cs = set(x for i, x in enumerate(f) if i in inx)
      if len(cs) == 5:
        sol.add(f)
    
    # find a set of the referenced colours that uniquely identify a break   
    q2s = partition_unique(sol, lambda x: tuple(x[i] for i in inx))[0][0]
    
    # colour names
    clr = ('', 'red', 'yellow', 'green', 'brown', 'blue', 'pink', 'black')
    
    s = ', '.join(f'{n} {clr[c]}' for c, n in q1s)
    # Question 2
    f, _, l = (', '.join(clr[q2s[i]] for i in inx)).rpartition(', ')
    t = ' and '.join((f, l))
    print(f'Q1: {s}; Q2: {t}.')
    

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: