hmyaaa
    lengod
    ouothns
    gitesnt
    nkpinu
    ikedoo
    pwtsaeee
    seengis
    shesinun
    brhoapeo

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUFF_SIZE 1024

typedef struct List_Node_t{
	char *word;
	struct List_Node_t *next;
}ListNode;

typedef struct Trie_Node_t{
	struct Trie_Node_t *children[26];
	ListNode *head;
}TrieNode;


/* function prototypes */
void trim(char *string);
void insert(char *string, TrieNode *node);
void printScrambles(char *string, TrieNode *node);
int char_cmp(const void *c1, const void *c2);
void insertRec(char *word, char *sorted, TrieNode *node, int index);
void insertAtHead(ListNode **head, char *word);
void printRec(TrieNode *node, char *sorted, int index);

void printAll(TrieNode *node);

int main(int argc, char **argv){
	//pathnames of input files
	char *dictfile = "wordlist.txt", *listfile = "scrambles.txt";
	FILE *infile; //handle to currently open file
	char buffer[BUFF_SIZE]; //read buffer;
	TrieNode *head = calloc(1, sizeof(TrieNode));
	
	if(argc > 1){
		dictfile = argv[1];
	}
	if(argc > 2){
		listfile = argv[2];
	}
	
	infile = fopen(dictfile, "r");
	if(!infile){
		printf("Unable to open %s.  Exitingn");
		exit(1);
	}
	
	//read words and insert into dictionary
	while(fgets(buffer, BUFF_SIZE, infile)){
		trim(buffer);
		insert(buffer, head);
	}
	
	fclose(infile);
	fopen(listfile, "r");
	if(!infile){
		printf("Unable to open %s.  Exitingn");
		exit(1);
	}
	
	//find matches and print
	while(fgets(buffer, BUFF_SIZE, infile)){
		trim(buffer);
		//printf("Unscrambling |%s|n", buffer);
		printScrambles(buffer, head);
	} 
	
	return 0;
}

/* 
 * Trims non-letter characters from end of a string
 */
void trim(char *string){
	char *ptr;
	for(ptr = string; ((*ptr >= 'a') && (*ptr <= 'z')) || ((*ptr >= 'A') && (*ptr <= 'Z')); ptr++);
	*ptr = '';
}

/*
 * inserts given word into trie
 */
void insert(char *string, TrieNode *node){
	char *sorted = calloc(strlen(string) + 1, sizeof(char));
	strcpy(sorted, string);
	qsort(sorted, strlen(sorted), sizeof(char), char_cmp);
	
	char *copy = calloc(strlen(string) + 1, sizeof(char));
	strcpy(copy, string);
	
	//printf("-Inserting |%s| |%s|n", copy, sorted);
	insertRec(copy, sorted, node, 0);
}

/*
 * compares two characters
 * for qsort
 */
int char_cmp(const void *c1, const void *c2){
	return (*((char *)c1) - *((char *)c2));
}

/*
 * recursive method that inserts a word into the trie
 */
void insertRec(char *word, char *sorted, TrieNode *node, int index){
	if(!sorted[index]){
		//printf("-Targer node found.  Insertingn");
		insertAtHead(&(node->head), word);
		free(sorted);
		return;
	}
	
	int trieIndex = (sorted[index] < 'a') ? (sorted[index] - 'A') : (sorted[index] - 'a');
	//printf("-Looking at letter |%c|, index |%d|n", sorted[index], trieIndex);
	if(!(node->children[trieIndex])){
		//printf("-No Node found, creating newn");
		node->children[trieIndex] = calloc(1, sizeof(TrieNode));
	}
	
	insertRec(word, sorted, node->children[trieIndex], index+1);
}

/*
 * inserts word into head of linked list of ListNodes
 */
void insertAtHead(ListNode **head, char *word){
	ListNode *node = calloc(1, sizeof(ListNode));
	node->word = word;
	node->next = *head;
	*head = node;
}

/*
 * prints words matching given scramble
 */
void printScrambles(char *string, TrieNode *node){
	//printf("Sorting/copying %sn", string);
	char *sorted = calloc(strlen(string) + 1, sizeof(char));
	strcpy(sorted, string);
	//printf("String copiedn");
	qsort(sorted, strlen(sorted), sizeof(char), char_cmp);
	//printf("String sortedn");
	
	printf("Matches for %s: ", string);
	printRec(node, sorted, 0);
	free(sorted);
}

/* 
 * recursive method to trawl trie for matches
 */
void printRec(TrieNode *node, char *sorted, int index){
	//printf("Looking at |%s| index |%d| character |%c|n", sorted, index, sorted[index]);
	
	if(!(sorted[index])){
		if(!node->head){
			printf("No matches foundn");
		}else{
			ListNode *ptr;
			for(ptr = node->head; ptr; ptr = ptr->next)
				printf("%s, ", ptr->word);
				
			printf("n");
		}
	}else{
		int trieIndex = (sorted[index] < 'a') ? (sorted[index] - 'A') : (sorted[index] - 'a');
		if(node->children[trieIndex])
			printRec(node->children[trieIndex], sorted, index+1);
		else{
			printf("No matches foundn");
			return;
		}
	}
}

void printAll(TrieNode *node){
	ListNode *ptr;
	for(ptr = node->head; ptr; ptr = ptr->next){
		printf("%sn", ptr->word);
	}

	int i;
	for(i=0; i<26; i++){
		if(node->children[i])
			printAll(node->children[i]);
	}
}

#!/usr/bin/env ruby

unless ARGV[0] 
    puts "Usage: ruby wordsort.rb [word_1 word_2 ...]"
    exit 0
end

scram_words = ARGV.compact.map {|x| x.split(//).sort.join}

File.open("wordlist.txt").each do |word|
    word.chop!
    scram_words.each {|scram| p word if word.split(//).sort.join == scram}
end

#!/usr/bin/env ruby


unless ARGV.size == 2
    puts "Usage: ruby wordsort.rb scram_file wordlist_file"
    exit 0
end

scram = Array.new
File.open(ARGV[0]).each do |word|
    scram << word.chop.split(//).sort.join
end

File.open(ARGV[1]).each do |word|
    word.chop!
    (0...scram.size).each { |i| 
        if word.split(//).sort.join == scram[i]
            p word 
            scram.delete_at i
            break
        end
    }
end

time ruby wordsort.rb scram.txt wordlist.txt         
real    0m0.082s
user    0m0.076s
sys     0m0.000s

 
time ruby wordsort.rb shuffle.txt 172K-words.txt   
real    35m27.748s
user    30m21.790s
sys     0m5.708s

#!/usr/bin/env ruby

unless ARGV.size == 2
    puts "Usage: ruby wordsort.rb scram_file wordlist_file"
    exit 0
end

scram = Array.new
real = Array.new

File.open(ARGV[0]).each do |word|
    scram << word.chop.split(//).sort.join
end

File.open(ARGV[1]).each do |word|
    real << word.chop    
end

scram.sort!
real.sort!

real.each do |word|
    sword = word.split(//).sort.join
    (0...scram.size).each do |i| 
        break if sword[0] < scram[i][0]
        if sword == scram[i]
            p word 
            scram.delete_at i
            break
        end
    end
end

time ruby wordsort.rb scram.txt wordlist.txt         
real    0m0.024s
user    0m0.024s
sys     0m0.000s

time ruby wordsort.rb shuffle.txt 172K-words.txt   
real    10m55.095s
user    10m54.685s
sys     0m0.376s