Thread: Broken Necklace

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    24

    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!!

  2. #2
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,130
    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)
    {
        
    string result;

        for( 
    string::const_iterator index s.end() - 1index != s.begin() - 1index--)
        {
            
    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::stringnecklace )
    {
        
    bool color_is_set false;
        
    char color_to_collect;
        
    int count 0;

        
    // iterate through all beads
        
    for( int index 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 current_split_position necklace.length() ; current_split_position++ )
        {
            
    // create the necklace at the current position
            
    current_split_necklace necklace.substrcurrent_split_position ) + necklace.substr0current_split_position );

            
    // collect beads from the left
            
    beads_left collectcurrent_split_necklace );

            
    // collect beads from the right
            
    beads_right collectreversecurrent_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;

    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  3. #3
    Registered User
    Join Date
    Dec 2005
    Posts
    24
    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

  4. #4
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,130
    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
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  5. #5
    Registered User
    Join Date
    Dec 2005
    Posts
    24

    case

    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; 
    }

  6. #6
    Registered User
    Join Date
    Dec 2005
    Posts
    24

    Never mind

    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!!

  7. #7
    Registered User
    Join Date
    Jul 2005
    Posts
    69
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. This CD Drive is broken?
    By alphaoide in forum Tech Board
    Replies: 3
    Last Post: 06-04-2005, 02:59 PM
  2. Broken While Loop
    By GamingMarvel in forum C++ Programming
    Replies: 6
    Last Post: 01-10-2005, 12:46 PM
  3. Is this a valid use of C++, or have I completely broken some major rules?
    By Lithorien in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 12-14-2004, 05:43 PM
  4. undeclared identifier problem
    By jjj93421 in forum C++ Programming
    Replies: 13
    Last Post: 04-24-2004, 09:22 AM
  5. broken pipe
    By samps005 in forum Linux Programming
    Replies: 1
    Last Post: 05-07-2003, 09:04 PM