Codewars Make Palindrome (v11)

Revision 11 of this benchmark created on October 23, 2014

Setup

var randomstring = '';
    while(randomstring.length < 1000){
      randomstring += (Math.random()+1).toString(36).substring(2,10);
    }
    
    
    
    function OverZealous(s, reverse){
      var i = 0, p = s;
      while(!OverZealousisPalindrome(p)) {
        p = s + OverZealousrev(s.slice(0,i));
        i++;
      }
      if(!reverse) {
        s = OverZealous(OverZealousrev(s), true);
        if(s.length < p.length) p = s;
      }
      return p;
    }
    
    function OverZealousisPalindrome(s) {
      return s == OverZealousrev(s);
    }
    
    function OverZealousrev(s) {
      return s.split('').reverse().join('');
    }
    
    
    String.prototype.Abbereverse = function() {
      return this.split('').reverse().join('');
    }
    String.prototype.AbbeisPalindrome = function() {
      return this == this.Abbereverse();
    }
    
    function Abbe(text){
      var shortestSuffixPalindrome = function(s) {
        var i = 0;
        while(!s.substring(i).AbbeisPalindrome()) i++;
        var prefix = s.substring(0,i)
        var palindrome = s.substring(i)
        return prefix + palindrome + prefix.Abbereverse();
      }
      var repeatSuffix = shortestSuffixPalindrome(text);
      var repeatPrefix = shortestSuffixPalindrome(text.Abbereverse());
      return repeatSuffix.length <= repeatPrefix.length ? repeatSuffix : repeatPrefix;
    }
    
    
    
    String.prototype.hencethusreverse = function () {
      var result = '', i = this.length;
      while (i--) result += this[i];
      return result;
    };
    
    String.prototype.hencethusisPalindrome = function () {
      return this == this.hencethusreverse();
    };
    
    var hencethus= function (text) {
      if (text.hencethusisPalindrome()) return text;
      
      var maybe, maybeNot;
      
      for (var i = 1, len = text.length; i <= len; i++) {
        maybe = text + text.slice(0, i).hencethusreverse();
        if (maybe.hencethusisPalindrome()) break;
      }
      
      for (var i = text.length - 1; i > 0; i--) {
        maybeNot = text.slice(i).hencethusreverse() + text;
        if (maybeNot.length >= maybe.length) return maybe;
        if (maybeNot.hencethusisPalindrome()) return maybeNot;
      }
    };
    
    
    
    
    function constablebrew(string){
      var txtBuildBackEnd = string.split(''),
      txtBuildFrontEnd = string.split(''),
      txtBuildBackEndReversed = string.split('').reverse(),
      txtBuildFrontEndReversed = string.split('').reverse(),
      backEndIsPalindrome = isPalindrome(txtBuildBackEnd, txtBuildBackEndReversed),
      frontEndIsPalindrome = isPalindrome(txtBuildFrontEnd, txtBuildFrontEndReversed),
      pos = 0,
      chr = '',
      loopLimit = string.length*2;
      
      function isPalindrome(a, b){
        return a.every(function(e,i){ return e === b[i]; });
      }
      
      while(!frontEndIsPalindrome
        && !backEndIsPalindrome
        && loopLimit--){
            
        // Adding characters from the start of the string to the end
        chr = txtBuildBackEnd[pos];
        txtBuildBackEnd.splice(txtBuildBackEnd.length - pos, 0, chr);
        txtBuildBackEndReversed.splice(pos, 0, chr);
        backEndIsPalindrome = isPalindrome(txtBuildBackEnd, txtBuildBackEndReversed);
        
        // Adding characters from the end of the string to the front
        chr = txtBuildFrontEnd[txtBuildFrontEnd.length - pos - 1];
        txtBuildFrontEnd.splice(pos, 0, chr);
        txtBuildFrontEndReversed.splice(txtBuildFrontEndReversed.length - pos, 0, chr);
        frontEndIsPalindrome = isPalindrome(txtBuildFrontEnd, txtBuildFrontEndReversed);
        
        ++pos;
      }
      
      return backEndIsPalindrome?txtBuildBackEnd.join(''):txtBuildFrontEnd.join('');
    }
    
    function SagePtr(text){
      function check(s){
        return s.split('').reverse().join('') == s;
      }
      if(check(text)) return text;
      var minhead, minheadi;
      //check head
      for(var i = 1; i <= text.length; i++){
        var s = text + text.substr(0,i).split('').reverse().join('');
        if(check(s)){
          minhead = s;
          minheadi = i;
          break;
        }
      }
      //check tail
      for(var i = 1; i < minheadi; i++){
        var s = text.substr(-i).split('').reverse().join('') + text;
        if(check(s)) return s;
      }
      return minhead;
    }
    
    
    function dulaccc_isPalindrome(chars) {
      return chars.join('') === chars.slice(0).reverse().join('');
    }
    
    function dulaccc(text) {
      var palinAsc = text.split(''),
          palinDesc = text.split(''),
          index = 0;
      
      while (!dulaccc_isPalindrome(palinAsc) && !dulaccc_isPalindrome(palinDesc)) {
        palinAsc.splice(palinAsc.length - index, 0, text[index]);
        palinDesc.splice(index, 0, text[text.length - 1 - index]);
        index++; 
      }
      
      return [palinAsc, palinDesc].filter(function(p) {
        return dulaccc_isPalindrome(p);
      })[0].join('');
    }
    
    
    
    function mweiss(text){
      var reversed = text.split("").reverse().join(""), palindrome = text;
      
      var isPalindrome = function(s) {
        return palindrome === palindrome.split("").reverse().join("");
      }
      
      for (var i = reversed.length; i > 0; i -= 1) {
        
        palindrome = text + reversed.substring(i);
        if (isPalindrome(palindrome)) {
          return palindrome;
        }
        
        palindrome = reversed.substring(0, reversed.length - i) + text;
        if (isPalindrome(palindrome)) {
          return palindrome;
        }
      }
      
      return palindrome;
    }
    
    function nivStartPalindrome(text) { 
      //store the maximum palindrome size
      var max_index = 1 ;
      //palindrome decreasing counters
      var candidates = [[],[0,1]] ;
      //scan the word letter by letter
      for(var i = 1; i < text.length; ++i) {
        //counters are read from this one
        var c_index = i%2 ;
        //counters kept are put in this one
        var next_c_index = 1-c_index ;
        //reset the set of counters written to
        candidates[next_c_index] = [] ;
        //scan the decreasing counters
        for(var j = 0; j < candidates[c_index].length; ++j) {
          if(text[i] === text[candidates[c_index][j]]) {
            //the counter remains valid
            if(candidates[c_index][j] === 0) {
              //a counter reaches 0, a longer palindrome is found
              max_index = i+1 ;
            } else {
              //the counter is not finished, keep it
              candidates[next_c_index].push(candidates[c_index][j]-1) ;
            }
          }
        }
        //add new candidates from position i
        candidates[next_c_index].push(i) ;
        candidates[next_c_index].push(i+1) ;    
      }
      return max_index ;
    }
    
    function nivoliev(text){
      //biggest prefixing palindrome size
      var start_pal = nivStartPalindrome(text) ;
      //biggest suffixing palindrome size
      var end_pal = nivStartPalindrome(text.split('').reverse().join('')) ;
      //build the completion from the letters not in the palindrome
      return end_pal >= start_pal ? 
        text + text.slice(0,text.length-end_pal).split('').reverse().join('') :
        text.slice(start_pal).split('').reverse().join('') + text ;
    }
    
    function laoris(text) {
      function basicAlgorithm(text, reversed) {
        // Check if the reversed string matches the end of the input text
        // If it doesn't, remove the last character of the reversed string and try again
        // This continues until it matches or the reversed string is only one character
        while (text.slice(text.length - reversed.length) != reversed)
          reversed = reversed.slice(0, -1);
        // Now build the palindrome by copying from input text, starting from the end
        // Skip the number of characters in the matching reversed string
        var result = text;
        for (var i = text.length - reversed.length; i--; result += text[i]);
        return result;
      }
      function reverseString(text) {
        return text.split('').reverse().join('');
      }
      // Make a palindrome starting at the end of the string
      // Then try again with a reversed version to see if it's shorter
      // Return the shorter one (forwards version if they're the same length)
      var reversed = reverseString(text);
      var forwards = basicAlgorithm(text, reversed);
      var backwards = reverseString(basicAlgorithm(reversed, text));
      return forwards.length <= backwards.length ? forwards : backwards;
    }
    
    String.prototype.clone53421reverse = function () {
      return this.split("").reverse().join("");
    };
    function clone53421isPalindrome(text) {
      for (var i = 0; i < text.length / 2 - .5; ++ i) {
        if (text.charAt(i) != text.charAt(text.length - 1 - i)) return false;
      }
      return true;
    };
    function clone53421(text) {
      if (clone53421isPalindrome(text)) return text;
      
      // see how many characters at the string's beginning and end are palindromes
      // since a 1-character string is always a palindrome, at least that much is
      for (var i = text.length; i > 0; -- i) {
        if (clone53421isPalindrome(text.substring(text.length - i))) {
          return text + text.clone53421reverse().substring(i);
        }
        if (clone53421isPalindrome(text.substring(0, i))) {
          return text.substring(i).clone53421reverse() + text;
        }
      }
    }

Test runner

OverZealous(randomstring);

Abbe(randomstring);

hencethus(randomstring);

constablebrew(randomstring);

SagePtr(randomstring);

dulaccc(randomstring);

mweiss(randomstring);

nivoliev(randomstring);

laoris(randomstring);

clone53421(randomstring);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 11: published on October 23, 2014