String ordering is working, but also not.

[jjordan33]

Hi,

I'm working on sorting a string of digits 1 - 5 until it equals 12345, one swap at a time, then printing the string after each swap.

The swap I want is supposed to start from the left each loop iteration. It does, most of the time.

2 1 5 3 4
becomes
1 2 5 3 4
1 2 3 5 4
1 2 3 4 5

Along with several other tests. However, I'm passing one of the tests about halfway in. Unfortunately, I don't know the specifics of the test.

(It's that personal challenge site I've mentioned before. It has a ranking system, but it's akin to the trophy system in video games. There's no formal competition.)

Can anyone see bad logic or code?

#include <iostream>
#include <string>

using namespace std;

int main(){
    
    string test = "12345"; // to compare the unordered string later
    string x;
    
    getline(cin, x); // unordered string with spaces. i.e. 1 3 2 4 5
    
    string clean = "";
    for (int i = 0; i < 9; i++){ // filters out spaces
       
        if (x[i] != ' '){
            clean += x[i]; // clean becomes 13245
        }
   
    }
   
    char temp;
    while (clean != test){ // while unordered 
       
        for (int i = 0; i < 5; i++){
           
            if (clean[i] > clean[i+1]){ // checks the char in front of i
                temp = clean[i]; // the 3 variable a, b , c swap method
                clean[i] = clean[i+1];
                clean[i+1] = temp;
                break; // once it swaps one time. breaks out of for loop.
            }
         
        } // continues on in the while loop...
        
        for (int i = 0; i < 4; i++){ // prints a space after clean[0-3]
            cout << clean[i] << " ";
        }
        cout << clean[4]; // prints last char separate to avoid trailing space
        
        cout << endl;
   
    } // starts the while loop over
    
}

Thank you.

[Ganado]

Your sorting logic is going out of bounds of the string.

Your "clean" string will be 5 characters long based on your input example in the comments.
On line 27, 29, and 30, you are going out of bounds when you try to access clean[i+1], when i == 4.

Perhaps start at i = 1 and compare [i] with [i-1] to prevent bounds issues.

[jjordan33]

Ganado >>

Something like this?

char temp;
    while (clean != test){
       
        for (int i = 1; i < 5; i++){
           
            if (clean[i] < clean[i-1]){ 
                temp = clean[i-1]; 
                clean[i-1] = clean[i];
                clean[i] = temp;
                break; 
            }
         
        } 

[Ganado]

Does it work?

Also, temp can be declared in the inner-most scope (line 7), no need to declare it outside.

[jjordan33]

It reorders the string one swap at a time, but it still fails one of the tests.

I think it's a detail of the rules I'm overlooking.

[Ganado]

I don't know then. I will say, your code is very, very specific, perhaps that is the issue. It will only work if the input is a permutation of 12345. Is that really what you want?

Unless you only want it to work with 12345, instead of while (clean != test) you should do something like

while (not_in_order(clean))
{ ... }

where the not_in_order function loops over the string and returns false if str[i] < str[i-1] for any i.

This seems more convoluted than necessary to work with strings. Why not just have an array or vector of 5 ints?

[jjordan33]

The challenge only wants a permutation of 12345, but there's no reason my code has to be so rigid. It would be better to approach this to work on anything.

https://open.kattis.com/problems/mjehuric

I'll try an array. I don't know the first thing about vectors yet.

[Ganado]

But just to clarify, it's telling you that a test is failing, but you don't know what's wrong with it, or what input causes a failure?

vectors are basically just arrays (but if you choose to, you could resize them).
You still access them just like arrays (or strings): vec[i].
Their initial setup is just a bit different:
int arr[5] = {}; --> vector<int> arr(5);

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> 

using namespace std;

void print(const vector<int>& vec)
{
    for (const auto& element : vec)
        cout << element << ' ';
    cout << '\n';
}

int main()
{  
    // 
    // Declare array of numbers (vector)
    //
    const int num_elements = 5;
    vector<int> vec(num_elements); // a vector is just a wrapper for a dynamic array
    
    //
    // Get numbers from user input
    // 
    for (int i = 0; i < num_elements; i++) {
        cin >> vec[i];   
    }

    //
    // Swap from left to right, and print until sorted.
    // Normally would just use std::sort here, but you are printing out intermediate forms.
    //
    while (!is_sorted(vec.begin(), vec.end())) {
        for (int i = 1; i < num_elements; i++) {        
            if (vec[i] < vec[i-1]) {
                std::swap(vec[i-1], vec[i]);
                break; 
            }
        }        
        print(vec);
    }
}

my input:
5 3 4 1 2

program output:
3 5 4 1 2 
3 4 5 1 2 
3 4 1 5 2 
3 1 4 5 2 
1 3 4 5 2 
1 3 4 2 5 
1 3 2 4 5 
1 2 3 4 5 

https://en.cppreference.com/w/cpp/algorithm/is_sorted

[Niccolo]

@jjordan33,

We would need to see what input appears to fail and why.

So far as I can see, as long as we alter your first post to loop from 0 to 4, it works.

It won't looping from 0 to 5, as you've already been told, that fails (badly)

But 0 to 4 worked as far as I can see.

[ne555]

you need to read the problem carefully.
you are not following the algorithm correctly because every time that there is a swap you go back to step 1.

for example, for input 4 5 3 2 1, you should output

4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
...

but your output is

4 3 5 2 1
3 4 5 2 1
3 4 2 5 1
...

(note how the 5 moves to the last place)

[jjordan33]

@ Ganado
>> But just to clarify, it's telling you that a test is failing, but you don't know what's wrong with it, or what input causes a failure?

That's correct.
**edit**
Your code fails the exact same test as mine. It's frustrating not knowing why.

@ne555
>> you need to read the problem carefully.
you are not following the algorithm correctly because every time that there is a swap you go back to step 1.

With it starting back over at condition one, which is...
If the number on the first piece is greater than the number on the second piece, swap them.

Shouldn't the 4 and the 3 be swapped the second go round? 4 is > 3.
**edit**
I stand corrected.

[Niccolo]

@ne555,

Never mind....I missed something...

[jjordan33]

I'm still missing it. :(

[jjordan33]

ohhhhhhhhh.

Thank you.

** edit **
I touched up my code to let it run through EACH step before going back to one, and fixed the out of bounds issue.

#include <iostream>
#include <string>

using namespace std;

int main(){
    
    string test = "12345";
    string x;
    getline(cin, x);
    string clean = "";
    for (int i = 0; i < 9; i++){
        if (x[i] != ' '){
            clean += x[i];
        }
    }
    char temp;
    while (clean != test){
        for (int i = 0; i < 4; i++){ // just lowered the bounds of the iteration.
            if (clean[i] > clean[i+1]){
                temp = clean[i];
                clean[i] = clean[i+1];
                clean[i+1] = temp;
                for (int j = 0; j < 4; j++){ // took out the break and swapped it with the print
                    cout << clean[j] << " ";
                }
                cout << clean[4];
                cout << endl;
            }
            
        }
        
    }
    
}