Four is the number of letters in the ...: Difference between revisions
Four is the number of letters in the ... (view source)
Revision as of 09:28, 4 June 2020
, 3 years agoAdded C solution
m (Reduce memory usage) |
(Added C solution) |
||
Line 49:
:* See the OEIS sequence [[oeis:A072424| A72424 "Five's the number of letters..."]]
<br><br>
=={{header|C}}==
<lang c>#include <ctype.h>
#include <locale.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef uint64_t integer;
typedef struct number_names_tag {
const char* cardinal;
const char* ordinal;
} number_names;
const number_names small[] = {
{ "zero", "zeroth" }, { "one", "first" }, { "two", "second" },
{ "three", "third" }, { "four", "fourth" }, { "five", "fifth" },
{ "six", "sixth" }, { "seven", "seventh" }, { "eight", "eighth" },
{ "nine", "ninth" }, { "ten", "tenth" }, { "eleven", "eleventh" },
{ "twelve", "twelfth" }, { "thirteen", "thirteenth" },
{ "fourteen", "fourteenth" }, { "fifteen", "fifteenth" },
{ "sixteen", "sixteenth" }, { "seventeen", "seventeenth" },
{ "eighteen", "eighteenth" }, { "nineteen", "nineteenth" }
};
const number_names tens[] = {
{ "twenty", "twentieth" }, { "thirty", "thirtieth" },
{ "forty", "fortieth" }, { "fifty", "fiftieth" },
{ "sixty", "sixtieth" }, { "seventy", "seventieth" },
{ "eighty", "eightieth" }, { "ninety", "ninetieth" }
};
typedef struct named_number_tag {
const char* cardinal;
const char* ordinal;
integer number;
} named_number;
const named_number named_numbers[] = {
{ "hundred", "hundredth", 100 },
{ "thousand", "thousandth", 1000 },
{ "million", "millionth", 1000000 },
{ "billion", "biliionth", 1000000000 },
{ "trillion", "trillionth", 1000000000000 },
{ "quadrillion", "quadrillionth", 1000000000000000ULL },
{ "quintillion", "quintillionth", 1000000000000000000ULL }
};
const char* get_small_name(const number_names* n, bool ordinal) {
return ordinal ? n->ordinal : n->cardinal;
}
const char* get_big_name(const named_number* n, bool ordinal) {
return ordinal ? n->ordinal : n->cardinal;
}
void fatal(const char* message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
void* xmalloc(size_t n) {
void* ptr = malloc(n);
if (ptr == NULL)
fatal("Out of memory");
return ptr;
}
void* xrealloc(void* p, size_t n) {
void* ptr = realloc(p, n);
if (ptr == NULL)
fatal("Out of memory");
return ptr;
}
char* xstrdup(const char* str) {
char* s = strdup(str);
if (s == NULL)
fatal("Out of memory");
return s;
}
typedef struct word_list_tag {
size_t size;
size_t capacity;
char** words;
} word_list;
void word_list_create(word_list* words, size_t capacity) {
words->size = 0;
words->capacity = capacity;
words->words = xmalloc(capacity * sizeof(char*));
}
void word_list_destroy(word_list* words) {
for (size_t i = 0; i < words->size; ++i)
free(words->words[i]);
free(words->words);
words->words = NULL;
}
void word_list_append(word_list* words, const char* str) {
size_t min_capacity = words->size + 1;
if (words->capacity < min_capacity) {
size_t new_capacity = (words->capacity * 3)/2;
if (new_capacity < min_capacity)
new_capacity = min_capacity;
words->words = xrealloc(words->words, new_capacity * sizeof(char*));
words->capacity = new_capacity;
}
words->words[words->size++] = xstrdup(str);
}
char* string_concat2(const char* str1, const char* str2) {
const size_t len1 = strlen(str1);
const size_t len2 = strlen(str2);
char* str = xmalloc(len1 + len2 + 1);
memcpy(str, str1, len1);
memcpy(str + len1, str2, len2);
str[len1 + len2] = 0;
return str;
}
char* string_concat3(const char* str1, const char* str2, const char* str3) {
const size_t len1 = strlen(str1);
const size_t len2 = strlen(str2);
const size_t len3 = strlen(str3);
char* str = xmalloc(len1 + len2 + len3 + 1);
memcpy(str, str1, len1);
memcpy(str + len1, str2, len2);
memcpy(str + len1 + len2, str3, len3);
str[len1 + len2 + len3] = 0;
return str;
}
size_t append_number_name(word_list* words, integer n, bool ordinal) {
size_t count = 0;
if (n < 20) {
word_list_append(words, get_small_name(&small[n], ordinal));
count = 1;
} else if (n < 100) {
if (n % 10 == 0) {
word_list_append(words, get_small_name(&tens[n/10 - 2], ordinal));
} else {
const char* name1 = get_small_name(&tens[n/10 - 2], false);
const char* name2 = get_small_name(&small[n % 10], ordinal);
char* str = string_concat3(name1, "-", name2);
word_list_append(words, str);
free(str);
}
count = 1;
} else {
const size_t names_len = sizeof(named_numbers)/sizeof(named_numbers[0]);
for (size_t i = 1; i <= names_len; ++i) {
if (i == names_len || n < named_numbers[i].number) {
integer p = named_numbers[i-1].number;
count += append_number_name(words, n/p, false);
if (n % p == 0) {
word_list_append(words, get_big_name(&named_numbers[i-1], ordinal));
++count;
} else {
word_list_append(words, get_big_name(&named_numbers[i-1], false));
++count;
count += append_number_name(words, n % p, ordinal);
}
break;
}
}
}
return count;
}
size_t count_letters(const char* str) {
size_t letters = 0;
for (size_t i = 0, n = strlen(str); i < n; ++i) {
if (isalpha((unsigned char)str[i]))
++letters;
}
return letters;
}
void sentence(word_list* result, size_t count) {
static const char* words[] = {
"Four", "is", "the", "number", "of", "letters", "in", "the",
"first", "word", "of", "this", "sentence,"
};
word_list_create(result, count + 10);
size_t n = sizeof(words)/sizeof(words[0]);
for (size_t i = 0; i < n && i < count; ++i)
word_list_append(result, words[i]);
for (size_t i = 1; count > n; ++i) {
n += append_number_name(result, count_letters(result->words[i]), false);
word_list_append(result, "in");
word_list_append(result, "the");
n += 2;
n += append_number_name(result, i + 1, true);
// Append a comma to the final word
char* last = result->words[result->size - 1];
char* new_last = string_concat2(last, ",");
free(last);
result->words[result->size - 1] = new_last;
}
}
size_t sentence_length(const word_list* words) {
size_t n = words->size;
if (n == 0)
return 0;
size_t length = n - 1;
for (size_t i = 0; i < n; ++i)
length += strlen(words->words[i]);
return length;
}
int main() {
setlocale(LC_ALL, "");
size_t n = 201;
word_list result = { 0 };
sentence(&result, n);
printf("Number of letters in first %'lu words in the sequence:\n", n);
for (size_t i = 0; i < n; ++i) {
if (i != 0)
printf("%c", i % 25 == 0 ? '\n' : ' ');
printf("%'2lu", count_letters(result.words[i]));
}
printf("\nSentence length: %'lu\n", sentence_length(&result));
for (n = 1000; n <= 10000000; n *= 10) {
word_list_destroy(&result);
sentence(&result, n);
const char* word = result.words[n - 1];
printf("The %'luth word is '%s' and has %lu letters. ", n, word, count_letters(word));
printf("Sentence length: %'lu\n" , sentence_length(&result));
}
word_list_destroy(&result);
return 0;
}</lang>
{{out}}
<pre>
Number of letters in first 201 words in the sequence:
4 2 3 6 2 7 2 3 5 4 2 4 8 3 2 3 6 5 2 3 5 3 2 3 6
3 2 3 5 5 2 3 5 3 2 3 7 5 2 3 6 4 2 3 5 4 2 3 5 3
2 3 8 4 2 3 7 5 2 3 10 5 2 3 10 3 2 3 9 5 2 3 9 3 2
3 11 4 2 3 10 3 2 3 10 5 2 3 9 4 2 3 11 5 2 3 12 3 2 3
11 5 2 3 12 3 2 3 11 5 2 3 11 3 2 3 13 5 2 3 12 4 2 3 11
4 2 3 9 3 2 3 11 5 2 3 12 4 2 3 11 5 2 3 12 3 2 3 11 5
2 3 11 5 2 3 13 4 2 3 12 3 2 3 11 5 2 3 8 3 2 3 10 4 2
3 11 3 2 3 10 5 2 3 11 4 2 3 10 4 2 3 10 3 2 3 12 5 2 3
11
Sentence length: 1,203
The 1,000th word is 'in' and has 2 letters. Sentence length: 6,279
The 10,000th word is 'in' and has 2 letters. Sentence length: 64,140
The 100,000th word is 'one' and has 3 letters. Sentence length: 659,474
The 1,000,000th word is 'the' and has 3 letters. Sentence length: 7,113,621
The 10,000,000th word is 'thousand' and has 8 letters. Sentence length: 70,995,756
</pre>
=={{header|C++}}==
| |||