7
\$\begingroup\$

I was given an assignment, it was as follows:

Give a JS code snippet which writes to the console from: "0" to "ZZZZZ" all the combination of the characters of a-z, 0-9 and A-Z.

Is my solution correct? I am sure there are better ways to achieve the same, can anybody show some? My code is:

function createCharSet(){
    var charset = "", c;

    for(c=48;c<58;c++){
        charset += String.fromCharCode(c);
    }
    for(c=97;c<123;c++){
        charset += String.fromCharCode(c);
    }   
    for(c=65;c<91;c++){
        charset += String.fromCharCode(c);
    }

    return charset;

}


function getNext(curr, charSet){
    var 
        length = curr.length,
        arr = curr.split(""),
        radix = charSet.length,
        i, c;

    for(i=length-1;i>-1;i--){
        c = charSet.indexOf(arr[i])+1;

        if(c==radix){
            arr[i]=charSet[0];
            if(i==0)
                return;
        }else{
            arr[i]=charSet[c];
            break;
        }
    }

    return arr.join("");
}

function iterate() {
    var 
        charSet = createCharSet(),
        maxLen = 4,
        len,
        i,
        arr,
        curr;

    for(len = 1;len<maxLen+1;len++){
        arr = [];
        for(i=0;i<len;i++){
            arr.push(charSet[0]);
        }

        curr = arr.join("");
        while(curr) {
            console.log(curr);
            curr = getNext(curr, charSet);
        };
    }

}

iterate();
\$\endgroup\$
3
  • \$\begingroup\$ Any reason why the title of your question is so different from the actual task you were given? \$\endgroup\$
    – Flambino
    Commented May 24, 2014 at 21:33
  • \$\begingroup\$ Reason: slept only a few hours. Edited the title... was it really so different? \$\endgroup\$
    – Androrider
    Commented May 24, 2014 at 23:02
  • \$\begingroup\$ Yes and no. The logic's the same, but the previous title implied that a was the lowest value in the charset, and 9 was the highest, but the code said otherwise. Also, an order of magnitude difference between the end values, which is something. \$\endgroup\$
    – Flambino
    Commented May 24, 2014 at 23:31

2 Answers 2

6
\$\begingroup\$

Minor observations:

  1. I'd just hardcode the charset in this case. Doing so is faster to write (and a lot more explicit) than building it with a bunch of loops.

  2. The modulo operator % is a good friend to have for this, as it'll let you "wrap around" array indices.

Overall, there's too much code here, I think. This is just counting in base 62.

It'd be awesome if Number.prototype.toString() accepted 62 as an argument, but, unfortunately, it only seems to accept bases 2-36. Similarly, it'd be great if we could somehow use the built-in base64 encoding function (btoa), but it's, well, base 64 (and it's got other issues). So we do have to roll our own.

Now, if this was base 10, we could obviously just do

var limit = Math.pow(10, 5); // i.e. 100000

for(var i = 0 ; i < limit ; i++) {
  console.log(i);
}

which will print 0-99999.

Using this same basic setup, we can print our base62 values. Our limit will be \$base^{numberOfDigits}\$ just like \$10^5\$ will end up printing five 9s. So for 0-ZZZZZ we'll need to loop from zero to Math.pow(62, 5).

And of course, we'll have to do the actual base62 conversion. The basic algorithm is:

  1. Get the char corresponding to \$value\bmod base\$ (e.g. charset[538 % 62] => charset[42]) and add it to the output string.
  2. Set \$value\$ to the quotient of \$\frac{value}{base}\$ (e.g. Math.floor(538 / 62) => 8).
  3. If value is bigger than zero, go to step 1. Otherwise, return the output.

In code:

var output = "";
do {
  output = charset[value % base] + output;
  value = (value / base) | 0; // bitwise floor trick
} while(value > 0);
return output;

Putting it all together, I get this:

// define our base62 function (using an IIFE)
var toBase62 = (function () {
  var charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",
      base = charset.length; // 62, natch

  return function (value) {
    // TODO: It'd be nice to guard against negative values here (see comments)
    var string = "";
    do {
      string = charset[value % base] + string;
      value = (value / base) | 0;
    } while(value > 0);
    return string;
  }
}());

// loop for a long, long time
for(var i = 0, l = Math.pow(62, 5) ; i < l ; i++) {
  console.log( toBase62(i) );
}

Note that it takes forever to print all the 916,132,832 values from 0 up to \$62^5\$. JS ain't that fast. I haven't explored optimization, so for testing, I'd advice using (much) fewer iterations.

\$\endgroup\$
4
  • \$\begingroup\$ To guard against negatives, you could swap out the do...while fo a while loop with the same condition and return string || "0"; since primitive empty string is falsy. \$\endgroup\$
    – cbojar
    Commented May 25, 2014 at 16:13
  • \$\begingroup\$ @cbojar Won't work, I'm afraid. The string will actually be "undefined" - not an empty string - if the input is negative. So you would have to check for negative values before entering the loop. \$\endgroup\$
    – Flambino
    Commented May 25, 2014 at 22:02
  • \$\begingroup\$ No it would not, as changing the do...while to a while loop would implicitly check at the top and bypass the loop completely. \$\endgroup\$
    – cbojar
    Commented May 26, 2014 at 1:18
  • \$\begingroup\$ @cbojar Sorry, misread your first comment. You're right \$\endgroup\$
    – Flambino
    Commented May 26, 2014 at 11:37
2
\$\begingroup\$

I would store the numeric value of each digit in an array, increment the array and then build a string, rather than trying to increment the string directly.

var charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",
    digits = [0, 0, 0, 0, 0],
    max = charset.length - 1, 
    length = digits.length, 
    i = length, 
    output = '0';

while(true) {
    console.log(output);
    while (digits[--i] == max) digits[i] = 0;
    if (i < 0) break;
    digits[i]++;
    for (output = '', i = 0; i < length; i++) {
        if (output || digits[i]) output += charset[digits[i]];
    }
}

Instead of rebuilding the output string from scratch each time we can also use substr and replace only the parts that have changed.

var charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",
    digits = [0, 0, 0, 0, 0],
    max = charset.length - 1, 
    end = digits.length - 1, 
    output = '0', 
    zeroes, i;

while(true) {
    console.log(output);
    for (i = end, zeroes = ''; digits[i] == max; i--) {
        digits[i] = 0;
        zeroes += '0';
    }
    if (i < 0) break;
    digits[i]++;
    output = output.substr(0, output.length - zeroes.length - 1) + charset[digits[i]] 
        + zeroes;
}

These will both still take an extremely long time.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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