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

Question

[PRodion]

Есть многомерный массив.

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]);
    } 
}

Важные нюансы:

1. Общее количество букв может быть больше чем 16.
   
2. Ячеек по горизонтали может быть больше чем 4. По задумки их количество указывается опционально var cells = 4;.
   
3. Ячеек по вертикали может быть ровно столько - сколько требуется для размещения всех слов.
   
4. Пустых ячеек быть не должно.
   

Пример:

cells = 4     cells = 4
| | | | |     | | | | |
| | | | |     | | | | |
| | | | |     | | | | |
| | | | | или | | | | |
16 букв       | | | | |
              20 букв

Над этой задачей я сижу 3й день, с 10:00 до 23:00. Очень сложный для меня алгоритм. Буду рад любой помощи, любым советам относительно реализации.

Comments

[Stalker_RED]

Разбор слов на буквы:

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]);
    } 
}

Что и ЗАЧЕМ делает этот код?

[Stalker_RED]

Приведите еще пару примеров исходных массивов, если не сложно. С этим ['один','два','три','четыре'] слишком большой соблазн скатиться к решению частного случая, что вчера и произошло.

[PRodion]

Stalker_RED, разбирает 'один', 'два', 'три', 'четыре' по буквам: о, д, и, н, д, в, а, т, р, и, ч, е, т, ы, р, е

[PRodion]

Stalker_RED,

var array = [
    [
        'один', // 4 буквы
        'два', // 3 буквы
        'три', // 3 буквы
        'четыре' // 6 букв

        // 16 букв
    ],
    [
        'first', // 5 буквы
        'second', // 6 буквы
        'third' // 5 буквы

        // 16 букв
    ]
];

[Stalker_RED]

PRodion,

разбирает 'один', 'два', 'три', 'четыре' по буквам

но тогда вы теряете границы слов.

[PRodion]

Stalker_RED, как бы вы поступили? В пустые ячейки нужно вставить "четыре".

|о|д|и|н|
| | | |т|
| | | |р|
|д|в|а|и|

[0xD34F]

А, скажем, такое расположение допускается? -

| | | | |
|е| | | |
|р| | | |
|ы|т|е|ч|

Или такое:

| | | | |
| |о|д| |
| |н|и| |
| | | | |

[PRodion]

0xD34F, допускается.

[PRodion]

0xD34F, Главная задача - оставить их читаемыми, а не сделать из 'один' - 'днио' (набор букв)(что бы суть слова не терялась).

Answer 1

[0xD34F]

Закрутите слова спиралью от краёв к центру. Типа так:

|о|д|и|н|
|е|т|ы|д|
|ч|е|р|в|
|и|р|т|а|

Собираете слова в одну строку, режете на отдельные символы - получаете массив букв всех слов. Создаёте двухмерный массив, изначально заполняете его элементы значениями-заглушками - null, например. Затем начинаете по нему двигаться от левого верхнего угла, заполняя символами слов. На каждом шаге проверяете следующий элемент, если его значение не null - значит вы достигли края массива или уже заполненной его части - меняете направление обхода (поворачиваете направо).

Как это может выглядеть:

function makeTable(data) {
  data = data.join('').split('');

  let width = Math.sqrt(data.length) | 0;
  let height = (data.length / width) | 0;

  while (width * height !== data.length) {
    width--;
    height = (data.length / width) | 0;
  }

  const position = [ 0, 0 ];
  const directions = [
    [  1,  0 ],
    [  0,  1 ],
    [ -1,  0 ],
    [  0, -1 ],
  ];
  let direction = 0;

  const result = Array.from({ length: height }, n => Array(width).fill(null));

  for (const n of data) {
    result[position[1]][position[0]] = n;

    if (null !== (result[position[1] + directions[direction][1]] || {})[position[0] + directions[direction][0]]) {
      direction = (direction + 1) % directions.length;
    }

    position[0] += directions[direction][0];
    position[1] += directions[direction][1];
  }

  return result.map(n => n.join(' ')).join('\n');
}

Примеры использования:

console.log(makeTable([ 'раз', 'два', 'три' ])); /*
р а з
р и д
т а в
*/
console.log(makeTable([ 'один', 'два', 'три', 'четыре' ])); /*
о д и н
е т ы д
ч е р в
и р т а
*/
console.log(makeTable([ 'hello', ',', ' ', 'world', '!!' ])); /*
h e
! l
! l
d o
l ,
r  
o w
*/

Answer 2

[Stalker_RED]

Простейшее заполнение змейкой:

function makeSnake(letters, width) {
  var snake = [];
  for (var i = 0; letters.length > 0; i++) {
  	var chunk = letters.splice(0, width)  // отрезаем куски по ширине
    if (i%2) chunk.reverse() // разворачиваем нечетные
    snake = snake.concat(chunk)
  }
  return snake
}

Осталось вывести их в табличку по порядку: https://jsfiddle.net/yvcs3r5n/

Comments

[Евгений Калибров]

Отлично! Только нужно доработать - https://jsfiddle.net/yvcs3r5n/1/ ;)

[Stalker_RED]

rework, по заявлениям автора наборы слов подготовлены так, чтобы не оставалось пустых клеток. Это было в предыдущем вопросе.

[Евгений Калибров]

Я про вывод надписи "undefined"

[Stalker_RED]

rework, она появляется потому, что вы изменили количество букв и они не вписываются в прямоугольную таблицу без остатка. Автор вопроса обещал, что слова будут подобраны так, чтобы вписывались.

В любом случае это набросок, а не готовый продукт.

[Евгений Калибров]

Stalker_RED, понятно, не видел этого условия.

Answer 3

[ⓒⓢⓢ]

Заинтересовал меня ваш вопрос, спортивным интересом =)
Как пример:
https://jsfiddle.net/zq9op1gL/4/

В начале скрипта, если isEditor == true, то будет редактор змейки, для создания пути.
Пользоваться так:
Кликаем по ячейкам как вам нужно по правилам формирования слов
Ниже таблицы будут выводиться координаты ячеек. Что то такое:
1,4 , 1,5 , 2,5 , 2,4 , 3,4 , 3,5 ,

Копируем эту строку с координатами и вставляем в переменную массив "path"
Всё новый путь для формирования слов готов.

Меняем isEditor на false, смотрим результат, поидее должно работать.
Единственное есть недочёт, как проверка конца пути, если больше чем осталось ячеек, то слово впишется не полностью, но это уже мелочи ...

Можно ещё рандомно сами слова переворачивать для усложнения, чтобы путь запутать и т.д.

https://jsfiddle.net/zq9op1gL/6/
Развлекуха, за качеством не гнался =)

Comments

[PRodion]

Можно пример хотя бы одного исходника с похожим функционалом? Я например не встречал таких.

[ⓒⓢⓢ]

PRodion, ссылка в моём комментарии, чем не пример?
Выдёргиваем с миру по нитке ...
Разброс и кол-во слов на поле
Проверки доступного места для слова
Проверки на соседние слова, от пересечений слов
Угловые смещения позиций символов (но это не надо, но интересно)

[PRodion]

JRK_DV, да, там много можно по заимствовать. Спасибо.

[ⓒⓢⓢ]

PRodion, ещё как идея, если алгоритм никак не поддаётся, попробуйте упростить:

Есть массив слов ["один","два,"три","сто", "100500"] и т.д.
Вручную нарисуйте 10-20 разных извилистых "змеек" на разные размеры полей
Запоминаем порядок (индексы) ячеек в поле, где прошла змейка.
сортируете рандомно массив со словами и расставляете символы слов линейно по индексам ...

[ⓒⓢⓢ]

PRodion, Заинтересовал меня ваш вопрос, спортивным интересом =)
Как пример:
https://jsfiddle.net/zq9op1gL/1/

В начале скрипта, если isEditor == true, то будет редактор змейки, для создания пути.
Пользоваться так:
Кликаем по ячейкам как вам нужно по правилам формирования слов
Ниже таблицы будут выводиться координаты ячеек. Что то такое:

1,4 , 1,5 , 2,5 , 2,4 , 3,4 , 3,5 ,

Копируем эту строку с координатами и вставляем в переменную массив "path"
Всё новый путь для формирования слов готов.

Меняем isEditor на false, смотрим результат, поидее должно работать.
Единственное есть недочёт, как проверка конца пути, если больше чем осталось ячеек, то слово впишется не полностью, но это уже мелочи ...

Можно ещё рандомно сами слова переворачивать для усложнения, чтобы путь запутать и т.д.

[PRodion]

JRK_DV, добавьте решение в ответ.

[PRodion]

PRodion, пример не работает. Первый раз выпало только слово 'будем', последующие вообще не одного слова, просто набор букв.

[ⓒⓢⓢ]

PRodion, на вашем скрине, я как минимум вижу ещё слово "blue"
ячейка 5x5 - b, далее правее, ниже, левее

[PRodion]

JRK_DV, я о том что часть слов куда-то пропадает. Есть 'будем', 'blue' и т.д, но нет 'делить и 'слова'.

[ⓒⓢⓢ]

PRodion, так там символов гораздо больше чем ячеек ... на это я как бы и рассчитывал.
Записываем кучу слов, слова сортируются и вписываются те которые поместились в поле.
Длина символов, сколько поместилось = кол-ву ячеек

[ⓒⓢⓢ]

PRodion, но вы правы, есть тут косяк, в массив запятые попадают
https://yadi.sk/i/D6uRpTAd3Mvdp9

[PRodion]

JRK_DV,
Работает через раз. Из 3 раз - один правильный.

let word = ['один', 'два', 'три'];
let path = [[0,0 , 1,0 , 2,0 , 3,0 , 3,7 , 4,7 , 5,7 , 0,3 , 0,4 , 0,5 ,]];

[ⓒⓢⓢ]

PRodion, https://jsfiddle.net/zq9op1gL/3/
косяк на 39 строке pop() на shift() изменил

[PRodion]

JRK_DV, жаль только что https://jsfiddle.net/zq9op1gL/6/ не на чистом js.(

Answer 4

[V Sh.]

Вот простейший пример: заполняем по порядку.
js fiddle

Comments

[PRodion]

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

|б|у|д|е|     | | | | |
|м| | | |     | |д|е|л|
| | | | |     |и|т|ь| |
| | | | | или | | | | |

Желаемый результат:

|б|у|д|е|     | | | | |
| | | |м|     | |д|е|л|
| | | | |     | | | |и|
| | | | | или | | |ь|т|