fork download
copy 
  1. /* -------------------------------------------------------------
  2.  * Project Euler, Problem #22 (more functions)
  3.  *
  4.  * Using names.txt (http://p...content-available-to-author-only...r.net/project/names.txt), a 46K text file
  5.  * containing over five-thousand first names, begin by sorting it into alphabetical
  6.  * order. Then working out the alphabetical value for each name, multiply this value
  7.  * by its alphabetical position in the list to obtain a name score.
  8.  *
  9.  * For example, when the list is sorted into alphabetical order, COLIN, which is
  10.  * worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would
  11.  * obtain a score of 938 ? 53 = 49714.
  12.  *
  13.  * What is the total of all the name scores in the file?
  14.  *
  15.  * Solution by: migf1
  16.  *	File contents are split and loaded into an ascending-ordered singly linked list
  17.  *	in one pass. A second pass traverses the list to calculate the total score. 
  18.  * -------------------------------------------------------------
  19.  */
  20. #include <stdio.h>
  21. #include <string.h>					// for strncpy(), strncmp()
  22. #include <stdlib.h>					// for calloc(), free()
  23.  
  24. #define MAX_WLEN	25+1
  25. #define LETTVAL(c)	((c)-'A'+1)		
  26.  
  27. typedef enum { FALSE=0, TRUE } Bool;
  28.  
  29. typedef struct node {
  30. 	char 	word[ MAX_WLEN ];			// the word
  31. 	struct 	node *next;				// pointer to next node
  32. } Node;
  33.  
  34. typedef struct {
  35. 	Node *head, *tail;				// pointers to 1st & last nodes
  36. } List;
  37.  
  38. // ------------------------------------------------------------------------------------
  39. // insert data into list in ascending order
  40. //
  41. Bool list_insert( List *list, char *data )
  42. {
  43. 	Node *curr = NULL, *prev = NULL;
  44. 	Node *new = calloc( 1, sizeof(struct node) );
  45. 	if ( !new || !data )			// calloc failed or invalid data
  46. 		return FALSE;
  47.  
  48. 	strncpy(new->word, data, MAX_WLEN-1);	// initialize newly created node
  49. 	new->next = NULL;			// ...
  50.  
  51. 	if ( list->head == NULL) {		// list was empty, direct insertion
  52. 		list->head = list->tail = new;
  53. 		return TRUE;
  54. 	}
  55. 						// direct append
  56. 	if ( strncmp(data, list->tail->word, MAX_WLEN ) >= 0 ) {
  57. 		list->tail->next = new;
  58. 		list->tail = new;
  59. 		return TRUE;
  60. 	}
  61.  
  62. 	curr = prev = list->head;		// general case (traversing)
  63. 	// find spot for the insertion
  64. 	while ( curr && strncmp(curr->word, data, MAX_WLEN) <= 0 )
  65. 	{					// use <= data, to allow duplicates
  66. 		prev = curr;			// save previous node
  67. 		curr = curr->next;
  68. 	}
  69.  
  70. 	// insert BEFORE 1st node
  71. 	if ( list->head == curr /* && curr->data != data */ ) {
  72. 		list->head = new;
  73. 		new->next = curr;
  74. 		return TRUE;
  75. 	}
  76. 	// insert AFTER 1st node
  77. 	if ( !curr || strncmp(curr->word, data, MAX_WLEN) != 0 ) {	
  78. 		prev->next = new;
  79. 		new->next = curr;
  80. 	}
  81.  
  82. 	return TRUE;
  83. }
  84.  
  85. // ------------------------------------------------------------------------------------
  86. void list_destroy( List *list )
  87. {
  88. 	Node *dummy = NULL;
  89.  
  90. 	while ( list->head ) {
  91. 		dummy = list->head->next;
  92. 		free( list->head );
  93. 		list->head = dummy;
  94. 	}
  95.  
  96. 	return;
  97. }
  98.  
  99. // ------------------------------------------------------------------------------------
  100. int get_stringval( const char *s, const long int pos )
  101. {
  102. 	if (!s || !*s || pos < 0)
  103. 		return 0;
  104.  
  105. 	int val = 0;
  106. 	while (*s)
  107. 		val += LETTVAL(*s++);
  108.  
  109. 	return (pos+1) * val; 
  110. }
  111.  
  112. // ------------------------------------------------------------------------------------
  113. long int get_totscore( List list )
  114. {
  115. 	long int pos, total = 0;
  116.  
  117. 	if ( !list.head )
  118. 		return 0;
  119.  
  120. 	for (pos=0; list.head; pos++ ) {
  121. 		total += get_stringval(list.head->word, pos);
  122. 		list.head = list.head->next;
  123. 	}
  124.  
  125. 	return total;
  126. }
  127.  
  128. // ------------------------------------------------------------------------------------
  129. Bool get_fcontents( const char *fname, const char *delims, List *list )
  130. {
  131. 	FILE *fp = fopen(fname, "r");
  132. 	char s[ MAX_WLEN ] = {0};			// important! filling up with 0s
  133.  
  134. 	if ( !fp || !list)				// fopen error or invalid list
  135. 		return FALSE;
  136.  
  137. 	while ( !feof(fp) )
  138. 	{
  139. 		fscanf(fp, delims, s);			// read next clean word
  140. 		if ( !list_insert( list, s) ) {		// if insertion to list fails
  141. 			list_destroy( list );			// cleanup
  142. 			fclose( fp );				// ...
  143. 			return FALSE;				// return error status
  144. 		}
  145. 	}
  146. 	fclose( fp );
  147.  
  148. 	return TRUE;
  149. }
  150.  
  151. // ------------------------------------------------------------------------------------
  152. int main( void )
  153. {
  154. 	List list = {.head=NULL, .tail=NULL};		// linked list for sorted words
  155.  
  156. 	if ( !get_fcontents( "names.txt", "\"%[A-Z]\",", &list ) ) {
  157. 		puts("*** internal error, aborting program...");
  158. 		exit( EXIT_FAILURE );
  159. 	}
  160. 	printf("%ld\n", get_totscore(list) );		// print the total score
  161. 	list_destroy( &list );				// free mem reserved for list
  162.  
  163. 	exit( EXIT_SUCCESS );
  164. }
  165.  
  166.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4vH8q
language:
C (gcc 8.3)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!