Move sticks to keep equations true

stick-1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


const char *digits[] =
{
  "1110111",
  "0100100",
  "1011101",
  "1101101",
  "0101110",
  "1101011",
  "1111011",
  "0100101",
  "1111111",
  "1101111"
};


void int2digits(const char *num, char *s)
{
  for(int i = 0; num[i] != '\0'; i++, s += 7) {
    strncpy(s, digits[num[i] - '0'], 7);
  }
}


int digit2int(const char *s, const char **next)
{
  int val = 0;
  while (!(*s == ';' || *s == '\0')) {
    int found = 0;
    for (int i = 0; i <= 9; i++) {
      if (strncmp(s, digits[i], 7) == 0) {
        found = 1;
        val = val * 10 + i;
        s += 7;
        break;
      }
    }
    if (!found) return -1;
  }

  if (next != NULL)
    *next = s;
  return val;
}


void check_formula(const char *formula, const char *origin, char op)
{
  if (strcmp(formula, origin) == 0) return;

  const char *next = formula;
  int left = digit2int(next, &next);
  int right = digit2int(next + 1, &next);
  int result = digit2int(next + 1, &next);

  // printf("check %s: %d - %d = %d\n", formula, left, right, result);
  if (left < 0 || right < 0 || result < 0) return;

  if (op == '+' ? (left + right == result) : (left - right == result)) {
    printf("%d - %d = %d\n", left, right, result);
  }
}


void move_in(char *formula, const char *origin, int avail_matches, int beg, char op)
{
  if (avail_matches == 0) {
    check_formula(formula, origin, op);
    return;
  }

  for (int i = beg; formula[i] != '\0'; i++) {
    if (formula[i] == '0') {
      formula[i] = '1';
      // printf("try move in %d: %s\n", avail_matches, formula);
      move_in(formula, origin, avail_matches - 1, i + 1, op);
      formula[i] = '0';
    }
  }
}


void move_out(char *formula, const char *origin, int required_matches, int total_matches, int beg, char op)
{
  if (required_matches == 0) {
    move_in(formula, origin, total_matches, 0, op);
    return;
  }

  for (int i = beg; formula[i] != '\0'; i++) {
    if (formula[i] == '1') {
      formula[i] = '0';
      // printf("try move out %d: %s\n", required_matches, formula);
      move_out(formula, origin, required_matches - 1, total_matches, i + 1, op);
      formula[i] = '1';
    }
  }
}


void sticks(char *equation, const char *origin, int n_sticks, char op)
{
  move_out(equation, origin, n_sticks, n_sticks, 0, op);
}


int main()
{
  char n[11], m[11], r[11];
  char op;
  int cnt;
  scanf("%s %c %s = %s %d", &n, &op, &m, &r, &cnt);
  int len_n = strlen(n) * 7, len_m = strlen(m) * 7, len_r = strlen(r) * 7;
  char *s = malloc(len_n + len_m + len_r + 2 + 1);
  *(s + len_n) = ';';
  *(s + len_n + 1 + len_m) = ';';
  *(s + len_n + 1 + len_m + 1 + len_r * 7) = '\0';
  int2digits(n, s);
  int2digits(m, s + len_n + 1);
  int2digits(r, s + len_n + 1 + len_m + 1);
  sticks(strdup(s), s, cnt, op);
}