· 8 years ago · Jul 08, 2018, 06:00 AM
1/*
2HackerRank Count Triplets challenge
3C - Hashmap implementation
4DerekM
5*/
6
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11typedef struct node{ // "Node" structure - Container pairs of values/counters for that value
12 long value; // Integer number which we are interested in
13 long count2; // Count of how many sequences are waiting for this value as a 2/3 of a triplet
14 long count3; // Count of how many sequences are waiting for this value as a 3/3 of a triplet
15 struct node *next; // Linked-list pointer to the next node
16} node; // Common name for node to be called
17
18typedef struct hastable_struct{ // "Hash table" structure - Contains indexes to each of our nodes
19 int size; // Size of the table
20 node **table; // Pointer indexes to our nodes
21} hashtable_struct; // Common name for the table structure
22
23// Function Prototypes
24long CheckValue (hashtable_struct*, long, int, int, long);
25hashtable_struct* CreateTable (int);
26long DoHash (long, hashtable_struct*);
27
28int main()
29{
30 int n,r; // Variables for size of array and ratio
31 long x,buf; //
32 long count=0; // Initialize our return counter value to 0
33 scanf("%i %i",&n,&r); // Read inputs 'n' (size of array) and 'r' (triplet ratio)
34 hashtable_struct *hashtable; // Initialize our table structure, to be named 'hashtable'
35 hashtable = CreateTable(n); // Run through creation of the table, mainly memory allocation
36
37 for(int i=0;i<n;i++) // Iterate through all inputs of the array
38 {
39 scanf("%i",&x); // Read i'th value of the array into 'x'
40 buf = CheckValue(hashtable,x,r,1,1); // Do the majority of the work here, return number of completed triplets
41 count += buf; // Update counter with number of completed triplets
42 }
43
44 printf("%ld",count); // Print our output
45 return 0; // Delete system32
46}
47
48long CheckValue(hashtable_struct *htable,long val,int r,int trp,long cnt)
49{
50 long bin=DoHash(val,htable); // Get the hash value for this input value
51 node* nextnode; // Create a node structure for checking if a node exists
52 node* newnode; // Create a node structure for the updated/new node
53 long retval=0; // Initialize value for returning number of complete triplets
54 int CreateNewNode=0; // Flag to check if a new node is needed
55 nextnode = htable->table[bin]; // Populate node with hashed table location
56
57 if(nextnode == NULL) // If this bin has never been used
58 {
59 CreateNewNode = 1; // We'll definitely need to create a fresh node
60 }
61 else // This bin has been used before
62 {
63 while(nextnode->value != val) // If the value is wrong (A collision has occured - it's ok)
64 { // This means we're creating a linked list at this hash table address
65 if(nextnode->next == NULL) // If this is the last link in the chain
66 {
67 CreateNewNode = 1; // We'll need to create a new node
68 break; // Break the loop here, we're done looking
69 }
70 nextnode = nextnode->next; // Otherwise, more nodes to check, keep going
71 }
72 if(nextnode->value == val) // If the value was a correct match (No collision)
73 newnode=nextnode; // Copy the node that was already being mapped to
74 }
75
76 if(CreateNewNode)
77 {
78 newnode = malloc(sizeof(node)); // Allocate memory for a new node
79 newnode->value = val; // Set the value to that of the input
80 newnode->count2 = 0; // Initialize the counters at 0
81 newnode->count3 = 0; //
82 newnode->next = NULL; // Initialize the next linked node as NULL - new node is last link in chain
83 if(nextnode == NULL) // If this was an empty bin
84 {
85 htable->table[bin] = newnode; // Point the hash map to this node - first link in chain
86 }
87 else // If the bin was not empty (collision occurred)
88 {
89 nextnode->next = newnode; // Point the previous node to link to the new node
90 }
91 }
92
93 if(trp==1) // For checking 1st value of triplets (from main loop only)
94 {
95 retval = newnode->count3; // Return number of triplets that were waiting for this value as 3/3 triplet
96
97 if(newnode->count2 > 0) // If there are pending 2/3 triplets
98 CheckValue(htable,val*r,r,3,newnode->count2); // Run this function recursively, to check nodes for the 3rd triplet value
99 CheckValue(htable,val*r,r,2,1); // Run this function recursively again, to check for nodes of the 2nd triplet value
100 }
101 if(trp==2) // If this iteration was to check 2/3 triplets (called from above recursion)
102 newnode->count2 += 1; // Update the node's 2/3 counter
103 if(trp==3) // If this iteration was to check 3/3 triplets
104 newnode->count3 += cnt; // Update the node's 3/3 counter
105
106 return retval; // Return the number of completed triplets, to update the total count
107}
108
109hashtable_struct* CreateTable(int nsize) // Create the initial hash table
110{
111 hashtable_struct *newtable; // Add a new structure
112 newtable = malloc(sizeof(hashtable_struct)); // Allocate memory for the structure itself
113 newtable->table = malloc(nsize*sizeof(node)); // Allocate memory for the table/node addresses
114 for(int i = 0; i < nsize; i++ ) {
115 newtable->table[i] = NULL; // Set all node addresses to NULL initially - all unused
116 }
117 newtable->size = nsize; // Set the table's size
118 return newtable; // Return the location
119}
120
121long DoHash(long value,hashtable_struct* htable) // Hash algorithm
122{ // This is a simple modulus of the total number of elements
123 value = value%(htable->size); // Plenty of collisions will occur with this.
124 return value; // I'm sure theres a more efficient choice to be made here
125}