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.
LI find_person ( list <string>& L, LI& p, constunsigned& 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 <string> :: iterator LI;*/
list <string> 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
}
elseif (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?
1 2 3 4 5 6 7 8 9 10
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 <string> q = p; doesn't compile
return p;
}
In your while loop you might consider checking for L.end() before doing p++
#include <iostream>
#include <list>
#include <iterator>
int main()
{
std::list<int> 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' ;
}
}
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.
#include <string>
#include <list>
#include <iostream>
usingnamespace std;
typedef list<string>::iterator LI;
LI find_person ( list <string>& L, LI& p, constunsigned& M ) {
// ---------------------------------------------------
// This doesn't compile
//list <string> 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
}
elseif (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<string> 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
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.
