CODEWITHSUNDEEP
arrayscfunctioncircular-referencejosephus
NoobCoder
NoobCoder

Reputation: 615

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

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:

Values of elements after the first turn:

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

Second turn:

Values of elements after the second turn:

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

What I thought about was:

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.

Upvotes: 0

Views: 323

Answers (3)

fvalasiad
fvalasiad

Reputation: 184

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 .

Upvotes: 2

Cheatah
Cheatah

Reputation: 1835

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.

Upvotes: 1

Eric Postpischil
Eric Postpischil

Reputation: 222754

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.

Upvotes: 3

Related Questions