0

I have a task, which is to scramble a single word, whose size is greater than 3 letters.

The scrambled word must not be equal to the original, and the first and last letters of the word must remain the same.

For example, the word stack, could give the one of the following results:

  • satck
  • scatk
  • stcak
  • sactk
  • etc

While words like is or hey for example, would remain unchanged for being too small.

My attempt to do this can be seen below. I have a JavaScript function that received a word to scramble, and then I choose random indexes within a certain limit to create a new scrambled word and return it. If the index I have chosen was already picked, then I try again hoping for a new result.

/**
 * Returns a scrambled word with the first and last letters unchanged
 * that is NOT EQUAL to the given parameter 'word', provided it has 
 * more than three characters.
 */
function scrambleWord(word){

  if(word.length <= 3)
    return word;

  var selectedIndexes, randomCharIndex, scrambledWord = word;

  while(word === scrambledWord){
    selectedIndexes = [], randomCharIndex, scrambledWord = '';
    scrambledWord += word[0];
    for(var j = 0; j < word.length-2; j++){

      //select random char index making sure it is not repeated
      randomCharIndex = getRandomInt(1, word.length-2);
      while(selectedIndexes.indexOf(randomCharIndex) > -1 && selectedIndexes.length != word.length-2){
        randomCharIndex = getRandomInt(1, word.length-2);
      }

      scrambledWord += word[randomCharIndex];
      selectedIndexes.push(randomCharIndex);
    }
    scrambledWord += word[word.length-1];
  }
  return scrambledWord;
}

/**
 * Returns a random integer between min (inclusive) and max (inclusive)
 * Using Math.round() will give you a non-uniform distribution!
 * See: http://stackoverflow.com/a/1527820/1337392
 */
function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

The problem with this approach, is that it is too slow. I fail the tests because I exceed the time limit of 6 seconds, so I definitely need to improve this solution, but I can't see where I can do it.

From an algorithm perspective, what is the most efficient way that uses the least amount of worst case operations that I can approach this problem?

  • Do you have to produce random results, or could you consistently scramble stack as sactk? – Bart van Ingen Schenau Dec 11 '15 at 15:03
  • The results must be random :D – Flame_Phoenix Dec 11 '15 at 15:03
  • 1
    Are you sure that this code works, and that the only problem with it is that it is too slow? – Mike Nakis Dec 11 '15 at 15:12
  • 5
    And what happens with words like "moot" ? – Mike Nakis Dec 11 '15 at 15:14
  • 1
    Rather than editing what you did back into your question, it would be appropriate to answer your own question. See Can I answer my own question? for more information. – Dan Pichelman Dec 11 '15 at 17:17
3

Something along the following lines; treating the string as a character array:

  • Handle strings that are 3 or fewer characters, or all the middle characters are the same
  • Create a sublist of the letters excluding the first and last
  • Fisher-Yates shuffle the middle letters until they don't match the original (this can be done in O(n) time)
  • Reattach the first and last letter

A faster shuffle can be used, if it is allowed to be less random (e.g. ln(n) random swaps). In the extreme case this can be reduced to Mike Nakis' answer

  • 2
    In the case of "moot", you wind up in an endless loop this way. – Neil Dec 11 '15 at 15:21
  • True. I've also not handled the case where the string is <=3 – Scroog1 Dec 11 '15 at 15:22
2
  1. Let n be word.length - 3. (Yes, '3'.)
  2. Issue a random index i in the range 0...n.
  3. Swap the letters at word[1 + n] and word[1 + n + 1].

you are done.

If there is a possibility that the word may contain two identical letters, then whoever gave you this assignment must first answer what happens with words like "moot". Assuming that they will say "moot" stays same, but "schmoot" must become something other than "schmoot", then:

1.b Check if all letters except first and last are same. If they are, you are done.

2.b Keep repeating step 2 until the letters at word[1 + n] and word[1 + n + 1] are different.

  • The example could equally be "mooot". It isn't sufficient to check if they're just 4-letter words. – Neil Dec 11 '15 at 15:29
  • @Neil You are right. I believe I have fixed it now. – Mike Nakis Dec 11 '15 at 15:33
  • 1
    It certainly works, and I give you props for the approach that is potentially O(1). – Neil Dec 11 '15 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.