countPermutations.js

gistfile1.txt

function countChars(word) {
  var counts = {};

  for (var i = 0; i < word.length; i++) {
    var letter = word[i];

    if (letter in counts && counts.hasOwnProperty(letter)) {
      counts[letter]++;
    } else {
      counts[letter] = 1;
    }
  }

  return counts;
}


function countPermutations(needle, haystack) {
  if (needle.length > haystack.length) {
    return 0;
  }

  var windowSize = needle.length;
  var charCountState = countChars(needle);
  var lettersRemaining = needle.length;
  var permutations = 0;

  for (var i = 0; i < haystack.length; i++) {
    var char = haystack[i];

    if (char in charCountState) {
      charCountState[char]--;

      if (charCountState[char] >= 0) {
        lettersRemaining--;
      }
    }

    if (i >= windowSize) {
      var charDropped = haystack[i - windowSize];

      if (charDropped in charCountState) {
        charCountState[charDropped]++;

        if (charCountState[charDropped] > 0) {
          lettersRemaining++;
        }
      }
    }

    if (lettersRemaining === 0) {
      permutations++;
    }
  }

  return permutations;
}

var ALPHABET = 'abcdefghijklmnopqrstuvwxyz';

function randomCharacter() {
  return ALPHABET[Math.floor(Math.random() * 26)];
}

function randomWord(length) {
  var word = "";

  for (var i = 0; i < length; i++) {
    word += randomCharacter();
  }

  return word;
}

function sortWord(word) {
  return word.split('').sort().join('');
}

function bruteForceCountPermutations(needle, haystack) {
  var windowSize = needle.length;
  var sortedNeedle = sortWord(needle);
  var lastIndex = haystack.length - windowSize + 1;
  var permutations = 0;

  for (var i = 0; i < lastIndex; i++) {
    if (sortWord(haystack.substr(i, windowSize)) === sortedNeedle) {
      permutations++;
    }
  }

  return permutations;
}

function runTests(needleSize, haystackSize, numberOfTests) {
  var correctCount = 0;
  var failedCount = 0;

  for (var i = 0; i < numberOfTests; i++) {
    var needle = randomWord(needleSize);
    var haystack = randomWord(haystackSize);

    var quickResult = countPermutations(needle, haystack);
    var slowResult = bruteForceCountPermutations(needle, haystack);

    if (quickResult === slowResult) {
      correctCount++;
    } else {
      console.log("countPermutations(" + needle + ", " + haystack +") => " + quickResult + " but expected " + slowResult);
      failedCount++;
    }
  }

  if (failedCount) {
    console.log(failedCount + "/" + numberOfTests + " failed.");
  } else {
    console.log(numberOfTests + " passed.");
  }
}

// e.g. runTests(5, 50, 10000);