Snooker

March 30, 2018

I lived in London during the 1980s, and like many people I was mesmerized by the snooker match between Dennis Taylor and Steve Davis. Davis was widely expected to win, and indeed he won the first game of the match, and carried his lead all the way to the end of the second day, when Taylor potted the final black ball and took the lead for the very first time over the two-day match, winning the world championship.

Snooker is scored by points for the balls of various colors: there are 15 red balls, each worth 1 point, plus one ball each of yellow, green, brown, blue, pink and black worth, respectively, 2, 3, 4, 5, 6 and 7 points. Players accumulate points in a break by potting balls one after another until they make a miss. As long as there is a red ball on the table, the player must pocket a red ball first; then, after making a red, the player can attempt to make a “colored” ball (other than red). If a color is potted, it is returned to the table (put on its spot) as long as there is a red on the table; once all the reds are potted, the colors must be potted in ascending point order, and are not respotted. A perfect game requires the player to pot 36 balls in order ā€” 15 reds, each with a black, followed the colors in order ā€” and earns 147 points. Perfect games are not common, but neither are they uncommon; in ranked match play, there are typically one or two perfect games per year.

Your task, which comes from an interview question, is to write a program that calculates the sequence of scores from a game of snooker; for a perfect game, the sequence is 1, 8, 9, 16, 17, 24, 25, 32, 33, 40, 41, 48, 49, 56, 57, 64, 65, 72, 73, 80, 81, 88, 89, 96, 97, 104, 105, 112, 113, 120, 122, 125, 129, 134, 140, 147 (A241263). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

7 Responses to “Snooker”

  1. Couldn’t resist perl golf
    [sourcecode language="perl"]
    say”@{[map{$t+=$_}(map{(1,7)}1..15),2..7]}”
    [sourcecode]

  2. chaw said

    I interpreted the question to require mapping a sequence of potted
    balls (including fouls) to scores, so this code handles such cases.
    However, my knowledge of snooker rules is limited to what’s mentioned
    in the question, so only those violations are caught.

    (import (scheme base)
            (scheme write)
            (srfi 2))
    
    ;; State of the game: config[i] = # of balls of value i on table, for
    ;; 0 < i < 8.  config[0], if nonzero, is the value of the last potted
    ;; ball.
    (define (initial-config)
      (vector 0 15 1 1 1 1 1 1))
    
    ;; Colors of balls
    (define ball-color
      '#(#f "red" "yellow" "green" "brown" "blue" "pink" "black"))
    
    ;; A break is represented as a sequence of values of potted balls.
    ;; Here's a perfect game, which should score to 147 points:
    (define perfect-game (append (apply append
                                        (make-list 15 '(1 7)))
                                 '(2 3 4 5 6 7)))
    
    (define (vector-decrement! vec idx)
      (vector-set! vec idx (- (vector-ref vec idx) 1)))
    
    ;; Update game configuration cfg (in place) to record ball being
    ;; potted. Return the points scored, or #f if ball is not on table.
    (define (pot-ball! cfg ball)
      (and (positive? (vector-ref cfg ball)) ; else impossible => #f
           ;; Check for scratch (config remains as is and no points awarded)
           (if (and (positive? (vector-ref cfg 1))
                    (not (= 1 ball))
                    (not (= 1 (vector-ref cfg 0))))
               0
               (begin
                 (when (or (= ball 1)
                           (and (zero? (vector-ref cfg 1))
                                (not (= 1 (vector-ref cfg 0)))))
                   (vector-decrement! cfg ball))
                 (vector-set! cfg 0 ball)
                 ball))))
    
    (define (game-score-sequence balls)
      (let ((cfg (initial-config)))
        (let f ((balls balls)
                (scores '(0)))
          (if (null? balls)
              (cdr (reverse scores))
              (and-let* ((points (pot-ball! cfg (car balls))))
                (f (cdr balls)
                   (cons (+ (car scores) points)
                         scores)))))))
    
    (display (game-score-sequence perfect-game))
    (newline)
    

  3. Daniel said

    Here’s a solution in Python 3.

    from itertools import accumulate
    l = list(accumulate([1,7]*15 + list(range(2,8))))
    print(l)
    

    Output:

    [1, 8, 9, 16, 17, 24, 25, 32, 33, 40, 41, 48, 49, 56, 57, 64, 65, 72, 73, 80, 81, 88, 89, 96, 97, 104, 105, 112, 113, 120, 122, 125, 129, 134, 140, 147]
    
  4. Daniel said

    Here’s a solution in C.

    [sourecode lang=”c”]
    /* snooker.c */

    #include <stdio.h>
    #include <stdlib.h>

    #define NUM_POTS 36

    void print_array(int* array, size_t n) {
    printf(“[“);
    for (size_t i = 0; i < n; ++i) {
    if (i > 0) printf(“, “);
    printf(“%d”, array[i]);
    }
    printf(“]\n”);
    }

    void accumulate(int* array, size_t n) {
    for (size_t i = 1; i < n; ++i) {
    array[i] += array[i-1];
    }
    }

    void calc_perfect_game(int* scores) {
    for (size_t i = 0; i < 15; ++i) {
    scores[i2] = 1;
    scores[i
    2 + 1] = 7;
    }
    for (size_t i = 0; i < 6; ++i) {
    scores[i+30] = i + 2;
    }
    accumulate(scores, NUM_POTS);
    }

    int main(void) {
    int scores[NUM_POTS];
    calc_perfect_game(scores);
    print_array(scores, NUM_POTS);
    return EXIT_SUCCESS;
    }
    [/sourcecode]

    Output:

    [1, 8, 9, 16, 17, 24, 25, 32, 33, 40, 41, 48, 49, 56, 57, 64, 65, 72, 73, 80, 81, 88, 89, 96, 97, 104, 105, 112, 113, 120, 122, 125, 129, 134, 140, 147]
    
  5. Daniel said

    I spelled “sourcecode” wrong. Here it is again with the correct spelling (and formatting).

    /* snooker.c */

    #include <stdio.h>
    #include <stdlib.h>

    #define NUM_POTS 36

    void print_array(int* array, size_t n) {
    printf("[");
    for (size_t i = 0; i < n; ++i) {
    if (i > 0) printf(", ");
    printf("%d", array[i]);
    }
    printf("]\n");
    }

    void accumulate(int* array, size_t n) {
    for (size_t i = 1; i < n; ++i) {
    array[i] += array[i-1];
    }
    }

    void calc_perfect_game(int* scores) {
    for (size_t i = 0; i < 15; ++i) {
    scores[i*2] = 1;
    scores[i*2 + 1] = 7;
    }
    for (size_t i = 0; i < 6; ++i) {
    scores[i+30] = i + 2;
    }
    accumulate(scores, NUM_POTS);
    }

    int main(void) {
    int scores[NUM_POTS];
    calc_perfect_game(scores);
    print_array(scores, NUM_POTS);
    return EXIT_SUCCESS;
    }

    Output:

    [1, 8, 9, 16, 17, 24, 25, 32, 33, 40, 41, 48, 49, 56, 57, 64, 65, 72, 73, 80, 81, 88, 89, 96, 97, 104, 105, 112, 113, 120, 122, 125, 129, 134, 140, 147]
    
  6. Daniel said

    Last try…

    /* snooker.c */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define NUM_POTS 36
    
    void print_array(int* array, size_t n) {
      printf("[");
      for (size_t i = 0; i < n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", array[i]);
      }
      printf("]\n");
    }
    
    void accumulate(int* array, size_t n) {
      for (size_t i = 1; i < n; ++i) {
        array[i] += array[i-1];
      }
    }
    
    void calc_perfect_game(int* scores) {
      for (size_t i = 0; i < 15; ++i) {
        scores[i*2] = 1;
        scores[i*2 + 1] = 7;
      }
      for (size_t i = 0; i < 6; ++i) {
        scores[i+30] = i + 2;
      }
      accumulate(scores, NUM_POTS);
    }
    
    int main(void) {
      int scores[NUM_POTS];
      calc_perfect_game(scores);
      print_array(scores, NUM_POTS);
      return EXIT_SUCCESS;
    }
    

    Output:

    [1, 8, 9, 16, 17, 24, 25, 32, 33, 40, 41, 48, 49, 56, 57, 64, 65, 72, 73, 80, 81, 88, 89, 96, 97, 104, 105, 112, 113, 120, 122, 125, 129, 134, 140, 147]
    
  7. Globules said

    Here’s a Haskell version. For fun we generate a random snooker game.

    import Prelude hiding ((++))
    import Control.Monad.Random
    import Data.Vector (Vector, (++))
    import qualified Data.Vector as V
    import qualified Data.Vector.Mutable as M
    import Text.Printf (printf)
    
    data Ball = Red | Yellow | Green | Brown | Blue | Pink | Black
      deriving (Enum)
    
    -- The number of points awarded for potting a ball.
    points :: Ball -> Int
    points = (+1) . fromEnum
    
    -- The 15 red balls.
    reds :: Vector Ball
    reds = V.replicate 15 Red
    
    -- The remaining coloured (non-red) balls.
    coloureds :: Vector Ball
    coloureds = V.enumFromTo Yellow Black
    
    -- A series of balls corresponding to a random game in which one player pots one
    -- ball per shot.
    --
    -- We construct a game by generating the sequence of shots:
    --
    --   r, c, r, c, ..., r, c, c, c, c, c, c, c
    --   +-------------------+  +--------------+
    --      15 (r,c) pairs         final 6 cs
    -- 
    -- which consists of 15 pairs of a red ball, and a coloured ball chosen randomly
    -- (with replacement), followed by all the coloured balls in increasing order of
    -- points.
    randomGame :: Rand StdGen (Vector Ball)
    randomGame = do
      cols <- randomSelection (V.length reds) coloureds
      return $ unpair (V.zip reds cols) ++ coloureds
    
    -- Show the accumulation of points for a sequence of potted balls.
    score :: Vector Ball -> String
    score = unwords . map show . V.toList . V.postscanl (+) 0 . V.map points
    
    -- The sequence of balls potted in a perfect game.
    perfect :: Vector Ball
    perfect = let blacks = V.map (const Black) reds
              in unpair (V.zip reds blacks) ++ coloureds
    
    main :: IO ()
    main = do
      rand <- getStdGen
      printf "perfect: %s\n" $ score perfect
      printf " random: %s\n" $ score $ evalRand randomGame rand
    
    
    --
    --                          Utility functions
    --
    
    -- Given [(a, b), (c, d), ...] return [a, b, c, d, ...].
    unpair :: Vector (a, a) -> Vector a
    unpair xs = V.create $ do
      ys <- M.new (2 * V.length xs)
      V.imapM_ (\i (x1, x2) -> M.write ys (2*i) x1 >> M.write ys (2*i+1) x2) xs
      return ys
    
    -- A random selection of size n from v, with replacement.
    randomSelection :: MonadRandom m => Int -> Vector a -> m (Vector a)
    randomSelection n xs =
      V.backpermute xs <$> V.replicateM n (getRandomR (0, V.length xs - 1))
    
    $ ./snooker
    perfect: 1 8 9 16 17 24 25 32 33 40 41 48 49 56 57 64 65 72 73 80 81 88 89 96 97 104 105 112 113 120 122 125 129 134 140 147
     random: 1 4 5 10 11 17 18 25 26 29 30 33 34 41 42 46 47 52 53 56 57 59 60 62 63 66 67 72 73 77 79 82 86 91 97 104
    

Leave a Reply

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 )

w

Connecting to %s

%d bloggers like this: