fork download
copy 
  1. /* -------------------------------------------------------------
  2.  * Project Euler, Problem #22 (less 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(), for strncmp()
  22. #include <stdlib.h>					// for calloc(), free()
  23.  
  24. #define MAX_WLEN	25+1				// max length for any word + '\0'
  25. #define LETTVAL(c)	((c)-'A'+1)			// letter value
  26.  
  27. typedef enum { FALSE=0, TRUE } Bool;			// our own boolean type
  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. void list_destroy( List *list )
  86. {
  87. 	Node *dummy = NULL;
  88. 	while ( list->head ) {
  89. 		dummy = list->head->next;
  90. 		free( list->head );
  91. 		list->head = dummy;
  92. 	}
  93.  
  94. 	return;
  95. }
  96. // ------------------------------------------------------------------------------------
  97. int main( void )
  98. {
  99. 	List list = {.head=NULL, .tail=NULL};		// linked list for sorted words
  100.  
  101. 	// read file contents into a singly linked list in ascending order
  102.  
  103. 	FILE *fp = fopen("names.txt", "r");
  104. 	if ( !fp )					// fopen error
  105. 		exit( EXIT_FAILURE );
  106.  
  107. 	while ( !feof(fp) )				// read file-contents loop
  108. 	{
  109. 		char s[ MAX_WLEN ] = {0};		// important! filling up with 0s
  110. 		fscanf (fp, "\"%[A-Z]\",", s);		// get clean uppercase words only
  111. 		if ( !list_insert( &list, s) ) {	// if insertion to list fails
  112. 			list_destroy( &list );			// cleanup
  113. 			fclose( fp );				// ...
  114. 			exit( EXIT_FAILURE );			// abnormal exit
  115. 		}
  116. 	}
  117. 	fclose( fp );
  118.  
  119. 	// traverse the sorted list & calc the total score, then destroy the list
  120.  
  121. 	Node *dummy = NULL;				// temp for traversing the list
  122. 	long int i, score = 0;				// node counter & total score 
  123.  
  124. 	for (i=0, dummy = list.head; dummy; i++ )	// traverse the sorted list
  125. 	{						// ...
  126. 		int wscore = 0;				// temp for individual word score
  127. 		char *cp = dummy->word;			// calc score of individual word
  128. 		while ( *cp )				// ...
  129. 			wscore += LETTVAL( *cp++ );	// ...
  130. 		score += (i+1) * wscore;		// update total score
  131. 		dummy = dummy->next;			// move to next node
  132. 	}
  133. 	list_destroy( &list );				// free mem reserved for list
  134.  
  135. 	// output the total score
  136. 	printf("%ld\n", score );
  137.  
  138. 	exit( EXIT_SUCCESS );
  139. }
  140.  
  141.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/t1Mcv
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!