1 Востаннє редагувалося FakiNyan (20.08.2016 09:58:16)

Тема: Буквенний тетріс та підрахунок можливих слів

Прів. Як краще знаходити слова в ось такій грі
http://i.imgur.com/igcREKz.gif
і як можна порахувати кількість всіх можливих слів, якщо найменше слово може мати 3 літери?

2

Re: Буквенний тетріс та підрахунок можливих слів

FakiNyan написав:

Прів. Як краще знаходити слова в ось такій грі
http://i.imgur.com/igcREKz.gif
і як можна порахувати кількість всіх можливих слів, якщо найменше слово може мати 3 літери?

По словнику.

3

Re: Буквенний тетріс та підрахунок можливих слів

тре по матриці

4

Re: Буквенний тетріс та підрахунок можливих слів

:o
як в таке грати?
також зі словником?

5

Re: Буквенний тетріс та підрахунок можливих слів

221VOLT написав:

:o
як в таке грати?
також зі словником?

а ви без словника й слів не знаєте?

6 Востаннє редагувалося P.Y. (22.08.2016 00:33:33)

Re: Буквенний тетріс та підрахунок можливих слів

Було б простіше, якби слова йшли тільки горизонтально або вертикально, а не зигзагами. Тоді, після того, як упав кубик, можна згенерувати регекс для горизонталі й вертикалі, де лежить новий кубик (слово, яке можна зняти, гарантовано перетинається з новим кубиком). Скажімо, якщо на полі ми маємо

. . . а б в . . . г ґ д
е є ж з и і ї й к л м н
о п р с т у ф х ц ч ш щ

то нам треба шукати слова, що містять "(а)?б(в)?|б(и(т)?)?" *
Робимо пошук за регексом по базі слів, беремо найдовше знайдене, стираємо зайняті ним клітинки на полі...
В принципі, подібним чином можна шукати й зигзаги, але генеровані для них регекси будуть дещо складнішими.

(Не впевнений, що варіант з регулярками найкращий з точки зору швидкості роботи, але я робив би так).

*) Порядок літер може бути не лише прямим, а й зворотнім — тобто, в наведений вираз треба ще дописати перевірку для зворотнього порядку символів.

7

Re: Буквенний тетріс та підрахунок можливих слів

Тут потрібна якась евристика.

Можна побудувати префіксне дерево.

Потім починаючи з кожної букви починати будувати слово. Наївним способом матимите для слова з 10 букв - 3^10 варіантів. Тобто спочатку ви можете рухатись у чотири боки, потім тільки у три. Звісно, межі поля, заборона самоперетинів і відсутність букв у комірках зменшують це число.

Евристикою може бути першими обробляти комірки з тими буквами які мають найбільше слів які з них починаються. І так далі на кожному кроці обирати варіант продовження такий. щоб префікс, який утворюється був найпоширенішим із можливих на цьому кроці.

Подякували: 221VOLT, leofun012