How to calculate fibonacci-sequence for String data set?

Question

I want to calculate Fibonacci sequence for a string data set. I'm writing a normal JavaScript function but I want to write the code using the latest ECMAScript features.

var message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";

function FibonacciSecret(message) {
  var s = '';
  for (var i = 0; i < 10; i++) {
    s += message.replace(/\s+/g, '').substr(getNthValue(i), 1).toUpperCase();
    if (i != 9) {
      s += "-";
    }
  }

  function getNthValue(n) {
    if (n <= 1) {
      return n;
    }
    if (n > 1) {
      return getNthValue(n - 1) + getNthValue(n - 2);
    }
  }
  return s;
}

console.log(FibonacciSecret(message)); // "T-H-H-E-D-V-C-E-M-T"

Answer 1

Memoization

Instead of calculate every time the n number of fibonacci you can simple look it up in a table if you calculated it once. This is called Memoization. You can read more about it in Faster JavaScript Memoization by Addy Osmani.

Your Code

The function getNthValue gets defined every time you call FibonacciSecret. It may be would have a better performance if you would define it outside, but I did't test it. But it would be definitely better to test your code.

Additionally on each iteration you remove whitspaces message.replace(/\s+/g, '') and call toUpperCasebut one call would be enough.

Example

I wrote it recursively because I think the code is easier to read. I pass in String without whitespaces (createSecretString(messageWithoutWhitespace, memory, secret) and save on each recursion a letter in secret. On the last recursion I return the array joined to a string and upper case all letters once. (secret.join('-').toUpperCase())

const message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";
const fibonacciMemory = {}

function fibonacci(x, memory = {}) {
  if (memory[x]) {
    return memory[x]
  }
  if (x < 1) {
    return 0
  }
  if (x <= 2) {
    return 1
  }
  return memory[x] = fibonacci(x - 1, memory) + fibonacci(x - 2, memory);
}

function createSecretString(message, memory, secret) {
  const length = secret.length - 1
  return length < 10 
    ? createSecretString(message, memory, secret.concat(message.substr(fibonacci(length, memory), 1))) 
    : secret.join('-').toUpperCase()
}

function fibonacciSecret(message, memory, secret = []) {
  const messageWithoutWhitespace = message.replace(/\s+/g, '')
  return createSecretString(messageWithoutWhitespace, memory, secret)
}

console.log(fibonacciSecret(message, fibonacciMemory))

"Benchmark"

with memoization

const message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";
const fibonacciMemory = {}

function fibonacci(x, memory = {}) {
  if (memory[x]) {
    return memory[x]
  }
  if (x < 1) {
    return 0
  }
  if (x <= 2) {
    return 1
  }
  return memory[x] = fibonacci(x - 1, memory) + fibonacci(x - 2, memory);
}

function createSecretString(message, memory, secret) {
  const length = secret.length - 1
  return length < 10 
    ? createSecretString(message, memory, secret.concat(message.substr(fibonacci(length, memory), 1))) 
    : secret.join('-').toUpperCase()
}

function fibonacciSecret(message, memory, secret = []) {
  const messageWithoutWhitespace = message.replace(/\s+/g, '')
  return createSecretString(messageWithoutWhitespace, memory, secret)
}

const t0 = performance.now();
fibonacciSecret(message, fibonacciMemory);
const t1 = performance.now();
console.log("First call took " + (t1 - t0) + " milliseconds.");

var t2 = performance.now();
fibonacciSecret(message, fibonacciMemory);
var t3 = performance.now();
console.log("Second call took " + (t3 - t2) + " milliseconds.");

without memoization

var message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";

function FibonacciSecret(message){
  var s = '';
   for(var i = 0; i < 10; i++) {
   s += message.replace(/\s+/g,'').substr(getNthValue(i), 1).toUpperCase();
   if(i != 9) {
       s += "-";
      }
   }

   function getNthValue(n) {
   if(n <= 1) {
       return n;
      }
   if(n > 1) {
       return getNthValue(n-1) + getNthValue(n-2);
      }
   }
   return s;
}

var t0 = performance.now();
FibonacciSecret(message);
var t1 = performance.now();
console.log("Call took " + (t1 - t0) + " milliseconds.");