Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Anagram checker

148.c

/* 148 - Anagram checker */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BS 64

/* Begin: Fri, 21 May 2010 12:09:08 +0200 */
/* End: Fri, 21 May 2010 14:14:59 +0200 */

int nwords;
char **words;

int ntwords;
char **twords;

char * phrase;
char sorted[1024];
int letters[26];

void
check(int pos, int left, char * result) {
	int i;
	int ok;
	if (left==0) {
		if (strcmp(result, sorted) != 0) {
			printf("%s =%s\n", phrase, result);
		}
		return;
	}
	if (pos==ntwords) {
		return;
	}
	for (i=0; i<strlen(twords[pos]); i++) {
		letters[twords[pos][i]-'A']--;
	}
	ok = 1;
	for (i=0; i<26; i++) {
		if (letters[i] < 0) {
			ok = 0;
			break;
		}
	}
	if (ok) {
		strcat(result, " ");
		strcat(result, twords[pos]);
		check(pos+1, left-strlen(twords[pos]), result);
		result[strlen(result)-strlen(twords[pos])-1] = 0;
	}
	for (i=0; i<strlen(twords[pos]); i++) {
		letters[twords[pos][i]-'A']++;
	}
	check(pos+1, left, result);
}

static int
cmpstringp(const void *p1, const void *p2) {
	return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int
main(void) {
	char buf[BS];
	char word[BS];
	while (fgets(buf, BS, stdin)) {
		if (buf[0]=='#') {
			break;
		}
		if (sscanf(buf, "%s", word) != 1) {
			abort();
		} else {
			int l = strlen(word);
			words = realloc(words, (nwords+1)*sizeof(char*));
			words[nwords] = malloc(l+1);
			strcpy(words[nwords], word);
			nwords++;
		}
	}
	twords = malloc((nwords+1)*sizeof(char*));
#if DEBUG
	{
		int i;
		for (i=0; i<nwords; i++) {
			printf("WORD[%d]: \"%s\"\n", i, words[i]);
		}
	}
#endif
	while (fgets(buf, BS, stdin)) {
		int i,j;
		int ok;
		int nletters = 0;
		char result[1024];

		if (buf[0]=='#') {
			break;
		}

		buf[strlen(buf)-1] = 0;
		phrase = buf;
		{
			int ntt = 0;
			char **tt = NULL;
			char copy[1024];
			char *s, *t;
			strcpy(copy, phrase);
			t = copy;
			while ((s = strtok(t, " \t\r\n"))) {
				t = NULL;
				tt = realloc(tt, (ntt+1)*sizeof(char *));
				tt[ntt++] = s;
			}
			qsort(tt, ntt, sizeof(char*), cmpstringp);
			sorted[0] = 0;
			for (i=0; i<ntt; i++) {
				strcat(sorted, " ");
				strcat(sorted, tt[i]);
			}
		}
		memset(letters, 0, sizeof(letters));
		for (i=0; i<strlen(buf); i++) {
			if (buf[i] >= 'A' && buf[i] <= 'Z') {
				letters[buf[i]-'A']++;
				nletters++;
			}
		}
		ntwords=0;
		for (i=0; i<nwords; i++) {
			ok=1;
			for (j=0; j<strlen(words[i]); j++) {
				if (!letters[words[i][j]-'A']) {
					ok = 0;
					break;
				}
			}
			if (ok) {
				twords[ntwords++] = words[i];
			}
		}
#if DEBUG
		{
			int i;
			printf("ntwords=%d\n", ntwords);
			printf("%s =", buf);
			for (i=0; i<ntwords; i++) {
				printf(" %s", twords[i]);
			}
			printf("\n");
		}
#endif
		result[0] = 0;
		check(0, nletters, result);
#if DEBUG
		printf("%s = ", buf);
		for (i=0; i<26; i++) {
			for (j=0; j<letters[i]; j++) {
				printf("%c", 'A'+i);
			}
		}
		printf("\n");
#endif
	}
	return 0;
}