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

#define MAX_SIZE 16
#define MAX_SYMBOLS 32

#define COUNTER_SIZE 4

typedef unsigned long counter[COUNTER_SIZE];

static void
clear_counter(counter *c) {
    int i;
    for (i = 0; i < COUNTER_SIZE; i++) (*c)[i] = 0;
}

static void
add_counter(counter *c, counter *inc) {
    int carry;
    int i;
    for(i = 0, carry = 0; i < COUNTER_SIZE; i++) {
        if (carry)
            if (++((*c)[i]))
                carry = 0;
        (*c)[i] += (*inc)[i];
        if ((*c)[i] < (*inc)[i])
            carry = 1;
    }
}

static void
inc_counter(counter *c) {
    int i;
    for (i = 0; i < COUNTER_SIZE; i++) {
        if (++(*c)[i]) return;
    }
}

static int
non_zero_counter(counter *c) {
    int i;
    for (i = 0; i < COUNTER_SIZE; i++) {
        if ((*c)[i]) return 1;
    }
    return 0;
}

static void
print_counter(counter *c) {
    int i;
    for (i=COUNTER_SIZE; i-- > 0;) {
        printf("%016lx", (*c)[i]);
    }
}

static double
calc_count_size(int size, int symbols) {
    double count_size = 1;
    int i;
    for (i = 1; i <= size; i++) 
        count_size *= 2 * (i < symbols ? i : symbols);
    // printf("count_size: %f\n", count_size);
    return count_size;
}

static int
st_to_ix(signed char *st_new, signed char *st_old, int size, int symbo
+ls) {
    signed char seen[MAX_SYMBOLS];
    int i;
    int m;
    int s;
    int ix;
    int top;

    for (i = 0; i < symbols; i++) seen[i] = -1;

    for (ix = 0, top = 0, i = 0; i < size; i++) {
        m = (i < symbols ? i + 1: symbols);
        ix *= 2 * m;
        s = st_new[i];
        if (s == st_old[i])
            ix += m;
        ix += (seen[s] >= 0 ? seen[s] : (seen[s] = top++));
    }
    /*
    if (d) {
        for (i = 0; i < size; i++) {
            printf("%c", (st[i] & 127) + (st[i] < 0 ? 'a' : 'A'));
        }
        printf(" ");
        for (i = 0; i < size; i++) {
            printf("%c", (seen[st[i] & 127]) + (st[i] < 0 ? 'a' : 'A')
+);
        }
        printf(" %8d\n", ix);
    }
    */
    return ix;
}

static void
ix_to_st(int ix, int size, int symbols, signed char *st, signed char *
+dups) {
    int i;
    int m;
    for (i = size; i > 0;) {
        m = (i < symbols ? i : symbols);
        st[--i] = ix % m;
        ix /= m;
        dups[i] = ix & 1;
        ix >>= 1;
    }

    /*
    int ix2 = st_to_ix(st, size, symbols);
    if (ix != ix2) {
        printf("bad conversion %d => ", ix);
        for (i = 0; i < size; i++)
            printf("%c", (st[i] & 127) + (st[i] < 0 ? 'a' : 'A'));
        printf(" => %d\n", ix2);
        // st_to_ix(st, size, symbols, 1);
    }
    */
    //else
    //    printf(".");
}

static void
dump_old_count(int count_size, counter *old_count) {
    int i;
    printf("old_count dump:\n");
    for (i = 0; i < count_size; i++) {
        printf("%8d: ", i);
        print_counter(old_count + i);
        printf("\n");
    }
    printf("\n");
}

static int
check_st_hor(signed char *st, int size) {
    int last;
    int reps;
    int i;
    for (reps = 1, last = st[0], i = 1; i < size; i++) {
        if (st[i] == last) {
            if (++reps > 2)
                return 0;
        }
        else {
            last = st[i];
            reps = 1;
        }
    }
    return 1;
}

static int
check_st_ver(signed char *st_new, signed char *st_old, signed char *du
+ps, int size) {
    int i;
    for (i = 0; i < size; i++) {
        if (dups[i] && (st_new[i] == st_old[i]))
            return 0;
    }
    return 1;
}

static void
dump_st(char *name, signed char *st, signed char *dups, int size) {
    int i;
    printf("%s: ", name);
    for (i = 0; i < size; i++) {
        printf("%c", st[i] + (dups[i] ? 'a' : 'A'));
    }
    printf("\n");
}

static void
init_old_count(int size, int symbols, counter *old_count) {
    int i;
    signed char st_new[MAX_SIZE];
    signed char st_old[MAX_SIZE];
    int ix;
    for (i = 0; i < size; i++) {
        st_new[i] = 0;
        st_old[i] = -1;
    }

    while (1) {
        ix = st_to_ix(st_new, st_old, size, symbols);
        if (check_st_hor(st_new, size))
            inc_counter(old_count + ix);
        for (i = 0; i < size; i++) {
            if (++st_new[i] < symbols)
                break;
            st_new[i] = 0;
        }
        if (i == size)
            break;
    }
}

static void
calc_new_count(int size, int symbols, int count_size, counter *old_cou
+nt, counter *new_count) {
    int i, j;
    signed char st_old[MAX_SIZE];
    signed char st_new[MAX_SIZE];
    signed char dups[MAX_SIZE];

    memset(new_count, 0, count_size * sizeof(counter));
  
    for (i = 0; i < count_size; i++) {
        if (non_zero_counter(old_count + i)) {
            ix_to_st(i, size, symbols, st_old, dups);
            for (j = 0; j < size; j++) st_new[j] = 0;

            while (1) {
                if (check_st_hor(st_new, size)) {
                    // dump_st("old", st_old, size);
                    // dump_st("new", st_new, size);
                    if (check_st_ver(st_new, st_old, dups, size))
                        add_counter(new_count + st_to_ix(st_new, st_ol
+d, size, symbols), old_count + i);
                }

                for (j = 0; j < size; j++) {
                    if (++st_new[j] < symbols)
                        break;
                    st_new[j] = 0;
                }
                if (j == size)
                    break;
            }
        }
    }
}

int
main (int argc, char *argv[]) {
    int size;
    int symbols;
    counter *old_count;
    counter *new_count;
    double count_size;
    int i;
    counter count;

    if (argc != 3) {
        fprintf(stderr, "Usage:\n pc size symbols\n");
        exit(1);
    }

    size = atoi(argv[1]);
    symbols = atoi(argv[2]);

    if (size >= MAX_SIZE || symbols >= MAX_SYMBOLS) {
        fprintf(stderr, "bad parameters\n");
        exit(1);
    }

    count_size = calc_count_size(size, symbols);

    if (count_size > (2 << 28)) {
        fprintf(stderr, "required count_size is too big: %f\n", count_
+size);
        exit(1);
    }

    old_count = (counter*)calloc(count_size, sizeof(counter));
    new_count = (counter*)calloc(count_size, sizeof(counter));

    if (!old_count || !new_count) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }

    init_old_count(size, symbols, old_count);

    // dump_old_count(count_size, old_count);

    for (i = 1; i < size; i++) {
        calc_new_count(size, symbols, count_size, old_count, new_count
+);
        counter *tmp = old_count;
        old_count = new_count;
        new_count = tmp;
        // dump_old_count(count_size, old_count);
    }

    clear_counter(&count);
    for (i = 0; i < count_size; i++)
        add_counter(&count, old_count + i);

    printf("the number of patterns is: ");
    print_counter(&count);
    printf("\n");
}
[download]

$ time ./pc 6 6
the number of patterns is: 000000000000000000000000000000000000000009d
+b3f0a5d231378f10a55ce

real    2m17.757s
user    2m17.520s
sys    0m0.100s

$ time ./pc 6 5
count_size: 38400.000000
the number of patterns is: 0000000000000000000000000000000000000000000
+21fc250b0d1218438d068

real    0m43.734s
user    0m43.450s
sys    0m0.040s

$ time ./pc 6 4
the number of patterns is: 0000000000000000000000000000000000000000000
+00011acd983d60a9fc37c

real    0m9.712s
user    0m9.680s
sys    0m0.000s

$ time ./pc 7 4
the number of patterns is: 0000000000000000000000000000000000000000157
+14ebbb97b7e0882fef50c

real    6m21.945s
user    6m20.710s
sys    0m0.260s

$ time ./pc 7 6
the number of patterns is: 00000000000000000000000000000000115617f50b0
+79b929aa76ddab1b0e24e

real    139m55.016s
user    139m29.330s
sys    0m7.910s
[download]