Main.c file #include "queue.h" #include #include #include

char testNewQueue(); char testEnqueue(); char testFront(); char testIsEmpty(); char testDequeue(); char testRandom(); char checkTail(struct Queue *Q, int target); void testJosephus();

int main(int argv, char **argc) { srand(time(0)); printf("Select Option from list. "); printf("0.) Run All Tests "); printf("1.) Test New Queue "); printf("2.) Test Enqueue "); printf("3.) Test Front "); printf("4.) Test isEmpty "); printf("5.) Test Dequeue "); printf("6.) Run Randomized Tests "); printf("7.) Josephus Puzzle "); printf("Enter Number of test to run: "); int testToRun = -1; int result = scanf("%d", &testToRun); if (result != 1 || testToRun < 0 || testToRun > 7) { printf("Invalid Menu Selection. "); return 1; } switch (testToRun) { case 7: testJosephus(); break; case 0: printf("Running ALL Tests "); case 1: if (!testNewQueue()) { return 1; } if (testToRun != 0) { break; }; case 2: if (!testEnqueue()) { return 1; } if (testToRun != 0) { break; }; case 3: if (!testFront()) { return 1; } if (testToRun != 0) { break; }; case 4: if (!testIsEmpty()) { return 1; } if (testToRun != 0) { break; }; case 5: if (!testDequeue()) { return 1; } if (testToRun != 0) { break; }; case 6: if (!testRandom()) { return 1; } if (testToRun != 0) { break; }; } return 0; }

char testNewQueue() { struct Queue *Q = newQueue(); if (Q == NULL) { printf("newQueue: FAILED "); printf("Calling newQueue returned NULL. "); return 0; } if (Q->head != NULL) { printf("newQueue: FAILED "); printf("Calling newQueue return object that did not have NULL head. "); return 0; } if (Q->tail != NULL) { printf("newQueue: FAILED "); printf("Calling newQueue return object that did not have NULL tail. "); return 0; } printf("newQueue: PASSED "); return 1; }

char testEnqueue() { struct Queue *Q = newQueue(); int tests = 10; // Check that elements are added in for (int i = 0; i < tests; i++) { enqueue(i, Q); // Sanity Check if (Q->head == NULL) { printf("enqueue: FAILED "); printf("Head Null After Enqueue Call! "); return 0; } if (Q->tail == NULL) { printf("enqueue: FAILED "); printf("Tail Null After Enqueue Call! "); return 0; } // Check for Value if (!checkTail(Q, i)) { printf("enqueue: FAILED "); printf("enqueue(%d,Q) did not add %d to tail of queue. ", i, i); printf("Tail Pointer must point to number. "); printQueue(Q); return 0; } } struct Node *ptr = Q->head; int count = 0; while (ptr != NULL) { if (ptr->value != count) { printf("Inserted Numbers from 0 to %d into Q. ", tests); printf("Did not find %d in correct location. ", count); printQueue(Q); return 0; } count++; ptr = ptr->next; } printf("enqueue: PASSED "); return 1; }

char testFront() { struct Queue *Q = newQueue(); if (front(Q) != -1) { printf("Front must return -1 on empty queue. "); printQueue(Q); printf("front: FAILED "); return 0; } enqueue(9, Q); if (front(Q) != 9) { printf("Called enqueue(9,Q) and 9 was not front afterwards. "); printQueue(Q); printf("front: FAILED "); return 0; } enqueue(7, Q); if (front(Q) != 9) { printf("Called enqueue(7,Q) after enqueue(9,Q) and 9 was not front " "afterwards. "); printQueue(Q); printf("front: FAILED "); return 0; } printf("front: PASSED "); return 1; }

char testIsEmpty() { struct Queue *Q = newQueue(); if (!isEmpty(Q)) { printf("Called isEmpty on a new Queue. "); printf("Function did not return true. "); printQueue(Q); printf("isEmpty: FAILED "); return 0; } enqueue(8, Q); if (isEmpty(Q)) { printf("Called isEmpty on Queue Containing 8. "); printf("Function did not return false. "); printQueue(Q); printf("isEmpty: FAILED "); return 0; } printf("isEmpty: PASSED "); return 1; }

char testDequeue() { struct Queue *Q = newQueue(); for (int i = 1; i < 6; i++) { enqueue(i, Q); } int expected = 1; while (!isEmpty(Q)) { if (front(Q) != expected) { printf("Expected %d at front of Queue but saw %d. ", expected, front(Q)); printf("Possible error in dequeue. "); printQueue(Q); printf("dequeue: FAILED "); return 0; } dequeue(Q); expected++; } if (expected != 6) { printf("Dequeue should have removed %d things but only removed %d. ", 6, expected); printf("Possible error in dequeue. "); printQueue(Q); printf("dequeue: FAILED "); return 0; }

printf("dequeue: PASSED "); return 1; }

char testRandom() { struct Queue *Q = newQueue(); for (int i = 0; i < 3; i++) { int size = rand() % 10 + 1; int *T = malloc(size * sizeof(int)); for (int k = 0; k < size; k++) { T[k] = rand() % 100 + 1; } for (int k = 0; k < size; k++) { enqueue(T[k], Q); } for (int k = 0; k < size; k++) { if (front(Q) != T[k]) { printf("Attempted to enqueue and dequeue repeatedly from Queue. "); printf("Failed on Repetition %d on Queue. ", i); printf("Tried to enqueue and dequeue: ["); for (int a = 0; a < size; a++) { printf("%d", T[a]); if (a + 1 != size) { printf(", "); } } printf("] "); printQueue(Q); printf("Random Values: FAILED "); return 0; } dequeue(Q); } } printf("Random Values: PASSED "); return 1; }

char checkTail(struct Queue *Q, int target) { struct Node *ptr = Q->tail; return ptr->value == target; }

void testJosephus() { int n; int m; printf("Enter Number of People (N): "); scanf("%d", &n); printf("Enter Person to Eliminate (M): "); scanf("%d", &m); int *R = josephus(n, m); printf("Order Eliminated: "); for (int i = 0; i < n; i++) { printf("%d", R[i]); if (i + 1 < n) { printf(" "); } } printf(" "); free(R); return; } --- queue.h

#ifndef _QUEUE_H_ #define _QUEUE_H_

struct Node{ int value; /**< The value stored at this node. */ struct Node* next; /**< A pointer to the next node in the list. */ }; typedef struct Node Node;

struct Queue{ Node* head; Node* tail; }; typedef struct Queue Queue;

Queue* newQueue(); char isEmpty(Queue* Q);

void enqueue(int v, Queue* Q);

int front(Queue* Q);

void dequeue(Queue* Q);

void printQueue(Queue* Q); int* josephus(int n, int m);

#endif --- queue.c edit this to complete part 2

#include "queue.h"

#include

#include

Queue *newQueue()

{

Queue *Q = malloc(sizeof(Queue));

Q->head = NULL;

Q->tail = NULL;

return Q;

}

char isEmpty(Queue *Q)

{

if (Q->head == NULL)

{

return 1;

}

else

{

return 0;

}

}

void enqueue(int v, Queue *Q)

{

Node *newNode = malloc(sizeof(Node));

newNode->value = v;

newNode->next = NULL;

if (isEmpty(Q))

{

Q->head = newNode;

Q->tail = newNode;

}

else

{

Q->tail->next = newNode;

Q->tail = newNode;

}

}

int front(Queue *Q)

{

if (isEmpty(Q))

{

return -1;

}

else

{

return Q->head->value;

}

}

void dequeue(Queue *Q)

{

if (!isEmpty(Q))

{

Node *temp = Q->head;

Q->head = Q->head->next;

free(temp);

}

}

void printQueue(Queue *Q)

{

Node *ptr = Q->head;

printf("Queue: ");

while (ptr != NULL)

{

printf("%d ", ptr->value);

ptr = ptr->next;

}

printf(" ");

}

int *josephus(int n, int m)

{

Queue *Q = newQueue();

for (int i = 1; i <= n; i++)

{

enqueue(i, Q);

}

int *T = malloc(n * sizeof(int));

int index = 0;

while (!isEmpty(Q))

{

for (int i = 0; i < m - 1; i++)

{

enqueue(front(Q), Q);

dequeue(Q);

}

T[index] = front(Q);

index++;

dequeue(Q);

}

return T;

}

Part 2: Josephus Puzzle

This question is from Algorithms, 4th Edition by Sedgewick and Wayne.

In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to N-1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated.

Learn more about the problem here: The Josephus Problem - Numberphile

Implement the function josephus(n,m) in queue.c.

You MUST use your Queue to solve this problem. The function takes to integers as input. The integers are n and m. Your program will return an array with the people in the order in which people are eliminated. Josephus will sit in whatever value is in the last index of the array. You must use your Queue from the previous part to solve this problem.

Simplification Assumptions:

You may assume the user will always give two positive numbers.

Your array will always have n elements.

The main program already prints the array for you.

Here are some example executions.

Test 01

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 7 Enter Number of People (N): 7 Enter Person to Eliminate (M): 2 Order Eliminated: 1 3 5 0 4 2 6 

Test 02

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 7 Enter Number of People (N): 7 Enter Person to Eliminate (M): 3 Order Eliminated: 2 5 1 6 4 0 3 

Test 03

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 7 Enter Number of People (N): 10 Enter Person to Eliminate (M): 2 Order Eliminated: 1 3 5 7 9 2 6 0 8 4 

Test 04

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 7 Enter Number of People (N): 100 Enter Person to Eliminate (M): 7 Order Eliminated: 6 13 20 27 34 41 48 55 62 69 76 83 90 97 4 12 21 29 37 45 53 61 70 78 86 94 2 11 22 31 40 50 59 68 79 88 98 8 18 30 42 52 64 74 85 96 9 23 35 47 60 73 87 0 15 28 44 58 75 91 5 24 39 57 77 93 14 33 54 72 95 17 43 66 89 16 46 71 1 32 65 99 36 80 10 56 3 51 7 67 26 92 82 81 84 25 63 19 38 49 

Test 05

 % ./main Select Option from list. 0.) Run All Tests 1.) Test New Queue 2.) Test Enqueue 3.) Test Front 4.) Test isEmpty 5.) Test Dequeue 6.) Run Randomized Tests 7.) Josephus Puzzle Enter Number of test to run: 7 Enter Number of People (N): 98 Enter Person to Eliminate (M): 12 Order Eliminated: 11 23 35 47 59 71 83 95 9 22 36 49 62 75 88 3 17 31 45 60 74 89 5 20 37 52 67 82 0 16 33 51 68 85 4 24 41 58 78 96 18 39 57 79 1 25 44 66 90 13 38 63 86 12 40 65 92 21 50 77 8 42 72 6 34 73 10 48 84 27 64 7 54 94 46 93 53 2 61 26 81 55 28 97 80 70 69 76 91 19 43 29 15 32 30 14 87 56