Как написать сложный алгоритм?

Question

[PRodion]

Есть массив:

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

        // и того 16 букв
    ]
];

Стоит задача: разобрать слова из level[0] на отдельные буквы и вывести их в сетке, каждая буква - это отдельная ячейка сетки. Общее количество букв может меняться. Например: 16 (как в примере), 20 и т.д. Не могу понять как разобрать слова на буквы и как правильно формулировать сетку, точнее как сделать ее зависимой от количества букв. Например: 16 букв = 4*4, 20 букв = 4*5 и т.д. То есть, иметь возможность опционально указать пропорции сетки в зависимости от количества букв.

Возможно я изначально имею не правильное представление о реализации. Не разу такие сложные задачи не решал и сейчас очень тяжело понят с какой стороны браться. Очень надеюсь на какую любо помощь, возможно подскажете элегантный вариант реализация.

Comments

[Stalker_RED]

Слова могут быть любые? Если получится 23 буквы, например, (или другое простое число), то невозможно будет построить прямоугольную таблицу, у которой все ячейки заняты.

[Labunsky]

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

[PRodion]

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

[Stalker_RED]

Labunsky, очевидно? У вас доступ к какой-то секретной методичке или ясновидение прокачано?

PRodion, отлично, при 20 буквах можно сделать 4х5 или 10х2. Нужно автоматически выбирать более "квадратные" пропорции или это указывается вручную?

[Labunsky]

Stalker_RED, дя, "курс алгебры" зовется

[Kovalsky]

Labunsky, алгебра не имеет к этому отношения, вопрос был об условиях задачи, которые ТС изначально не озвучил.

[Labunsky]

Никита Полевой, я все-таки думаю, что алгебра напрямую связана с невозможностью создания матрицы из ровно p клеток, где p - простое

[Kovalsky]

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

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

[xmoonlight]

PRodion, играл в слова на нокии (понравилось), типа сканворда - принцип 1-в-1 как на картинке.

Answer 1

[Labunsky]

Не сложный алгоритм. Берешь таблицу, и начинаешь слева-направо:
1. Берешь слово;
2. Выбираешь первую попавшуюся свободную клетку (при обходе слева-направо, сверху-вниз, специально для longclaps. Сначала это угол, потом как пойдет);
3. Выбираешь случайное направление движения из доступных (должна быть хоть одна свободная клетка по этому направлению);
4. Начинаешь записывать слово по буквам, используя обход в глубину (ячейки клетки - вершины графа, ребра образуются между двумя свободными клетками, соединенными под прямым углом), с приоретитом на сохранение направления (никаких поворотов, кроме как при упоре в стенку);
5. Если есть еще слова - бери их и иди в п.1.

Comments

[Labunsky]

Размер сетки неважен, да, бери любой с помощью простого разложения на множители

[longclaps]

Labunsky, фуфло гонишь
"раз", "два", "три"

|раз|
|   |
|   |

|раз|
| д |
| ва|

|раз|
|тди| ???
|рва|

[Labunsky]

longclaps, это что за выбор клетки такой? Рандомом?)
По каким-то причинам я думал, что очевиден выбор слева-направо

[longclaps]

Labunsky, по каким-то причинам я руководствовался твоими пунктами. Эта поправка не спасёт - мне даже лень писать контрпример. Поэтому - фуфло.

[Labunsky]

longclaps, да на здоровье, не пиши, чо комментить-то тогда не в тему?

[Stalker_RED]

Labunsky, Он как-бы намекает, что вы сами додумываете те условия, которые автор вопроса не стал указывать. И получается у вас не очень.

[longclaps]

Labunsky, ты не заставишь меня писать контрпример - я пока еще верю, что ты не тупой и увидишь его сам.
Не разочаровывай.

[Labunsky]

Stalker_RED, какие условия, что додумываю? Что не получается? Кто здесь?
longclaps - это вин, я щитаю

[xmoonlight]

longclaps, ты имел ввиду "вылазь из норки и ползи только вдоль препятствия, а доползая - прячься в норку"?)

[longclaps]

xmoonlight, увы, и это ловится. Когда-то я писал решалку для змейки (там, правда, кролики возникали непредсказуемо) - на все эвристики легко строились ловушки.
Эта задачка геморройная, переборая, на малых полях я бы начинал с простого решения - как разместить самые длинные слова. Тут ведь важна читаемость.

[xmoonlight]

longclaps, длинные слова - я не думаю, что будет особая разница при корректности размещения... (иногда - в этом то и смысл сложности отгадывания)
А вот про то, что я сказал - хотелось бы увидеть наглядно: как там и что ловится...
(пока - не могу сам представить и смоделировать...)

[longclaps]

xmoonlight, можно просто укладывать змейкой - это не ловится.
"abcd", "12345"

|abc|
|21d|
|345|

Но эстетически как-то не очень. Вот получше:

|123|
|a54|
|bcd|

Допустим, есть 2 разных размещения (решения), какое предпочтительнее? Нужна метрика. Какие идеи?
1 - чем меньше изломов - тем лучше.
2 - начало слова должно читаться слева->направо или сверху->вниз
3 - ???
Теперь пробуем строить эвристику - если полный перебор непосилен. Например такую: пока возможно, добавляем слова без изломов. Ну вот и ловушка - свободное пространство может оказаться сегментированым...

[xmoonlight]

longclaps, это может произойти только в случае, если мы будем оставлять сверху или слева такие слова, длина которых короче, чем слово над текущим или слева от текущего, соответственно.
Иначе - непонятно: как там может оказаться сегментированное свободное пространство. )
Ну здесь суть периметрального заполнения от края к центру, как я в своём ответе уже писал.
Главное - направления написания соблюдать, чтобы удобно было читать и всё.

Answer 2

[xmoonlight]

Например: 16 букв = 4*4, 20 букв = 4*5 и т.д. То есть, иметь возможность опционально указать пропорции сетки в зависимости от количества букв.

Квадратный корень из количества букв или ближайший извлекаемый квадратный корень из заданного числа (модульная разница которого меньше):
Условие: [общее кол-во букв = 20 ] <= x^2,
т.е. мы хотим поместить слова в максимально-квадратную область.

проверяем: x=2 => x^2=4 => мало.
проверяем: x=3 => x^2=9 => мало.
проверяем: x=4 => x^2=16 => мало.
проверяем: x=5 => x^2=25 => много. стоп.
Теперь, сравниваем:
abs(20-4^2)=4 < abs(20-5^2)=5
Т.е., мы выбираем максимальное приближение к искомому, а именно, число 4 и квадрат 4x4.
Затем, "довешиваем" (удлиняем) одну сторону квадрата до нужного числа (делаем прямоугольник), кратного перемножению короткой грани на только что созданную удлинённую на столько, чтобы могли поместиться все буквы.
Вот и будет как раз сетка: 4x5 (4x4+4=20)

Затем, заполняете всё нужными словами, а то, что останется - заполняете словом, с нужным (оставшимся) количеством букв.

Если возможно нужно как-то растянуто, но главное - чтобы всё влезло "впритык", то можно сразу искать через покрываемую площадь: S=X*Y и минимальную длину стороны, кратную числу всех букв и уже от этого отталкиваться...
Т.е., конечная задача найти НОД для пар значений: S и X, и для S и Y, где S нужное кол-во букв для всех слов.

Если число букв простое - то делается так же, как написано выше: ближайшим дополнением до произведения X*Y, превышающего общее кол-во букв на как можно меньшее количество добавочных клеток сетки (правда проще - найти нужное по размеру слово и заменить им короткое, или всегда следить за НУЖНОЙ кратностью суммарного числа всех букв в словах).

Укладывать слова в сетку можно по-спирали из любой точки внешнего периметра до полного кольца и затем, смещение к центру на 1 клетку и снова в том же направлении.

Comments

[Stalker_RED]

С размерами как-то сложно.

var variants = []
// Полный перебор всех размеров по одной из осей
for (var width = 1; width < letters_count; width++) {
  var height = letters_count / width
  if (Number.isInteger(height)) { // выбираем только те, где делится без остатка
  	variants.push({width: width, height: height, diff: Math.abs(width-height)})
  }
}
// сортируем по минимальной разнице высоты и ширины
variants.sort((a, b)=>{
  if (a.diff > b.diff) return 1
  if (a.diff < b.diff) return -1
  return 0
})

Или даже без сортировки, налету сравнивать разницу и при достижении минимума прерывать перебор.

[xmoonlight]

Stalker_RED, да, ты всё верно понял и код тот...
Просто решил на словах это максимально детально объяснить, чтобы был понятен основной принцип достижения результата.