JSFiddle - React, Tailwind, and code Playground

by emilcieslar

JavaScript

function solve(w, line) {
  const words = line.trim().split(' ');
  const matrix = [];
  for (let wordIndex = 1; wordIndex <= words.length; wordIndex++) {
    for (let weight = 0; weight <= w; weight++) {
      if (!matrix[weight]) {
        matrix[weight] = [];
      }
      const word = words[wordIndex - 1] || '';
      const wordLength = word.length;
      const previousResult = matrix[weight][wordIndex - 1] || {
        l: 0,
        c: []
      };
      if (wordLength <= weight) {
        const previousSack = matrix[weight - wordLength][wordIndex - 1] || {
          l: 0,
          c: []
        };
        const isPreviousSupreme = previousResult.l > previousSack.l + wordLength;
        matrix[weight][wordIndex] = isPreviousSupreme ?
          previousResult : {
            l: previousSack.l + wordLength,
            c: [...previousSack.c, word]
          };
      } else {
        matrix[weight][wordIndex] = previousResult || {
          l: 0,
          c: []
        };
      }
    }
  }
  return matrix[w][words.length];
}

function solveAll(w, lines) {
  lines.forEach((line, index) => {
    const solution = solve(w, line);
    console.log(`Solution #${index} of total length ${solution.l}: ${solution.c.join(' ')}`);
  });
}

// EXAMPLE
solveAll(15, ['as ad', 'asd asdasddd asdasddd', 'asdd asd asd asdddd', 'asdd asddd asdd', 'a asddd sdd asdd asddd asdd']);