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

#define MAX_SIZE 8
#define MAX_SYMBOLS 8

#define COUNTER_SIZE 3

typedef unsigned long counter[COUNTER_SIZE];

static void
clear_counter(counter *c) {
    memset(c, 0, sizeof(*c));
}

static void
add_counter(counter *c, counter *inc) {
    int i = COUNTER_SIZE;
    unsigned long carry = 0;
    while (i--) {
    unsigned long v = (*c)[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 = COUNTER_SIZE;
    while (i--) {
        if (++(*c)[i])
        return;
    }
}

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

static void
print_counter(counter *c) {
    int i;
    for (i = 0; i < COUNTER_SIZE; i++) {
        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(char *st_new, char *st_old, int size, int symbols) {
    char seen[MAX_SYMBOLS];
    int m, j, s, ix, top;

    memset(seen, -1, MAX_SYMBOLS);

    ix = 0;
    j = size;
    while (j--) {
    ix <<= 1;
    ix += (st_new[j] == st_old[j]);
    }

    top = 1;
    m = 1;
    j = size - 1;
    seen[st_new[j]] = 0;

    while (j--) {
    if (m < symbols) m++;
    ix *= m;
    s = st_new[j];
        ix += (seen[s] >= 0 ? seen[s] : (seen[s] = top++));
    }
    return ix;
}

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

st_to_ix_sym(char *st_new, char *dups, int size, int symbols) {
    char seen[MAX_SYMBOLS];
    int ix, i, j, s, top;

    memset(seen, -1, MAX_SYMBOLS);

    ix = 0;
    j = size;
    while (j--) {
    ix <<= 1;
    ix += dups[j];
    }

    top = 1;
    i = 1;
    j = size - 1;
    seen[st_new[j]] = 0;

    while (j--) {
    i++;
    ix *= (i < symbols ? i : symbols);
    s = st_new[j];
    ix += (seen[s] >= 0 ? seen[s] : (seen[s] = top++));
    }
    return ix;
}

static void
collapse_symmetric(int size, int symbols, int count_size, counter *old
+_count) {
    char st[MAX_SIZE];
    char dups[MAX_SIZE];
    int sym_ix;

    // for (i = 0; i < count_size; i++) {
    int i = count_size;
    while (i--) {
        if (non_zero_counter(old_count + i)) {
            ix_to_st(i, size, symbols, st, dups);
            sym_ix = st_to_ix_sym(st, dups, size, symbols);
            if (sym_ix != i) { 
                add_counter(old_count + i, old_count + sym_ix);
                clear_counter(old_count + sym_ix);
            }
        }
    }
}

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(char *st, int size, int symbols) {
    int i, last, reps;
    for (reps = 1, last = st[0], i = 1; i < size; i++) {
        if (st[i] == last) {
            if (++reps > 2) {
                for (i -= 2; i-- > 0;)
            st[i] = symbols - 1;
        return 0;
        }
        }
        else {
            last = st[i];
            reps = 1;
        }
    }
    return 1;
}

static void
dump_st(char *name, char *st, 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
check_st_to_ix(int ix, char *st_new, char *st_old, int size, int symbo
+ls) {
    char st_new1[MAX_SIZE];
    char seen[MAX_SIZE];
    char dups[MAX_SIZE];
    char st_undo[MAX_SIZE];
    char dups_undo[MAX_SIZE];
    int i, top;
    memset(seen, -1, MAX_SIZE);
    for (top = 0, i= 0; i < size; i++) {
    int s = st_new[i];
    st_new1[i] = (seen[s] >= 0 ? seen[s] : (seen[s] = top++));
    }
    ix_to_st(ix, size, symbols, st_undo, dups_undo);
    for (i = 0; i < size; i++)
    dups[i] = (st_new[i] == st_old[i] ? 1 : 0);
    if (memcmp(st_new1, st_undo, size) || memcmp(dups, dups_undo, size
+)) {
    printf("st differ, ix=%d\n", ix);
    dump_st("original", st_new, dups, size);
    dump_st("  before", st_new1, dups, size);
    dump_st("   after", st_undo, dups_undo, size);
    }
}


static void
init_old_count(int size, int symbols, counter *old_count) {
    int i;
    char st_new[MAX_SIZE];
    char st_old[MAX_SIZE];
    int ix;

    memset(st_old, -1, MAX_SIZE);
    memset(st_new, 0, MAX_SIZE);
    
    while (1) {
        ix = st_to_ix(st_new, st_old, size, symbols);
    // check_st_to_ix(ix, st_new, st_old, size, symbols);

        if (check_st_hor(st_new, size, symbols))
            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, ix;
    char st_old[MAX_SIZE];
    char st_new[MAX_SIZE];
    char dups[MAX_SIZE];
    int pass;

    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);
        memset(st_new, symbols - 1, size);
        pass = 0;
            while (1) {
                for (j = 0; j < size; j++) {
            if (dups[j]) {
            st_new[j]++;
            if (st_new[j] == st_old[j])
                st_new[j]++;
            if (st_new[j] < symbols)
                goto check_row;
            st_new[j] = (st_old[j] ? 0 : 1);
            }
            else {
            if (++st_new[j] < symbols)
                goto check_row;
            st_new[j] = 0;
            }
                }
                if (pass++)
                    break;

        check_row:
                if (check_st_hor(st_new, size, symbols)) {
            ix = st_to_ix(st_new, st_old, size, symbols);
            add_counter(new_count + ix, old_count + i);
                }
            }
        }
    }
}

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++) {
        collapse_symmetric(size, symbols, count_size, old_count);
        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]