Replacing a string until it matches a certain length

Question

I'm trying to make an SMS Shortner for a kata at Codewars:

Your task is to shorten the message to 160 characters, starting from end, by replacing spaces with camelCase, as much as necessary.

I've tried with a while loop and although the logic is correct, it's taking too long to process my tests. How can I optmize this and what parts are taking longer than it could?

const shortener = (message) => {
  let r = message.split('').reverse().join('');
  while (r.length > 160) {
    r = r.replace(/([^\s]\s)/, (m,s) => s.trim().toUpperCase());
  }
  return r.split('').reverse().join('');
}

Answer 1

That is an O(L²) algorithm: each replace involves copying the entire string. A better strategy would be to call replace just once. First, figure out how many spaces need to be eliminated. Then, use a callback that conditionally modifies its match based on a count.

It should be possible to do it that way without reversing the string twice.

Answer 2

I would tackle this quite differently. Instead of creating a bespoke function, I would tend to functionalise the process, giving me reusable functions, and a better level of readability and maintainability. If performance became a problem then I would look at reworking it.

function tokenise(str, delimiter) {
  return str.split(delimiter);
}

function countCharacter(str, character) {
  var first = character.charAt(0);
  return first === '' ? Infinity : Math.min(Math.max(tokenise(str, first).length - 1, 0), Infinity);
}

function splitAtNth(str, nth, delimiter) {
  const tokens = tokenise(str, delimiter);
  return [tokens.slice(0, nth).join(delimiter), tokens.slice(nth).join(delimiter)];
}

function chunk(arr, size) {
  const chunks = [];
  const length = arr.length;
  let index = 0;
  while (index < length) {
    chunks.push(arr.slice(index, index + size));
    index += size;
  }
  return chunks;
}

function pairs(arr) {
  return chunk(arr, 2);
}

function isEven(num) {
  return num % 2 === 0;
}

function camelCase(a, b) {
  return `${a}${b.charAt(0).toUpperCase()}${b.slice(1)}`;
}

function countSpaces(str) {
  return countCharacter(str, ' ');
}

function spacesSpare(sms) {
  const spaces = (sms.length - 160) - countSpaces(sms);
  return spaces < 0 ? Math.abs(spaces) : 0;
}

function splitAtNthSpace(str, nth) {
  return splitAtNth(str, nth, ' ');
}

function stringToEvenPadPairs(str) {
  const tokens = tokenise(str, ' ');
  if (!isEven(tokens.length)) {
    tokens.push('');
  }
  return pairs(tokens);
}

function camelAcumulate(acc, pair) {
  return camelCase(acc, camelCase(...pair));
}

function shortenSMS(sms) {
  const atNth = spacesSpare(sms);
  if (atNth) {
    const parts = splitAtNthSpace(sms, atNth);
    return stringToEvenPadPairs(parts[1]).reduce(camelAcumulate, parts[0]);
  }
  return stringToEvenPadPairs(sms).reduce(camelAcumulate, '');
}

const testSMS1 = 'Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';
const testSMS2 = '(octets * Eight bits / octet = 1120 bits). Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';
const testSMS3 = '(blah blah blah octets * Eight bits / octet = 1120 bits). Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';

console.log(shortenSMS(testSMS1));
console.log(shortenSMS(testSMS2));
console.log(shortenSMS(testSMS3));

Your code with the same strings

var shortener = function(sms) {
  let n = sms.match(/\s/g) ? sms.match(/\s/g).length : 0;
  n = sms.length <= 160 ? 0 : (sms.length - 160) > n ? n : sms.length - 160;
  const re = new RegExp("([^ ][ ][^ ]*){" + n + "}$");
  return !n ? sms : sms.replace(re, (ext) => {
    return ext.replace(/ [^ ]/g, (m, p1) => {
      return m.trim().toUpperCase();
    })
  });
};

const testSMS1 = 'Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';
const testSMS2 = '(octets * Eight bits / octet = 1120 bits). Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';
const testSMS3 = '(blah blah blah octets * Eight bits / octet = 1120 bits). Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';

console.log(shortener(testSMS1));
console.log(shortener(testSMS2));
console.log(shortener(testSMS3));

And a performance test of yours and my solution.

function test(fn, str1, str2, str3) {
  let count = 100000;
  const Ts = performance.now();
  while (count) {
    fn(str1);
    fn(str2);
    fn(str3);
    count -= 1;
  }
  const Te = performance.now();
  console.log(`name: ${fn.name} time: ${Math.ceil(Te - Ts)}`);
}

function tokenise(str, delimiter) {
  return str.split(delimiter);
}

function countCharacter(str, character) {
  var first = character.charAt(0);
  return first === '' ? Infinity : Math.min(Math.max(tokenise(str, first).length - 1, 0), Infinity);
}

function splitAtNth(str, nth, delimiter) {
  const tokens = tokenise(str, delimiter);
  return [tokens.slice(0, nth).join(delimiter), tokens.slice(nth).join(delimiter)];
}

function chunk(arr, size) {
  const chunks = [];
  const length = arr.length;
  let index = 0;
  while (index < length) {
    chunks.push(arr.slice(index, index + size));
    index += size;
  }
  return chunks;
}

function pairs(arr) {
  return chunk(arr, 2);
}

function isEven(num) {
  return num % 2 === 0;
}

function camelCase(a, b) {
  return `${a}${b.charAt(0).toUpperCase()}${b.slice(1)}`;
}

function countSpaces(str) {
  return countCharacter(str, ' ');
}

function spacesSpare(sms) {
  const spaces = (sms.length - 160) - countSpaces(sms);
  return spaces < 0 ? Math.abs(spaces) : 0;
}

function splitAtNthSpace(str, nth) {
  return splitAtNth(str, nth, ' ');
}

function stringToEvenPadPairs(str) {
  const tokens = tokenise(str, ' ');
  if (!isEven(tokens.length)) {
    tokens.push('');
  }
  return pairs(tokens);
}

function camelAcumulate(acc, pair) {
  return camelCase(acc, camelCase(...pair));
}

function shortenSMS(sms) {
  const atNth = spacesSpare(sms);
  if (atNth) {
    const parts = splitAtNthSpace(sms, atNth);
    return stringToEvenPadPairs(parts[1]).reduce(camelAcumulate, parts[0]);
  }
  return stringToEvenPadPairs(sms).reduce(camelAcumulate, '');
}

const testSMS1 = 'Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';
const testSMS2 = '(octets * Eight bits / octet = 1120 bits). Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';
const testSMS3 = '(blah blah blah octets * Eight bits / octet = 1120 bits). Short meSSages can be encoded using a variety of alphabets: the default GSM 7-bit alphabet, the 8-bit data alphabet, and the 16-bit UCS-2 alphabet.';

test(shortenSMS, testSMS1, testSMS2, testSMS3);

var shortener = function(sms) {
  let n = sms.match(/\s/g) ? sms.match(/\s/g).length : 0;
  n = sms.length <= 160 ? 0 : (sms.length - 160) > n ? n : sms.length - 160;
  const re = new RegExp("([^ ][ ][^ ]*){" + n + "}$");
  return !n ? sms : sms.replace(re, (ext) => {
    return ext.replace(/ [^ ]/g, (m, p1) => {
      return m.trim().toUpperCase();
    })
  });
};
test(shortener, testSMS1, testSMS2, testSMS3);

Answer 3

As the answer I accepted suggested, I was able to improve a lot my algorithm. I still wonder If I can do it by calling replace just once.

var shortener = function(sms) {
    let n = sms.match(/\s/g) ? sms.match(/\s/g).length: 0;
    n = sms.length <= 160 ? 0 : (sms.length - 160)  > n ? n : sms.length - 160;
    const re = new RegExp("([^ ][ ][^ ]*){" + n + "}$");
    return !n ? sms : sms.replace(re, (ext) => {
        return ext.replace(/ [^ ]/g, (m, p1) => {
            return m.trim().toUpperCase();
        })
    });
}