Coderbyte: String Reduction

Question

From Coderbyte:

Have the function StringReduction(str) take the str parameter being passed and return the smallest number you can get through the following reduction method. The method is: Only the letters a, b, and c will be given in str and you must take two different adjacent characters and replace it with the third. For example "ac" can be replaced with "b" but "aa" cannot be replaced with anything. This method is done repeatedly until the string cannot be further reduced, and the length of the resulting string is to be outputted. For example: if str is "cab", "ca" can be reduced to "b" and you get "bb" (you can also reduce it to "cc"). The reduction is done so the output should be 2. If str is "bcab", "bc" reduces to "a", so you have "aab", then "ab" reduces to "c", and the final string "ac" is reduced to "b" so the output should be 1.

Source ( passed all validations ):

var replacements = 
{
 "ab" : "c",
 "ac" : "b",
 "bc" : "a",
 "ba" : "c",
 "ca" : "b",
 "cb" : "a"
};
function StringReduction(s) 
{ 
 var original, key;
 while( s != original )
 {
 original = s;
 for( key in replacements )
 s = s.replace( key , replacements[key] );
 }
 return s.length;
}
// keep this function call here 
// to see how to enter arguments in JavaScript scroll down
StringReduction(readline());

The funny part of this challenge is that you write against time, so the first version was a terrible, recursive approach. Since then I rewrote it a few times before posting to CR, thinking each time mistakenly that it was perfect, at this point I would like to get your feedback on it.

Answer 1

A few minor notes:

1. Have the function StringReduction(str)

   strictly speaking, the parameter name is different:

   function StringReduction(s) 
   

   :-)

2. var original, key;
   

   I'd put the variable declarations to separate lines. From Code Complete 2nd Edition, p759:

   With statements on their own lines, the code reads from top to bottom, instead of top to bottom and left to right. When you’re looking for a specific line of code, your eye should be able to follow the left margin of the code. It shouldn’t have to dip into each and every line just because a single line might contain two statements.

   It could prevent some diff/merge conflicts (you modify the first variable, a coworker the second one at the same time).

3. (削除) key could be declared inside the while loop. (削除ここまで)

   • JavaScript variables declare outside or inside loop?
   • Effective Java, Second Edition, Item 45: Minimize the scope of local variables

   As @konijn pointed out in his comment, that may confuse maintainers. Anyway, extracting it out into a separate function solves the issue (#6).

4. The name original could be lastString or lastValue since it's not the original string, it's the result of the last loop.

5. Indentation is not consistent. Most of the places it's two spaces but the while loop is only one space indented, the body of the for loop has three spaces.

6. I'd extract out the for loop to a string translate(string, replacements) function for better readability.

• konijn: 3. is interesting, I avoid it due to the hoisting feature in JS which can confuse maintainers (github.com/airbnb/javascript#variables) 5. I'm an idiot ;)
• palacsint: @konijn: 3. Thanks, good point, answer updated.

Answer 2

I know this is very old, but I have a small update to this program, I believe you do not need the while loop and original because it always executes once or goes in indefinite loop if the string has no replacement combinations.

• Sᴀᴍ Onᴇᴌᴀ: Welcome to Code Review! How can it work without the while loop (or similar construct), given "If str is "bcab", "bc" reduces to "a", so you have "aab", then "ab" reduces to "c", and the final string "ac" is reduced to "b" so the output should be 1."?