### Josephus Problem Iteration Problem Hey guys! I'm almost done with this code. There's only one snag I'm running into. I'm running a Josephus problem from a list. For those who don't know what the Josephus problem is, it's where you start with a group of soldiers who then draw a number out of a hat, and slowly move through the group in an order until there's one person left and this person gets to go home. Well, I've got most of the program done, but I've hit a snag with my iterator.

 ``123456789101112131415161718192021222324252627282930313233`` `````` LI find_person ( list & L, LI& p, const unsigned& M ) { /*This routine is called to locate the M-th name in the list L, and the list iterator p refers to that name, where LI is defined as: typedef list :: iterator LI;*/ list q = p; // for debugging purposes only unsigned i = 1; cout << "Q" << i << ": " << *q << " "; while (i < M) { p++;//iterate through until we've moved M spaces q++; if (p == L.end() && i == 1) //trying to tell it that if it's at a blank space, {p = L.begin(); //and at the beginning of the loop, iterate one more p++; //time after resetting } else if (p == L.end() && i > 1) //else, just reset it. p = L.begin(); cout << "Q" << i << ": " << *q << " "; i++; } cout << "Q" << i << ": " << *q << endl; return p; }``````

where LI is defined as list<string>::iterator.

Now here's the problem. I've accounted for the possibility of hitting the end of the list, and then the iterator will adjust to the beginning to restart the process. However, this doesn't bode well when I have to return q to be erased from the list, leaving me on a blank spot at the end of the iterator. How do I get it to iterate one more time in case of a blank space? I've tried i-- to force it to loop through one more time and therefore iterate again. I've also tried just simply iterating one more time if it's the first go through the loop and it's already at the end of the loop. Why does this have no effect? I'm tearing my hair out here. How do I get it to iterate one more time in case of a blank space?
 ``12345678910`` ``````while (i < M){ // your code } // Check again if we are at the end of the list if ( p == L.end() ) p = L.begin(); cout << "Q" << i << ": " << *p<< endl; // You had *q but list q = p; doesn't compile return p; }``````
In your while loop you might consider checking for `L.end()` before doing `p++`
Last edited on Thanks a ton for the response and I had tried that earlier, but I still wasn't getting the proper results. It gives you a free() overload. ``123456789101112131415161718192021`` ``````#include #include #include int main() { std::list seq { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ; std::size_t M = 27 ; // locate the M-th element (M==0 is the first) in the sequence // the sequence is treated as a circular list // move forward M%N places where N is the number of elements in the sequence if( !seq.empty() ) { auto iter = std::begin(seq) ; std::advance( iter, M % seq.size() ) ; // move forward M%N places // http://en.cppreference.com/w/cpp/iterator/advance std::cout << "the " << M << "th element is: " << *iter << '\n' ; } }``````

http://coliru.stacked-crooked.com/a/c35c8b994801c30c Look at the comments. After you address the comments you should get the correct answer. Which I believe is 2.
M = 3
1, 2, 3
Kill 3
1, 2, 1
Kill 1
2 gets to live.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091`` ``````#include #include #include using namespace std; typedef list::iterator LI; LI find_person ( list & L, LI& p, const unsigned& M ) { // --------------------------------------------------- // This doesn't compile //list q = p; unsigned i = 1; // ---------------------------------------------------------- // Q: What happens when you try to dereference the L.end()? // A: Bad things. if ( p == L.end() ) { cout << "At the end" << endl; } else { cout << "Q" << i << ": " << &(*p) << " " << *p << " "; } // ---------------------------------------------------------- // Question to anyone else: // What is the best way to get the pointer value of // the iterator p? while (i < M) { //---------------------------------------------------------- // Q: Same question what happens here when you // pass in L.end()? // A: You get back to the head. // bits/stl_list.h: // ... a %list conceptually represented as // @code // A <---> B <---> C <---> D // @endcode // is actually circular; a link exists between A and D. // // The fact that it is cirular causes you an issue because // it doens't go from the last element back to the first. // It goes from the last element to the L.end() and then // back to the first element in the list. // This is an issue for you because it eats up one of you // M values on a person not in the circle, giving you the // wrong answer //---------------------------------------------------------- //---------------------------------------------------------- // You need to check to see if you are at the L.end() before // you increment the value of p p++; if (p == L.end() && i == 1) { cout << "Reset 1 "; p = L.begin(); p++; // <---- Look to see if you really need this } else if (p == L.end() && i > 1) { cout << "Reset 2 "; p = L.begin(); } //-------------------------------------------------------- // Maybe the two check above could be made into one, hint cout << "Q" << i << ": " << &(*p) << " " << *p << " "; i++; } // Check to see if we are at the end if (p == L.end()) // Reset to the beginning p = L.begin(); cout << "EQ" << i << ": " << &(*p) << " " << *p << " " << endl; return p; } int main(void){ list cir; cir.push_back("1"); cir.push_back("2"); cir.push_back("3"); LI pos1(cir.begin()); while(1 < cir.size()){ LI pos2(find_person(cir, pos1, 3)); cout << "Removing: " << *pos2 << endl; pos1 = cir.erase(pos2); } cout << "Last: " << cir.front() << endl; return 0; }`````` ```Q1: 0x1001000b0 1 Q1: 0x1001000f0 2 Q2: 0x100100130 3 EQ3: 0x100100130 3 Removing: 3 At the end Q1: 0x1001000b0 1 Q2: 0x1001000f0 2 EQ3: 0x1001000f0 2 Removing: 2 <----- This is not correct! Last: 1``` Wow, this is a funny problem. I like it much and tried to add it to my problem-solving site:

http://codeabbey.com/index/task_view/josephus-problem

And found that I could not invent faster solution than with list (which I think is about O(N*K)).

Thanks for idea!
Last edited on ``12345678910111213141516171819202122232425`` ``````#include #include #include int main() { std::list seq { "1. ab", "2. cd", "3. ef", "4. gh", "5. ij", "6. kl", "7. mn", "8. op", "9. qr", "10. st" } ; std::size_t M = 3 ; // remove every third string M -= 1 ; // adjust for start with count == 1 auto by = M % seq.size() ; while( seq.size() > 1 ) { auto iter = seq.begin() ; std::advance( iter, by ) ; std::cout << "erase: " << *iter << '\n' ; seq.erase(iter) ; by += M ; by %= seq.size() ; } std::cout << "remaining: " << seq.front() << '\n' ; }``````

http://coliru.stacked-crooked.com/a/a27dcc6b2f96cd32 Sorry I forgot to check back on this. Histrungalot, your solution definitely did the trick. Thanks a ton. There were some things I had to work out, but overall it did the trick.
Topic archived. No new replies allowed.