shithub: util

ref: 783f6d8fcd85aaa04d843d3ac282b7dc238b4c2c
dir: /anagrams.c/

#include <u.h>
#include <libc.h>
#include <stdio.h>

typedef struct _item {
	char *input;
	char *anagram;
	struct _item **children;
	int nchildren;
} item;

typedef struct _dlist {
	char *word;
	struct _dlist *next;
} dlist;

dlist *dict = nil;

void
removechars(char *input, char *word)
{
	int i, j;

	for (i = 0; i < strlen(word); i++)
		if (word[i] == '\'')
			continue;
		else for (j = 0; j < strlen(input); j++)
			if ((word[i] | 0x20) == (input[j] | 0x20)) {
				memmove(&input[j], &input[j+1], strlen(&input[j+1])+1);
				break;
			}
}

int
contains(char *in, char *word)
{
	int i, j;
	int r;

	char *input = strdup(in);

	if (strlen(word) > strlen(input)) {
		free(input);
		return 0;
	}

	r = 0;
	for (i = 0; i < strlen(word); i++) {
		if (word[i] == '\'')
			continue;
		else for (j = 0; j < strlen(input); j++)
			if ((word[i] | 0x20) == (input[j] | 0x20)) {
				r++;
				memmove(&input[j], &input[j+1], strlen(&input[j+1])+1);
				break;
			}
	}
	free(input);
	return (r == strlen(word));
}

void
findanagrams(item *items, int minlen)
{
	item *child;
	dlist *cur = dict;

	while(cur->word != nil){
		if(contains(items->input, cur->word)){
			child = calloc(1, sizeof(item));
			child->input = strdup(items->input);
			child->anagram = strdup(items->anagram);
			child->children = calloc(1, sizeof(item*));

			items->children = realloc(items->children, (items->nchildren+1) * sizeof(item*));
			items->children[items->nchildren] = child;
			items->nchildren++;

			if (contains(child->input, cur->word) == 0) {
				cur = cur->next;
				continue;
			}

			removechars(child->input, cur->word);
			child->anagram = realloc(child->anagram, strlen(child->anagram) + strlen(cur->word) + 2);
			sprintf(&child->anagram[strlen(child->anagram)], "%s ", cur->word);

			if (strlen(child->input) == 0)
				printf("%s\n", child->anagram);
			else
				findanagrams(child, minlen);
		}

		cur = cur->next;
	}
}

void
common(char *input)
{
	dlist *cur = dict;
	int i;
	char *commonwords[] = {"a", "I", "an", "at", "be", "by", "do", "he", "in", "is", "it", "my", "no", "oh", "or", "to", "us", "we", "and", "but", "for", "her", "him", "his", "its", "not", "too", "you", nil};

	for(i = 0; commonwords[i] != nil; i++){
		if (contains(input, commonwords[i])) {
			cur->word = strdup(commonwords[i]);
			cur->next = calloc(1, sizeof(dlist));
			cur = cur->next;
		}
	}
}

void
main(int argc, char **argv)
{
	char input[8192];
	item *items;
	int minlen = 0;
	char *wordsfilename = "";
	FILE *wordsfile;
	char word[8192];
	dlist *cur;
	item *child;
	int i;
	int commonwords = 0;

	dict = calloc(1, sizeof(dlist));

	for(i = 1; i < argc; i++){
		wordsfilename = argv[i];
		if(argv[i][0] == '-'){
			if((argv[i][1] == 'l') && (++i < argc)){
				minlen = atoi(argv[i]);
				continue;
			}else if (argv[i][1] == 'c'){
				commonwords = 1;
				continue;
			}
		}else continue;

		fprint(2, "usage:\n\t%s [-l[ength] minlen] [-c[ommonenglishwords] wordsfile\n", argv[0]);
		exits("usage");
	}

	wordsfile = fopen(wordsfilename, "r");
	if (wordsfile == nil)
		exits("fopen");

	read(0, input, sizeof(input));
	input[strcspn(input, "\n")] = '\0';
	while(contains(input, " "))
		removechars(input, " ");
	while(contains(input, "'"))
		removechars(input, "'");

	if (commonwords == 1)
		common(input);

	cur = dict;
	while(cur->word != nil)
		cur = cur->next;
	while(fgets(word, 8192, wordsfile) != nil){
		word[strcspn(word, "\n")] = '\0';

		if(strlen(word) < minlen)
			continue;

		if(contains(input, word)){
			cur->word = strdup(word);
			cur->next = calloc(1, sizeof(dlist));
			cur = cur->next;
		}
	}
	fclose(wordsfile);

	items = calloc(1, sizeof(item));
	items->input = strdup(input);
	items->anagram = strdup("");
	items->children = calloc(1, sizeof(item*));

	while(dict->word != nil){
		child = calloc(1, sizeof(item));
		child->input = strdup(items->input);
		child->anagram = strdup(items->anagram);
		child->children = calloc(1, sizeof(item*));

		items->children = realloc(items->children, (items->nchildren+1) * sizeof(item*));
		items->children[items->nchildren] = child;
		items->nchildren++;

		if (contains(child->input, dict->word) == 0) {
			dict = dict->next;
			continue;
		}

		removechars(child->input, dict->word);
		child->anagram = realloc(child->anagram, strlen(child->anagram) + strlen(dict->word) + 2);
		sprintf(&child->anagram[strlen(child->anagram)], "%s ", dict->word);

		if (strlen(child->input) == 0)
			printf("%s\n", child->anagram);
		else
			findanagrams(child, minlen);

		dict = dict->next;
	}
}