1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

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

// These values are used to print the progress
mpz_t poss;
mpz_t curr;

// Checks a string to see if it's valid brainfuck
// Note: All you really need to do is check if ['s and ]'s cancel one another out
// and that no ] appears before a matching [
int valid_bf(int *bf) {
    int loop = 0;
    while (*bf != -1) {
        if (*bf == 6)
            loop++;
        else if (*bf == 7) {
            if (loop == 0)
                return 0;
            loop--;
        }
        bf++;
    }
    return !loop;
}

// Converts an array of ints to a string (actual brainfuck)
// Note: not used.
char *createbf(int len, int *nums) {
    static const char bfchars[] = { ',', '.', '+', '-', '<', '>', '[', ']' };
    char *ret = calloc(len+1, sizeof(char));
    int i;
    for (i = 0; nums[i] != -1; i++) {
        ret[i] = bfchars[nums[i]];
    }
    return ret;
}

// Increases the number. Basically, we're using a base 8 number to represent brainfuck.
void incr(int *nums) {
    if (*nums == -1) {
        return;
    } else {
        *nums += 1;
        if (*nums == 8) {
            *nums = 0;
            incr(nums+1);
        }
    }
}

// Actually generate and test every possible brainfuck program (brute-force)
mpz_t *howmany(int num) {
    int *bla = calloc(num+1, sizeof(int));
    int *bla2 = calloc(num+1, sizeof(int));
    bla[num] = -1;
    bla2[num] = -1;
    mpz_t *retval = malloc(sizeof(mpz_t));
    mpz_init(*retval);
    int i;

    for (i = 0; i < num; i++) {
        bla2[i] = 7;
    }

    while (1) {
        mpz_add_ui(curr, curr, 1);
        if (valid_bf(bla))
            mpz_add_ui(*retval, *retval, 1);
        if (!memcmp(bla,bla2,num*sizeof(int))) {
            break;
        }
        incr(bla);
    }

    return retval;
}

// Signal handler for SIGUSR1
// Prints the progress that has been made thus far
void sigusr1(int signal) {
    printf("\n");
    mpz_out_str(NULL, 10, curr);
    printf("/");
    mpz_out_str(NULL, 10, poss);
    printf("--->");
    mpz_t bla;
    mpz_init(bla);
    mpz_mul_ui(bla, curr, 100);
    mpz_tdiv_q(bla, bla, poss);
    mpz_out_str(NULL, 10, bla);
    mpz_clear(bla);
    printf("%%");
    printf("\n");
}

int main(int argc, char **argv) {
    mpz_init(poss);
    mpz_init(curr);
    signal(SIGUSR1, sigusr1);
    int i;
    if (argc != 2) {
        return 0;
    }
    sscanf(argv[1], "%d", &i);
    mpz_ui_pow_ui(poss, 8, i);
    mpz_t *bla = howmany(i);
    printf("Possible brainfuck programs with a length of %d: ", i);
    mpz_out_str(stdout, 10, *bla);
    printf("\n");
    mpz_clear(*bla);

    return 0;
}