JS String Encryption Algorithm

This week, I was given a technical challenge that involved creating an encryption for a string. I’m pulling from memory, but the the task was roughly as follows: given a string, an r value, and a c value, encrypt the string so that it is split into a grid measuring r characters across and c characters down. Then, transform the string so that it reads top to bottom. The string will always be a length measuring r * c, and spaces count toward the string.

I was given a few test cases for this algorithm, which I’ve lost, but I’ve created my own for the purposes of this demo. Let’s work with the very convenient (and broken) string I gave myself: "This message is 25 charac" and r and c values both equal to 5.

According to the instructions, we would want to transform this string to look something like:

“This
messa
ge is
25 c
harac”

This should then give us the following string:

"Tmg hhee2ais 5rssi a ascc"

My approach to this was sound, but the final code was clumsy. So I want to walk you through how I approached it and then refactored it.

Following the instructions, I thought the best approach was to manipulate the string into a matrix measuring r rows and c columns, and the transform that matrix into a string, moving down column by column.

My first steps were to make a function with three arguments (duh) function encrypString(message, r, c) declare a matrix let matrix = [] and then to split the string into an array let msgArr = message.split(‘’). Easy enough

The next step was to populate the array. To do this, I opted for the creation of a for loop inside a while loop. With each iteration of the for loop, a new character was added to an empty array, which would stop when the array achieves a length of c - 1 — that is, the end column of the matrix given by the function (in this case 5). When the for loops completes, this new subarray is pushed into the matrix. This loop operates destructively on the msgArr variable, running until the array is empty.

  while(msgArr.length > 0){
    let newArr = [];
    for(let i = 0; i < c; i++){
      let newChar = msgArr.splice(0, 1)
      newArr.push(newChar)
    }
    matrix.push(newArr.flat())
  }

Admittedly, this is not the most beautiful solution. We’ll come back to a better alternative later that is less clunky. But for the time being, this produces the matrix that we need.

In my handling, the next step was to create an empty string which will be used to produced a return value (our answer) (let str = ‘’)and then manipulate the array by columns so that we can have our encrypted string. I chose the very clunky way of running a for loop inside of a for loop, once again manipulating the string one character at a time.

  for (let i = 0; i < c; i++){
    for (let j = 0; j < r; j++){
      str += matrix[j][i]
    }
  }

I’ll note the importance thing here is how the i and j values are set. The outer for loop runs according to the c value — that is the column — and the inner loop runs according to the row size (r). Every time the inner loop completes, this means we have emptied the nth column of every row, and then can move onto the next one. This does the work that we need it to and helps us arrive, but it’s not the most beautiful.

Having completed this text, I knew I could do better. These loops take too much time. Let’s look first at our initial loop to create the matrix using a while loop inside a for loop.

I realized two things going into this. First, I did not need to take up additional memory space by saving my original string under a new variable. I could simply declare message = message.split(‘’). Goodbye msgArr variable. Second, I did not abandon a loop entirely, but I did find a way to form the matrix one row at a time rather than one character at time by employing splice (still destructively manipulating the array).

  for(let i = 0; i < c; i++){
      matrix.push(message.splice(0, c))
  }

What is happening here is the message array is spliced each time from its beginning to c characters, destructively manipulating the message array and producing a new array of length c, which is then pushed to our matrix. Additionally, because splice produces an array, there is no need to declare an empty array with each loop. This allows the loop to run only c times, rather than once per character plus once per row (in our example 25 times for the string in the for loop, plus 5 times for the while loop. That would get long fast!).

This is good progress. But we can do better still. Once again, we have a double for loop to manipulate our string. This is not necessary. A single loop can accomplish the same goal. Rather than manipulate the array one character at a time, we can go one column at a time using destructing and the map function.

let encoded = []
while (matrix.length > 0){
    encoded.push(...matrix.map(subArr => subArr.shift()))
}

The restructuring allows us to pass in the matrix, and then map new arrays from each of its subarrays. By calling shift, we destructively manipulate the array, pulling the first value from each subarray. In total, this gives us an entire column of the matrix with each loop. What we achieved with two for loops that run character by character now run column by column. Not bad!

I’ll note that instead of creating an empty string, I’ve chosen to push these subarrays to an empty array, which requires calling .join(‘’) in our return value. I think join could be called on the mapped arrays as well and we could just push to the string as we did originally, str += ...

Let's compare, starting with our old version:

function encryptString(message, r, c){
  let matrix = []
  let msgArr = message.split('')
  while(msgArr.length > 0){
    let newArr = [];
    for(let i = 0; i < c; i++){
      let newChar = msgArr.splice(0, 1)
      newArr.push(newChar)
    }
    matrix.push(newArr.flat())
  }
  message = message.split('')
  for(let i = 0; i < c; i++){
      let newArr = []
      newArr.push(message.splice(0, c))
      matrix.push(newArr)
  }
  let str = ''
  for (let i = 0; i < c; i++){
    for (let j = 0; j < r; j++){
      str += matrix[j][i]
    }
  }
  console.log(str)
  return str
}

The new version:

function encryptString(message, r, c){
  let matrix = []
  message = message.split('')
  for(let i = 0; i < c; i++){
      matrix.push(message.splice(0, c))
  }
  let word = []
  while(matrix[0].length > 0){
    word.push(...matrix.map(subArr => subArr.shift()))
  }
  return word.join('')
}

This drastically cuts down the length of the function and the run time, and I think ends up being a lot more readable too. Not bad! If only I could have done this in the live coding exercise.

UPDATE 21 SEPTEMBER

Always trying to improve, I've stayed looking at this algorithm and realized that, with a little pattern recognition, there would probably be a better way to perform the string encryption. And I realized that we can effectively disregard the c variable and simply collect the values row by row. Imagine r = 5. We know the string will be a multiple of 5, so we can just collect every fifth value to form the first part of the string. These would be the values of column[0]. We need to append the second part of the string (this would have been column[1]), which would be every string at index of r - 1. With the addition of a counter and a while loop, this logic becomes a lot easier to track.

This logic could be kept inside a for loop, checking every index value or we can just implement this by filtering the string and checking if the index of the specific character divided by r has a remainder equal to the column it would be in. With x corresponding to the column number, this looks like: message.indexOf(char) % r === x. You can see this all at work in a much more efficient function below:

function encryptString(message, r, c){
  message = message.split('')
  let newStr = ''
  let x = 0
  while(x < r){
    // for every turn of the loop on x, add the character at the value r - x (x corresponding to the rows)
    newStr += message.filter(char => message.indexOf(char) % r === x).join('')
    x++
  }
  return newStr
}