Circular array and elimination in C, how to return the last "living" element index?

Question

I am trying to write a code that will simulate a circle of a fixed size of people that have one sword. The closest "living person" to the current index will be eliminated and the sword will be passed to the next living person (after the one who got killed) and so on.

I want it to be written without linked lists.

Example: A group of 3 people: arr[0] = 1, arr[1] = 1, arr[2] = 1

First turn:

• arr[0] KILLS arr[1] and the sword gets PASSED to arr[2]

Values of elements after the first turn:

arr[0] = 1, arr[1] = 0, arr[2] = 1

Second turn:

• arr[2] KILLS arr[0] and stays the last player

Values of elements after the second turn:

arr[0] = 0, arr[1] = 0, arr[2] = 1

• arr[2]'s index gets returned by the main function.

What I thought about was:

• array
• set the values all of elements to 1
• circulate and check each time if (1 == arr[i])
• set a flag to determine whether to kill or just pass the sword to this guy.
• return the current index that indicates that's the index of the last player alive.

For example, lets say we have 5 people in our group: [1] [1] [1] [1] [1]

First round:

give_sword = 0

i = 0 does not enter the first if because give_sword is not 1. It enters the second if, and finds the closest living person using the function findClosestLivingPerson and gets his index and sets his value to 0 (== kills the closest living person). It sets give_sword to 1.

Decreases the players_counter and checks if there is only one player left. If not, continues the loop.

This is my code:

#include <stdio.h>

int findClosestLivingPerson(int arr[], int index, int group_size);


int main (int argc, char *argv[])
{
    
    int group_size = 0, players_counter = 0;
    int i = 0, give_sword = 0;
    int arr[100] = {0};
    
    printf("Enter group size: \n");
    scanf("%d",&group_size);
    
    for (i = 0; i < group_size; i++)
    {
         arr[i] = 1;
    }
   
    players_counter = group_size;
    
        for (i = 0; i < group_size; (i+1) % group_size)
        {
            if (1 == arr[i])
            {
                if(1 == give_sword) /* should give sword, not to kill */
                {
                    give_sword = 0;
                }
                else /* should be killed */
                {
                    arr[findClosestLivingPerson(arr,i, group_size)] = 0;
                    give_sword = 1;
                    --players_counter;
                    if (players_counter == 1)
                    { 
                        break;
                    }
                }
            }
        }
    printf("Winner is %d ",i);
    return 0;
}

int findClosestLivingPerson(int arr[], int index, int group_size)
{
    for (; index < group_size; (index+1) % group_size)
    {
        if (arr[index] == 1)
        return index;
    }
    return 0;
}

The compiler says:

In function ‘main’: last_man.c:23:43: warning: statement with no effect [-Wunused-value] 23 | for (i = 0; i < group_size; (i+1) % group_size)

last_man.c: In function ‘findClosestLivingPerson’: last_man.c:49:42: warning: statement with no effect [-Wunused-value] 49 | for (; index < group_size; (index+1) % group_size)

The (index+1) % group_size is meant to circulate through this array.

Answer 1

As the compiler says, (i+1) % group_size has no effect. It computes the remainder of the sum of i and one. After that, it does nothing with the result.

The third part of a for statement is just an expression that is evaluated. It does not automatically update the loop index or do anything else. If you want it to update i, you must write an assignment, like i = (i+1) % group_size.

Answer 2

I think you've misunderstood how for loop works .

Format should be like this:

for( initialization, condition, iteration )

example:

for( int i = 0; i < size; i = i + 1 )

(i + 1) % group_size isn't an iteration( it isn't assigning the result to i ) , what you really want to do is

i = ( i + 1 ) % group_size;

Same applies for the second warning .

Answer 3

I would suggest a different approach. Let's do this in a way that results in nice code.

struct actor {
    int label;
    struct actor *next;
};

With this struct we can make a nice linked list and loop it back around:

int n = 5;
int i;

struct actor *actors = calloc(n, sizeof *actors);
for (i = 0; i < n - 1; i++) {
    actors[i].label = i;
    actors[i].next = &actors[i+1];
}
actors[i].label = i;
actors[i].next = &actors[0];

Ok, now we can assign the first killer:

struct actor *k = actors;

We also need a kill function:

struct actor *kill(struct actor *a)
{
    if (a->next != a) {
        printf("%d kills %d\n", a->label, a->next->label);
        a->next = a->next->next;
    } else {
        printf("%d is last man standing\n", a->label);
        a->next = NULL;
    }
    return a->next;
}

What this does: it removes the next person from the circular linked list (as that is the one that is killed). The lookup time for the next person is always the same.

And with everything in place, we can start the spree:

while (k) {
    k = kill(k);
}

This is not perfect code by any means, but it is a nice example of how you can make the algorithm incredibly simple if you put a little effort in setting up.