It's for a contest, so written code can be brought with us, but only if it's our own. And if it's too long, I can't spend 20+ minutes typing it all out from my notes, so it has to be something compact.
This is the current solution I have. I tried to keep it as compact as possible, but capable of insertion and retrieval.
This current example is meant to be specific to input where the key is "A-Z", but there could often be unexpected input such as "a", or "z", or "az". Therefore, the only reason a hash table is being used instead of an array of 26 elements, is to handle those exceptions. Performance of the buckets is not important, so building a linked list for collisions isn't tragic.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Input Specifications Begin */
#define MAX_KEY 20
#define HT_WIDTH 26
#define VAL_TYPE int
int hash(char *key) {
int i=0;
do{i+=*key+13;}while(*++key);
return i%HT_WIDTH;
}
/* Input Specifications End */
/* Hash Table Begin */
int ht_error;
typedef struct ht_me {struct ht_me *next; char key[MAX_KEY]; VAL_TYPE value;} ht_b;
ht_b *ht_table[HT_WIDTH];
void ht_init() {
int i;
for(i=0;i<HT_WIDTH;i++)ht_table[i]=NULL;
}
void ht_insert(char *key, VAL_TYPE value) {
int i=hash(key);
ht_b *node;
node = (ht_b *) malloc(sizeof( ht_b ));
strcpy(node->key, key);
node->value = value;
node->next = ht_table[i];
ht_table[i] = node;
}
int ht_lookup(char *key) {
ht_error=0;
int i=hash(key);
ht_b *node;
node = ht_table[i];
while(node) {
if(!strcmp(node->key,key))return node->value;
node=node->next;
}
return ht_error=1;
}
void ht_clean_bucket(ht_b *node) {
if(!node)return;
ht_clean_bucket(node->next);
free(node);
}
void ht_kill() {
int i;
for(i=0;i<HT_WIDTH;i++) {
ht_clean_bucket(ht_table[i]);
ht_table[i]=NULL;
}
}
/* Hash Table End */
int main() {
int value = 0;
char key[3];
key[2] = 0;
ht_init();
for(key[0]='A';key[0]<='Z';key[0]++)
for(key[1]='A';key[1]<='Z';key[1]++)
ht_insert(key, value++);
value = ht_lookup("ZZ");
if(!ht_error) printf("%d\n", value);
else printf("Key Does Not Exist\n");
ht_kill();
return 0;
}