/*
 * Problem session, Wednesday October 16th, 2002
 *
 * This program starts by trying to solve the "Jumble" puzzle,
 * that is, given a permuted (jumbled) word, find the legal
 * English word it was jumbled from.
 *
 * Example:   dynas -----> sandy
 *
 * A function that systematically generates all permutations
 * of the jumble (permute) can then search for these in a
 * list of words.
 *
 * Once the original problem is solved, my attention shifts to
 * trying to reverse the process: give me a legal English word,
 * and I try to generate a permutation of it that's very 
 * different ("far") from it.  One approach is to randomly
 * permute it (rand_permute).  Another approach is to generate
 * all permutations, and somehow measure how far they are from
 * the original.
 *
 * My first attempt at a distance function (permdist) doesn't seem
 * too successful.  I try another approach: count the number of
 * transpositions (swaps) it takes to transform one permutation
 * into another.  Still to be proved: the number of swaps is
 * minimal.
 *
 * This last distance leads to a completely different topic (group
 * theory, part of mathematics).  I also notice that permutations
 * don't need to be "far" apart according to my distance functions
 * to end up being psychologically far apart (hard to de-jumble).
 */

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <ctype.h>
#include <limits.h>

#define WORDCOUNT 45427

static void permute(char *string, int index, int mindist);
static int permdist(char *perm1, char *perm2);
static void swap (char *string, int index1, int index2);
static void max_permute(char *string, int index);
static void buildList();
static int searchList(char *key, int from, int to);
static void rand_permute(char *string);
char orig[80]; /* copy of original string */
int maxpermute = 0;
int maxp = 0;
char *wordList[WORDCOUNT];

int main()
{
    char input[80] = "non-empty";
/*
    max_permute(input, 0);
    printf("max permute: %d\n", maxpermute);
    permute(input,0);
*/
    buildList();

    printf("type a string: ");
    while (scanf("%s", input) != EOF) {
      strcpy(orig, input);
      maxp = 0;
      permute(input,0,INT_MAX);
      permute(input,0,maxp);
      printf("Maximum permute distance: %d\n", maxp);
      rand_permute(input);
      printf("type a string: ");
    }

    return 0;
}


void permute(char *string, int index, int mindist)
{
    int i;
    if (index == strlen(string) - 1) {
      /*
	if (maxp < permdist(orig,string))
	    maxp = permdist(orig,string)
	    if (mindist <= permdist(orig,string))
      */
      int wordIndex = searchList(string,0,WORDCOUNT);
      if (wordIndex > -1 &&
	  strcmp(wordList[wordIndex], string) == 0)
	printf("%s has distance %d\n",string, 
	       permdist(orig,string));
    } else {
	for (i = index; i < strlen(string); i++) {
	    swap(string, i, index);
	    permute(string, index + 1, mindist);
	    swap(string, i, index);
	}
    }
}


void max_permute(char *string, int index)
{
    int i;
    if (index == strlen(string) - 1) {
      if (maxpermute < permdist(string,orig))
	  maxpermute = permdist(string, orig);
    } else {
	for (i = index; i < strlen(string); i++) {
	    swap(string, i, index);
	    max_permute(string, index + 1);
	    swap(string, i, index);
	}
    }
}


void swap (char *string, int index1, int index2)
{
    char tmp;
    tmp = string[index1];
    string[index1] = string[index2];
    string[index2] = tmp;
}


int permdist(char *perm1, char *perm2)
{
  int i, sum = 0;
  for (i = 0; i < strlen(perm1); i++) {
    sum += abs((perm1 + i) - strchr(perm1, perm2[i]));
  }
  return sum;
}


void buildList()
{
    char input[80];
    int i = 0;
    FILE *words;
    words = fopen("./words","r");
    assert (words != NULL);
    while (fscanf(words,"%s",input) != EOF) {
	wordList[i] = (char *) malloc(strlen(input) + 1);
	strcpy(wordList[i],input);
	wordList[i][0] = tolower(wordList[i][0]);
	i++;
    }
}


int searchList(char *key, int from, int to)
{

    while (from != to - 1) {
	int mid = (to + from) / 2;
	
	if (strcmp(wordList[mid],key) > 0)
	    to = mid;
	else
	    from = mid;
    }
    return from;
}

void rand_permute(char *string)
{
    int i;
    char *cpy;
    cpy = (char *)malloc(strlen(string) + 1);
    strcpy(cpy,string);
    for (i = 0; i < strlen(string); i++) {
	swap(cpy, i, i + (rand() % (strlen(cpy) - i)));
    }
    printf ("%s has distance %d\n", cpy, permdist(cpy,orig));
    free(cpy);
}