Как я могу равномерно сбалансировать строку по минимальному количеству строк, используя только JavaScript?

Question

Я пытаюсь равномерно сбалансировать текст по нескольким строкам , используя только JavaScript и не заботясь о сложности размеров шрифта.

При заданной входной строке и максимальном ¹ количество символов в каждой строке, как я могу равномерно сбалансировать ² текст над минимальным количеством строк?

Я использую актуальную версию Google Chrome и поддержка устаревших браузеров не важна для моего вопроса.

Ниже приведена моя попытка без попытки сбалансировать текст (что я хочу, но я не знаю, как go сделать это).

Возможно удалить один или оба метода replace(), изменив строку RegExp в методе match().

const stringInputsAndExpectedArrayOutputs = [
  ['', ['']],
  [' ', ['']],
  ['  ', ['']],
  ['.', ['.']],
  ['The ', ['The']],
  ['The quick\nbrown fox', ['The quick brown', 'fox']],
  ['Thequickbrownfox jumpsoverthelazydog.', ['Thequickbrownfox', 'jumpsoverthelazydog.']],
  ['   The   quick   brown   fox   jumps   over   the   lazy   dog.   ', ['The quick brown', 'fox jumps over', 'the lazy dog.']],
  ['The quick brown fox jumps over the lazy dog.', ['The quick brown', 'fox jumps over', 'the lazy dog.']]
];
const maximumCharactersPerLine = 15;

const distributeTextOverLines = ((stringInput, maximumCharactersPerLine) => {
  let arrayOutput = stringInput.replace(/[\r\n ]+$/g, '').replace(/[\r\n ]{2,}|[\r\n]/g, ' ');
  arrayOutput = arrayOutput.match(new RegExp(`(?! )(?:.{1,${maximumCharactersPerLine}}|[^ ]+)(?= |$)`, 'g')) || [''];
  return arrayOutput;
});

for (const [stringInput, expectedArrayOutput] of stringInputsAndExpectedArrayOutputs) {
  const arrayOutput = distributeTextOverLines(stringInput, maximumCharactersPerLine);
  const arrayOutputDifferentThanExpected = !(arrayOutput.length === expectedArrayOutput.length && arrayOutput.every((value, index) => value === expectedArrayOutput[index]));
  if (arrayOutputDifferentThanExpected) {
    console.log('array output:');
    console.log(arrayOutput);
    console.log('expected array output:');
    console.log(expectedArrayOutput);
    continue;
  }
  const stringOutput = arrayOutput.join('\n');
  console.log('string output:');
  console.log(stringOutput);
}

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

---

¹ Если слово длиннее максимального предела, тогда строка должна содержать целое слово, переполняющее его.
² Распределите текст таким образом, чтобы в каждой строке было столько же символов, сколько и в других, что делает ширину всех строк вместе как можно меньше.

Answer 1

Для четного распределения я бы предложил алгоритм двоичного поиска:

1. Сделайте жадное распределение, как вы уже сделали. Это фиксирует количество строк, которое должно иметь решение.
2. Рассчитайте теоретическую минимальную ширину на основе общего количества символов, максимальной ширины и количества строк, которые у вас есть.
3. Выполните двоичный поиск в диапазоне между этими двумя крайние значения ширины, чтобы найти наименьшую ширину, для которой (жадное) распределение все еще может вписаться в это количество строк.

Вот интерактивный фрагмент, который позволяет вам предоставить текст и максимальную ширину. Вывод генерируется при каждом внесенном вами изменении.

Просто для удобства вывод начинается с дополнительной строки дефисов, заполняющей заданную максимальную ширину. Таким образом, вы сможете лучше представить, насколько результат под ним отклоняется от ширины ввода.

function breakLines(text, maxWidth) {
    function greedy(wordSizes, maxWidth) {
        let width = 0;
        let lineWidth = maxWidth;
        let firstWordPerLine = [];
        wordSizes.forEach((wordSize, i) => {
            if (lineWidth + wordSize >= maxWidth) {
                firstWordPerLine.push(i);
                lineWidth = wordSize;
            } else {
                lineWidth += 1 + wordSize;
            }
            if (lineWidth > width) width = lineWidth;
        });
        
        return { firstWordPerLine, width }
    }
    
    let words = text.match(/\S+/g);
    if (!words) return "";
    let wordSizes = words.map(word => word.length);
    let letterCount = wordSizes.reduce((a, b) => a+b);
    
    // Perform a greedy distribution
    let { firstWordPerLine, width } = greedy(wordSizes, maxWidth);
    let bestLines = firstWordPerLine;
    if (width <= maxWidth) { // There is not a word that causes overflow:
        let minWidth = Math.ceil((letterCount + words.length) / bestLines.length) - 1;
        // Perform binary search for optimal width
        while (minWidth < maxWidth) {
            let mid = (minWidth + maxWidth) >> 1;
            let { firstWordPerLine, width } = greedy(wordSizes, mid);
            if (firstWordPerLine.length > bestLines.length) {
                minWidth = mid + 1;
            } else if (width > mid) {
                bestLines = firstWordPerLine;
                break;
            } else {
                maxWidth = width;
                bestLines = firstWordPerLine;
            }
        }
    }
    // Convert bestLines & words to output
    let output = [];
    while (bestLines.length) {
        output.push(words.splice(bestLines.pop(), Infinity).join(" "))
    }
    return output.reverse().join("\n");
    
}

// I/O handling
let widthInput = document.querySelector("#maxwidth");
let inputText = document.querySelector("#text");
let outputText = document.querySelector("#aligned");

document.addEventListener("input", refresh);

function refresh() {
    let text = inputText.value;
    let maxWidth = Math.min(text.length, Math.max(0, +widthInput.value || 0));
    text = breakLines(text, maxWidth);
    outputText.textContent = "-".repeat(maxWidth) + "\n" + text;
}
refresh();

#maxwidth { width: 5em; }
#text { width: 100%; height: 5em }
#aligned { border: 0.5px solid; width:min-content }

max width: 

Input: 

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.


Output:

(откройте фрагмент в режиме полной страницы для лучшего опыта)