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?

Multiple String Replacement Sugar

How many times have you needed to run multiple replacement operations on the same string? It's not too bad, but can get a bit tedious if you write code like this a lot.

str = str.
	replace( /&(?!#?\w+;)/g , '&amp;'    ).
	replace( /"([^"]*)"/g   , '“$1”'     ).
	replace( /</g           , '&lt;'     ).
	replace( />/g           , '&gt;'     ).
	replace( /…/g           , '&hellip;' ).
	replace( /“/g           , '&ldquo;'  ).
	replace( /”/g           , '&rdquo;'  ).
	replace( /‘/g           , '&lsquo;'  ).
	replace( /’/g           , '&rsquo;'  ).
	replace( /—/g           , '&mdash;'  ).
	replace( /–/g           , '&ndash;'  );

A common trick to shorten such code is to look up replacement values using an object as a hash table. Here's a simple implementation of this.

var hash = {
	'<' : '&lt;'    ,
	'>' : '&gt;'    ,
	'…' : '&hellip;',
	'“' : '&ldquo;' ,
	'”' : '&rdquo;' ,
	'‘' : '&lsquo;' ,
	'’' : '&rsquo;' ,
	'—' : '&mdash;' ,
	'–' : '&ndash;'
};

str = str.
	replace( /&(?!#?\w+;)/g , '&amp;' ).
	replace( /"([^"]*)"/g   , '“$1”'  ).
	replace( /[<>…“”‘’—–]/g , function ( $0 ) {
		return hash[ $0 ];
	});

However, this approach has some limitations.

  • Search patterns are repeated in the hash table and the regular expression character class.
  • Both the search and replacement are limited to plain text. That's why the first and second replacements had to remain separate in the above code. The first replacement used a regex search pattern, and the second used a backreference in the replacement text.
  • Replacements don't cascade. This is another reason why the second replacement operation had to remain separate. I want text like "this" to first be replaced with “this”, and eventually end up as &ldquo;this&rdquo;.
  • It doesn't work in Safari 2.x and other old browsers that don't support using functions to generate replacement text.

With a few lines of String.prototype sugar, you can deal with all of these issues.

String.prototype.multiReplace = function ( hash ) {
	var str = this, key;
	for ( key in hash ) {
		str = str.replace( new RegExp( key, 'g' ), hash[ key ] );
	}
	return str;
};

Now you can use code like this:

str = str.multiReplace({
	'&(?!#?\\w+;)' : '&amp;'   ,
	'"([^"]*)"'    : '“$1”'    ,
	'<'            : '&lt;'    ,
	'>'            : '&gt;'    ,
	'…'            : '&hellip;',
	'“'            : '&ldquo;' ,
	'”'            : '&rdquo;' ,
	'‘'            : '&lsquo;' ,
	'’'            : '&rsquo;' ,
	'—'            : '&mdash;' ,
	'–'            : '&ndash;'
});

If you care about the order of replacements, you should be aware that the current JavaScript specification does not require a particular enumeration order when looping over object properties with for..in. However, recent versions of the big four browsers (IE, Firefox, Safari, Opera) all use insertion order, which allows this to work as described (from top to bottom). ECMAScript 4 proposals indicate that the insertion-order convention will be formally codified in that standard.

If you need to worry about rogue properties that show up when people mess with Object.prototype, you can update the code as follows:

String.prototype.multiReplace = function ( hash ) {
	var str = this, key;
	for ( key in hash ) {
		if ( Object.prototype.hasOwnProperty.call( hash, key ) ) {
			str = str.replace( new RegExp( key, 'g' ), hash[ key ] );
		}
	}
	return str;
};

Calling the hasOwnProperty method on Object.prototype rather than on the hash object directly allows this method to work even when you're searching for the string "hasOwnProperty".

Lemme know if you think this is useful.

Remove Nested Patterns with One Line of JavaScript

Here's a neat little trick I came up with for removing nested patterns from a string.

var str = "abc<1<2<>3>4>def";

while (str != (str = str.replace(/<[^<>]*>/g, "")));

// str -> "abcdef"

Notice that the regex in this one-liner doesn't try to deal with nested patterns at all. The while loop's condition replaces instances of <…> (where angled brackets are not allowed in the inner pattern) with an empty string. This repeats from the inside out, until the regex no longer matches. At that point, the result of the replacement is the same as the subject string, and the loop ends.

You can use a similar approach to grab nested patterns rather than delete them, as shown below.

[Edit (6/6/2008): The following code does not correctly handle input like "((a)(b))". If you browse tag recursion on this blog you'll find a variety of other approaches for matching nested constructs that actually work correctly.]

var str = "abc(d(e())f)(gh)ijk()",
    re = /\([^()]*\)/,
    output = [],
    match, parts, last;

while (match = re.exec(str)) {
    parts = match[0].split("\uFFFF");
    if (parts.length < 2) {
        last = output.push(match[0]) - 1;
    } else {
        output[last] = parts[0] + output[last] + parts[1];
    }
    str = str.replace(re, "\uFFFF");
}

// output -> ["(d(e())f)", "(gh)", "()"]

Since once again we're working from the inside out, reassembling each complete match requires us to mark the position at which the previous deepest-level match was removed. I've used the Unicode escape sequence \uFFFF to mark such positions, because that's a permanently-unassigned code point.

Note that using a negated character class like [^()] to match the inner pattern as shown in the examples here only works correctly if you're using single-character delimiters like (…) or <…>. If you want to match/remove nested patterns that use multi-character delimiters, you can use a regex like /<<(?:(?!<<|>>)[\S\s])*>>/. Just change both instances of << to your left delimiter, and >> to your right delimiter.

Test Your XRegExps with JRX

Cüneyt Yılmaz's JRX is a cool JavaScript regex tester inspired by the RX tool of Komodo IDE. Cüneyt recently added my XRegExp library to his tester, so JRX is now a nice and easy way to test XRegExp's singleline and extended modes, as well as named capture and other XRegExp-provided syntax. Check it out!

As for XRegExp, it has recently been upgraded to v0.5.2, which resolved a corner-case bug involving XRegExp.matchRecursive. See the changelog for details.

I'll take this opportunity to highlight some of my other favorite online regex testers. I've actively looked for these kinds of apps over the years and have seen more than 50 of them. Odds are you'll find something new here.

Edit (2008-06-18): Updated the list with a couple that have come out very recently.

  • RegexPal — My own JavaScript regex tester. It includes real-time regex syntax and match highlighting. Although RegexPal uses XRegExp to provide the singleline option, unlike JRX it uses JavaScript regex syntax without the XRegExp syntax extensions.
  • regex — Simple name, simple interface. Great set of flavor support (JavaScript, Perl, Python, PCRE, POSIX ERE).
  • Regexp Editor — Java regex tester with regex syntax highlighting.
  • RegExr — ActionScript regex tester with regex syntax highlighting.
  • reWork — JavaScript regex workbench.
  • reAnimator — Fun app for visualizing regex FSAs.
  • RegexMate — JavaScript regex console.
  • The REWizard — IE only, but offers regex building tools and an interesting visualization.
  • MyRegexTester — Includes code generation and plain-text explanations (via the YAPE::Regex::Explain Perl module).
  • Regular Expression Analyzer — Real-time regex explanation tree that mostly emulates Java, JavaScript, and Perl flavors. Its regex parsing code is very readable.
  • Nregex — .NET regex tester.
  • Rubular — Ruby regex tester.

Have fun!

XRegExp 0.5 Released!

Update: This version of XRegExp is outdated. See XRegExp.com for the latest, greatest version.

If you haven't seen the prior versions, XRegExp is an MIT-licensed JavaScript library that provides an augmented, cross-browser implementation of regular expressions, including support for additional modifiers and syntax. Several convenience methods and a new, powerful recursive-construct parser that uses regex delimiters are also included.

Here's what you get beyond the standard JavaScript regex features:

  • Added regex syntax:
    • Comprehensive named capture support. (Improved)
    • Comment patterns: (?#…). (New)
  • Added regex modifiers (flags):
    • s (singleline), to make dot match all characters including newlines.
    • x (extended), for free-spacing and comments.
  • Added awesome:
    • Reduced cross-browser inconsistencies. (More)
    • Recursive-construct parser with regex delimiters. (New)
    • An easy way to cache and reuse regex objects. (New)
    • The ability to safely embed literal text in your regex patterns. (New)
    • A method to add modifiers to existing regex objects.
    • Regex call and apply methods, which make generically working with functions and regexes easier. (New)

All of this can be yours for the low, low price of 2.4 KB. smile Version 0.5 also introduces extensive documentation and code examples.

If you're using a previous version, note that there are a few non-backward compatible changes for the sake of strict ECMA-262 Edition 3 compliance and compatibility with upcoming ECMAScript 4 changes.

  • The XRegExp.overrideNative function has been removed, since it is no longer possible to override native constructors in Firefox 3 or ECMAScript 4 (as proposed).
  • Named capture syntax has been changed from (<name>…) to (?<name>…), which is the standard in most regex libraries and under consideration for ES4. Named capture is now always available, and does not require the k modifier.
  • Due to cross-browser compatibility issues, previous versions enforced that a leading, unescaped ] within a character class was treated as a literal character, which is how things work in most regex flavors. XRegExp now follows ECMA-262 Edition 3 on this point. [] is an empty set and never matches (this is enforced in all browsers).

Get it while it's hot! Check out the new XRegExp documentation and source code.