Scramble Middle Letters

What exactly do you mean by "scramble"?

If you literally mean randomly permute then you can use std::shuffle - see
http://www.cplusplus.com/reference/algorithm/shuffle/

On the other hand, your "expected" outcome might be construed as std::rotate - see
http://www.cplusplus.com/reference/algorithm/rotate/

Meanwhile your code sample seems to be trying to do reversal. No idea how it gives the output that you cite.

So please give more explanation (and a complete, runnable code).

Here's a variant with a random shuffle - but that might not be what you meant.

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <ctime>
#include <random>
using namespace std;


mt19937 gen( time( 0 ) );


string scramble( string str )
{
   int N = str.size();
   if ( N > 2 ) shuffle( str.begin() + 1, str.begin() + N - 1, gen );
   return str;
}


int main()
{
   string sentence;
   cout << "Enter a sentence: ";
   getline( cin, sentence );
   stringstream ss( sentence );
   for ( string str; ss >> str; ) cout << scramble( str ) << ' ';
}

Enter a sentence: The quick brown fox
The qcuik bwron fox

Last edited on

I'd have to assume swapLetters is receiving one word at a time, but that's not clear. It could be a line of text for all I know.

The context of the code thus far suggests one word at a time.

If so, then your first "rejection" opportunity is when the length if input <= 3. Only words > 3 are candidates for this shuffle.

The definition of "middle letters" appears to be, based on your "expected" sample, from the second character to the second to last character of the word.

You haven't calculated that. It is simple, though. If a word has, say, 4 characters, then you are at most scrambling 4 - 2, or 2 characters (this input.length() / 3 makes no sense). If the word had 6 characters, you're skipping both the first and last character, so you're swapping around 6 - 2 or 4 characters.

Correctly, you start at character 1 (since 0 is the first character).

If 'scramble' merely means reversal, you're close but....

Your sequence runs from 1 to the middle (not 1/3) of the string.

For an odd numbered sequence, the center character will not be moved with this approach, is that acceptable for the definition of "scramble"?

@lastchance, if you look at the existing code, there's an obvious missed opportunity for std::swap, and noting the rest of the nature of the code and the question, I doubt any of the algorithms are an option here.

This student probably has no access to them.

Also, the output can be explained if this algorithm processed the entire line. The output "tof", skipping the first character, took the "o" from "fox", and then the "f" from fox, whereas the end sequence shows the "h" from the and the "e" from the.

So, this function took the entire line of text....my assumption is incorrect.

This means, @gonggong, you must first plan how to strip this incoming sequence of words into individual words for swapping.

Have a plan for that?

Last edited on

niccolo wrote:
@lastchance, if you look at the existing code, there's an obvious missed opportunity for std::swap, and noting the rest of the nature of the code and the question, I doubt any of the algorithms are an option here.

Well, I thought std::swap was actually an algorithm: http://www.cplusplus.com/reference/algorithm/swap/

I note that

expected: the q(SCRAMBLED LETTERS)k b(SCRAMBLED)n fox
output sample: the qicuk bowrn fox

is either done (per word) by random shuffling or a rotate left by 1. Definitely not by swap unless my spelling has really collapsed.

So I'll call for more explanation.

Last edited on

@lastchance,

Yes, certainly swap is part of the algorithms library, hence my point

I doubt any of the algorithms are an option here

...and, thus, rotate and shuffle.

However, @gongong will have to say if those algorithms are or are not possible in his code for an assignment (some professors specifically deny the use of libraries, functions or classes which have not yet been presented in lecture).

Certainly the sample output shows rotation for quick and brown, but again @gongong will have to answer as to what is to be chosen. The reversal isn't bad, if it qualifies for the assignment, though the center of an odd length sequence wouldn't move in such a case.

That brings up an interesting question for @gongong. The code presented uses the length member function of the string class. Noting the nature of the assignment, it seems clear to me that you are being tasked to look up the documentation for the string class to use what functions are documented there for this task.

For example, the [] operator on the string class is a member function.

There's also something to find a character in a string, and since spaces separate words, and separating words is apparently a required part of the assignment, could you use the string's function for searching for a character or would you have to avoid a string function not yet presented in class, thus requiring you to write your own?

Or, for that matter, can you use stringstream as in @lastchance's example?

Last edited on

Hi People!!

Thanks for your reply!!

It's just a quick exercise my Java/CPP professor gave me.
He was kind enough to give me exercises for the summer so that I won't forget whatever I learned and I'd get a headstart for what we're gonna be learning for the second half of CPP.
I've been doing Java for the last month, so my CPP skills suck more than usual c':

There was no set instructions. Just scramble the middle letters of each word from an input sentence.

here's the whole code:

#include <iostream>
#include <string>

using namespace std;

string swapLetters(string input)
{
	for (int i = 1; i < input.length() / 3; i++)
	{
		char ch = input[i];
		input[i] = input[input.length() - 1 - i];
		input[input.length() - 1 - i] = ch;
	}
	return input;
}
string userPrompt(string input)
{
	cout << "Enter a sentence (end with a period): ";
	getline(cin, input, '.');
	return input;
}
string toLower(string string)
{
	for (int i = 0; i < string.length(); i++)
	{
		string.at(i) = tolower(string.at(i));
	}
	return string;
}

int main()
{
	string userInput;
	userInput = userPrompt(userInput);
	userInput = toLower(userInput);

	cout << endl << "You input: " << userInput << endl;

	userInput = swapLetters(userInput);
	cout << endl << "Scrambled: " << userInput << endl;
	return 0;
}

Last edited on

Ok, so have you thought about this in light of the discussion @lastchance and I have had about it?

Hi!

Since I don’t know the algorithm library yet, I was thinking of incorporating rand with the indexes??

If that even works, I think that’s just way to long to code and not very efficient.

So..........you haven't really thought about the discussion above?

Step 1....what about splitting the line of text into words?

StringStream?

Something else?

Can't get all the way to rand with indexes until you have words (not lines) to scramble

We haven’t gone over SS.
Hold on. I’ll work again on this after class. I need to research more about SS

Shibitto (27)

How do they do the matrix scramble would be better fitting.

Avoiding <algorithm> and <sstream> makes this ... mmm ... difficult. Back-to-basics coding here. Only benefit: it retains the word spacing.

#include <iostream>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cctype>
using namespace std;


//======================================================================


bool nextWord( const string &str, int pos, int &p, int &q )             // if successful, word is indices [p,q)
{
   // Find start of word (here, defined as first non-space) starting scanning from index pos
   p = pos;
   while ( p < str.length() && isspace( str[p] ) ) p++;
   if ( p >= str.length() ) return false;

   // Find next space (or end of string)
   q = p + 1;
   while ( q < str.length() && !isspace( str[q] ) ) q++;

   return true;
} 


//======================================================================


void scramble( string &str, int i1, int i2 )                           // scramble string from i1 to i2 inclusive
{
   int N = i2 - i1 + 1;                                                // number of letters
   if ( N < 2 ) return;                                                // nothing to do

   int Nshuffle = 1 + log( 0.01 ) / log( 1 - 2.0 / N + 2.0 / N / N );  // number of swaps to ensure that one letter
                                                                       //    has greater than 99% chance of moving

   for ( int i = 1; i <= Nshuffle; i++ )                               // lots of letter swapping
   {
      int a = i1 + rand() % N;
      int b = i1 + rand() % N;
      char temp = str[a];   str[a] = str[b];   str[b] = temp;
   }
} 


//======================================================================


int main()
{
   srand( time( 0 ) );

   string sentence;
   cout << "Enter a sentence: ";
   getline( cin, sentence );

   int pos = 0, p, q;
   while ( nextWord( sentence, pos, p, q ) )
   {
      scramble( sentence, p + 1, q - 2 );
      pos = q;
   }

   cout << sentence << '\n';
}

Enter a sentence: The     quick       brown fox     jumps over  the    lazy dog
The     qciuk       borwn fox     jupms over  the    lzay dog

Last edited on

Ganado (6812)

I'd honestly prefer just the circular shift to the randomness, because a shift isn't guaranteed when it's random (e.g. your "over" output).

Oh wow. Those are way too advanced for me!!

This is what I up with:

string scramble(string str)
{
        //should the srand() go here or in the main?
	int spot = rand()% str.length(); 
	return str.substr(spot, 1) + scramble(str.substr(0, spot) + str.substr(spot + 1));
}

Enter a sentence: the quick brown fox jumped over the lazy dog
the qicuk brwon fox juempd oevr the lazy dog 

Enter a sentence: the quick brown fox jumped over the lazy dog
the qucik brown fox jpmued oevr the lzay dog 

Enter a sentence: the quick brown fox jumped over the lazy dog
the qciuk borwn fox jpemud oevr the lzay dog

EDIT:
I just reread the discussions above, and I apologize for missing so many points.

Can't get all the way to rand with indexes until you have words (not lines) to scramble

I read about the sstream and somewhat understood the concept, so I decided to just keep using it. Professor said that it's the scrambler function that's going to be scrutinized.

He said to research about recursion since it's going to be the main thing we're going to learn about in the second half of CPP (along with 1. c-strings, strings, vectors 2. pointers and dynamic arrays 3. defining classes 4. friends, overloaded operators, and arrays in classes 5. separate compilation and namespaces 6. pointers and linked lists 7. recursion 8. inheritance 9. exception and handling 10. templates 11. c++11) I thought I'd list down the things I haven't learned so that you may assist me efficiently.

you must first plan how to strip this incoming sequence of words into individual words for swapping.

When I was reading about parsing, I didn't really understand it. I remember coding something that counts the words in a string, so maybe I could repurpose that if I were to go this route?

if those algorithms are or are not possible in his code for an assignment

He allowed me to dig into recursion but not algorithms

Last edited on

void scramble( string &str, int i1, int i2 )                           // scramble string from i1 to i2 inclusive
{
   int N = i2 - i1 + 1;                                                // can't we use the .length() function?
   if ( N < 2 ) return;                                                // shouldn't it be < 3 ?

   int Nshuffle = 1 + log( 0.01 ) / log( 1 - 2.0 / N + 2.0 / N / N );  // I haven't taken any maths in awhile, 
                                                                       // but I presume Nshuffle equation is some kind of pre-defined equation?

   for ( int i = 1; i <= Nshuffle; i++ )                               // lots of letter swapping
   {
      int a = i1 + rand() % N;
      int b = i1 + rand() % N;
      char temp = str[a];
      str[a] = str[b];
      str[b] = temp;
   }
}

Last edited on

mbozzi (3933)

Use the Fisher-Yates algorithm?

#include <string>
#include <iostream>
#include <cstdlib>

// Fisher-Yates algorithm:
// https://en.wikipedia.org/wiki/Fisher–Yates_shuffle
std::string scramble_middle(std::string s)
{
  // TODO: write your own swap function
  for (int i = s.size() - 2; i >= 2; --i)
    std::swap(s[i], s[(std::rand() % i) + 1]);  
    
  return s;
}

int main()
{
    for ( std::string word; std::cin >> word; )
        std::cout << scramble_middle(word) << '\n';
}

Last edited on

gongong wrote:
// can't we use the .length() function?

It wasn't used here because this version is only scrambling PART of the string (the middle of one word, which is a small portion of the whole sentence). My earlier code used .size() or .length() because the string was a single word. In this instance I hadn't actually split up the sentence and I was retaining the arbitrary spacing between words which using a stream extractor >> wouldn't do.

gongong wrote:
// shouldn't it be < 3 ?

Depends how long you want your words to be before you scramble them. I was simply working on whichever words were possible to scramble when you removed the first and last letters.

gongong wrote:
// I haven't taken any maths in awhile, // but I presume Nshuffle equation is some kind of pre-defined equation?

I worked it out to do what it said in my code assuming that I was going to pick a succession of random pairs to swap; with hindsight that's a pretty lousy, inefficient method. @mbozzi's suggestion is much much more sensible, as it ensures that letters get moved rather than relying on probability. I have no idea how the actual std::shuffle works.

gongong wrote:
He allowed me to dig into recursion but not algorithms

Err, ... right! Lucky you!

Thanks for giving us a fun theme to play with, though!

Last edited on

Duthomhas (13212)

So tihs asmnesignt si bsead upon teh fcat that plpeoe raed whole-wrod pnttreas, nto the iiidanvdul letrets.
Teh msot imrntopat tnihg is taht het frist and lsat lteetr fo eht wrod si nto trosensapd; except rfo two ro tehre letetr wrdos, werhe ayn slcrmbae is fnie.
:
Hree's ym tyo:

#include <algorithm>
#include <chrono>
#include <ciso646>
#include <iostream>
#include <random>
#include <sstream>
#include <string>

#include <boost/algorithm/string/trim.hpp>
std::string trim( const std::string& s )
{
  auto r = s;
  boost::trim( r );
  return r;
}

bool find_next_word( const std::string& s, std::size_t& a, std::size_t& b )
{
  const char* letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  a = s.find_first_of( letters, b );
  if (a == s.npos) return false;

  b = s.find_first_not_of( letters, a );
  if (b == s.npos)
  {
    b = s.size();
    return true;
  }

  return true;
}

void scramble_word( std::string& s, std::size_t a, std::size_t b )
{
  static std::ranlux24 rng( std::chrono::system_clock::now().time_since_epoch().count() );
  std::size_t b1 = (b - a) > 3;
  std::size_t a1 = b1 || std::isupper( s[a] );
  std::shuffle( s.begin() + a + a1, s.begin() + b - b1, rng );
}

int main()
{

  std::string text;
  {
    std::cout << "Enter your text. Press ENTER twice to finish.\n";
    std::string s;
    while (getline( std::cin, s ) and !trim( s ).empty())
      text += s + "\n";
  }

  // Shuffle letters in words
  std::size_t a, b = 0;
  while (find_next_word( text, a, b ))
    scramble_word( text, a, b );

  std::cout << text;
}

This was a quick hack. I’m certain it could be significantly improved...

Ganado (6812)

trosensapd

This took me a few too many seconds to figure out, so let's make a program for that...

#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <algorithm>

int main(int argc, char** argv)
{
    if (argc != 2)
    {
        std::cout << "Usage: " << argv[0] << " <scrambled word>\n";
        return 1;
    }
    
    // https://raw.githubusercontent.com/dwyl/english-words/master/words.txt
    std::set<std::string> words;
    {
        std::ifstream fin("words.txt"); 
        std::string word;
        while (fin >> word)
        {
            words.insert(word);   
        }
    }

    std::string scrambled = argv[1];
    std::sort(scrambled.begin(), scrambled.end());
    do {
        if (words.find(scrambled) != words.end())
        {
            std::cout << scrambled << '\n';
        }
    } while (std::next_permutation(scrambled.begin(), scrambled.end()));
        
    return 0; 
}

>unscramble trosensapd
transposed

Last edited on