How to scramble a word, keeping first and last characters the same? (JS)

Question

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.

Any ideas?

Write a function that scrambles _all_ the letters in a string. Then write a function that returns a copy of the string you give it except with the first and last characters chopped off. Then do `function scramble_all_but_ends(s){return first_char(s) + scramble_all(chop_off_ends(s)) + last_char(s));}` — Kevin, Dec 11 '15 at 15:01
Apologies for a flippant comment, but I think what you meant was "I hvae a tsak, wihch is to sacmlbre a slinge wrod, woshe szie is gtreear tahn 3 ltreets." — Anton Knyazyev, Dec 11 '15 at 16:14
@AntonKnyazyev Son of a ...... well done actually! Well done.... I read it through like a charm and only realized the pun when I was writing my comment :P kudos++ sir! — Flame_Phoenix, Dec 11 '15 at 16:23

score 4 · Accepted Answer · edited May 23 '17 at 12:30

There's an answer Here that deals with quick ways of shuffling a string. All you then need to do is take off the first and last letters like you are doing, use this approach to shuffle the string and then tack your first and last letters back on.

For completeness I would leave your checks that the answer you get isn't the same as the original just in case, and the checks that the string is > 3 characters as these are unique to your requirements.

This should be dramatically quicker than what you already have because it's your random shuffling that's taking all the time!

How to scramble a word, keeping first and last characters the same? (JS)

1 Answers1