shithub: util

ref: 3732da628dd47af6164197499bade76408d27f09
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;

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(char *words, item *items, int minlen)
{
	FILE *wordsfile = fopen(words, "r");
	char word[8192];
	item *child;

	if (wordsfile == nil)
		exits("fopen");

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

		if (strlen(word) < minlen)
			continue;

		if(contains(items->input, 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, word);
			child->anagram = realloc(child->anagram, strlen(child->anagram) + strlen(word) + 2);
			sprintf(&child->anagram[strlen(child->anagram)], "%s ", word);

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

			findanagrams(words, child, minlen);
		}
	}

	fclose(wordsfile);
}

void
main(int argc, char **argv)
{
	char input[8192];
	item *items;
	int minlen = 0;
	char *wordsfile;

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

	wordsfile = argv[1];

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

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

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

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

	findanagrams(wordsfile, items, minlen);
}