Распределение слов по ячейкам таблицы

Есть многомерный массив.
var array = [ [ 'один', 'два', 'три', 'четыре'
// всего 16 букв ] ];
Список слов из array[0] должен быть размещен в таблицу, каждая буква - это отдельная ячейка таблицы. Расположение слов в таблице - не имеет значения. Главная задача - оставить их читаемыми по одной из сторон.
|о|д|и|н| |ч|е|т|ы| |ч|е|р|т| |т|д|о|р| |е|т|ы|р| |р|в|д|е| |д|в|а|и| или |и|а|и|н|
Мне кажется что вставить их без разбора на буквы - нереально. Вся проблема в том, что некоторые слова могут быть "закручены" (не знаю как правильно сказать). Пример:
| | | | | |ч|е|т|ы| |ч|е|р| | | | | |р| |е|т|ы| | | | | |е| | | | | | или | | | | |
Разбор слов на буквы:
for(var value = 0; value < array[0].length; value++) { for (var index = 0; index < array[0][value].length; index++) { // console.log(array[0][value][index]); } }
Важные нюансы:
Общее количество букв может быть больше чем 16. Ячеек по горизонтали может быть больше чем 4. По задумки их количество указывается опционально var cells = 4; Ячеек по вертикали может быть ровно столько - сколько требуется для размещения всех слов. Пустых ячеек быть не должно.
Пример:
cells = 4 cells = 4 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | или | | | | | 16 букв | | | | | 20 букв
Над этой задачей я сижу 3й день, с 10:00 до 23:00. Очень сложный для меня алгоритм. Буду рад любой помощи, любым советам относительно реализации.

Ответ

Вопрос не достаточно конкретизирован. Я рискну предположить, что автор имеет ввиду следующее:
Пусть задан набор слов из N

Пусть задано число M (== 16). Необходимо найти такие номера слов, что их суммарная длина будет равна M.
Решение 1
Для начала, заметим, что слова, как объекты нас не интересуют. Нам интересны лишь их длины. Длины их обозначим через l_i. Т.е. теперь у нас есть последовательность длин слов (их даже следует назвать множеством):

Математически строго поставим задачу (к решению имеет косвенное отношение).
В таком случае, нам нужно понять, существует ли решение хотя бы одного уравнения A_k над нашим множеством X

Т.е. существует ли решение уравнения

или

и т.д.
x_i может принимать значения из множества X ограниченное число раз.
Продолжение решения
Нам нужно найти комбинацию l_i, которые в сумме дадут M
Отсортируем последовательность

по убыванию и выбросим все те, для которых:

так как они не смогут участвовать в финальной сумме. После сортировки имеем:

где

Теперь нам нужно перебрать все варианты решения (т.к. M=16, т.е. небольшое, то мы в полне уложимся в перебор). Для перебора будем использовать DFS.
Как мы это будем делать
Возьмём s_0. Проверим s_0 != M. Если равно, то решение найдено. Попробуем подобрать для него такое число s_i, что s_0 + s_i <= M. Все варианты i для которых s_0 + s_i > M рассматривать не будет. В силу того, что объекты отсортированы, нам необходимо лишь перебрать их в порядке следования. Если s_0 + s_i = M, то решение найдено. Если нет, то продолжаем поиск. Т.е. выберем для s_i такое s_j (j >= i), что s_0 + s_i + s_j <= M (аналогично пункту 2).
На некотором шаге может оказаться, что s_0 + s_i + s_{i+1} >= M. В таком случае дальше осуществлять перебор не имеет смысла. Это справедливо, поскольку всё элементы отсортированы.
Необходимо вернуться на предыдущий шаг и найти s_k (k > j). Т.е. подобрать s_0 + s_i + s_k <= M. Если мы перебрали все возможные варианты, но не нашли сумму такую, что она равна M, то решения нет.
Для большего понимания, как следует организовать перебор, приведу псевдокод:
def dfs(s, sum): for number in get_next_number(s): new_sum = sum + number answ = False if new_sum == m: # Если нашли решение, то выходим из перебора return True elif new_sum < m: # Если решение не нашли, то пытаемся взять следующее число и повторить итерацию answ = dfs(number, new_sum) if answ: return True return False # Если ни в одном случае не удалось подобрать сумму, то выходим
dfs нужно запустить от каждого из имеющихся чисел s
Точно сложность не могу оценить, но дам верхнюю оценку. Она точно не больше O(N^3) по времени. Но следует понимать, что это завышенная оценка. Скорее всего, реальное время работы будет близко к O(N^2) или даже O(N log N)
Я также предполагаю, что можно предложить более умное решение динамическим программированием, в частности, свести эту задачу, к задаче о рюкзаке.
Другое решение
Для этого решения достаточно каждому слову поставить в соответствие метку 1 или 0, которая будет обозначать: нужно ли брать в ответ слово или не нужно. Таким образом, мы имеем битовую маску, состоящую из 0 и 1. Нам необходимо перебрать все возможные комбинации (их 2^N), посчитав для каждой из них суммарную длину выбранных слов.
Приведу пример:
один // длина 4
два_ // длина 4
пять // длина 4
три // длина 3
четыре // длина 6
Пусть M = 12
Маска будет состоять из 5 битов. Будем начинать перебор с маски 00000
10000. Слова: один. Суммарная длина 4 != M
01000. Слова: два_. Суммарная длина 4 != M
11000. Слова: один, два_. Суммарная длина 8 != M
00100. Слова: пять. Суммарная длина 4 != M
10100. Слова: один, пять. Суммарная длина 8 != M
11100. Слова: один, два_, пять. Суммарная длина 12 == M
В ответ могут войти слова: [один, два_, пять]
Спешу заметить, что вычислительная сложность алгоритма велика: O(2^N). Т.е. уже при 30 словах вы получите достаточно долго работающий алгоритм (минута или более).
Задание размеров сетки
Что касается сетки, то для задания её размеров можно задавать A, B -- размеры её сторон. По этим величинам вы генерируете саму сетку. A * B = M
Псевдокод
Для расположения слов, согласно вышеописанному алгоритму, можно воспользоваться "зейкой". Вы перебираете последовательно ячейки и кладёте туда по одной букве. Предварительно, разумеется, следует расположить все слова друг за другом:
words = 'одиндватричетыре' letters_count = 0 for x in range(0, A): if x % 2 == 0: line = range(0, B) else: line = range(B, 0, -1) for y in line: matrix[y][x] = words[letters_count] letters_count += 1