group_anagrams.c

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

static int FACTORS[] = {2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31, 37, 41,
                        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

struct map_entry {
  int sort_key;
  int arg_index;
};

int to_key(char *word) {
  int key = 1;
  while (*word) {
    char letter = *word++;
    if (letter >= 'a' && letter <= 'z') {
      key *= FACTORS[letter - 'a'];
    }
  }
  return key;
}

int compare(const void *a, const void *b) {
  return ((struct map_entry *)a)->sort_key - ((struct map_entry *)b)->sort_key;
}

int main(int argc, char **argv) {
  int nwords = argc - 1;
  struct map_entry *entries = malloc(nwords * sizeof(struct map_entry));

  for (int i = 0; i < nwords; i++) {
    entries[i].sort_key = to_key(argv[i + 1]);
    entries[i].arg_index = i + 1;
  }

  qsort(entries, nwords, sizeof(struct map_entry), compare);

  int key = entries->sort_key;
  int sol = 1;
  for (int i = 0; i < nwords; i++) {
    if (key == entries[i].sort_key) {
      if (!sol)
        printf(" ");
      sol = 0;
      printf("%s", argv[entries[i].arg_index]);
    } else {
      key = entries[i].sort_key;
      sol = 1;
      printf("\n%s ", argv[entries[i].arg_index]);
    }
  }
  printf("\n");

  free(entries);

  return 0;
}