Broken Necklace

I've been working on this problem for quite a while. Everytime I try to change the code to make it work, I run into more and more problems. Anyway this is the problem:

Broken Necklace
You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:

1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.

Example
For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration will include the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.

PROGRAM NAME: beads
INPUT FORMAT
Line 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w

SAMPLE INPUT (file beads.in)
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
SAMPLE OUTPUT (file beads.out)
11

OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****
Here's the code I'm using. If someone knows a good or better way to approach the problem just say the word.

Code:

---

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n, n1=1, n2=1;
    string bString;
    string combString;
    char khar;
    char zhar;
    /*
    ifstream fin("beads.in",ios::in);
    ofstream fout("beads.out",ios::out);
   
    if(!fin)
    {
            cerr << "File could not be opened";
            exit(1);
    }
    if(!fout)
    {
            cerr << "File could not be opened";
            exit(1);
    }
    */
    cin >> n >> bString;
   
   
   
   
               
    vector<int> n1array(n);
    vector<int> n2array(n);
    vector<int> n3array(n);
    for (int s=0; s<n; s++)
    {
        n1array[s]=0;
        n2array[s]=0;
    }
   
   
    combString=bString+bString;
   
   
    for (int k=0;k<n;k++)
    {
        for(int i=k; combString[i]==combString[i-1] || combString[i]==khar; i--)// loop backward
        {
           
            if (combString[i-1]=='w' && combString[i] !='w')
            {
            khar=combString[i];
            cout << combString[i] <<endl;
           
            }
           
            if (combString[i-1]!='w' && combString[i]=='w')
            {
                                      n1++;
                                      n1array[k]=n1;
            }
           
            n1++;
            n1array[k]=n1;
        }
        for(int j=k+1; combString[j]==combString[j+1] || combString[j]==zhar; j++)//loop forward
        {
            if (combString[j+1]=='w' && combString[j] !='w')
            {
            zhar=combString[j];
            cout << combString[j] << endl;
           
            }
            if (combString[j+1] !='w' && combString[j]=='w')
            {
                                n2++;
                                n2array[k]=n2;
            }
           
            n2++;
            n2array[k]=n2;
        }
    }
        for (int e=0; e<n; e++)//fill empty ones
        {
            if (n1array[e]==0)
            n1array[e]=1;
            if (n2array[e]==0)
            n2array[e]=1;
        }
       
   
        for (int l=0; l<n; l++)//combine both arrays
        {
           
           
            n3array[l]= n1array[l]+n2array[l];
        }
        int temp=n3array[0];
        for (int m=0; m<n; m++)//calculate highest value
        {
            if (n3array[m]>temp)
            temp=n3array[m];
        }
        if (temp>n)
        temp=n;
        cout << temp << "\n";
     
       
        int we;
        cin >>we;
       
        return 0;
}

---

Thanks!!

I'm not sure if it's better, but it's 06:00 local time here and I'm not really awake enough to understand your code, so I implemented a solution myself. Check it, maybe test it and see for yourself if it's better or not.

PHP Code:

---

#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

char WHITE_BEAD = 'w';
char RED_BEAD   = 'r';
char BLUE_BEAD  = 'b';

// when i coded this whole thing, 
// i assumed that any self-respecting 
// string class would have a reverse() 
// method. When my context help failed
// finding reverse(), this was the best
// I could find googling. I seriously 
// hope that this is my inexperience
// with std::string, because not having
// a reverse() method in a standard 
// container really sucks. 
string reverse( const string& s )
{
    string result;

    for( string::const_iterator index = s.end() - 1; index != s.begin() - 1; index--)
    {
        result += *index;
    }

    return result;
}

// counts the number of beads of the same color 
// that can be collected from the left of a necklace
int collect( const std::string& necklace )
{
    bool color_is_set = false;
    char color_to_collect;
    int count = 0;

    // iterate through all beads
    for( int index = 0 ; index < necklace.length() ; index++ )
    {
        char current_bead = necklace[index];

        if( current_bead == WHITE_BEAD )
        {
            // white beads can always be used 
            count++;
        }
        else if( ! color_is_set )
        {
            // if the color was not yet determined, 
            // set the current color as the color to collect
            color_to_collect = current_bead;
            color_is_set = true;

            // the first bead of a color is always collected
            count++;
        }
        else if( current_bead == color_to_collect )
        {
            // collect another bead of the same color
            count++;
        }
        else
        {
            // bead of a different color was found, stop collecting
            break;
        }
    }

    return count;
}

int main()
{
    /* INPUT FROM FILE HERE */

    string necklace = "brbrrrbbbrrrrrbrrbbrbbbbrrrrb";
    
    int            max_position_beads = 0;
    int            max_split_position = 0;
    string        max_split_necklace;
    
    int         beads_left = 0;
    int         beads_right = 0;
    int            currect_position_beads = 0;
    int            current_split_position = 0;
    string        current_split_necklace;
        
    for( current_split_position = 0 ; current_split_position < necklace.length() ; current_split_position++ )
    {
        // create the necklace at the current position
        current_split_necklace = necklace.substr( current_split_position ) + necklace.substr( 0, current_split_position );

        // collect beads from the left
        beads_left = collect( current_split_necklace );

        // collect beads from the right
        beads_right = collect( reverse( current_split_necklace ) );

        // count the collected beads
        currect_position_beads = beads_left + beads_right;

        cout << "Split the necklace at position " << current_split_position;
        cout << " as " << current_split_necklace;
        cout << " and collected " << currect_position_beads << " beads";

        // check if it's greater than all splits we collected before
        if( currect_position_beads > max_position_beads )
        {
            max_split_position = current_split_position;
            max_split_necklace = current_split_necklace;

            cout << " <- this is our new maximum";
        }

        cout << endl;
    }

    cout << "If the necklace is split at position " << max_split_position;
    cout << " resulting in  " << max_split_necklace;
    cout << " you can collect " << currect_position_beads << " beads." << endl;
    cout << "No other split will collect more beads. " << endl;
    
    /* OUTPUT TO FILE HERE */

    return 0;
} 


---

Thanks so much. It actually works!! I'm finally done with that problem! Thanks again nvoigt.
The figures were even screwed up too. Wow.
sybariticak47

Reading it 24 hours later, I think apart from the spelling mistake of currect_position_beads, it should also read max_position_beads in the last output lines. I shouldn't code that early in the morning :D

It's weird I found some of those mistakes and it worked out ok with some of the large cases I presented it with but when I presented it with: "rwrbbw" it said that the largest break was the third position collecting 7 beads when there are only six beads in the necklace. (the seventh was a w). I was wondering if you knew what was going on here's the code I edited.
All I did was change currect to current, added max to the last statement, and in the if statement assigned current_position_beads to max_position_beads because max wouldn't change otherwise. Thanks a ton.

Code:

---

#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;
using std::cin;

char WHITE_BEAD = 'w';
char RED_BEAD  = 'r';
char BLUE_BEAD  = 'b';

// when i coded this whole thing,
// i assumed that any self-respecting
// string class would have a reverse()
// method. When my context help failed
// finding reverse(), this was the best
// I could find googling. I seriously
// hope that this is my inexperience
// with std::string, because not having
// a reverse() method in a standard
// container really sucks.
string reverse( const string& s )
{
    string result;

    for( string::const_iterator index = s.end() - 1; index != s.begin() - 1; index--)
    {
        result += *index;
    }

    return result;
}

// counts the number of beads of the same color
// that can be collected from the left of a necklace
int collect( const std::string& necklace )
{
    bool color_is_set = false;
    char color_to_collect;
    int count = 0;

    // iterate through all beads
    for( int index = 0 ; index < necklace.length() ; index++ )
    {
        char current_bead = necklace[index];

        if( current_bead == WHITE_BEAD )
        {
            // white beads can always be used
            count++;
        }
        else if( ! color_is_set )
        {
            // if the color was not yet determined,
            // set the current color as the color to collect
            color_to_collect = current_bead;
            color_is_set = true;

            // the first bead of a color is always collected
            count++;
        }
        else if( current_bead == color_to_collect )
        {
            // collect another bead of the same color
            count++;
        }
        else
        {
            // bead of a different color was found, stop collecting
            break;
        }
    }

    return count;
}

int main()
{
    /* INPUT FROM FILE HERE */

    string necklace = "rwrbbw";
   
    int            max_position_beads = 0;
    int            max_split_position = 0;
    string        max_split_necklace;
   
    int        beads_left = 0;
    int        beads_right = 0;
    int            current_position_beads = 0;
    int            current_split_position = 0;
    string        current_split_necklace;
       
    for( current_split_position = 0 ; current_split_position < necklace.length() ; current_split_position++ )
    {
        // create the necklace at the current position
        current_split_necklace = necklace.substr( current_split_position ) + necklace.substr( 0, current_split_position );

        // collect beads from the left
        beads_left = collect( current_split_necklace );

        // collect beads from the right
        beads_right = collect( reverse( current_split_necklace ) );

        // count the collected beads
        current_position_beads = beads_left + beads_right;

        cout << "Split the necklace at position " << current_split_position;
        cout << " as " << current_split_necklace;
        cout << " and collected " << current_position_beads << " beads";

        // check if it's greater than all splits we collected before
        if( current_position_beads > max_position_beads )
        {
            max_split_position = current_split_position;
            max_split_necklace = current_split_necklace;
            max_position_beads = current_position_beads;

            cout << " <- this is our new maximum";
        }

        cout << endl;
    }

    cout << "If the necklace is split at position " << max_split_position;
    cout << " resulting in  " << max_split_necklace;
    cout << " you can collect " << max_position_beads << " beads." << endl;
    cout << "No other split will collect more beads. " << endl;
    int y;
    cin >> y;
    /* OUTPUT TO FILE HERE */

    return 0;
}

---

Never mind. If it's a good break it will repeat; therefore, I made it so that if the break is larger than the string, the break equals the string. Thanks again!!

Just a comment on std::string reverse method comment. If I'm understanding correctly I'd normally write something like:

Code:

---

reverse(current_split_necklace.begin( ), current_split_necklace.end( ));

---

Regards,
Brian