a

[cOOKIE5D]

zsdga

[jonnin]

if you MUST use arrays.. you don't have to grow and shrink them. just swap the 'deleted' one with the 'last' one and update 'last' so that it has the index of the current last guy. To avoid growth, just allocate enough for the max # of players to begin with and use a subset of that if you need less. Ideally you would let a vector handle this stuff for you.

randoms should not be out of range if you use rand()%last and the above concept.

See if approaching it this way helps simplify the code and clear up your issues. The code seems to be overly complicated for the job; see if you can do the job with less logic and pointer manipulations.

[dhayden]

just swap the 'deleted' one with the 'last' one and update 'last' so that it has the index of the current last guy.

But that changes the order of the players and I think the game requires that the circle just shrinks each time someone dies.

In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle

Where do you start when proceeding around the circle? For example, suppose you have players 1 2 3 4 5 6. You start at 1 and skip 2 players . So skip #2 and #3, then shoot #4, leaving 1,2,3,5,6. Now do you start at #5 and skip 6 & 1? Or start at 3 and skip 5 & 6?

PrintPlayers(Players, K);
K is the number of players to skip. NPlayers is the total number. Don't you want to print NPlayers instead of K? This mistake is in two places.

One point that you seem to have missed is that you can go around the circle more than once: if you start with N=10 and K=10, then after shooting 6 people, you have N=4 and K=10. You go around the circle two and a half times to select the next victim. If P is the position that you start from then the person who gets shot is at position (P+K+1) % N. Change ShootRandomPlayer to use this math. Hint: you don't currently pass the value of N.

Use Players[i] instead of *(Players+i). These are equivalent but most people will find the former easier to read.

In ShootRandomPlayer, you have a loop but you break out of every path in the loop. So you don't need a loop at all.

Your description doesn't mention anything about a gunholder. What is their function? Is NRandom the position where you start counting? And upon exit, is NRandom the position if the one who gets shot? Please add comments describing what ShootRandomPlayer is supposed to do. Then we can help you figure out if it's doing what it should.

In main, your loop is wrong since NPlayers will probably shink each time through it.

I modified the program to work, assuming that after one person is killed, you start at the dead soul's former position. I didn't use GunHolder since your description doesn't mention this role. My ShootRandomPlayer signature looks like this:

// "Players" points to an array of "NPlayers" players. Starting at position P,
// Skip K players and shoot the K+1'th.  Print your action and
// remove the shot player from the array. Upon return,
// Players, NPlayers and P are updated.
void
ShootRandomPlayer(int * &Players, int &NPlayers, int &P, int K)

Here's my output with N=10, K=3 and starting at P=2:
Starting at index 2 and skipping 3 players at each turn

INDEX : 0  1  2  3  4  5  6  7  8  9


ARRAY : 1  2  3  4  5  6  7  8  9  10
shot 7

ARRAY : 1  2  3  4  5  6  8  9  10
shot 2

ARRAY : 1  3  4  5  6  8  9  10
shot 8

ARRAY : 1  3  4  5  6  9  10
shot 4

ARRAY : 1  3  5  6  9  10
shot 1

ARRAY : 3  5  6  9  10
shot 10

ARRAY : 3  5  6  9
shot 3

ARRAY : 5  6  9
shot 6

ARRAY : 5  9
shot 9

ARRAY : 5
Player 5 is the last one standing

[tpb]

[/code]
Lists are good for removing elements from the middle.

#include <iostream>
#include <iomanip>
#include <list>
#include <cstdlib> // atoi

int main(int argc, char **argv) {
    int size = 20, step = 7;
    if (argc > 1) size = std::atoi(argv[1]);
    if (argc > 2) step = std::atoi(argv[2]);

    std::list<int> list;
    for (int i = 0; i < size; i++)
        list.push_back(i);

    std::list<int>::iterator it = list.begin();
    while (list.size() > 1) {

        int i = 0;
        for (auto x: list) {
            for ( ; i < x; i++) std::cout << "-- ";
            std::cout << std::setw(2) << x << ' ';
            i++;
        }
        for ( ; i < size; i++) std::cout << "-- ";
        std::cout << '\n';

        for (int i = 0; i < step; i++)
            if (++it == list.end())
                it = list.begin();
        it = list.erase(it);
        if (it == list.end())
            it = list.begin();
    }

    int i = 0;
    for ( ; i < list.front(); i++) std::cout << "-- ";
    std::cout << std::setw(2) << list.front();
    for (i++; i < size; i++) std::cout << " --";
    std::cout << '\n';
}

$ ./josephus 10 3
 0  1  2  3  4  5  6  7  8  9 
 0  1  2 --  4  5  6  7  8  9 
 0  1  2 --  4  5  6 --  8  9 
 0 --  2 --  4  5  6 --  8  9 
 0 --  2 --  4  5 -- --  8  9 
 0 -- -- --  4  5 -- --  8  9 
 0 -- -- --  4  5 -- --  8 -- 
 0 -- -- --  4  5 -- -- -- -- 
-- -- -- --  4  5 -- -- -- -- 
-- -- -- --  4 -- -- -- -- --

[dhayden]

Lists are good for removing elements from the middle.

I considered that. This is an interesting problem because it involves jumping over items in the collection and removing items from the middle. Lists are bad at jumping over items (you have to do it one at a time) but good at deleting from the middle. Vectors are good at jumping over items (just add) but bad at deleting in the middle.

So which is better? Let's dig a little deeper.

To get to the last person, you kill N-1 of them. At each turn, you have to advance K places around the circle. So for a list, it's (N-1)*K operations to advance through the list and N-1 operations to remove from the list so it O((N-1)(K+1)).

For a vector it's N-1 operations to move through the list, but what about deleting items from it? I'll make the rash assumption that on average, you delete from the middle of the list which means moving S/2 items where S is the current list size. That means the total number of operations is sum(S=2 to N, S/2) = (N^2+2N)/4. So overall with a vector, it's O((N^2+6N-4) / 4).

For large values, that O(N*K) for the list and O(N^2) for the vector. If K << N, the list is faster.

This assumes my hand-waving on the vector calculations is reasonable, and could well be flawed. Maybe someone else can come up with a better analysis?

[jonnin]

what about a lazy delete?

struct deadguy
{
bool deleted; //killed? whatever word
int data;
};

vector<deadguy> mylist;

and check deleted each time?

The thing about O() is that its relative and only ONE way to measure things. Wall clock is another way to measure. That is:
if one iteration of a bad algorithm (like, cough, resizing an array every iteration)
takes 1 second, and a different algorithm takes 1/2 a nanosecond, then it takes a bit of time before the O(1) is actually truly faster than O(N^2) ...

[dhayden]

what about a lazy delete?

But then you have to visit at least K nodes for each round. You can't just skip ahead K people because several of the intervening ones might be dead.

Probably the best way to do this is to analyze the math carefully. It's probably possible to compute the answers rather than simulating how humans might do it.

if one iteration of a bad algorithm (like, cough, resizing an array every iteration)
takes 1 second, and a different algorithm takes 1/2 a nanosecond, then it takes a bit of time before the O(1) is actually truly faster than O(N^2) ...

Ain't that the truth! I learned the hard way is that sometimes log(N) < K. What I mean is that if algorithm 1 runs in O(N*log(N)) time and algo 2 runs in O(N) time, don't assume that algo 2 is faster for your problem. Algo 2's runtime might be proportional to N, but if the proportion is, say 20, then it might run slower for N<16 million (log₂(16 million) is about 20.

[jonnin]

Yea, I haven't looked it up, I enjoy playing with these things, but I don't see a direct computation yet.

You can't skip directly, but you can iterate really fast over the dead ones. /shrug. Its not optimal for sure. Maybe the list really is the best way for this one... you can make a circular list, for that matter...

[Ganado]

I don't have any comments on the code itself, but I have to link this video:
The Josephus Problem - Numberphile
https://www.youtube.com/watch?v=uCsD3ZGzMgE
Spoiler: The solution is O(1), but it isn't random like the OP's assignment, so I'm not sure if it applies.