What are the properties of the Numbers Game? Richard Harris continues his analysis.
In the first part of this article we introduced the Countdown numbers game [ Countdown ]. Part of the longest running game show on UK television and one of the longest running in the world, it involves picking 6 numbers from a choice of 4 large and 20 small numbers, being the integers 25, 50, 75 and 100 and 2 of each of the integers from 1 to 10 respectively.
The contestants must then seek to construct a formula using the binary operators of addition, subtraction, multiplication and division with each of these 6 numbers no more than once, and with no non-integer intermediate values, that evaluates to a randomly selected target between 1 and 999.
Reverse Polish Notation
In order to simplify the automatic generation of formulae, we introduced Reverse Polish notation, or RPN, a notation for arithmetic formulae supremely suited to programmatic manipulation.
Unlike the more familiar infix notation, RPN places operators immediately to the right, rather than between, their arguments. For example the infix expression 3+4 would be written as 3 4 + in RPN.
RPN utilises a stack to keep track of the intermediate values in a calculation, and in doing so makes explicit the order in which operators are applied, making parentheses redundant.
Every time a number appears in the input sequence it is pushed on to the stack. Every time an operator appears it pops the arguments it requires off of the stack and pushes its result back on to it. If there are not enough arguments on the stack for an operator, or if there is more than one value on the stack at the end of the RPN formula, an error occurs.
For example, Figure 1 illustrates the state of the stack after each term in the RPN formula 3 4 × 2 +
|
| Figure 1 |
Formula templates
Rather than enumerate the set of valid formulae in any possible Countdown numbers game directly, we instead decided to generate templates into which we could substitute operators and arguments. Acting as place-holders for the operators and arguments we used the o and x symbols respectively.
We described an algorithm for generating the set of all formula templates with up to a given number of arguments in which, starting with a single x symbol, recursively replaced x symbols with the symbols xxo . Since both the former and the latter result in a single value on the stack, we cannot therefore create an invalid formula by doing so.
In general, this approach could generate some formula template more than once, so we kept track of the generated templates with a set of string s. The declaration of the all_templates function that implements this algorithm is:
std::set<std::string> all_templates(
size_t arguments);
Since each substitution introduces 1 additional argument, we can ensure that we terminate the recursion when we have exhausted the available arguments by subtracting 1 from their number with each substitution and stopping when we reach 0.
Figure 2 gives the complete set of formula templates for up to 5 arguments in order of increasing length, as calculated using these functions.
|
|
||||||||||||||||||||||||
| Figure 2 |
Evaluating RPN formula templates
We concluded by implementing a mechanism by which we could evaluate a given formula template for a given set of operators and arguments. The first step was to implement an abstract base class to represent arbitrary RPN operators and concrete classes derived from it to represent the four valid binary operators of the Countdown number game. The base class and the declarations of the operators are provided in Listing 1.
template<class T>
class rpn_operator
{
public:
typedef std::stack<std::vector<T> > stack_type;
virtual ~rpn_operator();
virtual bool apply(stack_type &stack) const = 0;
};
template<class T> class rpn_add;
template<class T> class rpn_subtract;
template<class T> class rpn_multiply;
template<class T> class rpn_divide;
|
| Listing 1 |
Note that since the standard stack class does everything we require of an RPN stack, we very sensibly, or very lazily, opted to use it rather than implement our own.
The definitions of the four operator classes are, with the exception of their names, identical, so we provide just the definition of rpn_divide in Listing 2.
template<class T>
class rpn_divide : public rpn_operator<T>
{
public:
virtual bool apply(stack_type &stack) const;
};
|
| Listing 2 |
Recall that we gave the operators themselves the responsibility for issuing errors in the event that there are not enough arguments on the stack since this allows us to implement operators that require any particular number of arguments should we have cause to do so.
The rpn_divide operator is something of a special case in that it is undefined for some arguments. Specifically, for floating point calculations the second argument must be non-zero and for integer calculations it must wholly divide the first.
It is, therefore, the only one of the four operators that might return false from its apply member function, indicating that an invalid intermediate value resulted from its application.
We then implemented a simple structure to represent both the validity and the value of the result of a calculation. Given in Listing 3, the rpn_result structure is considered valid if it is constructed with a value and invalid if it is not.
template<class T>
struct rpn_result
{
rpn_result();
explicit rpn_result(const T &t);
bool valid;
T value;
};
|
| Listing 3 |
Finally, we implemented a function that, given a formula template represented by a string of o and x characters, a vector of pointers to rpn_operators and a vector of arguments, would substitute the latter pair into the former to produce a result.
The rpn_evaluate function, the declaration of which is shown in Listing 4, iterated over the formula template string, pushing the current argument on to the stack of the current term is an x , and applying the current operator if it is an o . We assert the correctness of the calculation by throwing exceptions if there aren't enough arguments or operators, or if there is not exactly one value on the stack at the end.
template<class T>
rpn_result<T>
rpn_evaluate(const std::string &formula,
const std::vector<rpn_operator<T> const *>
&operators,
const std::vector<T> &arguments);
|
| Listing 4 |
Whilst this approach isn't particularly useful as a general purpose RPN calculator due to the separation of the formula template, the operators and the arguments, it is particularly well suited to the programmatic evaluation of formulae for precisely the same reason.
Counting the number of formulae
We noted that in order to fully investigate the statistical properties of the Countdown numbers game we should need a means to enumerate every possible formula that might be expressed.
Recall that we proved that the total number of formulae that it is possible to construct with the 4 binary operations and 6 of the 24 possible arguments was
where 24 C 6 is the number of ways in which we can choose 6 from 24 items when their order is not important, T i is the number of formula templates with i arguments, 4 i -1 is the number of sets of binary operators that can appear in a formula with i arguments, and 6 P i is the number of ways in which we can choose i from 6 items when their order is important.
In light of this result, we concluded that in order to generate every possible formula we would need to enumerate the 24 C 6 combinations of selected numbers, the set of templates with up to 6 arguments, the 4 n -1 sets of operators required by formulae with n arguments and the 6 P n permutations of n out of 6 arguments.
We closed with the suggestion that the standard next_permutation function might be an excellent example to follow and it is at this point that I mean to resume our study.
Evaluating every formula for a given template
Fortunately for us, we solved the second part of this task during our analysis of knots in a previous study [ Harris08 ]. The rotate_state and next_state functions which we used to iterate through every possible state of a set of sequential integer-like values are presented again in Listing 5.
template<class BidIt, class T>
bool
rotate_state(BidIt it, const T &lb, const T &ub)
{
bool last = ++*it==ub;
if(last) *it=lb;
return last;
}
template<class BidIt, class T>
bool
next_state(BidIt first, BidIt last,
const T &ub, const T &lb = T())
{
BidIt it = last;
while(it!=first && rotate_state(--it, lb, ub));
return first!=last && (it!=first || *it!=lb);
}
|
| Listing 5 |
Since iterators behave in a sequential integer-like fashion, we can place instances of our four RPN operators in a container and use next_state with the iterators ranging over it to generate every possible set of operators.
The third part is a little more complicated. The standard library already provides us with a function to iterate through every permutation of a strictly ordered set of values in next_permutation . Unfortunately, it does not give us a mechanism for iterating through the permutations of the subsets of such a set, so we shall have to knock one together ourselves.
Since next_permutation enumerates the permutations of the elements in the iterator range passed to it in lexicographical order, we can trick it into jumping past permutations of the elements not in the subset of interest. We do this by ensuring that they are in their lexicographically final order, thus forcing the next permutation to be the one that enumerates the next subset. Specifically we sort the spare elements in decreasing order, as illustrated in Listing 6.
template<class BidIt>
bool
next_permutation(BidIt first,
BidIt mid, BidIt last)
{
std::sort(mid, last);
std::reverse(mid, last);
return std::next_permutation(first, last);
}
|
| Listing 6 |
This new version of the next_permutation function thus enumerates the permutations of mid-first elements from the iterator range first to last in lexicographical order. Listing 7 shows how we would use this function to enumerate the set of permutations of two elements from a vector containing the integers 0 to 3.
std::vector<long> seq;
for(size_t i=0;i!=4;++i) seq.push_back(i);
std::vector<long>::iterator first = seq.begin();
std::vector<long>::iterator mid = seq.begin()+2;
std::vector<long>::iterator last = seq.end();
do
{
std::vector<long>::iterator it = first;
while(it!=mid) std::cout << *it++ << " ";
std::cout << std::endl;
}
while(next_permutation(first, mid, last));
|
| Listing 7 |
The output of this code snippet is given in Figure 3 and, as you can see, it correctly lists the permutations of two elements in lexicographically increasing order.
|
0 1
|
| Figure 3 |
Note that since we have implemented our new next_permutation function in terms of the standard one, we are subject to its restrictions. Specifically, the sequence cannot contain two or more elements with equivalent ordering. This condition shall not necessarily be met by the numbers we pick in the Countdown numbers game since there are two of each of the integers from 1 to 10. We shall sidestep this by instead considering permutations of iterators from a sequence of the selected numbers, which will guaranteed to be unique.
The major issue I have with this new overload is that it sorts the spare elements at every step, despite the fact that in a series of calls to it they are guaranteed to be sorted for all but the first call.
We can improve matters somewhat by first checking whether or not these elements are already sorted. Assuming we have n unused elements, this is at worst an n -step operation; hardly ideal, but certainly better than the worst case of the call to sort which is greater by a factor of the base 2 logarithm of n . We shall do this using another function, sorted , as illustrated in Listing 8. 1
template<class BidIt>
bool
sorted(BidIt first, BidIt last)
{
BidIt next = first;
if(next!=last) ++next;
while(next!=last && !(*next<*first)) {
++first; ++next;}
return next==last;
}
template<class BidIt>
bool
next_permutation(BidIt first, BidIt mid,
BidIt last)
{
if(!sorted(mid, last)) std::sort(mid, last);
std::reverse(mid, last);
return std::next_permutation(first, last);
}
|
| Listing 8 |
Whilst I'm sure that with some thought we could come up with something more efficient, the relative simplicity of this approach is enough to convince me to stick with it.
Enumerating the choice of numbers
Well, we're nearly ready to start investigating the properties of the Countdown numbers game in detail.
All that remains to do is to implement a mechanism for enumerating every way in which we might pick 6 numbers from the available 24. We don't care about their order since we shall be iterating through the permutations of the chosen numbers when we evaluate each function template. Hence we shall need to enumerate the combinations of 6 out of the 24 numbers.
We might as well shoot for a general purpose implementation along the lines of our next_permutation overload, as illustrated by the following declaration:
template<class BidIt> bool next_combination(
BidIt first, BidIt mid, BidIt last);
This function should transform the range first to mid to the lexicographically subsequent combination of mid-first elements from the range first to last . Furthermore, like next_permutation , it should, upon having exhausted the set of combinations, leave the range in a sorted state and return false .
An algorithm for enumerating combinations
Having trawled through my personal library for an algorithm to enumerate combinations in such a fashion, I unfortunately emerged empty handed. We shall therefore have to don the mantle of such luminaries as Knuth and Cormen et al and come up with an algorithm of our own.
The first thing we should note in seeking an algorithm to enumerate the combinations of a set is that combinations are subsets that are distinguished only by the elements that they contain and not by the order of those elements, as permutations are. To simplify their enumeration it therefore makes sense to keep the elements of the combinations in a particular order; specifically in increasing order.
To describe the algorithm, I shall use the example of enumerating the combinations of four of the integers from 1 to 6. Since we want the algorithm to act as much like the standard next_permutation function as possible, and hence work for any elements that can be strictly ordered, we must avoid all operations other than assignment, or strictly speaking swapping, and the less than operator.
We shall represent a permutation as a sequence of elements, with a bar separating the elements that are in the combination from those that are not. For example, the lexicographically first combination of four from six integers shall be represented as
1 2 3 4 | 5 6
The clue that nudges us in the direction of an effective algorithm is that fact that if we rotate the last three elements of the sequence one to the left, we generate the lexicographically subsequent combination
1 2 3 5 | 6 4
Doing so again generates the next combination
1 2 3 6 | 4 5
At this point applying the same operation will return us to a lexicographically earlier combination; the very first as it happens. Fortunately, we can identify that this is about to happen since the element after the bar is now less than the element before it.
What we need to do next is return the sequence to its original order and rotate the last four elements, yielding
1 2 4 5 | 6 3
And herein lays the basic principal by which our algorithm shall algorithmicate.
If the rotation of the last element in the combination would yield a lexicographically earlier sequence, we iterate backwards through the combination seeking an element for which we can rotate the following elements to return it and them to their lowest lexicographical order. We then rotate both it and them together to yield the lexicographically subsequent combination.
As an example, let us consider the combination
2 4 5 6 | 1 3
As we iterate back through the elements of the combination we find that the last element for which we can rotate subsequent the elements into an increasing order is in fact the first. Choosing the lexicographically earliest sequence we can thusly generate we have
2 3 4 5 | 6 1
Now rotating the first and subsequent elements yields
3 4 5 6 | 1 2
which is, as can easily be confirmed, the lexicographically next greatest combination.
The full enumeration of our example combinations would proceed as illustrated in Figure 4, in which we differentiate the valid combinations from the intermediate steps with a bold font and we identify the elements that we shall need to rotate by underlining them.
|
1 2 3
4
|
5
6
|
| Figure 4 |
Implementing our algorithm in C++
Now English is a pretty damn inconvenient language in which to describe algorithms, which is of course why Algol was invented. That said, this is ostensibly a C++ article and so, Algol be damned, we shall formally describe our algorithm in C++.
Before we can proceed to an implementation of the next_combination function, however, we shall need some helper functions.
As we did in our next_permutation overload, we shall need to check whether or not the input sequence represents a valid combination and if not, rearrange its elements so that it does. Again, the reason for performing the check first is that it is computationally less expensive than rearranging the elements and the sequence will always be a valid combination after the call to the function.
Specifically a valid combination will be sorted between first and mid , and from mid to last will be a rotation of the sorted elements such that either mid contains the next largest element than the one that precedes it, or that every element in the range is smaller than it.
Listing 9 illustrates the function that we shall use to check whether or not the sequence is a combination.
template<class BidIt>
bool
is_combination(BidIt first, BidIt mid, BidIt last)
{
if(mid==first || mid==last) return sorted(
first, last);
if(!sorted(first, mid)) return false;
BidIt prev = mid; --prev;
BidIt next = mid; ++next;
while(next!=last && !(*next<*mid)
&& *prev<*mid) {++mid;++next;}
if(next==last) return true;
if(*mid<*prev) return false;
++mid; ++next;
while(next!=last && !(*next<*mid)
&& !(*prev<*mid)) {++mid;++next;}
return next==last;
}
|
| Listing 9 |
We make a sequence into a combination by sorting the elements between first and mid and the elements between mid and last before finally rotating the latter so that the smallest of them that is greater than the last of the former is in mid .
Listing 10 provides the definition of the function that rearranges the elements into valid a combination.
template<class BidIt>
void
make_combination(BidIt first, BidIt mid,
BidIt last)
{
std::sort(first, mid);
std::sort(mid, last);
BidIt prev = mid;
if(prev!=first)
{
std::rotate(mid, std::upper_bound(
mid, last, *--prev), last);
}
}
|
| Listing 10 |
The final helper function that we shall need is one to find the smallest element in the range mid to last that is larger than the last in the range first to mid that is smaller than any of them. We cannot use upper_bound this time since the range will not, in general, be sorted. Listing 11 illustrates the function that we shall use to locate the element in question.
template<class BidIt, class T>
BidIt
min_greater(BidIt first, BidIt last, const T &t)
{
BidIt result = last;
while(first!=last)
{
if(t<*first && (
result==last || *first<*result))
result = first;
++first;
}
return result;
}
|
| Listing 11 |
We are now ready to implement the next_combination as shown in Listing 12. As you can clearly see, this is simply our algorithm directly translated into C++, with a few extra conditions to cover the corner cases of combinations of none or all of the elements in the sequence.
template<class BidIt>
bool
next_combination(BidIt first, BidIt mid,
BidIt last)
{
if(!is_combination(first, mid, last))
{
make_combination(first, mid, last);
}
if(mid==first || mid==last) return false;
BidIt next = mid;
BidIt prev = mid; --prev;
if(!(*prev<*next))
{
BidIt target = last;
while(target==last && prev!=first)
{
target = min_greater(mid, last, *--prev);
}
if(target==last)
{
std::rotate(first, mid, last);
return false;
}
next = prev; ++next;
std::rotate(next, target, last);
}
std::rotate(prev, next, last);
return true;
}
|
| Listing 12 |
Note that, like next_permutation , this function can't cope with sequences that contain multiple elements with equivalent orderings and will terminate before having enumerated the full set of combinations for such sequences.
Once again, I'm not entirely convinced that this is the most efficient possible algorithm. However, given that checking whether or not an input sequence of n elements is a combination requires at best n operations, and that our algorithm requires at worst a fixed multiple of n operations, I suspect that it could only be bettered by some constant factor.
Figure 5 illustrates the result of enumerating the set of combinations of four from the integers 1 to 6 using this function.
|
1 2 3 4
|
| Figure 5 |
But does it actually work?
Now, it's all well and good describing, implementing and demonstrating our algorithm, but we cannot be certain that it will work for all possible sets of combinations until we get on with the rather more tedious business of proving it. Fortunately for us, it's not too onerous a task.
The key point is in fact addressed by the is_combination function. If we can demonstrate that whenever a sequence satisfies this condition, our algorithm generates the lexicographically subsequent combination, and that the sequence representing it also satisfies the condition, then our work is done.
Representing a combination of r from n elements as
x 0 x 1 x 2 ... x i ... x i -1 | x r ... x j ... x n -1
where the i th element is the last that is smaller than any of those in the range r to n -1 and the j th is the smallest in that range that is larger than the i th.
Now if this is the very last combination, the elements r to n -1 must be smaller than the elements 0 to r -1 and both ranges must be in increasing order. Rotating the sequence so that the latter precede the former therefore returns us to the first combination.
If i is equal to r -1, then since our condition is assumed to be satisfied, j must be equal to r . Applying our algorithm therefore results in the sequence
x 0 x 1 x 2 ... x r | x r +1 ... x n -1 ... x r -1
This is trivially the lexicographically subsequent combination and must satisfy our condition. Indeed, if it did not, it would imply a contradiction since the r - 1 th element would have to be greater than both the r th and the n -1 th .
Otherwise, we can be certain that the i +1th to the r -1th elements must all be larger than the j th to the n -1th and that both sequences must be sorted in increasing order.
The first rotation we perform must therefore return the sequence to the lexicographically smallest with the i th element in its given position. Since this previous combination could not have been the lexicographically last, there must now be at least 1 element larger in the range r to n -1 that is larger than those in the range 0 to r -1. Most importantly, the r th element must be larger than the r -1th. The second rotation therefore results in the lexicographically subsequent combination. Furthermore, it too must satisfy our condition, since the before the second rotation the elements after the i th were in increasing order up to some element after the r -1th and the elements that follow those, if any, must be smaller than the i th.
QED.
I think .
I'll freely admit that this has been a somewhat handwaving attempt at a proof, and that I wouldn't be terribly surprised to learn that I've missed a corner case or two. Nevertheless, I believe that we can be reasonably confident that our algorithm will correctly enumerate any set of combinations and so we can happily use it to analyse the Countdown numbers game.
Putting it all together
Note that our formula template evaluation function expects vector s of pointers to rpn_operator objects and long integers, and we shall be using our choice enumeration functions with sequences containing iterators into these in order that their elements exhibit the strict ordering and integer-like behaviour that they require.
We shall therefore need a pair of functions to convert to and from vector s of values and vector s of iterators, as provided in Listing 13.
template<class FwdIt>
void
fill_iterator_vector(FwdIt first, FwdIt last,
std::vector<FwdIt> &vec)
{
vec.resize(std::distance(first, last));
std::vector<FwdIt>::iterator out = vec.begin();
while(first!=last) *out++ = first++;
}
template<class FwdIt, class T>
void
fill_dereference_vector(FwdIt first, FwdIt last,
std::vector<T> &vec)
{
vec.resize(std::distance(first, last));
std::vector<T>::iterator out = vec.begin();
while(first!=last) *out++ = **first++;
}
|
| Listing 13 |
To simplify the gathering of various forms of information regarding the numbers game, we shall take a leaf out of the STL's book and build a function template like the standard for_each to do the actual iteration and forward on the calculation to a function passed in as an argument.
We shall build this in two parts, the first of which iterates through the combinations of selections of numbers to work with, and the second of which iterates through every possible game that can be played with those numbers. By doing so we shall be able to examine the properties of both every possible game and any specific game.
Illustrated in Listing 14, the first of these functions expects four arguments. The first and last arguments represent the numbers from which we can choose our arguments, the args argument the number that we shall choose and finally the f argument the function we wish to apply to the result of every calculation.
template<class BidIt, class Fun>
Fun
for_each_numbers_game(BidIt first, BidIt last,
size_t args, Fun f)
{
std::vector<BidIt> number_choice;
fill_iterator_vector(first, last,
number_choice);
if(args>std::distance(first, last))
{
throw std::invalid_argument("");
}
std::vector<BidIt>::iterator first_choice
= number_choice.begin();
std::vector<BidIt>::iterator mid_choice
= first_choice+args;
std::vector<BidIt>::iterator last_choice
= number_choice.end();
do
{
f = for_each_numbers_game(first_choice,
mid_choice, f);
}
while(next_combination(first_choice,
mid_choice, last_choice));
return f;
}
|
| Listing 14 |
This function simply iterates through the combinations of args from our available numbers, passing the iterator range representing each of them together with the function to be called on to the second version of the function.
The second, significantly longer, function is illustrated in Listing 15. Note that this enumerates the permutations of arguments for each formula template using the iterator range representing the current choice of numbers. Since the next_permutation function will eventually return it to lexicographical order, we can be sure that at the end of this function, the full range into which they point will once again represent a valid combination.
The operation of this second function is reasonably straightforward. Firstly, it constructs the full set of formula templates and a collection of the available operators. It then iterates through every formula template, argument choice and operator choice, calculating the result of each function thus generated using temporary buffers into which the argument and operator choices are dereferenced, and calls our statistics gathering function for each valid result.
template<class BidIt, class Fun>
Fun
for_each_numbers_game(BidIt first_number_choice,
BidIt last_number_choice,
Fun f)
{
typedef
rpn_operator<long> const * operator_type;
typedef
std::vector<operator_type> operators_type;
typedef
operators_type::const_iterator
operator_iterator;
const size_t args =
std::distance(first_number_choice,
last_number_choice);
operators_type operators(4);
const rpn_add<long> add;
operators[0] = &add;
const rpn_subtract<long> subtract;
operators[1] = &subtract;
const rpn_multiply<long> multiply;
operators[2] = &multiply;
const rpn_divide<long> divide;
operators[3] = ÷
std::vector<operator_iterator> operator_choice(
args-1, operators.begin());
const std::set<std::string> templates(
all_templates(args));
operators_type used_operators;
std::vector<long> used_arguments;
std::set<std::string>::const_iterator
first_template = templates.begin();
std::set<std::string>::const_iterator
last_template = templates.end();
while(first_template!=last_template)
{
const size_t template_args = (
first_template->size()+1)/2;
do
{
fill_dereference_vector(first_number_choice,
first_number_choice+template_args,
used_arguments);
do
{
fill_dereference_vector(
operator_choice.begin(),
operator_choice.begin()
+template_args-1,
used_operators);
const rpn_result<long> result =
rpn_evaluate(*first_template,
used_operators, used_arguments);
if(result.valid) f(result.value);
}
while(next_state(operator_choice.begin(),
operator_choice.begin()+template_args-1,
operators.end(), operators.begin()));
}
while(next_permutation(first_number_choice,
first_number_choice+template_args,
last_number_choice));
++first_template;
}
return f;
}
|
| Listing 15 |
Unfortunately, however, I have spent so much time developing the tools with which we shall perform our analysis that I have run out of time in which we might actually do it.
So we shall have to wait until the next instalment before we can answer the question that we originally posed.
Until then, dear reader, farewell.
Acknowledgements
With thank to Keith Garbutt for proof reading this article.
References and further reading
[Countdown] http://www.channel4.com/programmes/countdown
[Harris08] Harris, R., The Model Student: A Knotty Problem, Overload 84, 2008.
1 The upcomingnew C++ standard library will in fact have an is_sorted function, but for now we must write our own.
