Generator of Befunge script for numbers using * and + operations written in C. Compile using gcc -lm -O3 -o polish_numbers polish_numbers.c

polish_numbers.c

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

typedef struct {
    unsigned char length;
    char op;
} best_rec_head;

typedef struct {
  int x;
  int y;
} best_rec_args;

typedef struct {
    best_rec_head *heads;
    best_rec_args *args;
    int max_in_length[256];
} cache;

#define max(a,b)                                                    \
    ({                                                              \
     typeof(a) __a = (a);                                           \
     typeof(b) __b = (b);                                           \
     __a > __b ? __a : __b;                                         \
     })

#define min(a,b)                                                    \
    ({                                                              \
     typeof(a) __a = (a);                                           \
     typeof(b) __b = (b);                                           \
     __a > __b ? __b : __a;                                         \
     })

cache init_cache(int n) {
  cache cache = {
      .heads = (best_rec_head *)calloc(max(10, n+1), sizeof(best_rec_head)),
      .args = (best_rec_args *)calloc(n+1, sizeof(best_rec_args)),
      .max_in_length = {1, 9}
  };
  int i;
  for(i=0; i<10; i++) {
    cache.heads[i].op = i;
    cache.heads[i].length = 1;
  }
  return cache;
}

void destroy_cache(cache cache) {
    free(cache.heads);
    free(cache.args);
    cache.heads = (best_rec_head *)NULL;
    cache.args = (best_rec_args *)NULL;
}

unsigned char concat(cache cache, int dest, int x, int y, char op) {
  cache.heads[dest].op = op;
  cache.args[dest].x = x;
  cache.args[dest].y = y;
  return cache.heads[dest].length = cache.heads[x].length + cache.heads[y].length + 1;
}

static inline int possible(cache cache, int maxi, int n, unsigned char best_len) {
    unsigned char k;
    for(k = 1; k < best_len; k++)
        if(maxi + cache.max_in_length[k] >= n)
            return 1;
    return 0;
}

#define unlikely(expr)   (__builtin_expect((expr) != 0, 0))

unsigned char gen(cache cache, int n) {
  int j;
  unsigned char best_len;
  for(j = 10; j <= n; j++) {
    best_len = 255;
    int mini, i, d, maxi;
    unsigned char li, x;
    for(i = 2, maxi = floor(sqrt(j)); i <= maxi; i++){
      if unlikely( j % i == 0 && (cache.heads[i].length + cache.heads[d = j/i].length + 1 < best_len))
        best_len = concat(cache, j, i, d, '*');
    }
    mini = 1;
    for(x = 1; x <= best_len - 2; x++) {
        maxi = cache.max_in_length[x];
        if(possible(cache, maxi, j, best_len - x - 1))
            for(i = mini, maxi = min((j-1)/2, maxi); i <= maxi; i++){
              if unlikely(cache.heads[i].length + cache.heads[d = j-i].length + 1 < best_len)
                best_len = concat(cache, j, i, d, '+');
            }
        mini = maxi + 1;
    }
    cache.max_in_length[best_len] = j;
  };
  return best_len;
}

char *str_result(cache cache, char *str, int n) {
  if(cache.heads[n].op < 10) {
    *str++ = cache.heads[n].op + '0';
    return str;
  }
  str = str_result(cache, str, cache.args[n].x);
  str = str_result(cache, str, cache.args[n].y);
  *str++ = cache.heads[n].op;
  return str;
}

int generate(int n, char *result) {
  cache cache = init_cache(n);
  int len = gen(cache, n);
  *(str_result(cache, result, n))=0;
  destroy_cache(cache);
  return len;
}

int usage(const char *name) {
    fprintf(stderr, "Usage: %s number\n", name);
    return 1;
}

char result[100];

int main(int argc, const char* argv[] ) {
  const char *name = argv[0];
  char *tmp;
  int i, l;
  if(argc != 2) return usage(name);
  i = strtol(argv[1], &tmp, 10);
  if(*tmp != '\0' || i < 0) return usage(name);
  l = generate(i, result);
  printf("Result for %d: %s, length %d\n", i, result, l);
  return 0;
}