[FIXED] How do I generate a string that contains a keyword?

Issue

I'm currently making a program with many functions that utilise Math.rand(). I'm trying to generate a string with a given keyword (in this case, lathe). I want the program to log a string that has "lathe" (or any version of it, with capitals or not), but everything I've tried has the program hit its call stack size limit (I understand exactly why, I want the program to generate a string with the word without it hitting its call stack size).

What I have tried:

function generateStringWithKeyword(randNum: number) {
  const chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/";
  let result = "";
  for(let i = 0; i < randNum; i++) {
    result += chars[Math.floor(Math.random() * chars.length)];
    if(result.includes("lathe")) {
      continue;
    } else {
      generateStringWithKeyword(randNum);
    }
  }
  console.log(result);
}

This is what I have now, after doing brief research on stackoverflow I learned that it might have been better to add the if/else block with a continue, rather than using

if(!result.includes("lathe")) return generateStringWithKeyword(randNum);

But both ways I had hit the call stack size limit.

Solution

A "correct" version of your algorithm, written as an iterative function instead of as a recursive one so as not to exceed stack depth, would look something like this:

function generateStringWithKeyword(randNum: number) {
    const chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/";
    let result = "";
    let attemptCnt = 0;
    while (!result.toLowerCase().includes("lathe")) {
        attemptCnt++;
        result = "";
        for (let i = 0; i < randNum; i++) {
            result += chars[Math.floor(Math.random() * chars.length)];
        }
        if (attemptCnt > 1e6) {
            console.log("I GIVE UP");
            return;
        }
    }
    console.log(result);
    return result;
}

I don't like when my browser hangs because of a script that won't finish, so I put a maximum attempt count in there. A million chances seems reasonable. When you try it out, this happens:

generateStringWithKeyword(10); // I GIVE UP

Which makes sense; let's perform a rough back-of-the-envelope probability calculation to see how long we might expect this to take. The chance that "lathe" will appear in some case at position 1 of the word is (2/64)×(2/64)×(2×64)×(2/64)×(2/64) ("L" or "l" appears first, followed by "A" or "a", etc) which is approximately 3×10^-8. For a word of length 10, "lathe" can appear starting at positions 1, 2, 3, 4, 5, or 6. While this isn't exactly correct, let's think of this as multiplying your chances by 6 of getting the word somewhere, so the actual chance of getting a valid result is somewhere around 1.8×10^-7. So we can expect that you'd need to make approximately 1 ÷ 1.8×10^-7 = 5.6 million chances to succeed.

Oh, darn, I only gave it a million. Let's up that to 10 million and try again:

generateStringWithKeyword(10); // "lATHELEYSc"

Great! Although, it does sometimes still give up. And really, an algorithm which needs millions of tries before it succeeds is very, very inefficient. You might want to read about bogosort, a sorting algorithm which works by randomly shuffling things and checking to see if they are sorted, and it keeps trying until it works. It's used for educational purposes to highlight how such techniques don't really perform well enough to be practical. Nobody would ever want to use such an algorithm for real.

---

So how would you do this "the right" way? Well, my suggestion here is to just build your result correctly the first time. If you have 10 characters and 5 of them need to be "lathe" in some case, then you will need 5 truly random characters. So randomly decide how many of those letters should be before "lathe". If you pick 2, for example, then put 2 random characters, plus "lathe" in a random case, plus 3 more random characters.

It could be something like this, where I mostly use your same style of for-loops and += string concatenation:

function generateStringWithKeyword(randNum: number) {
    const keyword = "lathe";
    if (randNum < keyword.length) throw new Error(
        "This is not possible; \"" + keyword + "\" doesn't fit in " + randNum + " characters"
    );
    const actuallyRandNum = randNum - keyword.length;
    const chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/";
    let result = "";
    const kwInsertionPoint = Math.floor(Math.random() * (actuallyRandNum + 1));
    for (let i = 0; i < kwInsertionPoint; i++) {
        result += chars[Math.floor(Math.random() * chars.length)];
    }
    for (let i = 0; i < keyword.length; i++) {
        result += Math.random() < 0.5 ? keyword[i].toLowerCase() : keyword[i].toUpperCase();
    }
    for (let i = kwInsertionPoint; i < actuallyRandNum; i++) {
        result += chars[Math.floor(Math.random() * chars.length)];
    }
    return result;
}

If you run this, you will see that it is very efficient, and never gives up:

console.log(Array.from({ length: 4 }, () => generateStringWithKeyword(5)).join(" "));
// "lathE LaThe lATHe LatHe"

console.log(Array.from({ length: 4 }, () => generateStringWithKeyword(7)).join(" "));
// "p6lAtHe laThE01 nlaTheK lATHeRJ" 

console.log(Array.from({ length: 4 }, () => generateStringWithKeyword(10)).join(" "));
// "giMqzLaTHe 5klAthegBo oVdLatHe0q twNlATheCr"

Playground link to code

Answered By - jcalz

Answer Checked By - Katrina (PHPFixing Volunteer)