mirror of https://github.com/TheAlgorithms/C
150 lines
3.7 KiB
C
150 lines
3.7 KiB
C
/**
|
|
* \file
|
|
* \brief [Problem 22](https://projecteuler.net/problem=22) solution
|
|
* \author [Krishna Vedala](https://github.com/kvedala)
|
|
*/
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <time.h>
|
|
#ifdef _OPENMP
|
|
#include <omp.h>
|
|
#endif
|
|
|
|
#define MAX_NAMES 6000 /**< Maximum number of names to store */
|
|
#define MAX_NAME_LEN 20 /**< Maximum length of each name */
|
|
|
|
/**
|
|
* Alphabetical sorting using 'shell sort' algorithm
|
|
*/
|
|
void shell_sort(char data[][MAX_NAME_LEN], int LEN)
|
|
{
|
|
const int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1};
|
|
const int gap_len = 8;
|
|
int i, j, g;
|
|
|
|
for (g = 0; g < gap_len; g++)
|
|
{
|
|
int gap = gaps[g];
|
|
for (i = gap; i < LEN; i++)
|
|
{
|
|
char tmp_buffer[MAX_NAME_LEN];
|
|
strcpy(tmp_buffer, data[i]);
|
|
|
|
for (j = i; j >= gap && strcmp(data[j - gap], tmp_buffer) > 0;
|
|
j -= gap)
|
|
strcpy(data[j], data[j - gap]);
|
|
strcpy(data[j], tmp_buffer);
|
|
}
|
|
}
|
|
#ifdef DEBUG
|
|
for (i = 0; i < LEN; i++) printf("%s\t", data[i]);
|
|
#endif
|
|
}
|
|
|
|
/**
|
|
* Alphabetical sorting using 'lazy sort' algorithm
|
|
*/
|
|
void lazy_sort(char data[][MAX_NAME_LEN], int LEN)
|
|
{
|
|
int i, j;
|
|
for (i = 0; i < LEN; i++)
|
|
{
|
|
for (j = i + 1; j < LEN; j++)
|
|
{
|
|
if (strcmp(data[i], data[j]) > 0)
|
|
{
|
|
char tmp_buffer[MAX_NAME_LEN];
|
|
strcpy(tmp_buffer, data[i]);
|
|
strcpy(data[i], data[j]);
|
|
strcpy(data[j], tmp_buffer);
|
|
}
|
|
}
|
|
}
|
|
#ifdef DEBUG
|
|
for (i = 0; i < LEN; i++) printf("%s\t", data[i]);
|
|
#endif
|
|
}
|
|
|
|
/** Main function */
|
|
int main(int argc, char **argv)
|
|
{
|
|
unsigned long COUNT = 0;
|
|
char *fname = "names.txt";
|
|
char names[MAX_NAMES][MAX_NAME_LEN];
|
|
short method = 0; /* sorting algorithm to use. 0 = lazy, 1 = shell-sort */
|
|
|
|
if (argc == 2)
|
|
method = atoi(argv[1]);
|
|
|
|
FILE *fp = fopen(fname, "rt");
|
|
if (!fp)
|
|
{
|
|
perror("Unable to open file");
|
|
return -1;
|
|
}
|
|
|
|
/*
|
|
* Loops to get total number of rows and columns in the file
|
|
*/
|
|
do
|
|
{
|
|
int ret = fscanf(fp, "\"%[^\",]\",", names[COUNT++]);
|
|
if (ret <= 0)
|
|
continue;
|
|
// printf("%s\t", names[COUNT - 1]);
|
|
} while (!feof(fp));
|
|
fclose(fp);
|
|
|
|
printf("\nTotal number of names: %lu\n", COUNT);
|
|
|
|
if (method == 0)
|
|
{
|
|
clock_t start_time = clock();
|
|
shell_sort(names, COUNT);
|
|
clock_t end_time = clock();
|
|
printf("\nShell sort: %.4g millisecond\n",
|
|
1e3 * (end_time - start_time) / CLOCKS_PER_SEC);
|
|
}
|
|
else if (method == 1)
|
|
{
|
|
clock_t start_time = clock();
|
|
lazy_sort(names, COUNT);
|
|
clock_t end_time = clock();
|
|
printf("\nLazy sort: %.4g millisecond\n",
|
|
1e3 * (end_time - start_time) / CLOCKS_PER_SEC);
|
|
}
|
|
|
|
long sum_score = 0;
|
|
clock_t start_time = clock();
|
|
int i;
|
|
|
|
#ifdef _OPENMP
|
|
#pragma omp parallel for schedule(runtime) reduction(+ : sum_score)
|
|
#endif
|
|
#ifdef DEBUG
|
|
for (i = 935; i < 940; i++)
|
|
#else
|
|
for (i = 0; i < COUNT; i++)
|
|
#endif
|
|
{
|
|
long score = 0;
|
|
/* score the alphabets in i^th name */
|
|
for (int j = 0; names[i][j] != '\0'; j++)
|
|
score += names[i][j] - 'A' +
|
|
1; /* convert ASCII character to integer score */
|
|
sum_score += score * (i + 1);
|
|
#ifdef DEBUG
|
|
printf("Name: %s\tScore: %u x %u = %lu\n", names[i], score, i + 1,
|
|
(unsigned long)score * (i + 1));
|
|
#endif
|
|
}
|
|
clock_t end_time = clock();
|
|
printf("Scoring time: %.4g millisecond\n",
|
|
1e3 * (end_time - start_time) / CLOCKS_PER_SEC);
|
|
|
|
printf("Total Score = %lu\n", sum_score);
|
|
|
|
return 0;
|
|
}
|