Code Challenge: Change Dispenser

I recently encountered a brain teaser that asked to take an amount of change and return the equivalent in dollars and coins.

Here's the five-minute solution I first came up with.

function makeChange (money) {
    var i, num,
        output = [],
        coins  = [
            [100, "dollar",  "dollars" ],
            [25,  "quarter", "quarters"],
            [10,  "dime",    "dimes"   ],
            [5,   "nickel",  "nickels" ],
            [1,   "penny",   "pennies" ]
        ];
    money = money * 100; // avoid float precision issues
    for (i = 0; i < coins.length; i++) {
        num = Math.floor(money / coins[i][0]);
        money -= num * coins[i][0];
        if (num) {
            output.push(num + " " + coins[i][num > 1 ? 2 : 1]);
        }
    }
    return output.join(", ");
}

makeChange(0.37); // "1 quarter, 1 dime, 2 pennies"

I feel like I'm missing something, though. How would you improve this code to make it shorter, faster, or otherwise better?

Regex Day Contest

A few months ago Ben Nadel (a regex fan and prominent ColdFusion blogger) asked me if I was interested in promoting his idea for a "National Regular Expression Day," where he'd give away some shirts and books and basically just have some fun with regex evangelism. Well, Ben finally kicked if off, assigning the honor to June 1st, 2008. Make sure to check out his blog post, because by simply posting a comment noting your preferred item from his list before June 2nd, you're entered to win it.

I'm all for regex evangelism, so I figured I'd get in on the action with my own regex contest where you can win the best commercial regex products I know of, worth up to $150! The rules are a little different here though. For one thing, you've got more time to enter — I'll keep this open until the end of Friday, June 13. Second, this isn't a lottery. The rules are still pretty simple, though.

  • Write (or link to) some kind of creative regex content in a comment on this blog post.
  • It has to be something new, specifically for this contest.
  • Enter by unlucky Friday, June 13.
  • When submitting your entry, make sure to include an email address where I can reach you in the email field (it won't be visible to others, and I'll only use it to contact you about this contest).
  • You can submit multiple entries, but each will be judged on its own and one person cannot win more than one award.
  • I get to be the judge and jury.

As for what kind of content is eligible, well, pretty much anything as long as it's regex related. You can write a regex joke (preferably not ending with the punchline "now they have two problems"), post a regex article somewhere, create a regex comic strip, share your favorite regex you've written, design a regex superhero, create a regex game, tell a story about how regexes saved the day, link to a blog post you've written about Regular Expression Day, or whatever you can come up with. Go nuts.

Here's what the winners can choose from. If you win first or second place but none of the prizes in that tier interest you, you can pick two items from a lower level.

Good luck, and I hope you have fun with this. smile (Once again, make sure to check out Ben's post that started this.)

JavaScript Roman Numeral Converter

While looking for something quick to do during a brief internet outage, I wrote some code to convert to and from Roman numerals. Once things were back up I searched for equivalent code, but only found stuff that was multiple pages long, limited the range of what it could convert, or both. I figured I might as well share what I came up with:

function romanize (num) {
  if (!+num) return false;
  var digits = String(+num).split('');
  var key = ['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM',
             '','X','XX','XXX','XL','L','LX','LXX','LXXX','XC',
             '','I','II','III','IV','V','VI','VII','VIII','IX'];
  var roman = '', i = 3;
  while (i--) roman = (key[+digits.pop() + (i * 10)] || '') + roman;
  return Array(+digits.join('') + 1).join('M') + roman;
}

function deromanize (str) {
  var str = str.toUpperCase();
  var validator = /^M*(?:D?C{0,3}|C[MD])(?:L?X{0,3}|X[CL])(?:V?I{0,3}|I[XV])$/;
  var token = /[MDLV]|C[MD]?|X[CL]?|I[XV]?/g;
  var key = {M:1000,CM:900,D:500,CD:400,C:100,XC:90,L:50,XL:40,X:10,IX:9,V:5,IV:4,I:1};
  var num = 0, m;
  if (!(str && validator.test(str))) return false;
  while (m = token.exec(str)) num += key[m[0]];
  return num;
}

How would you rewrite this code? Can you create a shorter version?

JavaScript String Multiplication Performance Exploration

Since JavaScript concatenates strings with the + operator, it would be nifty if it would also let you multiply strings using e.g. str * 10 (as can be done in Python, at least). Since you can't do that, and no native string multiplication method is provided, I recently explored a few ways to pull it off…

A naive approach to writing a string multiplier function goes something like this:

function mul0 (str, num) {
	if (!num) return "";
	var newStr = str;
	while (--num) newStr += str;
	return newStr;
}

As many JavaScripters are aware, that isn't the best approach since string concatenation can be quite slow in Internet Explorer. And while IE tends to get a bad rap for this (fortunately, the IE team is fixing the problem in the next version of their browser), Firefox isn't exactly blazing fast at string concatenation either. Due to the performance issues, the typical string multiplication approach is to build an array and join it. Here's a nice, short way to do that:

function mul1 (str, num) {
	return num ? Array(num + 1).join(str) : "";
}

Note that the falsy num handling is probably not warranted in this case since the function would handle value 0 correctly without it. It's done anyway to keep functionality equivalent across the variations.

Unfortunately, mul1 can still be pretty slow in Firefox 2 when multiplying large strings many times. It might be unnoticeable with small strings and repetition numbers, but the completion time goes up at a super-linear rate as the numbers increase. In search of a faster solution, I tried using a regex to keep down the size of the string being worked with:

var mul2 = function () {
	function mul (str, num) {
		return Array(num + 1).join(str);
	}
	return function (str, num) {
		return num ? str.replace(/^/, mul("$'", num - 1)) : "";
	};
}();

The above multiplies the two-character string "$'" num - 1 times, then uses that as the replacement for a regex which just matches the start of the string ($' returns the text to the right of the match). How does that perform? It delivers in Firefox 2 on my Windows Vista system, with numbers like 95ms vs. 29800ms (mul1) when using a 2700x2700 string length/multiplier. However, based on my testing, that sort of speed gain appears to be limited to Firefox, and in Safari 3 beta mul2 is considerably slower that the alternative versions.

Finally, I tried creating a version which multiplied the string at an exponential rate:

function mul3 (str, num) {
	if (!num) return "";
	var	orig = str,
		soFar = [str],
		added = 1,
		left, i;
	while (added < num) {
		left = num - added;
		str = orig;
		for (i = 2; i < left; i *= 2) {
			str += str;
		}
		soFar.push(str);
		added += (i / 2);
	}
	return soFar.join("");
}

Although that might be more code than you're willing to dedicate to a string multiplication method, it's the fastest of the above versions on average cross-browser. I've also tried a few variations using from zero to two arrays and various array methods (push, concat, etc.), but the above seems to be the fastest on average across the big four browsers.

Make sure to try the tests for yourself, and let me know your thoughts and how you would improve the code.


Edit: Kris Kowal contributed mul4 (shown below, and added to the test page). It uses binary interpolation, and in Kris's words "it takes advantage of a fun bitwise identity: (1 << n) == Math.pow(2, n)". On my system it's significantly faster than mul3 in Firefox, but a little slower than mul3 in IE, Safari, and Opera. Due to its high speed and lighter weight, this looks like the one to beat. Try the test page in several browsers and see what you think.

function mul4 (str, num) {
	var acc = [];
	for (var i = 0; (1 << i) <= num; i++) {
		if ((1 << i) & num)
			acc.push(str);
		str += str;
	}
	return acc.join("");
}

Edit 2: LiuCougar of the Dojo development team posted a follow-up which includes several additional variations, and David Andersson emailed me an additional four variations including this one:

function mul8 (str, num) {
	var	i = Math.ceil(Math.log(num) / Math.LN2),
		res = str;
	do {
		res += res;
	} while (0 < --i);
	return res.slice(0, str.length * num);
}

I should clarify however that this is mostly just academic discussion, since repeating the kinds of strings in the test page as many times as it does is a pretty crazy idea. Still, it's fun to experiment. smile


Edit 3: All the variations posted or emailed in response to this post can be seen at stevenlevithan.com/demo/mul/all.js. For the sake of consistency I've made a few minor adjustments to some of the functions such as whitespace tweaks and renaming the input arguments to str and num.