#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
/* #define XMALLOC */
#if defined XMALLOC
#include "xmalloc.h"
#define malloc(x)
#define free(x)
#define realloc(x, y)
#else
#define xmalloc(x, y) malloc((x))
#define xfree(x, y) free((x))
#define xrealloc(x, y, z) xrealloc((x), (y))
#define xmallocdump()
#endif
#define ID_STR 1001
#define ID_NODE 1002
#define N 4 /* only 4 is allowed. */
struct list {
char *data;
struct list *next;
};
void setlist(struct list **root, char *data) {
char *p;
struct list *q;
#if defined XMALLOC
if (root == NULL) {
perror("setlist(): root is null\n");
abort();
}
#endif
if ((p = xmalloc(strlen(data) + 1, ID_STR)) == NULL)
return;
if ((q = xmalloc(sizeof(struct list), ID_NODE)) == NULL) {
xfree(p, ID_STR);
return;
}
strcpy(p, data);
q->data = p;
q->next = *root;
*root = q;
}
int getlist(struct list **root, char **s_malloc) {
struct list *p;
#if defined XMALLOC
if (root == NULL) {
perror("getlist(): root is null\n");
abort();
}
#endif
if (*root == NULL)
return 0;
*s_malloc = (*root)->data;
p = *root;
*root = p->next;
xfree(p, ID_NODE);
return 1;
}
/*--------------------------------------------------*/
int inv(char c) {
return (islower((int)c)) ? c - 'a' + 'A' : c - 'A' + 'a';
}
int match(char *exp, char *dic) {
char *p;
int flag;
flag = 1;
for (;*dic; dic++) {
for (p = exp; *p; p++)
if (*dic == inv(*p)) {
flag = 0;
goto jump;
}
}
jump:
return flag;
}
void getexp(char *exp, int work[][N]) {
int i, j;
static char *dic[][N] = {
{"abcd", "aBcd", "ABcd", "Abcd"},
{"abcD", "aBcD", "ABcD", "AbcD"},
{"abCD", "aBCD", "ABCD", "AbCD"},
{"abCd", "aBCd", "ABCd", "AbCd"}};
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
work[i][j] = (match(exp, dic[i][j])) ? 1 : 0;
}
void maketable(struct list **root, int table[][N + 1]) {
int i, j;
static int work[N][N];
char *ps;
struct list *p;
for (p = *root; p; p = p->next) {
ps = p->data;
getexp(ps, work);
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (work[i][j])
table[i][j] = work[i][j];
}
for (i = 0; i < N; i++)
table[i][N] = table[i][0];
for (i = 0; i < N + 1; i++)
table[N][i] = table[0][i];
}
void printtable(int table[][N + 1]) {
int i, j;
printf(" AB\n");
printf(" 00 01 11 10\n");
for (i = 0; i < N; i++) { /**/
if (i == 0)
printf("CD ");
else
printf(" ");
switch (i) {
case 0:
printf("00 :");
break;
case 1:
printf("01 :");
break;
case 2:
printf("11 :");
break;
case 3:
printf("10 :");
break;
default:
printf(" ");
break;
}
for (j = 0; j < N; j++) /**/
printf(" %2d", table[i][j]);
putchar('\n');
}
}
void printfinishtable(int table[][N]) {
int i, j;
printf(" AB\n");
printf(" 00 01 11 10\n");
for (i = 0; i < N; i++) { /**/
if (i == 0)
printf("CD ");
else
printf(" ");
switch (i) {
case 0:
printf("00 :");
break;
case 1:
printf("01 :");
break;
case 2:
printf("11 :");
break;
case 3:
printf("10 :");
break;
default:
printf(" ");
break;
}
for (j = 0; j < N; j++) /**/
printf(" %2d", table[i][j]);
putchar('\n');
}
}
/*------------------------------------------*/
int isfinished(int finisht[][N]) {
int i, j;
int flag;
flag = 1;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (finisht[i][j] > 0) {
flag = 0;
goto jump;
}
jump:
return flag;
}
void step0(int table[][N + 1], int finisht[][N], struct list **root) {
int i, j;
int flag;
flag = 1;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (!finisht[i][j]) {
flag = 0;
goto jump1;
}
jump1:
if (flag) {
setlist(root, "1");
for (i = 0; i < N + 1; i++)
for (j = 0; j < N + 1; j++)
finisht[i][j] = 0;
return;
}
flag = 1;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (finisht[i][j]) {
flag = 0;
goto jump2;
}
jump2:
if (flag) {
setlist(root, "0");
return;
}
return;
}
void step1(int table[][N + 1], int finisht[][N], struct list **root) {
static char *index[] = {"c", "D", "C", "d" };
int k, i, j;
int flag;
for (k = 0; k < N; k++) {
flag = 1;
for(i = k; i < k + 2; i++)
for (j = 0; j < N; j++) {
if (!table[i][j]) {
flag = 0;
goto jump;
}
}
jump:
if (flag) {
setlist(root, index[i]);
for (i = k; i < k + 2; i++)
for (j = 0; j < N; j++)
if (i >= N)
finisht[i - N][j] = 0;
else
finisht[i][j] = 0;
}
}
}
void step2(int table[][N + 1], int finisht[][N], struct list **root) {
static char *index[] = {"a", "B", "A", "b" };
int k, i, j;
int flag;
for (k = 0; k < N; k++) {
flag = 1;
for(i = k; i < k + 2; i++)
for (j = 0; j < N; j++)
if (!table[j][i]) {
flag = 0;
goto jump;
}
jump:
if (flag) {
setlist(root, index[i]);
for (i = k; i < k + 2; i++)
for (j = 0; j < N; j++)
if (i >= N)
finisht[j][i - N] = 0;
else
finisht[j][i] = 0;
}
}
}
void step3(int table[][N + 1], int finisht[][N], struct list **root) {
static char *index[] = {"cd", "cD", "CD", "Cd" };
int i, j;
int flag;
for (i = 0; i < N; i++) {
flag = 1;
for (j = 0; j < N; j++)
if (!table[i][j]) {
flag = 0;
goto jump;
}
jump:
if (flag) {
setlist(root, index[i]);
for (j = 0; j < N; j++)
finisht[i][j] = 0;
}
}
}
void step4(int table[][N + 1], int finisht[][N], struct list **root) {
static char *index[] = {"ab", "aB", "AB", "Ab" };
int i, j;
int flag;
for (i = 0; i < N; i++) {
flag = 1;
for (j = 0; j < N; j++)
if (!table[j][i]) {
flag = 0;
goto jump;
}
jump:
if (flag) {
setlist(root, index[i]);
for (j = 0; j < N; j++)
finisht[j][i] = 0;
}
}
}
void step5(int table[][N + 1], int finisht[][N], struct list **root) {
int i, j, a, b, c, d;
static char *index[][N] = {
{"ac", "Bc", "Ac", "bc" },
{"aD", "BD", "AD", "bD" },
{"aC", "BC", "AC", "bC" },
{"ad", "Bd", "Ad", "bd" }
};
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (table[i][j] && table[i][j + 1] && table[i + 1][j] && table[i + 1][j + 1]) {
setlist(root, index[i][j]);
a = i;
b = i + 1;
c = j;
d = j + 1;
if (b >= N) b -= N;
if (d >= N) d -= N;
finisht[a][c] = 0;
finisht[a][d] = 0;
finisht[b][c] = 0;
finisht[b][d] = 0;
}
}
void step6(int table[][N + 1], int finisht[][N], struct list **root) {
int i, j;
static char *index[][N] = {
{ "acd", "Bcd", "Acd", "bcd" },
{ "acD", "BcD", "AcD", "bcD" },
{ "aCD", "BCD", "ACD", "bCD" },
{ "aCd", "BCd", "ACd", "bCd" }
};
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (table[i][j] && table[i][j + 1]) {
setlist(root, index[i][j]);
finisht[i][j] = 0;
if (j + 1 >= N)
finisht[i][j + 1- N] = 0;
else
finisht[i][j + 1] = 0;
}
}
void step7(int table[][N + 1], int finisht[][N], struct list **root) {
int i, j;
static char *index[][N] = {
{ "abc", "aBc", "ABc", "Abc" },
{ "abD", "aBD", "ABD", "AbD" },
{ "abC", "aBC", "ABC", "AbC" },
{ "abd", "aBd", "ABd", "Abd" }
};
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (table[i][j] && table[i + 1][j]) {
setlist(root, index[i][j]);
finisht[i][j] = 0;
if (i + 1 >= N)
finisht[i + 1 - N][j] = 0;
else
finisht[i + 1][j] = 0;
}
}
void step8(int table[][N + 1], int finisht[][N], struct list **root) {
int i, j;
static char *index[][N] = {
{ "abcd", "aBcd", "ABcd", "Abcd" },
{ "abcD", "aBcD", "ABcD", "AbcD" },
{ "abCD", "aBCD", "ABCD", "AbCD" },
{ "abCd", "aBCd", "ABCd", "AbCd" }
};
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (table[i][j]) {
setlist(root, index[i][j]);
finisht[i][j] = 0;
}
}
void abridge(int table[][N + 1], struct list **root) {
static int work[N + 1][N + 1];
struct list **p, *q;
int i, j, flag;
p = root;
while ((*p)->next) {
q = *p;
*p = q->next;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
work[i][j] = 0;
maketable(root, work);
flag = 1;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (work[i][j] != table[i][j]) {
flag = 0;
goto jump;
}
jump:
if (flag) {
xfree(q->data, ID_STR);
xfree(q, ID_NODE);
} else {
*p = q;
p = &((*p)->next);
}
}
}
void calc(int table[][N + 1], struct list **root) {
int i, j;
static int finishtable[N][N];
for (i = 0; i < N + 1; i++)
for (j = 0; j < N + 1; j++)
finishtable[i][j] = table[i][j];
for (;;) {
step0(table, finishtable, root);
if (isfinished(finishtable))
break;
step1(table, finishtable, root);
if (isfinished(finishtable))
break;
step2(table, finishtable, root);
if (isfinished(finishtable))
break;
step3(table, finishtable, root);
if (isfinished(finishtable))
break;
step4(table, finishtable, root);
if (isfinished(finishtable))
break;
step5(table, finishtable, root);
if (isfinished(finishtable))
break;
step6(table, finishtable, root);
if (isfinished(finishtable))
break;
step7(table, finishtable, root);
if (isfinished(finishtable))
break;
step8(table, finishtable, root);
if (isfinished(finishtable))
break;
putchar('\n');
printf("Internal error has occured. bugs exist.\n");
break;
}
abridge(table, root);
}
int main() {
static int table[N + 1][N + 1];
static char *in[] = {"Bcd", "Abcd", "aBc", "aB", "abC", NULL }; /* Acd + aC + aB */
/* static char *in[] = {"acd", "Ca", "CD", "aBD", "aCd", "Abd", NULL }; */ /* bd + aB + CD */
struct list *root;
char **p, *s;
int flag_first;
root = NULL;
for (p = in; *p; p++)
setlist(&root, *p);
maketable(&root, table);
printtable(table);
while(getlist(&root, &s))
xfree(s, ID_STR);
assert(root == NULL);
calc(table, &root);
flag_first = 1;
while (getlist(&root, &s)) {
if (!flag_first)
printf(" + ");
else
flag_first = 0;
printf("%s", s);
xfree(s, ID_STR);
}
putchar('\n');
xmallocdump();
return 0;
}
/* end */