Cannot get my head around this basic algorithm involving a simple for-loop?

Question

Consider a string whose first letter is always "M" and whose other characters can be pretty much any combinations of "I"s and "U"s (no other letter allowed, just Is and Us). For example: MIU, MUI, MIUIU, MUIIUIU, MUIIIUIIIUIII, MIUUIUIIIUUI are all strings of this kind.

I want a function that given any such string as input, returns an array with all the possible ways the pattern "III" can, if it appears at all in the input string, be replaced with "U" in the input. For example, there are 2 ways "III" can be replaced with "U" in "MIIII", namely MUI and MIU. Therefore, the function should, given MIIII as input, return [MUI, MIU].

This is my (flawed) function. The idea behind it is that of looping through the input string (i.e. MIstring) looking for "III". Each time "III" is found, MIstring is added to the IIIoptions array but with "U" replacing "III".

function ruleThree() {
    var IIIoptions = [];
    for (var i = 0; i < MIstring.length; i++) {
        if (MIstring.slice(i, i+3) === "III") {          
           IIIoptions.push(MIstring.replace(MIstring.slice(i, i+3), "U"));
        }
    }
    return IIIoptions;
}

Given the input MIIII, I expected the function to return [MUI, MIU]. However, it returns [MUI, MUI]. I have tried with different inputs and it displays the same problem, that is, all the items in the array are the same. For example, given the string MIIIIUIIIIU it gives me [MUIUIIIIU, MUIUIIIIU, MUIUIIIIU, MUIUIIIIU] instead of [MUIUIIIIU, MIUUIIIIU, MIIIIUUIU, MIIIIUIUU]. So the function gets the number of "III"s contained in MIstring right, but it does not return the array that I would expect it to return.

What is wrong with my function?

This is because your .replace always replaces the first III -- no matter what the actual position is. What you need is result.push(slice-before-the-position + U + slice-after-the-position) instead of replace. — georg
– georg, Commented May 15, 2019 at 21:18
Or, if you don't need to use a for() loop, use reduce() and avoid the side-effect nature of your code. — Randy Casburn
– Randy Casburn, Commented May 15, 2019 at 21:20

Shidersz · Accepted Answer · 2019-05-15 22:16:36Z

The main problem is that you are using String.replace() and that method will always replace the first matching sequence of III by U the way you are calling it. You can use String.slice() to generate the new string with the replacement when a match is found, like this:

const input = "MIIIII";

function ruleThree(str)
{
    var IIIoptions = [];

    for (var i = 0; i < str.length; i++)
    {
        if (str.slice(i, i + 3) === "III")
           IIIoptions.push(str.slice(0, i) + "U" + str.slice(i + 3));
    }
    
    return IIIoptions;
}

console.log(ruleThree(input));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

However, note the previous approach will fail if you need more than one replacement at a time, for example, if your input is MIIIIII it will not generate the MUU string. In this case, you will have to use a recursive way:

const input = "MIIIIIII";

function getCombs(str, res = new Set())
{
    for (var i = 0; i < str.length; i++)
    {
        if (str.slice(i, i + 3) === "III")
        {
           let r = str.slice(0, i) + "U" + str.slice(i + 3);
           res.add(r);
           getCombs(r, res);
        }
    }

    return [...res];
}

console.log(getCombs(input));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Collectives™ on Stack Overflow

Cannot get my head around this basic algorithm involving a simple for-loop?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related