// The 'Carol Vorderman' solver for Countdown.
// Written is a style that should make it easy to convert into Scratch...
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> // for 'isdigit' in argv processing.
#ifndef TRUE
#define TRUE (0==0)
#define FALSE (0!=0)
#endif
#define NUM 0
#define OP 1
#define OP_ADD 1
#define OP_SUBTRACT 2
#define OP_MULTIPLY 3
#define OP_DIVIDE 4
#define OP_END 5
#define SIX 7 // :-)
#define ELEVEN 12 // little joke here, it's to allow for C's 0-based arrays vs Scratch's 1-based arrays
int last_rp_item = 0;
int num_or_op_val[ELEVEN]; // max size is 6 nums + 5 ops - may use fewer ops if balanced tree
int num_or_op_type[ELEVEN];
int selection[SIX];
int target;
// remove the 0th element of initialised arrays when converting to Scratch:
int order[] = { 0, 1, 2, 3, 4, 5, 6 }; // this indexes 'selection', and is shuffled by 'permute'
char *opstr[] = { "", "+", "-", "*", "/" };
int nums_emitted = 0;
int invalid;
int seeking = TRUE;
float stack[SIX];
int eval_stack_ptr;
void push(float f) {
stack[++eval_stack_ptr] = f;
}
float pop(void) {
return stack[eval_stack_ptr--];
}
static float a, b;
void operate(int op, int io) {
b = pop();
a = pop(); // order needed for - and /
if (op == OP_ADD) {
push(a+b);
} else if (op == OP_SUBTRACT) {
if (a <= b) {
push(1.0);
invalid = TRUE;
} else push(a-b); // negative results disallowed, also subtractions that result in 0? (See 'simcarol')
} else if (op == OP_MULTIPLY) {
if ((a == 1.0) || (b == 1.0)) {
push(1.0);
invalid = TRUE;
} else push(a*b); // banning * 1 or / 1 makes for more interesting solutions
} else if (op == OP_DIVIDE) {
if ((b == 0.0) || (b == 1.0)) {
push(1.0);
invalid = TRUE;
} else {
push(a/b);
if (stack[eval_stack_ptr] - (float)((int)stack[eval_stack_ptr]) != 0.0) invalid = TRUE;
}
}
if (io) printf("%d %s %d = %d\n", (int)a, opstr[op], (int)b, (int)stack[eval_stack_ptr]);
}
static float eval_result;
static int eval_i;
void eval(int io) {
eval_stack_ptr = 0; // reset evaluation stack ptr in case a previous calculation left the stack unbalanced by setting 'invalid' and exiting
for (eval_i = 1; eval_i <= last_rp_item; eval_i++) {
if (num_or_op_type[eval_i] == NUM)
push((float)num_or_op_val[eval_i]);
else
operate(num_or_op_val[eval_i], io);
}
eval_result = stack[eval_stack_ptr];
}
static int operator;
static int operator_stack[SIX];
static int operator_sp = 0;
void compute(int rp_index, int nextnum) {
// try all operators in all positions when we have an operator on the RP stack
operator_sp += 1;
operator_stack[operator_sp] = operator;
if (rp_index <= last_rp_item) {
if (num_or_op_type[rp_index] == NUM) {
num_or_op_val[rp_index] = selection[order[nextnum]];
compute(rp_index+1, nextnum+1);
} else {
for (operator = OP_ADD; operator != OP_END; operator++) {
num_or_op_val[rp_index] = operator;
compute(rp_index+1, nextnum);
}
}
} else {
invalid = FALSE;
eval(FALSE);
if ((!invalid) && (eval_result == (float)target)) {
eval(TRUE);
seeking = FALSE;
}
}
operator = operator_stack[operator_sp];
operator_sp -= 1;
}
static int permute_j; // this needs to be translated carefully into Scratch - keep a stack for the j's
static int permute_j_stack[SIX];
static int permute_j_sp = 0;
static int swap;
void permute(int i, int n) { // calc all orderings of 6 items
permute_j_sp += 1; // trick to support recursion in Scratch
permute_j_stack[permute_j_sp] = permute_j;
if (i == n) compute(0, 1); else {
for (permute_j = i; permute_j <= n; permute_j++) {
if (seeking) {
swap = order[i];
order[i] = order[permute_j];
order[permute_j] = swap;
permute(i+1, n);
swap = order[i];
order[i] = order[permute_j];
order[permute_j] = swap;
}
}
}
permute_j = permute_j_stack[permute_j_sp];
permute_j_sp -= 1;
}
static int virtual_stack_depth = 0; // no of items that would be on the stack when evaluating the RP at this position
void undo(int num_or_op) {
if (num_or_op == NUM) {
nums_emitted -= 1;
virtual_stack_depth -= 1;
} else {
virtual_stack_depth += 1; // - 1 (rslt) + 2 (opds)
}
last_rp_item -= 1;
}
void emit(int num_or_op) {
last_rp_item += 1;
if ((num_or_op) == NUM) {
nums_emitted += 1;
virtual_stack_depth += 1;
} else {
virtual_stack_depth -= 1;
}
num_or_op_type[last_rp_item] = num_or_op;
}
void generate_rp_formulae(int max) { // generate all the valid RP expressions for 6 variables
if (seeking) {
if (nums_emitted == max) {
if (virtual_stack_depth == 1) { // we've output enough ops to calculate the result
permute(1, max);
} else {
emit(OP);
generate_rp_formulae(max);
undo(OP); // need more ops
}
} else {
if (virtual_stack_depth >= 2) {
emit(OP);
generate_rp_formulae(max);
undo(OP);
}
emit(NUM);
generate_rp_formulae(max);
undo(NUM); // haven't used all nums yet (must we?)
}
}
}
static int i;
int main(int argc, char **argv)
{
if (argc != 8) {
fprintf(stderr, "syntax: %s target n1 n2 n3 n4 n5 n6\n", argv[0]);
exit(1);
}
if (!isdigit(*argv[1])) {
fprintf(stderr, "carol: the target must be a number. (\"%s\" isn't)\n", argv[1]); exit(1);
} else {
target = atol(argv[1]);
}
// probably better to use strtol than atol, to check for characters after the integer part
if (target < 100 || target >= 1000) {
fprintf(stderr, "carol: the target must be a 3-digit number. (\"%s\" isn't)\n", argv[1]); exit(1);
}
for (i = 0; i < 6; i++) {
if (!isdigit(*argv[i+2])) {
fprintf(stderr, "carol: all arguments must be numbers. (\"%s\" isn't)\n", argv[i+2]); exit(1);
}
selection[i+1] = atol(argv[i+2]);
if (selection[i+1] <= 0 || selection[i+1] >= 100) {
fprintf(stderr, "carol: the numbers must be between 1 and 99. (\"%s\" isn't)\n", argv[i+2]); exit(1);
}
}
printf("Target: %d\n", target);
printf("Numbers: %d %d %d %d %d %d\n", selection[1],selection[2],selection[3],selection[4],selection[5],selection[6]);
for (i = 2; i < 6; i++) {
if (seeking) generate_rp_formulae(i); // we assume the target number is not trivially in the selection!
}
if (!seeking) exit(0);
printf("No exact solution found! I haven't yet written the code to remember the next closest solution, sorry.\n");
exit(2);
}