Programming Praxis

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.

Pages: 1 2