Programming solution to the GCHQ puzzle on BBC Radio 4, Mon 3rd July 2017

gchq-puzzle.c

/**
 * Programming solution to the GCHQ puzzle on BBC Radio 4, Mon 3rd July 2017
 * http://www.bbc.co.uk/programmes/articles/5wkxjTtqRvq8Cyrrjxtk7tc/puzzle-for-today
 *
 * Output:
 * 4 -> 123+45-67+8-9
 * 4 -> 123+4-5+67-89
 * 3 -> 123-45-67+89
 * 6 -> 123-4-5-6-7+8-9
 * 6 -> 12+3+4+5-6-7+89
 * 6 -> 12+3-4+5+67+8+9
 * 6 -> 12-3-4+5-6+7+89
 * 6 -> 1+23-4+56+7+8+9
 * 6 -> 1+23-4+5+6+78-9
 * 6 -> 1+2+34-5+67-8+9
 * 7 -> 1+2+3-4+5+6+78+9
 */

#include <stdio.h>

// These are the three possible operations that can occur between the digits (nothing, + and -).
// Now we can represent every possible solution as 8 of these operations between each of the 9 digits.
#define OP_NONE 0
#define OP_ADD 1
#define OP_SUB 2

// This function will take the 8 operations and work out the value of the resultant expression
int evaluate_operations(int operations[8])
{
  int total, digit, carry, last_operation;

  for (total = 0, digit = 1, carry = 0, last_operation = OP_ADD; digit <= 9; digit++) {
    carry *= 10;
    carry += digit;

    if (digit == 9 || OP_NONE != operations[digit - 1]) {
      if (OP_ADD == last_operation) {
        total += carry;
        carry = 0;
      } else if (OP_SUB == last_operation) {
        total -= carry;
        carry = 0;
      }

      if (digit <= 8) {
        last_operation = operations[digit - 1];
      }
    }
  }

  return total;
}

// This function will take the operations and then print them to the standard output
void print_operations(int operations[8])
{
  int digit;

  for (digit = 1; digit <= 9; digit++) {
    printf("%d", digit);

    if (operations[digit - 1] == OP_ADD) {
      putchar('+');
    } else if (operations[digit - 1] == OP_SUB) {
      putchar('-');
    }
  }

  putchar('\n');
}

// This will take a set of operations and modify them to the next potential solution
// e.g.
// 123456789 -> 12345678+9
// 12345678+9 -> 12345678-9
// 12345678-9 -> 1234567+89
// ...
// 1-2-3-4-5-6-7-8+9 -> 1-2-3-4-5-6-7-8-9
int increment_operations(int operations[8], int index)
{
  if (operations[index] != OP_SUB) {
    operations[index]++;
    return 1;
  } else if (index > 0) {
    operations[index] = OP_NONE;
    return increment_operations(operations, index - 1);
  }

  return 0;
}

// This will count the number of actual operations (not OP_NONE) used in a solution
int count_operations(int operations[8])
{
  int count = 0, i;

  for (i = 0; i < 8; i++) {
    if (operations[i] != OP_NONE) {
      count++;
    }
  }

  return count;
}

int main(int argc, char *argv[])
{
  // Start with the "smallest" solution
  int operations[8] = { OP_NONE, OP_NONE, OP_NONE, OP_NONE, OP_NONE, OP_NONE, OP_NONE, OP_NONE };

  // Test every operation plausible, print the ones that evaluate to 100
  do {
    int result = evaluate_operations(operations);

    if (result == 100) {
      printf("%d -> ", count_operations(operations));
      print_operations(operations);
    }
  } while (increment_operations(operations, 7));

  return 0;
}