Here is my solution for the Josephus Problem (of user inputted sized circle and "magic" number) using a circularly linked list.
Any suggestions on what I could have, or should have, done differently for better efficiency or best practices?
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
unsigned childNum;
struct node* next;
}node;
unsigned findSolution(unsigned size, unsigned n){
node* firstChild = (node*)malloc(sizeof(node));
node* lastChild = (node*)malloc(sizeof(node));
node* currentChild = (node*)malloc(sizeof(node));
node* trailNode = (node*)malloc(sizeof(node));
node* p; /* used to delete node */
firstChild->childNum = 0;
/* if the size of the list to be created is only 1 child, return as the solution */
if(size == 1) return size;
/* create the circlularly linked list of size - 1 */
for(unsigned i = 1; i < size; i++){
node* nextChild = (node*)malloc(sizeof(node));
nextChild->childNum = i;
nextChild->next = NULL;
if(firstChild->childNum < 1){
firstChild = nextChild;
lastChild = nextChild;
}else{
lastChild->next = nextChild;
lastChild = nextChild;
}
}
/* create the last node */
node* nextChild = (node*)malloc(sizeof(node));
nextChild->childNum = size;
lastChild->next = nextChild;
lastChild = nextChild;
lastChild->next = firstChild;
/* iterate the list and delete the nth node until currentChild points to itself */
currentChild = firstChild;
while(currentChild != NULL && currentChild->next != currentChild){
if(n > 1){
for(unsigned i = 1; i < n; i++){
trailNode = currentChild;
currentChild = currentChild->next;
}
/* delete this child */
trailNode->next = trailNode->next->next;
p = currentChild;
currentChild = currentChild->next;
free(p);
}else{
/* n == 1, remove every child */
p = currentChild;
/* if the next child is the last child, point it to itself to exit loop */
if(currentChild->next = lastChild){
lastChild->next = lastChild;
}
currentChild = currentChild->next;
free(p);
}
}
/* only 1 node remaining -- this is the solution */
return currentChild->childNum;
}
int main(void){
unsigned size = 0;
unsigned n = 0;
do{
printf_s("How many children are in the circle -- must be > 0: ");
scanf_s("%u", &size);
printf_s("Remove every nth child -- value for n must be > 0: ");
scanf_s("%u", &n);
printf_s("\n\n");
}while(size < 1 || n < 1);
printf_s("Computing the answer...");
printf_s("\n\n\nChild number %li is the winner.", findSolution(size, n));
for(;;);
return 0;
}
