Given an array, find the two shortest strings, extract them and append them to the end until only one string remains

Question

I am stuck on a coding challenge for two hours and need help. The full instructions are as follows:

Given an array of strings, produce a single string as follows:

Repeat the following steps while there is more than one string in the array:

Find the shortest string in the array (if there are several strings of the same length take the leftmost one);

Find the shortest string among the rest (if there are several strings of the same length take the rightmost one);

Extract the chosen strings from the array;

Append the result of their concatenation (the second string should be added to the end of the first string) to the right end of the array.

After the algorithm has finished, there will be a single string left in the array. Return that string.

My attempt at a solution

function concatenationProcess(init) {
  var shortestString = init[0];
  var shorterString = init[0];
  var appendedString = "";
  while (init.length > 0) {
    for (i = init.length - 1; i >= 0; i--) {
      if (init[i].length <= shortestString.length) {
        shortestString = init[i];
      }
    }
    var newArray = init;
    newArray = init.splice(init.indexOf(shortestString), 1)
    for (i = 0; i < init.length; i++) {
      if (init[i].length <= shorterString.length) {
        shorterString = init[i];
      }
    }
    init.splice(init.indexOf(shorterString), 1)
    var newInit = init;
    console.log(shorterString, "shorter string")
    appendedString = shortestString + shorterString
    init.push(appendedString)
    console.log(init)
  }
}

Answer 1

A question like this begs for a recursive solution.

Consider this and an different way of thinking about the problem which leads to a very concise solution (as recursive functions often do):

function conArray(arr) {
  if (arr.length === 1) return arr
  var idx = arr.reduce((acc, curr, i) => curr.length < arr[acc].length ? i : acc, 0)  
  var str = arr.splice(idx, 1) 

  idx = arr.reduce((acc, curr, i) => curr.length <= arr[acc].length ? i : acc, 0) 
  str = str + arr.splice(idx, 1)

  arr.push(str)
  return conArray(arr)
}
conArray(["a","abc","abcc","aaa","z","","qw"])
// [ 'abcaaaabccqwaz' ]

This takes an array. If the array is only one element, it's done, just return it. Otherwise find the shortest (from the left) and next shortest from the right, push them onto the array and feed it back into the function.

Answer 2

After running your program, I think I found your problem. You correctly set shortestString and shorterString the first time through the array, but don't reset them before the second time. This leads to program failing to find shorter or equal length strings and crashing. However, resetting like you're doing now leads to a similar issue: if the first string is the shortest, it is returned for both the shortest and the shorter (because it's saved into shorterString before it's removed). To fix this, simply store the length of each string, so that you can initialize them both to Number.MAX_SAFE_INTEGER (or I guess Infinity would work). Your condition to stop the while loop is init.length > 0 instead of > 1. You have a couple of assignments (i.e. newArray and newInit) that are pointless and unused. Anyways, after writing your function from scratch I end up with this:

function concatenationProcess (init) {
    var shortestLength;
    while (init.length > 1) {
        shortestLength = Number.MAX_SAFE_INTEGER;
        var shortestString;
        for (var i = init.length-1; i >= 0; i--) {
            if (init[i].length <= shortestLength) {
                shortestString = init[i];
            }
        }
        init.splice(init.indexOf(shortestString), 1);

        shortestLength = Number.MAX_SAFE_INTEGER;
        var shorterString;
        for (var i = 0; i < init.length; i++) {
            if (init[i].length <= shortestLength) {
                shorterString = init[i];
            }
        }
        init.splice(init.indexOf(shorterString), 1);

        init.push(shortestString + shorterString);
    }
    return init[0]
}

Answer 3

Here you have a full working model here. Every time you can see how the array changes!! Do run it. The idea is very simple, find the shortest and the shorter element, delete them, and append the appended string. Repeat this until the length of array is greater than 1.

By the way, if you want the value, then of course replace alert with console.log or return.

function concatenationProcess(init) {
    while(init.length>1){
      var shortest = init[0];
      var appended = "";
      var p=0; // for storing the position of shortest/shorter
        for (i = init.length - 1; i >= 0; i--) {// find shortest
          if (init[i].length <= shortest.length) {
            shortest = init[i];
            p=i;
          }
        }
        init.splice(p,1); // remove shortest
        var shorter= init[0];
        for (i = 0; i <init.length; i++) { // find shorter
          if (init[i].length <= shorter.length) {
            shorter = init[i];
            p=i;
          }
        }
        init.splice(p,1); // remove shorter
       appended = shortest+shorter;
       init.push(appended); //append the appended string
       alert(init);
       }
    }
    var x = [ "thinking", "whatface", "cantare", "wait", "jay", "cutler"];
    concatenationProcess(x);

Answer 4

This condition makes the loop infinite:

while (init.length > 0) {

You need to stop when there is only 1 element left in the array, so change the 0 to 1.

You also have a bug. You need to update the values of shortestString and shorterString at the end of each iteration, otherwise they may keep their outdated values. For example in the example input ["thinking", "whatface", "cantare", "wait", "jay", "cutler"] they will stay set to jay and wait, never changing, and resulting in incorrect output.

And probably you want to return init[0] at the end of the function.