4
\$\begingroup\$

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('');
}
\$\endgroup\$
1
\$\begingroup\$

That is an O(L2) 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.

\$\endgroup\$
1
\$\begingroup\$

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);

\$\endgroup\$
  • \$\begingroup\$ Very Nice! I definitely learned a lot from your answer. If this algorithm was to be used in a project or something I would certainly be doing like this! Thanks! \$\endgroup\$ – Abensur Sep 20 '16 at 3:53
0
\$\begingroup\$

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();
        })
    });
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.