2 ms·
This is an extended version of the numbers game on the UK TV gameshow Countdown, which is itself based off of a French gameshow (I don't know the details of it,
by barrkel 15y ago
This is an extended version of the numbers game on the UK TV gameshow Countdown, which is itself based off of a French gameshow (I don't know the details of it, though).
I had to solve this version of the problem once upon a time in a programming competition. I approached it slightly differently than this article; I implemented a RPN stack machine evaluator, and a recursive routine which permuted first over operators, then operands; the core routine looked like this:
static int FindSolutions(int[] numbers, int numberIndex, int stackDepth)
{
int result = 0;
if (stackDepth == 1)
if (Evaluate(g_program.Program) == g_target)
++result;
// Try the operators (all are binary here)
if (stackDepth > 1)
{
for (OpCode opCode = OpCode.Add; opCode <= OpCode.Div; ++opCode)
{
g_program.Push(opCode);
result += FindSolutions(numbers, numberIndex, stackDepth - 1);
g_program.Pop();
}
}
if (numberIndex < numbers.Length)
{
// Try each number
for (int i = numberIndex; i < numbers.Length; ++i)
{
Swap(numbers, numberIndex, i);
g_program.Push(numbers[numberIndex]);
result += FindSolutions(numbers, numberIndex + 1, stackDepth + 1);
g_program.Pop();
Swap(numbers, numberIndex, i);
}
// Try without the number
result += FindSolutions(numbers, numberIndex + 1, stackDepth);
}
return result;
}
If you know that g_program is writing the RPN program as a stack itself (so it can easily push and pop the last instruction), I think it's reasonably easy to follow.