Catenyms

Catenyms

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms:

dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,

aloha.aloha.arachnid.dog.gopher.rat.tiger

Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once. The first line of standard input contains

t

, the number of test cases. Each test case begins with 3 <=

n

<= 1000 - the number of words in the dictionary.

n

distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself. For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

aloha.arachnid.dog.gopher.rat.tiger
***

#include <stdio.h>

int i,j,k,m,n;
char buf;

int state;
double base, val;

int v;

#define check(x) if (!(x)) {printf("no\n");goto bad;}

#define DSTART 1
#define DEC 2
#define BSTART 3
#define BASE 4
#define BDONE 5

main(){
for (i=0;i<255;i++) v[i] = -1;
for (i=0;i<=9;i++) v[i+'0'] = i;
for (i=0;i<=5;i++) v[i+'a'] = i+10;
scanf("%d",&n);
gets(buf);
while (n--) {
if (!gets(buf)) {
printf("Error - short input!\n");
exit(1);
}
state = DSTART;
val = base = 0;
for (i=0;buf[i];i++) {
char c = buf[i];
switch(state) {
case DSTART: {
check(v[c] >=0 && v[c] <= 9);
val = v[c];
state = DEC;
break;
}
case DEC: {
if (c == '#') {
check(val >= 2 && val <= 16);
base = val;
val = 0;
state = BSTART;
break;
}
check (v[c] >= 0 && v[c] <= 9);
val = val * 10 + v[c];
break;
}
case BSTART: {
check (v[c] >= 0 && v[c] < base);
val = v[c];
state = BASE;
break;
}
case BASE: {
if (c == '#') {
state = BDONE;
break;
}
check (v[c] >= 0 && v[c] < base);
val = val * base + v[c];
break;
}
case BDONE: {
check (c == '#');
check (val >=2 && val <= 16);
base = val;
val = 0;
state = BSTART;
break;
}
}
}
check(state == DEC || state == BDONE);
printf("yes\n");
}
if (gets(buf)) printf("Error - excessinput!\n");
}

#include <stdio.h>

int i,j,k,m,n;
char buf;

int state;
double base, val;

int v;

#define check(x) if (!(x)) {printf("no\n");goto bad;}

#define DSTART 1
#define DEC 2
#define BSTART 3
#define BASE 4
#define BDONE 5

main(){
for (i=0;i<255;i++) v[i] = -1;
for (i=0;i<=9;i++) v[i+'0'] = i;
for (i=0;i<=5;i++) v[i+'a'] = i+10;
scanf("%d",&n);
gets(buf);
while (n--) {
if (!gets(buf)) {
printf("Error - short input!\n");
exit(1);
}
state = DSTART;
val = base = 0;
for (i=0;buf[i];i++) {
char c = buf[i];
switch(state) {
case DSTART: {
check(v[c] >=0 && v[c] <= 9);
val = v[c];
state = DEC;
break;
}
case DEC: {
if (c == '#') {
check(val >= 2 && val <= 16);
base = val;
val = 0;
state = BSTART;
break;
}
check (v[c] >= 0 && v[c] <= 9);
val = val * 10 + v[c];
break;
}
case BSTART: {
check (v[c] >= 0 && v[c] < base);
val = v[c];
state = BASE;
break;
}
case BASE: {
if (c == '#') {
state = BDONE;
break;
}
check (v[c] >= 0 && v[c] < base);
val = val * base + v[c];
break;
}
case BDONE: {
check (c == '#');
check (val >=2 && val <= 16);
base = val;
val = 0;
state = BSTART;
break;
}
}
}
check(state == DEC || state == BDONE);
printf("yes\n");