#include <ctype.h>
#include <stdarg.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
constexpr size_t MAX_TOKEN_COUNT = 10'000,
MAX_SUCCESSOR_COUNT = MAX_TOKEN_COUNT / 2,
TOKEN_NOT_FOUND = SIZE_MAX, // Used as sentinel in `token_find`
SENTENCE_SIZE = 1000; // Size of the sentence buffer.
constexpr int MIN_SENTENCE_TOKEN_COUNT =
10; // Minimum token count in the generated sentence.
// Array of tokens registered so far.
//
// No duplicates are allowed.
const char *tokens[MAX_TOKEN_COUNT];
// Current number of tokens in `tokens`
size_t token_count = 0;
// Successor tokens to each token.
//
// Duplicates are allowed.
// One token has many successor tokens. `succs[token_id]` corresponds to
// `token[token_id]`'s successors. E.g., `Hello world Hello` leads to:
// token[0] => Hello
// token[1] => world
// succs[0] => world
// succs[1] => Hello
//
// We store strings (const char*) instead of `token_id`s, because we
// will only print them in this application.
const char *succs[MAX_TOKEN_COUNT][MAX_SUCCESSOR_COUNT];
// `succs`'s current size
size_t succ_counts[MAX_TOKEN_COUNT];
// Saves the character to continue with in the next iteration.
char *strtok_saveptr;
// Exits the program with an error message printed on stderr.
[[noreturn]] void die_at(const char *file, int line, const char *func,
const char *fmt, ...) {
va_list ap;
fprintf(stderr, "%s:%d: %s: ", file, line, func);
va_start(ap, fmt);
vfprintf(stderr, fmt, ap);
va_end(ap);
fputc('\n', stderr);
exit(EXIT_FAILURE);
}
// Augments `die_at` with filename, line number, and function name.
#define DIE(...) die_at(__FILE__, __LINE__, __func__, __VA_ARGS__)
// Overwrites non-printable characters in `str` with a space.
//
// Text may contain non-printable characters, which can lead to unnecessary
// tokens like like `"\xefthe"` (`\xef` is a hexadecimal code of a non-printable
// character), which actually stands for `"the"`. This function gets rid of
// these.
//
// `str`: input string
// Returns the number of replaced characters.
int replace_non_printable_chars_with_space(char *str) {
int replaced_char_count = 0;
//// BEGIN SOLUTION
for (size_t i = 0; i < strlen(str); ++i) {
if (!isprint(str[i])) {
str[i] = ' ';
++replaced_char_count;
}
}
//// END SOLUTION
return replaced_char_count;
}
// Returns the token index if `token` exists in `tokens`, otherwise
// returns the sentinel TOKEN_NOT_FOUND.
//
// `tokens`: token array
// `token_count`: current number of tokens in `tokens`.
// `token`: token to look up
size_t token_find(const char *token) {
//// BEGIN SOLUTION
size_t i; // Token index
for (i = 0; i < token_count; ++i) {
if (strcmp(tokens[i], token) == 0) {
return i;
}
}
return TOKEN_NOT_FOUND;
//// END SOLUTION
}
// Appends `token` to `tokens`.
//
// Returns the index of `token` in `tokens`.
size_t token_append(const char *token) {
if (token_count == MAX_TOKEN_COUNT) {
DIE("Token array full. Increase its size or reduce the amount of text. "
"token_count: %zu",
token_count);
}
//// BEGIN SOLUTION
tokens[token_count] = token;
return token_count++;
//// END SOLUTION
}
// Integrates `token_find` and `token_append`.
//
// If the token is found then it returns `token_find`s output. Otherwise, the
// `token_append` is used its return value returned.
size_t token_find_or_append(const char *token) {
//// BEGIN SOLUTION
size_t index = token_find(token);
if (index == TOKEN_NOT_FOUND) {
return token_append(token);
}
return index;
//// END SOLUTION
}
// Appends the token `succ` to the successors array of `token`.
//
// Duplicate tokens are allowed. E.g., in `Hello world Hello world`, the token
// `Hello` will have the following successors: `world`, `world`.
void succs_append(const size_t token_index, const char *succ) {
if (succ_counts[token_index] == MAX_SUCCESSOR_COUNT)
DIE("Successor array full for token_index %zu. Increase its size or reduce "
"the amount of text",
token_count);
succs[token_index][succ_counts[token_index]++] = succ;
}
// Splits `str` into tokens.
//
// Uses `strtok_r` to fill `tokens` and `succs`
// `str`: Input string. Will be modified by `strtok_r`.
// `tokens`: Output
// `delimiters`: String with delimiter characters used to tokenize the string.
void tokenize_and_fill_succs(char *str, const char *delimiters) {
char *token = strtok_r(str, delimiters, &strtok_saveptr);
char *predecessor_token = nullptr;
while (token != nullptr) {
token_find_or_append(token);
if (predecessor_token)
succs_append(token_find(predecessor_token), token);
predecessor_token = token; // Keep last token so we can update successors.
token =
strtok_r(nullptr, delimiters, &strtok_saveptr); // Get the new token.
}
}
// Returns the last character of a string.
//
// Returns `\0` if the string is empty.
// For example:
// `hello` => `o`
// `` => `\0`
char last_char(const char *str) {
//// BEGIN SOLUTION
int len = strlen(str);
if (len)
return str[strlen(str) - 1];
else // str empty
return '\0';
//// END SOLUTION
}
// Does the string end with `!`, `?` or dot (`.`)?
bool ends_a_sentence(const char *str) {
/// BEGIN SOLUTION
switch (last_char(str)) {
case '!':
case '?':
case '.':
return true;
}
return false;
/// END SOLUTION
}
// Returns the `token_index` of a random `token` that starts
// with a capital letter.
//
// `tokens`: token array
// `token_count`: current token
size_t random_token_index_that_starts_a_sentence() {
//// BEGIN SOLUTION
size_t token_index;
const char *token;
do {
token_index = rand() % token_count;
token = tokens[token_index];
} while (!isupper(token[0]));
// Find a token that starts with a capital letter
return token_index;
//// END SOLUTION
}
// Has a token any successors?
//
// Useful when generating sentences, e.g., if a token does not have any
// successors, then we must stop looking for further successors.
bool has_a_successor(const size_t token_index) {
//// BEGIN SOLUTION
return succ_counts[token_index] != 0;
//// END SOLUTION
}
// Generates a random sentence.
//
// The sentence array will be filled up to `sentence_size`-1 characters using
// random tokens.
//
// `sentence`: Random sentence output.
// Will be overwritten. Does not have to be initialized.
// `sentence_size`: countof(sentence)
// Returns the token count in of `sentence`.
int generate_sentence(char *sentence, size_t sentence_size) {
int sentence_token_count = 0;
size_t token_index = random_token_index_that_starts_a_sentence();
const char *token = tokens[token_index];
sentence[0] = '\0';
strcat(sentence, token);
sentence_token_count++;
if (ends_a_sentence(token))
return sentence_token_count;
// Calculated sentence length for the next iteration.
// Used to stop the loop if the calculated length *would* exceed
// `sentence_size-1`.
// Concatenates random successors to the sentence as long as
// `sentence` can hold them.
do {
if (!has_a_successor(token_index))
return sentence_token_count;
const char *succ = succs[token_index][rand() % succ_counts[token_index]];
// Space + successor + '\0` must fit in sentence_size
if (strlen(sentence) + 1 + strlen(succ) + 1 > sentence_size)
return sentence_token_count;
strcat(sentence, " ");
strcat(sentence, succ);
sentence_token_count++;
if (ends_a_sentence(succ))
return sentence_token_count;
token_index = token_find(succ);
} while (true);
return sentence_token_count;
}
// For testing the functionality
void generate_sentence_using_text(char *text) {
printf("# Replaced %d non-printable characters with spaces.\n",
replace_non_printable_chars_with_space(text));
puts("");
const char *delimiters = " \n\r"; // Full stop (`.`), exclamation mark (`!`)
// etc will be part of a token.
tokenize_and_fill_succs(text, delimiters);
puts("# After tokenize_and_fill_succs:");
printf("Token count: %zu\n", token_count);
printf("First token: %s\n", tokens[0]);
printf("First four successors of the first token:");
for (size_t i = 0; i < 4; ++i)
printf(" %s", succs[0][i]);
puts("\n");
char sentence[SENTENCE_SIZE];
srand(time(nullptr)); // Be random each time we run the program
puts("# Random sentence ending with a full-stop:");
int sentence_token_count;
do {
sentence_token_count = generate_sentence(sentence, sizeof sentence);
} while (last_char(sentence) != '.' ||
sentence_token_count < MIN_SENTENCE_TOKEN_COUNT);
puts(sentence);
}
void reset_data_structures() {
token_count = 0;
for (size_t i = 0; i < MAX_TOKEN_COUNT; ++i)
succ_counts[i] = 0;
}
int main() {
char text_basic[] = {
#embed "basic.txt" // Stores the content of the file as an array of chars
, '\0'}; // and appends a null character to make it a string.
char text_moon[] = {
#embed "moon.txt"
, '\0'};
puts("### BASIC");
generate_sentence_using_text(text_basic);
puts("\n");
puts("### MOON");
reset_data_structures();
generate_sentence_using_text(text_moon);
}