8 July 2008

Dustin’s programming problem

Dustin Diaz has a programming problem in JavaScript that I had a look at today. Dmitry said I should publish my solution. Although it’s not very meaningful to me, Dustin’s summary of the problem is this:

Group together all duplicate items that occur anytime beyond twice by wrapping them with a tag, naturally “bookending” them.

Basically, if you have an array with lots of the same items in a row, you want to group together elements 3+ in the sequence of the same item inside a tag. I guess in his actual problem he wants to replace the tag with ellipsis or something, so the list looks like this:

a, b, c, c, d, e, e, …, f, e, f, etc.

Here’s my solution:

var arr = ["a", "b", "c", "c", "d", "e", "e", "e", "e", "e",
  "f", "e", "f", "e", "f", "a", "a", "a", "f", "f", "f"];
var out = [];
for (var i=0, j=0; i<arr.length; i=j, j=i+1) {
  while (arr[i] == arr[j]) j++;
  if (j - i > 2)
    out.push(arr.slice(i, i+2).join(" ") + 
      " <span>" + arr.slice(i+2, j).join(" ") + "<span>");
  else
    out.push(arr.slice(i, j).join(" "));
}
console.log(out.join(" "));

I found it counter-productive to use a ‘foreach’ style loop, because modifying the loop index while you go through makes the algorithm much simpler.