Coderbyte Solution: Pattern Chaser

Update: My solution is featured on the Coderbyte blog. Go check it out and pay the lovely folks over there a visit.

A sequence of events: I write a solution for Pattern Chaser. I attend Hack Reactor and become a much better coder. Coderbyte asks me to write a solution post for their blog. I look at my code and weep for its complexity. I write a better solution for Pattern Chaser.

Here you can find the Better Pattern Chaser, but I have included my original solution at the bottom that you may learn from my mistakes.

The better solution

The most interesting thing to note here is the use of regular expressions. There are ways of solving this without them, but the gain in readability they provide here is tremendous.

We are also relying on a little trick with the match method. It returns an array of all (non-overlapping) strings that match the RegExp, and we can use the length of that array to determine whether something is a pattern.

The most important optimization from my original solution is that we are working through our possible patterns from longest to shortest and front to back, which means that the first pattern we find is exactly the one we want. We can simply return out of the function without worrying about any further iterations.

function PatternChaser(str) {

  // Best practice: define our variables up front
  var l, i, pattern, count;

  // For each possible pattern length, starting at the max
  // and counting down to 2, the minimum possible length
  for (l = Math.floor(str.length / 2); l >= 2; l--) {

    // Iterate through each starting position that
    // won't put us over the end, given the current max
    for (i = 0; i < str.length - l; i++) {

      // Capture a possible pattern as a string
      pattern = str.substr(i, l);

      // Create a new regular expression consisting of the
      // possible pattern, and see how many times it occurs
      count = str.match(new RegExp(pattern,'g')).length;

      // If the string occurs more than once, it is a pattern
      // and we return a properly formatted success string
      if (count > 1) return 'yes ' + pattern;
    }
  }

  // If we went all the way through our iterations and no
  // pattern was found, return the failure string
  return 'no null';
}

The original solution

function PatternChaser(str) { 

  var patterns = [];

  for (var i = 2; i < Math.floor(str.length / 2); i++) {
    for (var j = 0; j < str.length - i; j++) {
      var pattern = str.substr(j, i);
      var count = str.match(new RegExp(pattern,'g')).length;
      if (count > 1) patterns.push(pattern);
    };
  };

  patterns = patterns.sort(function(a, b){
    return b.length - a.length;
  });

  return (patterns.length > 0) ? "yes " + patterns[0] : "no null";
}

It's not a bad first go. It's easy to read and makes use of quite a few Javascript features: floor, substr, match, push, RegExp and ternary expressions. It's showy, and these are all useful to things know.

The problem is, by going through and collecting all the patterns before returning, we are pretty much guaranteeing the worst case time complexity in every case, and then tossing a sort in for good measure.