shithub: util

ref: a6ed04f41557953cd022f331ff5dfdb28e05ad2e
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++)
		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++) {
		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++;

			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);

			findanagrams(child, minlen);
		}

		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;

	if (argc < 2) {
USAGE:
		fprint(2, "usage:\n\t%s [-l minlen] wordsfile\n", argv[0]);
		exits("usage");
	}

	wordsfilename = argv[1];

	if (strcmp(argv[1], "-l") == 0) {
		if (argc < 4)
			goto USAGE;

		minlen = atoi(argv[2]);
		wordsfilename = argv[3];
	}

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

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

	dict = calloc(1, sizeof(dlist));
	cur = dict;
	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++;

			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;
	}
}