#define BOWLING_PROGRAM__BULWARK_OPEN {
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdint.h>
#include <inttypes.h>
#include <limits.h>
#include <string.h>
struct bowling_program__data_up__program_state {
/* Everything, at once. */
FILE * bowling_program__field__input_file;
/* The input file, this one. */
FILE * bowling_program__field__output_file;
/* This is where the answer goes, hopefully. */
char * bowling_program__field__line_buffer_itself;
/* fgets() bounded input, why read input any other way. */
size_t bowling_program__field__line_buffer_its_size;
/* The byte size of the line buffer, as a size_t; size_t for sizez … */
int bowling_program__field__line_buffer_its_isize;
/* The byte size of the line buffer itself, as an int, for fgets(). */
size_t * bowling_program__field__kayles_values_array_itself;
/* The array to store the Kayles sequence, at least its first 204 terms; 204 = 17·12. */
size_t bowling_program__field__kayles_values_array_its_size;
/* The malloc() -ed size of the Kayles sequence above, nothing too fancy. */
size_t * bowling_program__field__mex_set_array_itself;
/* A set encoded with an incrementing marker, perfectly suited for computing mex values. */
size_t bowling_program__field__mex_set_array_its_size;
/* The malloc() -ed size of the mex set array just above, nothing too fancy. */
};
#define BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE 0
#define BOWLING_PROGRAM__EXIT_STATUS__FAILURE__OUT_OF_MEMORY 1
#define BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT 2
#define BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_SIZE_TYPE 3
#define BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_INT_TYPE 4
#define BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR 5
#define BOWLING_PROGRAM__CONSTRAINTS__MIN_T__ITSELF 1
#define BOWLING_PROGRAM__CONSTRAINTS__MIN_T__ITS_DECIMAL_REPRESENTATION "1"
#define BOWLING_PROGRAM__CONSTRAINTS__MAX_T__ITSELF 10
#define BOWLING_PROGRAM__CONSTRAINTS__MAX_T__ITS_DECIMAL_REPRESENTATION "10"
#define BOWLING_PROGRAM__CONSTRAINTS__MIN_N__ITSELF 1
#define BOWLING_PROGRAM__CONSTRAINTS__MIN_N__ITS_DECIMAL_REPRESENTATION "1"
#define BOWLING_PROGRAM__CONSTRAINTS__MAX_N__ITSELF 50000
#define BOWLING_PROGRAM__CONSTRAINTS__MAX_N__ITS_DECIMAL_REPRESENTATION "50000"
#define BOWLING_PROGRAM__FINICKY_CHOICES__LEEWAY__ITSELF 2000
#define BOWLING_PROGRAM__FINICKY_CHOICES__LEEWAY__ITS_DECIMAL_REPRESENTATION "2000"
#define BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITSELF 102010
#define BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITS_DECIMAL_REPRESENTATION "102010"
#define BOWLING_PROGRAM__BULWARK_CLOSE }
int bowling_program__code_up__validate_size_t_value (size_t the_value_itself, char const * the_value_its_decimal_representation) {
/* Step is define and declare a few local variables. */ {
BOWLING_PROGRAM__BULWARK_CLOSE
int exit_status = BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE;
BOWLING_PROGRAM__BULWARK_OPEN
}
/* Step is answer the question, on condition the literal, its value, is zero. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
if (0 == the_value_itself) {
if (0 != strcmp("0", the_value_its_decimal_representation)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_SIZE_TYPE;
}
}
}
}
/* Step is answer the question, on condition the literal, its value, is greater than zero. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
if (0 < the_value_itself) {
size_t remaining_value = 0;
size_t remaining_length = 0;
char current_intended_symbol = 0;
size_t current_actual_digit = 0;
char current_actual_symbol = '\0';
remaining_value = the_value_itself;
remaining_length = strlen(the_value_its_decimal_representation);
while ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (0 < remaining_value) && (0 < remaining_length)) {
current_intended_symbol = the_value_its_decimal_representation[remaining_length - 1];
current_actual_digit = remaining_value % 10;
current_actual_symbol = (char)(((size_t)'0') + current_actual_digit);
if (current_intended_symbol != current_actual_symbol) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_SIZE_TYPE;
}
else {
remaining_value /= 10;
remaining_length -= 1;
}
}
}
}
}
/* Step is pass the baton.. */ {
return exit_status;
}
}
size_t bowling_program__code_up__number_of_digits (size_t the_value_itself) {
size_t the_result = 1999;
if (0 == the_value_itself) {
the_result = 1;
}
else {
size_t remaining_value = 0;
size_t count_so_far = 0;
assert(0 < the_value_itself);
remaining_value = the_value_itself;
count_so_far = 0;
while (0 < remaining_value) {
count_so_far += 1;
remaining_value /= 10;
}
the_result = count_so_far;
}
return the_result;
}
int bowling_program__code_up__acquire_all_resources_up_front (struct bowling_program__data_up__program_state * * receptacle) {
/* Step is define and declare a few local variables. */ {
BOWLING_PROGRAM__BULWARK_CLOSE
int exit_status = BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE;
struct bowling_program__data_up__program_state * program_state = NULL;
FILE * input_file = NULL;
FILE * output_file = NULL;
char * line_buffer_itself = NULL;
size_t line_buffer_its_size = 0;
size_t line_buffer_its_isize = 0;
size_t * kayles_values_array_itself = NULL;
size_t kayles_values_array_its_size = 0;
size_t * mex_set_array_itself = NULL;
size_t mex_set_array_its_size = 0;
BOWLING_PROGRAM__BULWARK_OPEN
}
/* Step is validate the constraints and the choices. */ {
/* Step is save a few words on what is the objective here ? */ {
/* Simply verify that the literals fit into their intended data types.
*
* The defines introducing these literals, they could be changed.
*
* Changed to run this program with larger constraints.
*
* With this in mind, let's check if the literals fit into size_t variables.
*
* Also check that the constraints are consistent, like 1 ≤ min_n ≤ max_n.
*
* Also check that the derived values, like max line length for given max_n, max_t, they are plentiful.
*
* For example, says one would change n to 200000, then the line buffer should be at least 400000 + change, say change = 20.
*
* One goes from 200000 to 400000, because at least one space before each 0 or 1 used to encode the state of a pin.
*
* Plus change, this is considering one also needs to encode N, before the bowling pins, in a line from the input file.
*
* Leeway is to allow the lines be possibly extended with annotations, after N and the pins are provided.
*
* For example, one could write a few words, noting what it is interesting about the respective game configuration.
*
*
*
* In short, a self test.
*
* The program would not continue its execution if the self test is not passed.
*
* The self test passed, the remaining of the implementation of the program should be fine for the task at hand.
*
*/
}
/* Step is verify the min t, to fit within size_t variables. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t value_itself = 0;
const char * value_its_decimal_representation = NULL; ;
int status_of_sorts = 0;
value_itself = BOWLING_PROGRAM__CONSTRAINTS__MIN_T__ITSELF;
value_its_decimal_representation = BOWLING_PROGRAM__CONSTRAINTS__MIN_T__ITS_DECIMAL_REPRESENTATION;
status_of_sorts = bowling_program__code_up__validate_size_t_value(value_itself, value_its_decimal_representation);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status = status_of_sorts;
}
}
}
/* Step is verify the max t, to fit within size_t variables. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t value_itself = 0;
const char * value_its_decimal_representation = NULL; ;
int status_of_sorts = 0;
value_itself = BOWLING_PROGRAM__CONSTRAINTS__MAX_T__ITSELF;
value_its_decimal_representation = BOWLING_PROGRAM__CONSTRAINTS__MAX_T__ITS_DECIMAL_REPRESENTATION;
status_of_sorts = bowling_program__code_up__validate_size_t_value(value_itself, value_its_decimal_representation);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status = status_of_sorts;
}
}
}
/* Step is verify the min n, to fit within size_t variables. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t value_itself = 0;
const char * value_its_decimal_representation = NULL;
int status_of_sorts = 0;
value_itself = BOWLING_PROGRAM__CONSTRAINTS__MIN_N__ITSELF;
value_its_decimal_representation = BOWLING_PROGRAM__CONSTRAINTS__MIN_N__ITS_DECIMAL_REPRESENTATION;
status_of_sorts = bowling_program__code_up__validate_size_t_value(value_itself, value_its_decimal_representation);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status = status_of_sorts;
}
}
}
/* Step is verify the max n, to fit within size_t variables. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t value_itself = 0;
const char * value_its_decimal_representation = NULL;
int status_of_sorts = 0;
value_itself = BOWLING_PROGRAM__CONSTRAINTS__MAX_N__ITSELF;
value_its_decimal_representation = BOWLING_PROGRAM__CONSTRAINTS__MAX_N__ITS_DECIMAL_REPRESENTATION;
status_of_sorts = bowling_program__code_up__validate_size_t_value(value_itself, value_its_decimal_representation);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status = status_of_sorts;
}
}
}
/* Step is validate the constraints among themselves. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t min_t = 0;
size_t max_t = 0;
size_t min_n = 0;
size_t max_n = 0;
min_t = BOWLING_PROGRAM__CONSTRAINTS__MIN_T__ITSELF;
max_t = BOWLING_PROGRAM__CONSTRAINTS__MAX_T__ITSELF;
min_n = BOWLING_PROGRAM__CONSTRAINTS__MIN_N__ITSELF;
max_n = BOWLING_PROGRAM__CONSTRAINTS__MAX_N__ITSELF;
if ((max_t < min_t) || (min_n < 1) || (max_n < min_n)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
}
}
/* Step is validate the line, its size, to fit within size_t variables. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t value_itself = 0;
const char * value_its_decimal_representation = NULL;
int status_of_sorts = 0;
value_itself = BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITSELF;
value_its_decimal_representation = BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITS_DECIMAL_REPRESENTATION;
status_of_sorts = bowling_program__code_up__validate_size_t_value(value_itself, value_its_decimal_representation);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status = status_of_sorts;
}
}
}
/* Step is validate the line, its size, to fit with int variables. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
/* One uses fgets() to read from the input file.
*
* fgets() started its existence with int, for its buffer size parameter.
*
* This block is sequentially coupled with the one above.
*
* The block above, where it is verified that line buff, its size, can be stored in size_t variables.
*
* Wee sequential coupling, saved by neat locality of behavior; it is fine, don't worry about it.
*/
size_t line_buffer_its_max_size = 0;
line_buffer_its_max_size = BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITSELF;
if ( ((unsigned int)INT_MAX) < line_buffer_its_max_size) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_INT_TYPE;
}
}
}
/* Step is validate the leeway, to fit within size_t variables. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t value_itself = 0;
const char * value_its_decimal_representation = NULL;
int status_of_sorts = 0;
value_itself = BOWLING_PROGRAM__FINICKY_CHOICES__LEEWAY__ITSELF;
value_its_decimal_representation = BOWLING_PROGRAM__FINICKY_CHOICES__LEEWAY__ITS_DECIMAL_REPRESENTATION;
status_of_sorts = bowling_program__code_up__validate_size_t_value(value_itself, value_its_decimal_representation);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status = status_of_sorts;
}
}
}
/* Step is validate the leeway, to be a reasonably useful value, useful. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t leeway_itself = 0;
leeway_itself = BOWLING_PROGRAM__FINICKY_CHOICES__LEEWAY__ITSELF;
if (leeway_itself < 2000) {
/* Arguably, a leeway of at least 2000 bytes is fine.
*
*
* On one hand, if the line is not annotated, or contains extra problems, fgets(), it would not burn daylight for nothing.
*
* It would simply scan throgh the \n line ending, and return the line, no problemo.
*
*
* On the other hand, one may add quite hefty comments after the values in the line were provided, so the input format is not too strict.
*
* It, the format of the input file, it would allow one to scribble at the end of the lines, say enough details about the respective line.
*
*/
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
}
}
/* Step is validate the line buffer, it is plentiful engouh to contain the header line from the input file, in its entirety. */ {
size_t line_buffer_its_size = 0;
size_t leeway_itself = 0;
size_t max_t_itself = 0;
size_t max_t_its_number_of_digits = 0;
size_t remaining_space = 0;
line_buffer_its_size = BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITSELF;
leeway_itself = BOWLING_PROGRAM__FINICKY_CHOICES__LEEWAY__ITSELF;
max_t_itself = BOWLING_PROGRAM__CONSTRAINTS__MAX_T__ITSELF;
max_t_its_number_of_digits = bowling_program__code_up__number_of_digits(max_t_itself);
remaining_space = line_buffer_its_size;
if ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (remaining_space < max_t_its_number_of_digits)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
remaining_space -= max_t_its_number_of_digits;
}
if ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (remaining_space < leeway_itself)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
remaining_space -= leeway_itself;
}
if ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (remaining_space < 1)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
remaining_space -= leeway_itself; /* the terminating line feed, fgets() keeps this, in its result. */
}
}
/* Step is validate the line buffer, it is plentiful engouh to contain any game configuration line from the input file, in its entirety. */ {
size_t line_buffer_its_size = 0;
size_t leeway_itself = 0;
size_t max_n_itself = 0;
size_t max_n_its_number_of_digits = 0;
size_t remaining_space = 0;
line_buffer_its_size = BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITSELF;
leeway_itself = BOWLING_PROGRAM__FINICKY_CHOICES__LEEWAY__ITSELF;
max_n_itself = BOWLING_PROGRAM__CONSTRAINTS__MAX_N__ITSELF;
max_n_its_number_of_digits = bowling_program__code_up__number_of_digits(max_n_itself);
remaining_space = line_buffer_its_size;
if ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (remaining_space < max_n_its_number_of_digits)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
remaining_space -= max_n_its_number_of_digits;
}
if ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && ((remaining_space / 2) < max_n_itself)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
remaining_space -= (2 * max_n_itself);
}
if ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (remaining_space < leeway_itself)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
remaining_space -= leeway_itself;
}
if ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (remaining_space < 1)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
remaining_space -= leeway_itself; /* the terminating line feed, fgets() keeps this, in its result. */
}
}
}
/* Step is malloc() acquire the program state object itself. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_bytes = sizeof(struct bowling_program__data_up__program_state);
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__OUT_OF_MEMORY;
}
else {
/* publish */
program_state = pointer_itself;
}
}
}
/* Step is fopen() acquire the input file itself. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
FILE * pointer_itself = NULL;
pointer_itself = fopen("bowling.in", "r");
if (NULL == pointer_itself) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
/* publish */
input_file = pointer_itself;
}
}
}
/* Step is fopen() acquire the output file itself. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
FILE * pointer_itself = NULL;
pointer_itself = fopen("bowling.out", "w");
if (NULL == pointer_itself) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
/* publish */
output_file = pointer_itself;
}
}
}
/* Step is malloc() acquire the line buffer itself. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_elements = BOWLING_PROGRAM__FINICKY_CHOICES__LINE_BUFFER__ITS_SIZE__ITSELF;
element_byte_size = sizeof(char);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__OUT_OF_MEMORY;
}
else {
/* publish */
line_buffer_itself = pointer_itself;
line_buffer_its_size = number_of_elements;
line_buffer_its_isize = (size_t) number_of_elements; /* safe cast, tee-hee */
}
}
}
}
/* Step is malloc() acquire the kayles values array itself. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_elements = 204; /* size_t variable is asssigned 204 is okay, because SIZE_MAX is at least 65535, don't worry about it … */
element_byte_size = sizeof(size_t);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__OUT_OF_MEMORY;
}
else {
/* publish */
kayles_values_array_itself = pointer_itself;
kayles_values_array_its_size = number_of_elements;
}
}
}
}
/* Step is malloc() acquire the mex set array itself. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
/* Unsurprisingly, the mex set array, its size, it depends on the size of the kayles values array.
*
* In the case of Kayles game, practically, the size is much smaller.
*
* In general, the bound is the size of the array holding the nimbers of the game.
*
* This bound may be understood considering a topological ordering of the nodes of the game.
*
* Computing the values for the nodes of this graph, the nodes visited in their sorted order.
*
* The bound is tight, the nimber of a single pile of n rocks, when playing the Nim game itself.
*/
if (SIZE_MAX <= kayles_values_array_its_size) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_elements = kayles_values_array_its_size + 1;
element_byte_size = sizeof(size_t);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__OUT_OF_MEMORY;
}
else {
/* publish */
mex_set_array_itself = pointer_itself;
mex_set_array_its_size = number_of_elements;
}
}
}
}
}
/* Step is pass the baton, the execution status. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
program_state->bowling_program__field__input_file = input_file;
program_state->bowling_program__field__output_file = output_file;
program_state->bowling_program__field__line_buffer_itself = line_buffer_itself;
program_state->bowling_program__field__line_buffer_its_size = line_buffer_its_size;
program_state->bowling_program__field__line_buffer_its_isize = line_buffer_its_isize;
program_state->bowling_program__field__kayles_values_array_itself = kayles_values_array_itself;
program_state->bowling_program__field__kayles_values_array_its_size = kayles_values_array_its_size;
program_state->bowling_program__field__mex_set_array_itself = mex_set_array_itself;
program_state->bowling_program__field__mex_set_array_its_size = mex_set_array_its_size;
/* publish */
*receptacle = program_state;
}
else {
if (NULL != mex_set_array_itself) {
free(mex_set_array_itself);
mex_set_array_itself = NULL;
mex_set_array_its_size = 0;
}
if (NULL != kayles_values_array_itself) {
free(kayles_values_array_itself);
kayles_values_array_itself = NULL;
kayles_values_array_its_size = 0;
}
if (NULL != line_buffer_itself) {
free(line_buffer_itself);
line_buffer_itself = NULL;
line_buffer_its_size = 0;
line_buffer_its_isize = 0;
}
if (NULL != output_file) {
int status_too = 0;
status_too = fclose(output_file);
output_file = NULL;
(void) status_too;
}
if (NULL != input_file) {
int status_too = 0;
status_too = fclose(input_file);
input_file = NULL;
(void) status_too;
}
if (NULL != program_state) {
free(program_state);
program_state = NULL;
}
}
return exit_status;
}
}
int bowling_program__code_up__solve_the_problem_already (struct bowling_program__data_up__program_state * program_state) {
/* Step is define and declare a few local variables. */ {
BOWLING_PROGRAM__BULWARK_CLOSE
int exit_status = BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE;
(void) program_state;
BOWLING_PROGRAM__BULWARK_OPEN
}
/* Step is compute the Kayles table, using the recurrence relations satisfied by the terms of the Kayles sequence. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
/* https://en.wikipedia.org/wiki/Kayles
*
*
*
* K₀ = 0.
*
* Kₙ = {Kₛ ⊕ Kₜ; x, s, t, x ∈ ℤ, 1 ≤ x ≤ 2, 0 ≤ s ≤ t, n ≤ s + x + t ≤ n}.
*
* Kₙ, the nim value, the nimber, of any n consecutive bowling pins.
*
*
*
* It is known that K(n) = K(n − 12), ∀ n ∈ ℤ, 84 ≤ n ⇒ 84 = 7·12.
*
* [∀ n ∈ ℤ, 84 ≤ n ⇒ K(n) = K(n − 12)] ⇔ [∀ r ∈ ℤ, ∀ g ∈ ℤ, 7 ≤ r ∧ 0 ≤ g ≤ 11 ⇒ K(r·12 + g) = K(6·12 + g)]
*
* It is known, for example the Wikipedia, its Kayles page.
*
*
*
* Hopefully, in this lexical block, a proof of the above claim on the peridicity of the Kaykes sequence Kₙ, n ∈ ℕ ∪ {0}.
*/
size_t * kayles_values_array_itself = NULL;
size_t kayles_values_array_its_size = 0;
size_t * mex_set_array_itself = NULL;
size_t mex_set_array_its_size = 0;
size_t current_number_n = 0;
size_t current_level_h = 0;
size_t current_number_x = 0;
size_t current_number_n1 = 0;
size_t current_number_n2 = 0;
size_t current_nimber_g = 0;
size_t current_nimber_g1 = 0;
size_t current_nimber_g2 = 0;
kayles_values_array_itself = program_state->bowling_program__field__kayles_values_array_itself;
kayles_values_array_its_size = program_state->bowling_program__field__kayles_values_array_its_size;
mex_set_array_itself = program_state->bowling_program__field__mex_set_array_itself;
mex_set_array_its_size = program_state->bowling_program__field__mex_set_array_its_size;
if ((mex_set_array_its_size < kayles_values_array_its_size) || (kayles_values_array_its_size < 3)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
current_level_h = 0;
current_nimber_g = 0;
while (current_nimber_g < kayles_values_array_its_size) {
mex_set_array_itself[current_nimber_g] = current_level_h;
current_nimber_g += 1;
}
current_number_n = 0;
kayles_values_array_itself[current_number_n] = 0; /* K₀ = 0 */
current_number_n += 1;
current_level_h += 1;
while ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (current_number_n < kayles_values_array_its_size)) {
current_number_x = 1;
while ((current_number_x <= 2) && (current_number_x <= current_number_n)) {
current_number_n1 = 0;
current_number_n2 = (current_number_n - current_number_x) - current_number_n1;
while (current_number_n1 <= current_number_n2) {
current_nimber_g1 = kayles_values_array_itself[current_number_n1];
current_nimber_g2 = kayles_values_array_itself[current_number_n2];
current_nimber_g = current_nimber_g1 ^ current_nimber_g2;
if (current_nimber_g <= current_number_n) {
mex_set_array_itself[current_nimber_g] = current_level_h;
}
else {
/* a moment's thought would reveal one needs not bother marking this nimber value,
*
* in the mex set array itself, which is why one simply skips in the alternative block,
*
* doing what the program only does in the consequent block, above.
*
*
* https://en.wikipedia.org/wiki/Conditional_(computer_programming)
*
* if (Boolean condition) { consequent-block } else { alternative-block }, adapted from Wikipedia,
* and only a little bit; let's go!
*
*
*/
}
current_number_n1 += 1;
current_number_n2 -= ((current_number_n2 > 0) ? 1 : 0);
}
current_number_x += 1;
}
current_nimber_g = 0;
while ((current_nimber_g <= current_number_n) && (current_level_h == mex_set_array_itself[current_nimber_g])) {
current_nimber_g += 1;
}
if (current_number_n < current_nimber_g) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
/* Kₙ = mex ({Kₛ ⊕ Kₜ; s, t ∈ ℤ, 0 ≤ s ≤ t, s + 1 + t = n ∨ s + 2 + t = n}
*
* S ⊆ ℕ ∪ {0}, S finite; mex S := min ((ℕ ∪ {0}) \ S), the minimum excluded value.
*
*/
kayles_values_array_itself[current_number_n] = current_nimber_g;
current_number_n += 1;
current_level_h += 1;
}
}
}
}
}
/* Step is verify the Kayles table is periodic, ∀ n ∈ ℤ, 84 ≤ n ⇒ K(n) = K(n − 12); K(n) and Kₙ, the n -th term in the Kayles sequence. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t * kayles_values_array_itself = NULL;
size_t kayles_values_array_its_size = 0;
size_t current_term_its_index = 0;
size_t current_term_itself = 0;
size_t period_related_term_its_index = 0;
size_t period_related_term_itself = 0;
kayles_values_array_itself = program_state->bowling_program__field__kayles_values_array_itself;
kayles_values_array_its_size = program_state->bowling_program__field__kayles_values_array_its_size;
if (kayles_values_array_its_size < 204) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
/* Kₙ₋₁₂ = Kₙ, ∀ n ≥ 84, n ∈ ℤ; It is known.
*
* 204, this one would suffice to conclude that the K(n − 12) = K(n) holds for all n ≥ 84, not only for those ≤ 204 − 1.
*
* The 204, it would return in a short proof.
*/
current_term_its_index = 84;
while ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (current_term_its_index < kayles_values_array_its_size)) {
current_term_itself = kayles_values_array_itself[current_term_its_index];
period_related_term_its_index = current_term_its_index - /* the period: */ 12;
period_related_term_itself = kayles_values_array_itself[period_related_term_its_index];
if (period_related_term_itself != current_term_itself) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR;
}
else {
current_term_its_index += 1;
}
}
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
/* T The 204, it would return in a short proof; well, it has.
* T
* T
* T 2 Let ⊕ be the XOR operation.
* T 2
* T 2 3 Say a = ∑ j ← 0 … w − 1 ∷ aⱼ·2ʲ, b = ∑ j ← 0 … w − 1 ∷ bⱼ·2ʲ, where aⱼ, bⱼ ∈ {0, 1}, j := 0 … w − 1.
* T 2 3
* T 2 3 Letter w, short for [bit] width.
* T 2 3
* T 2 3 a ⊕ b = c ⇔ [c = ∑ j ← 0 … w − 1 ∷ aⱼ·2ʲ; cⱼ = 1 ⇔ aⱼ ≠ bⱼ, cⱼ = 0 ⇔ aⱼ = bⱼ, ∀ j ∈ ℤ, 0 ≤ j ≤ w − 1].
* T
* T
* T 2 For n ∈ ℤ, n ≥ 1, MEX_SET(n), defined as follows.
* T 2
* T 2
* T 2 3 MEX_SET(n) := {K(n₁) ⊕ K(n₂); ∀ n₁, n₂ ∈ ℤ, ∃ x ∈ {1, 2}, 0 ≤ n₁ ≤ n₂, n₁ + x + n₂ = n}.
* T
* T
* T 2 Recurrence relations for the Kayles sequence, its terms.
* T 2
* T 2
* T 2 3 K(0) = 0
* T 2
* T 2 3 K(n) = mex(MEX_SET(n)).
* T
* T
* T 2 K(n) = K(n − 12), ∀ n ∈ [84, 203] ∩ ℤ.
* T 2
* T 2
* T 2 3 These 203 − 84 + 1 = 120 indeed hold true, just verified with this program.
* T
* T
* T 2 Induction hypothesis IH(n), it is K(w) = K(w − 12), ∀ w ∈ ℤ, 84 ≤ w ≤ n − 1; 84 = 7·12.
* T 2
* T 2 One may recast IH(N), as K(s·12 + j) = K(6·12 + j), ∀ s ∈ ℤ, ∀ j ∈ ℤ, 7 ≤ s, 0 ≤ j ≤ 11, s·12 + j ≤ n − 1.
* T
* T
* T 2 No doubt, n = r·12 + g, for some two integers r ∈ ℤ, g ∈ ℤ, 17 ≤ r, 0 ≤ g ≤ 11.
* T 2
* T 2 Let m = 192 + g; 192 = 16·12; m ≤ n − 1.
* T 2
* T 2 One will show that MEX_SET(n) = MEX_SET(m).
* T 2
* T 2
* T 2 3 Choose x ∈ {1, 2}, any one would do.
* T 2 3
* T 2 3
* T 2 3 4 On one hand,
* T 2 3 4 for any pair (n₁, n₂), such that n₁ ∈ ℤ, n₂ ∈ ℤ, 0 ≤ n₁ ≤ n₂, n₁ + x + n₂ = n,
* T 2 3 4 one gives a pair (m₁, m₂), such that m₁ ∈ ℤ, m₂ ∈ ℤ, 0 ≤ m₁ ≤ m₂, m₁ + x + m₂ = m, and
* T 2 3 4 K(n₁) ⊕ K(n₂) = K(m₁) ⊕ K(m₂).
* T 2 3 4
* T 2 3 4 For example, given (n₁, n₂), one simply gives back (m₁, m₂),
* T 2 3 4 where m₁ := min(n1, 72 + g), and m₂ := (m − x) − m₁.
* T 2 3
* T 2 3
* T 2 3
* T 2 3 4 On the other hand,
* T 2 3 4 for any pair (m₁, m₂), such that m₁ ∈ ℤ, m₂ ∈ ℤ, 0 ≤ m₁ ≤ m₂, m₁ + x + m₂ = m,
* T 2 3 4 one gives a pair (n₁, n₂), such that n₁ ∈ ℤ, n₂ ∈ ℤ, 0 ≤ n₁ ≤ n₂, n₁ + x + n₂ = n, and
* T 2 3 4 K(n₁) ⊕ K(n₂) =K(m₁) ⊕ K(m₂).
* T 2 3 4
* T 2 3 4 For example, given (m₁, m₂), one simply gives back (n₁, n₂),
* T 2 3 4 where n₁ := m₁, and n₂ := (n − x) − n₁.
* T 2 3
* T 2 3
* T 2 3 4 It results then that MEX_SET(n) = MEX_SET(m), wherefrom K(n) = K(m),
* T 2 3 4 and one already knows that K(m) = K(72 + g), so K(n) = K(72 + g) = K(n − 12). ⚑
* T
* T
* T
* T 3 Let SG(n) := Kₙ, the Sprague Grundy function for n consecutive bowling pins, the NIMber.
* T 3
* T 3
* T 3 4 SG(n) = Kₙ, on condition n ∈ [0, 83] ∩ ℤ;
* T 3 4
* T 3 4 SG(n) = K(6 + n % 12), on condition n ∈ ℤ, 84 ≤ n.
* T 3 4
* T 3 4 Tertium non datur, and what a relief.
*/
}
}
}
}
/* Step is pass the baton, the execution status. */ {
return exit_status;
}
}
int bowling_program__code_up__write_the_output_already (struct bowling_program__data_up__program_state * program_state) {
/* Step is define and declare a few local variables. */ {
BOWLING_PROGRAM__BULWARK_CLOSE
int exit_status = BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE;
size_t number_of_tests = 0;
BOWLING_PROGRAM__BULWARK_OPEN
}
/* Step is read the number of tests or challenges, the number T from the problem statement, at least 1, at most 10. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t min_t = 0;
size_t max_t = 0;
FILE * input_file_itself = NULL;
char * line_buffer_itself = NULL;
size_t line_buffer_its_isize = 0;
char * pointer_from_fgets = NULL;
size_t length_itself = 0;
size_t value_t = 0;
size_t status_from_sscanf = 0;
min_t = BOWLING_PROGRAM__CONSTRAINTS__MIN_T__ITSELF;
max_t = BOWLING_PROGRAM__CONSTRAINTS__MAX_T__ITSELF;
input_file_itself = program_state->bowling_program__field__input_file;
line_buffer_itself = program_state->bowling_program__field__line_buffer_itself;
line_buffer_its_isize = program_state->bowling_program__field__line_buffer_its_isize;
pointer_from_fgets = fgets(line_buffer_itself, line_buffer_its_isize, input_file_itself);
if ((NULL == pointer_from_fgets) || (pointer_from_fgets != line_buffer_itself)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
length_itself = strlen(line_buffer_itself);
if ((length_itself < 1) || (line_buffer_itself[length_itself - 1] != '\n')) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
status_from_sscanf = sscanf(line_buffer_itself, "%zu", &value_t);
if (1 != status_from_sscanf) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
if ((value_t < min_t) || (max_t < value_t)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
/* publish */
number_of_tests = value_t;
}
}
}
}
}
}
/* Step is one by one, read a test, solve a test, rinse and repeat, the lot of them, solve, solve, solve, and let's go, already! */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t current_test_its_index = 0; /* say tests are indexed from 0, up to T − 1, to make a plan on how to loop over these things. */
size_t line_its_char_size = 0;
size_t the_current_victor = 0;
while ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) && (current_test_its_index < number_of_tests)) {
/* Step is read the line containing the test, from the file, into the memory, all of it, up to its list byte, the line feed. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
FILE * input_file_itself = NULL;
char * line_buffer_itself = NULL;
size_t line_buffer_its_isize = 0;
char * pointer_from_fgets = 0;
size_t line_its_length = 0;
input_file_itself = program_state->bowling_program__field__input_file;
line_buffer_itself = program_state->bowling_program__field__line_buffer_itself;
line_buffer_its_isize = program_state->bowling_program__field__line_buffer_its_isize;
pointer_from_fgets = fgets(line_buffer_itself, line_buffer_its_isize, input_file_itself);
if (NULL == pointer_from_fgets) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
line_its_length = strlen(line_buffer_itself);
if ((1 > line_its_length) || ('\n' != line_buffer_itself[line_its_length - 1])) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
line_buffer_itself[line_its_length - 1] = '\0';
line_its_length -= 1;
/* publish */
line_its_char_size = line_its_length;
}
}
}
}
/* Step is solve the current challenge, the test just read from the line, from the file, find the answer, Narghileanu or Fumeanu. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
size_t * kayles_values_array = NULL;
char * line_buffer_itself = NULL;
size_t number_of_bowling_pins = 0;
int bytes_scanned_through = 0;
int status_from_sscanf = 0;
size_t line_buffer_where_at = 0;
char current_symbol = 0;
size_t number_of_consecutive_bowling_pins_itself = 0;
size_t number_of_consecutive_bowling_pins_its_nimber = 0; /* SG(number_of_consecutive_bowling_pins_itself), the nimber. */
/* SG, the Sprague Grundy function */
size_t number_of_bowling_pin_spots_described_so_far = 0;
size_t the_game_its_xor_sum = 0;
kayles_values_array = program_state->bowling_program__field__kayles_values_array_itself;
line_buffer_itself = program_state->bowling_program__field__line_buffer_itself;
status_from_sscanf = sscanf(line_buffer_itself, "%zu" "%n", &number_of_bowling_pins, &bytes_scanned_through);
if ((1 != status_from_sscanf) || (0 > bytes_scanned_through) || (SIZE_MAX < ((unsigned) bytes_scanned_through))) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
line_buffer_where_at = (size_t) bytes_scanned_through;
while ((BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) &&
(line_buffer_where_at < line_its_char_size) &&
(number_of_bowling_pin_spots_described_so_far < number_of_bowling_pins)) {
current_symbol = line_buffer_itself[line_buffer_where_at];
if (('0' != current_symbol) && ('1' != current_symbol) && (' ' != current_symbol)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
if ('1' == current_symbol) {
number_of_consecutive_bowling_pins_itself += 1;
number_of_bowling_pin_spots_described_so_far += 1;
}
else {
if ('0' == current_symbol) {
if (0 != number_of_consecutive_bowling_pins_itself) {
if (number_of_consecutive_bowling_pins_itself < 84) {
number_of_consecutive_bowling_pins_its_nimber = kayles_values_array[number_of_consecutive_bowling_pins_itself];
}
else {
number_of_consecutive_bowling_pins_its_nimber = kayles_values_array[72 + (number_of_consecutive_bowling_pins_itself % 12)];
}
the_game_its_xor_sum ^= number_of_consecutive_bowling_pins_its_nimber;
number_of_consecutive_bowling_pins_itself = 0;
}
number_of_bowling_pin_spots_described_so_far += 1;
}
else {
/* the space, simply skip this one. */
}
}
line_buffer_where_at += 1;
}
}
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
if (number_of_bowling_pin_spots_described_so_far < number_of_bowling_pins) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
else {
if (0 != number_of_consecutive_bowling_pins_itself) {
if (number_of_consecutive_bowling_pins_itself < 84) {
number_of_consecutive_bowling_pins_its_nimber = kayles_values_array[number_of_consecutive_bowling_pins_itself];
}
else {
number_of_consecutive_bowling_pins_its_nimber = kayles_values_array[72 + (number_of_consecutive_bowling_pins_itself % 12)];
}
the_game_its_xor_sum ^= number_of_consecutive_bowling_pins_its_nimber;
number_of_consecutive_bowling_pins_itself = 0;
}
/* At each move, the game state is a simply a bag of integers.
*
* Each integer in the bag represents a maximal sequence of consecutive bawling pins.
*
* Say that the bag contains integers x₁, x₂, …, xₖ.
*
* First player can force a win, with perfect play, if and only the XOR sum S of the values SG(xⱼ), it differs zero.
*
* This is the Sprague Grundy theorem, applied to this game, and SG(xⱼ) = Kₙ, with n := xⱼ.
*
*
*
* Let S = SG(x₁) ⊕ SG(x₂) ⊕ … ⊕ SG(xₖ).
*
* One claims that it must be the case that the player who moves first, they can force a win when and only when S ≠ 0.
*
* Since S ≠ 0, there is at least one j so that SG(xⱼ) ≠ 0.
*
* Also, k ∈ ℤ, 1 ≤ k, point being that k is a finite number.
*
* Also each of these k numbers, SG(xⱼ) is a nonegative integer.
*
* There exists then a power of 2, say 2ʷ. w fow width, so that one and two hold.
*
* One is that ∀ j ∈ ℤ, 1 ≤ j ≤ n ⇒ SG(xⱼ) < 2ʷ⁺¹.
*
* Two is that ∃ j ∈ ℤ, 2ʷ ≤ SG(xⱼ).
*
* Okay, so player who moves first, they can simply pick one of these j values for which 2ʷ ≤ SG(xⱼ) < 2ʷ.
*
* Player who moves first, they simply replace xⱼ with xₖ₊₁ and xₖ₊₂ so that either xₖ₊₁ + 1 + xₖ₊₂ = xⱼ or xₖ₊₁ + 2 + xₖ₊₂ = xⱼ.
*
* Player who moves first, they would pick xₖ₊₁ and xₖ₊₂ so that S ⊕ SG(xⱼ) ⊕ (SG(xₖ₊₁) ⊕ SG(xₖ₊₂)) = 0.
*
* This is possible SG(xⱼ) ⊕ (SG(xₖ₊₁) to not have 2ʷ as a bit, and any other bit accordingly picked so that the XOR sum is 0.
*
* This works, considering that SG(xⱼ) = Kₙ, with n := xⱼ, and how Kayles sequence, the Kₙ, was defined.
*
* Yup, in short, the classic Nim game move, the classic Sprague – Grundy Theorem, its proof move.
*
* What happened is that player who moves first, they changed the bag from a non zero sum to a zero sum.
*
* Player who moves next, if the bag contains at least one xⱼ at least 2, they can only reach a zero XOR sum.
*
* The sequence of moves is finite because at each step the sum of the numbers in the bag decreases by at least 1.
*
* In the end, the bag would contain a bunch of 1ₜ and a bunch of 0ₜ, no other value is possible in the bag, at the end. ⚑
*
*
*
*
* Nothing too fancy: the neat part, to pick the maximal sequence of bowling pins as the building block for this problem.
*
* The neat part, the Wikipedia, and having read the proof of the Sprague — Grundy theorem, and articles about this theorem.
*
* https://infoarena.ro/numerele-sprague-grundy https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Kayles
*
* https://en.wikipedia.org/wiki/Sprague–Grundy_theorem https://en.wikipedia.org/wiki/Impartial_game
*
* https://en.wikipedia.org/wiki/Combinatorial_game_theory https://en.wikipedia.org/wiki/Nimber
*
* https://en.wikipedia.org/wiki/Multiset (multiset or bag, same thing)
*
* Also, this YT video is quite neat, on the topic of combinatorial games.
*
* https://www.youtube.com/watch?v=e7xuc_NrbE0
*
* Lecture 41 - Combinatorial Games, Nim and the Sprague-Grundy Theorem, by Amir Goharshady
*/
if (0 != the_game_its_xor_sum) {
the_current_victor = 0;
}
else {
the_current_victor = 1;
}
}
}
}
}
}
/* Step is write the answer just determined, to the output file, 0 → “Nargy\n”, 1 → "Fumeanu\n”; go, go, we're burning daylight. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
if ((0 != the_current_victor) && (1 != the_current_victor)) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__LOGIC_ERROR; /* non sequitur */
}
else {
char * the_literal_answer = NULL;
int expected_status = 0;
FILE * output_file = NULL;
int status_from_fprintf = 0;
if (0 == the_current_victor) {
the_literal_answer = "Nargy\n";
expected_status = 6; /* 5 letters in “Nargy”, each a byte, 1 byte the line feed, the \n, for a total of 6 bytes. */
}
else {
the_literal_answer = "Fumeanu\n";
expected_status = 8; /* 7 letters in “Fumeanu”, each a byte, 1 byte the line feed, the \n, for a total of 8 bytes. */
}
output_file = program_state->bowling_program__field__output_file;
status_from_fprintf = fprintf(output_file, "%s", the_literal_answer);
if (status_from_fprintf != expected_status) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
}
}
}
/* Step is icrement the current test, its index, on condition all was fine, and lets' continue with the loop, let's go! */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
current_test_its_index += 1;
}
}
}
}
}
/* Step is pass the baton, the execution status. */ {
return exit_status;
}
}
int bowling_program__code_up__release_all_resources_down_back (struct bowling_program__data_up__program_state * program_state) {
/* Step is define and declare a few local variables. */ {
BOWLING_PROGRAM__BULWARK_CLOSE
int exit_status = BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE;
BOWLING_PROGRAM__BULWARK_OPEN
}
/* Step is free() release the mex set array itself. */ {
free(program_state->bowling_program__field__mex_set_array_itself);
program_state->bowling_program__field__mex_set_array_itself = NULL;
program_state->bowling_program__field__mex_set_array_its_size = 0;
}
/* Step is free() release the kayles values array itself. */ {
free(program_state->bowling_program__field__kayles_values_array_itself);
program_state->bowling_program__field__kayles_values_array_itself = NULL;
program_state->bowling_program__field__kayles_values_array_its_size = 0;
}
/* Step is free() release the line buffer itself. */ {
free(program_state->bowling_program__field__line_buffer_itself);
program_state->bowling_program__field__line_buffer_itself = NULL;
program_state->bowling_program__field__line_buffer_its_size = 0;
program_state->bowling_program__field__line_buffer_its_isize = 0;
}
/* Step is fclose() release the output file itself. */ {
int status_too = 0;
status_too = fclose(program_state->bowling_program__field__output_file);
program_state->bowling_program__field__output_file = NULL;
if (0 != status_too) {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
}
}
/* Step is fclose() release the input file itself. */ {
int status_too = 0;
status_too = fclose(program_state->bowling_program__field__input_file);
program_state->bowling_program__field__input_file = NULL;
if (0 != status_too) {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
exit_status = BOWLING_PROGRAM__EXIT_STATUS__FAILURE__INPUT_OUTPUT;
}
}
}
/* Step is free() release the program state object itself. */ {
free(program_state);
program_state = NULL;
}
/* Step is pass the baton, the executable status. */ {
return exit_status;
}
}
int main (void) {
/* Step is declare and define, local variables. */ {
BOWLING_PROGRAM__BULWARK_CLOSE
int exit_status = BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE;
struct bowling_program__data_up__program_state * program_state = NULL;
BOWLING_PROGRAM__BULWARK_OPEN
}
/* Step is acquire all resources, up front. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
int status_too = 0;
struct bowling_program__data_up__program_state * pointer_p = NULL;
status_too = bowling_program__code_up__acquire_all_resources_up_front(&pointer_p);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_too) {
assert(NULL == pointer_p);
exit_status = status_too;
}
else {
assert(NULL != pointer_p);
program_state = pointer_p;
}
}
}
/* Step is solve the problem, already. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
int status_too = 0;
status_too = bowling_program__code_up__solve_the_problem_already(program_state);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_too) {
exit_status = status_too;
}
}
}
/* Step is write the output, already. */ {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
/* Yeah, writing the output, in rare cases may also consist of reading the question.
*
* Read the question from the input file, write its answer into the output file, repeat.
*
*/
int status_too = 0;
status_too = bowling_program__code_up__write_the_output_already(program_state);
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_too) {
exit_status = status_too;
}
}
}
/* Step is release all resources, down back. */ {
if (NULL != program_state) {
int status_too = 0;
status_too = bowling_program__code_up__release_all_resources_down_back(program_state);
program_state = NULL;
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE != status_too) {
if (BOWLING_PROGRAM__EXIT_STATUS__SUCCESS__ALL_WAS_FINE == exit_status) {
exit_status = status_too;
}
}
}
}
/* Step is pass the baton, already. */ {
return exit_status;
}
}
Marius B mgnt