I’m currently learning about data structures and algorithms (DSA) by reading the book “Learning JavaScript Data Structures and Algorithms – 2nd Edition” by Loiane Groner. I am implementing the DSAs in C because I have seen many people saying that C is better for truly understanding these concepts, and also because I like languages such as C/C++, Rust, and Java.
I am trying to implement one of the examples from the book, which is a Hot Potato game using a deque data structure, but I keep getting the same result every time. I tried asking Perplexity AI for help, but it did not work.
btw, i'm using Clion.
Here is my full code:
#include <stdio.h>
#include <stdbool.h>
#define MAX_PLAYERS 5
#define MAX_NAME_LEN 20
#define PASSES 7
#define MAX_SIZE 100
// === Deque ===
typedef struct Deque {
int array[MAX_SIZE];
int head;
int tail;
int size;
} Deque;
void createDeque(Deque *queue) {
queue->head = 0;
queue->tail = 0;
queue->size = 0;
}
bool deque_isEmpty(Deque *queue) {
return queue->size == 0 ? true : false;
}
bool deque_isFull(Deque *queue) {
return queue->size == MAX_SIZE ? true : false;
}
void addFront(Deque *queue, int data) {
if (deque_isFull(queue)) {
printf("Deque is full\n");
return;
}
for (int i = queue->size; i >= 1; i--) {
queue->array[i] = queue->array[i - 1];
}
queue->array[0] = data;
queue->head = 0;
queue->size++;
}
void addBack(Deque *queue, int data) {
if (deque_isFull(queue)) {
printf("Deque Overflow\n");
return;
}
queue->array[queue->tail] = data;
queue->tail++;
queue->size++;
}
int removeFront(Deque *queue) {
if (deque_isEmpty(queue)) {
printf("Deque Underflow\n");
return -1;
}
int data = queue->array[queue->head];
queue->head++;
queue->size--;
return data;
}
int removeBack(Deque *queue) {
if (deque_isEmpty(queue)) {
printf("Deque Underflow\n");
return -1;
}
int removed = queue->array[queue->tail];
queue->tail--;
queue->size--;
return removed;
}
int peekFront(Deque *queue) {
if (deque_isEmpty(queue)) {
printf("Deque Underflow\n");
return -1;
}
return queue->array[queue->head];
}
int peekBack(Deque *queue) {
if (deque_isEmpty(queue)) {
printf("Deque Underflow\n");
return -1;
}
return queue->array[queue->tail - 1];
}
void deque_clear(Deque *queue) {
if (deque_isEmpty(queue)) {
printf("Deque is empty\n");
return;
}
queue->head = 0;
queue->tail = 0;
queue->size = 0;
}
// === HOT POTATO GAME ===
void printDeque(Deque *queue) {
if (deque_isEmpty(queue)) {
printf("Deque is empty\n");
return;
}
for (int i = queue->head; i < queue->tail; i++) {
printf("%d ", queue->array[i]);
}
printf("\n");
}
void hotPotato(char *players[], int num_players, int passes) {
Deque queue;
createDeque(&queue);
for (int i = 0; i < num_players; i++) {
addBack(&queue, i);
}
printf("=== HOT POTATO GAME ===");
printf("Passing %d times...\n\n", passes);
int eliminated[MAX_PLAYERS];
int eliminated_count = 0;
while (!deque_isEmpty(&queue)) {
for (int i = 0; i < passes; i++) {
int player = removeFront(&queue);
addBack(&queue, player);
}
int eliminated_player = removeFront(&queue);
eliminated[eliminated_count++] = eliminated_player;
printf("%s was eliminated from the game.\n", players[eliminated_player]);
if (deque_isEmpty(&queue))
break;
}
printf("The winner is: %s!\n", players[eliminated[eliminated_count - 1]]);
}
int main() {
char *players[MAX_PLAYERS] = {
"Carl", "Ingrid", "Camila", "Jack", "John"
};
hotPotato(players, MAX_PLAYERS, PASSES);
return 0;
}
As per the good comments, due to the fact that values do not change and functions work in a predetermined sequence, one would always get the same winner when launching this program.
To better investigate the behavior of this program and to illustrate the program behavior to you, I did some slight refactoring of the "hotPotato" function to include some "printf" statements to provide some debug like information.
void hotPotato(char *players[], int num_players, int passes)
{
Deque queue;
createDeque(&queue);
for (int i = 0; i < num_players; i++)
{
addBack(&queue, i);
}
printf("=== HOT POTATO GAME === ");
printf("Passing %d times...\n\n", passes);
int eliminated[MAX_PLAYERS], eliminated_count = 0, eliminated_player;
while (!deque_isEmpty(&queue))
{
for (int i = 0; i < passes; i++)
{
int player = removeFront(&queue);
printf("%d ", player); /* Illustrate the player shuffle */
addBack(&queue, player);
}
printf("%d player to eliminate is: %s\n", queue.array[queue.head], players[queue.array[queue.head]]); /* Note which player will be eliminated */
eliminated_player = removeFront(&queue);
eliminated[eliminated_count++] = eliminated_player;
if (deque_isEmpty(&queue))
break;
}
printf("The winner is: %s!\n", players[eliminated[eliminated_count - 1]]);
}
Running the program in the terminal resulted in the following output.
craig@Vera:~/C_Programs/Console/HotPotato/bin/Release$ ./HotPotato
=== HOT POTATO GAME === Passing 7 times...
0 1 2 3 4 0 1 2 player to eliminate is: Camila
3 4 0 1 3 4 0 1 player to eliminate is: Ingrid
3 4 0 3 4 0 3 4 player to eliminate is: John
0 3 0 3 0 3 0 3 player to eliminate is: Jack
0 0 0 0 0 0 0 0 player to eliminate is: Carl
The winner is: Carl!
To be brief, what this output is saying is that when the "hotPotato" function is called with a parameter value of seven passes, the elimination sequence will always be, player #3 (Camila), player #2 (Ingrid), player #5 (John), and then player #4 (Jack), finishing up with player #1 (Carl) winning.
As a further test, I refactored the use of the "hotPotato" function in the "main" function to have the function called with various pass iteration values.
int main()
{
char *players[MAX_PLAYERS] =
{
"Carl", "Ingrid", "Camila", "Jack", "John"
};
for (int i = 7; i < 10; i++) /* Executing the elimination process using increasing passes */
hotPotato(players, MAX_PLAYERS, i);
return 0;
}
Executing this version of the program illustrates that different winners are generated when a different number of passes are attempted.
=== HOT POTATO GAME === Passing 7 times...
0 1 2 3 4 0 1 2 player to eliminate is: Camila
3 4 0 1 3 4 0 1 player to eliminate is: Ingrid
3 4 0 3 4 0 3 4 player to eliminate is: John
0 3 0 3 0 3 0 3 player to eliminate is: Jack
0 0 0 0 0 0 0 0 player to eliminate is: Carl
The winner is: Carl!
=== HOT POTATO GAME === Passing 8 times...
0 1 2 3 4 0 1 2 3 player to eliminate is: Jack
4 0 1 2 4 0 1 2 4 player to eliminate is: John
0 1 2 0 1 2 0 1 2 player to eliminate is: Camila
0 1 0 1 0 1 0 1 0 player to eliminate is: Carl
1 1 1 1 1 1 1 1 1 player to eliminate is: Ingrid
The winner is: Ingrid!
=== HOT POTATO GAME === Passing 9 times...
0 1 2 3 4 0 1 2 3 4 player to eliminate is: John
0 1 2 3 0 1 2 3 0 1 player to eliminate is: Ingrid
2 3 0 2 3 0 2 3 0 2 player to eliminate is: Camila
3 0 3 0 3 0 3 0 3 0 player to eliminate is: Carl
3 3 3 3 3 3 3 3 3 3 player to eliminate is: Jack
The winner is: Jack!
So, changing the number of passes executed will result in a different winner. And if you are looking for different winners, it probably would be time to study tutorials using random numbers within a "C" program. Just to give a taste of what might be done, following is some further refactoring of your code to introduce random number generation.
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define MAX_PLAYERS 5
#define MAX_NAME_LEN 20
#define PASSES 7
#define MAX_SIZE 1000
. . .
/* Existing code */
. . .
void hotPotato(char *players[], int num_players, int passes)
{
Deque queue;
createDeque(&queue);
for (int i = 0; i < num_players; i++)
{
addBack(&queue, i);
}
printf("=== HOT POTATO GAME === ");
printf("Passing %d times...\n\n", passes);
int eliminated[MAX_PLAYERS], eliminated_count = 0, eliminated_player;
while (!deque_isEmpty(&queue))
{
for (int i = 0; i < passes; i++)
{
int player = removeFront(&queue);
printf("%d ", player); /* Illustrate the player shuffle */
addBack(&queue, player);
}
printf("%d player to eliminate is: %s\n", queue.array[queue.head], players[queue.array[queue.head]]); /* Note which player will be eliminated */
eliminated_player = removeFront(&queue);
eliminated[eliminated_count++] = eliminated_player;
if (deque_isEmpty(&queue))
break;
}
printf("The winner is: %s!\n", players[eliminated[eliminated_count - 1]]);
}
int main()
{
char *players[MAX_PLAYERS] =
{
"Carl", "Ingrid", "Camila", "Jack", "John"
};
srand(time(NULL));
int i = PASSES + rand() % 25; /* Produces some sizable randomness */
hotPotato(players, MAX_PLAYERS, i);
return 0;
}
To recap the refactoring, <stdlib.h> was included for accessing the "rand()" function, <time.h> was included to provide what is known as "random seeding" initialization, and because the breadth of passes might increase the need for larger array sizes, the "#define" directive for the array size was enlarged.
In the "main" function, the random seeding and random number generation functions are added to provide different possible hot potato scenarios every time the program is executed as noted in a couple of runs at the terminal.
craig@Vera:~/C_Programs/Console/HotPotato/bin/Release$ ./HotPotato
=== HOT POTATO GAME === Passing 26 times...
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 player to eliminate is: Ingrid
2 3 4 0 2 3 4 0 2 3 4 0 2 3 4 0 2 3 4 0 2 3 4 0 2 3 4 player to eliminate is: John
0 2 3 0 2 3 0 2 3 0 2 3 0 2 3 0 2 3 0 2 3 0 2 3 0 2 3 player to eliminate is: Jack
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 player to eliminate is: Carl
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 player to eliminate is: Camila
The winner is: Camila!
craig@Vera:~/C_Programs/Console/HotPotato/bin/Release$ ./HotPotato
=== HOT POTATO GAME === Passing 8 times...
0 1 2 3 4 0 1 2 3 player to eliminate is: Jack
4 0 1 2 4 0 1 2 4 player to eliminate is: John
0 1 2 0 1 2 0 1 2 player to eliminate is: Camila
0 1 0 1 0 1 0 1 0 player to eliminate is: Carl
1 1 1 1 1 1 1 1 1 player to eliminate is: Ingrid
The winner is: Ingrid!
Reviewing that your initial goal was understanding the use of data structures, you definitely would still want to delve into "C" tutorials regarding such definitions and uses. However, since your test program strays over into the realm of games, which usually relies on random scenarios, it would also be helpful for you to study "C" tutorials on using random number functionality.