Побудова кросвордів з допомогою мови Wolfram Language (Mathematica)


Переклад поста Майкла Тротта (Michael Trott), «Constructing Crossword Arrays Faster».
Скачати переклад у вигляді документа Mathematica, який містить весь код використаний у статті, можна тут.


У розділі 6 моєї книги Mathematica GuideBook Programming for, як приклад роботи зі списками я обговорив те, як побудувати масив, який представляє собою кросворд. Хоча цей приклад був хороший для демонстрації просунутої роботи зі списками, тим не менше, використання списків не є оптимальним шляхом побудови масиву кросворду. Складність додавання нового слова в масив з вже розміщеними n-1 словами становила для цього алгоритму ConstructingCrosswordArrays_1.jpeg, таким чином загальна складність складання масиву кросворду з n слів ставала рівною ConstructingCrosswordArrays_2.jpeg.

Протягом останніх декількох років, деякі користувачі Mathematica питали мене про те, чи можна побудувати більш швидкий алгоритм. Відповідь — так, можна. Якщо ми будемо застосовувати методи хешування, то ми зможемо швидко і за одне і теж час перевіряти, чи можна використовувати деякий елемент масиву і, отже, ми зможемо знизити загальну складність алгоритму з ConstructingCrosswordArrays_3.jpegConstructingCrosswordArrays_4.jpeg, що для кросвордів з тисячі слів дасть велику різницю в часі, затрачиваемом на обчислення. Цей алгоритм реалізований в даній статті. Коли ми розміщуємо окремі букви слова в деякій прямокутній таблиці необхідно розглядати безліч різних ситуацій. В результаті у статті міститься більше, ніж зазвичай, кількість процедурного коду. Хоча деякі визначення функцій кілька довгі, завдяки коментарям між кроками обчислень і гілками рішень код повинен бути досить простим для читання і розуміння.

Для того, щоб стаття була самодостатня, ми не будемо використовувати жодні алгоритми, реалізовані в GuideBook.

Ось формулювання завдання, яке ми будемо вирішувати:

Припустимо, що нам дано список слів у вигляді рядків. Наше завдання полягає в тому, щоб вставити їх в прямокутну таблицю, що складається з квадратів таким чином, щоб кожне слово було розташоване горизонтально (читалося зліва-направо) або вертикально (читалося зверху-вниз), при цьому слова повинні з'єднуватися в квадратах, що містять однакові для них літери.
Ось приклад, який використовує прізвища вчених (громадян СРСР і Росії), що стали нобелівськими лауреатами. (В іншій частині статті, ми будемо використовувати в якості прикладів слова, що мають пряме відношення до Mathematica.)

ConstructingCrosswordArrays_5.jpeg

Для поліпшення читаності кросворду, ми вимагатимемо також, щоб будь-які два горизонтальних або будь-які два вертикальних слова були відокремлені один від одного принаймні одним порожнім квадратом. На додаток до цього, ніяке горизонтальне слово не повинно починатися або закінчуватися в квадраті, який межує з квадратом, зайнятим буквою вертикального слова, і, аналогічно, ніяке вертикальне слово не повинно починатися або закінчуватися в квадраті, який межує з квадратом, зайнятим буквою горизонтального слова. (Іншими словами, квадрати, що примикають ліворуч і праворуч до горизонтального слова і квадрати, що примикають зверху і знизу до вертикального речі повинні залишатися порожніми.) Однак, ми дозволяємо словами починатися або закінчуватися в квадратах, зайнятих іншим словом.

Ми будемо розташовувати всі слова в квадратній таблиці (не обмеженій за розміром), побудованої з окремих квадратів і будемо відстежувати вміст кожного квадрата.

Функція

positionAWord[characterList,k,{i0,j0},hv]

має список символів characterList таким чином, що k-й елемент списку буде розташовуватися в квадраті {i0,j0} і слово characterList буде розташовано у відповідності зі значенням параметра hv (горизонтально або вертикально, що буде відзначатися "↔" або "↕", відповідно). Ми будемо використовувати конструкцію виду C[data] для того, щоб задавати поточний статус квадрата, при цьому можливі такі ситуації:

  • C[] — квадрат повинен залишатися порожнім;
  • C[«char»] — квадрат містить символ char є частиною горизонтального або вертикального слова.
  • C[«char»,"↔"] — квадрат містить символ char у вертикальному слові і може бути використаний також в горизонтальному слові.
  • C[«char»,"↕"] — квадрат містить символ char в горизонтальному слові і може бути використаний також у вертикальному слові.
  • C[_,"↔"] — квадрат не має поки що ніяких символів і може бути використаний в горизонтальному слові.
  • C[_,"↕"] — квадрат не має поки що ніяких символів і може бути використаний у вертикальному слові.
Вся ця інформація буде асоційована з down values функції status. При цьому status[{i,j}] буде обчислювати поточний стан квадрата з центром в точці {i,j}. На виході вона видасть об'єкт виду C[...] або залишиться в невычисленном вигляді, якщо квадрат ще не був використаний будь-яким способом або ж не є сусідом для деякого з вже розташованих в таблиці слів.

Ми зв'яжемо значення цієї функції з поточним вмістом квадратом допомогою виразу status[square]=value. Це дозволить нам зафіксувати час пошуку статусу кожного з потрібних квадратів за допомогою обчислення виразу status[square].

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

Необов'язковий останній аргумент функції positionAWord служить для створення возмножных побічних ефектів, таких як, скажімо, моніторинг порядку додавання слів, який ми будемо використовувати нижче. У реалізації цієї функції довелося розглянути велику кількість різних ситуацій — це легко побачити в коментарях до коду нижче.

In[1]:=

ConstructingCrosswordArrays_6.jpeg

В якості прикладу, ми розташуємо слово Mathematica, починаючи з квадрата {1,1} горизонтально.

In[2]:=

ConstructingCrosswordArrays_7.jpeg

Нижче наведено список квадратів, які були помічені.

In[3]:=

ConstructingCrosswordArrays_8.jpeg

Out[3]=

ConstructingCrosswordArrays_9.jpeg

Для того, щоб побачити наживо процес побудови, створимо функцію makeCWPGridGraphics, яка буде ракрашивать квадрати відповідно з їх поточним статусом.

In[4]:=

ConstructingCrosswordArrays_10.jpeg

Наведений нижче графік показує поточний статус квадратів, сусідніх з вже розташованими по квадратах символами.

In[5]:=

ConstructingCrosswordArrays_11.jpeg

Out[5]=

ConstructingCrosswordArrays_12.jpeg

Функція

positioningAWordIsPossibleQ[characterList,k,{i0,j0},hv]

перевіряє, чи можливо список символів characterList розташувати таким чином, щоб k-й елемент списку розташовувався в квадраті {i0,j0}, а слово characterList було розташоване у відповідності зі значенням параметра hv (горизонтально "↔" або вертикально "↕"). Для того, щоб зробити це нам потрібно перевірити, щоб кожен із необхідних квадратів був або доступний, або ж мав необхідний символ вже на місці. Також, сусідні квадрати повинні бути або порожні, або повинні мати літери з вже розташованого перпендикулярно слова. Допоміжна функція whileTrueLoops є ітеративної функцією, яка закінчує свою роботу, як тільки з допомогою техніки Throw-Catch знайдений перший несумісний квадрат. Надалі ми завжди будемо припускати, що нове слово розміщується тільки з допомогою функції positionAWord і тільки тоді, коли функція positioningAWordIsPossibleQ видає значення True.

In[6]:=

ConstructingCrosswordArrays_13.gif

In[8]:=

ConstructingCrosswordArrays_14.jpeg

Якщо ми вже розташували слово Mathematica горизонтально, ми можемо розташувати ще одну копію слова Mathematica вертикально.

In[9]:=

ConstructingCrosswordArrays_15.jpeg

Out[9]=

ConstructingCrosswordArrays_16.jpeg

Але ми не можемо розташувати горизонтально слово Mathematica в тій же позиції.

In[10]:=

ConstructingCrosswordArrays_17.jpeg

Out[10]=

ConstructingCrosswordArrays_18.jpeg

В цілому, можна було б помістити іншу копію вздовж вже розташованої, починаючи з літери «t» в позиції {3, 3}.

In[11]:=

ConstructingCrosswordArrays_19.jpeg

Out[11]=

ConstructingCrosswordArrays_20.jpeg

Звичайно, ми могли б помістити іншу копію слова Mathematica посередині, скажімо, зробити її вертикальної, що проходить через другу літеру «m» горизонтальної копії слова Mathematica.

In[12]:=

ConstructingCrosswordArrays_21.jpeg

Out[12]=

ConstructingCrosswordArrays_22.jpeg

In[13]:=

ConstructingCrosswordArrays_23.jpeg

За допомогою коду нижче ми можемо наочно відобразити поточний стан нашої таблиці.

In[14]:=

ConstructingCrosswordArrays_24.jpeg

Out[14]=

ConstructingCrosswordArrays_25.jpeg

Функція

findAPossiblePositionAndPositionaword[characterList]

шукає можливе розташування символів слова characterList і потім розміщає їх. Функція повертає координати додається символу, або $Failed, у разі, якщо ніякого способу додати слово немає. Ми також забезпечили цю функцію кількома досить очевидними опціями, які, серед іншого, дозволяють розташовувати слова або настільки щільно, наскільки це можливо, або навпаки — максимально вільно. Якщо значення параметру AttachmentPosition зроблено рівним Inner, то функція прагне додавати кожне нове слово всередині вже розміщених значення Outer — навпаки, якщо ж використовується значення RandomSample, то позиція нового слова вибирається випадковим чином.

In[15]:=

ConstructingCrosswordArrays_26.jpeg

In[16]:=

ConstructingCrosswordArrays_27.jpeg

In[17]:=

ConstructingCrosswordArrays_28.jpeg

Нарешті, ми создади функцію makeCWPGrid[status], яка буде конструювати власне таблицю з букв на основі down values функції status.

In[18]:=

ConstructingCrosswordArrays_29.jpeg

Графік нижче показує стан всіх вже доданих квадратів після того, як слово Mathematica було додано 6 разів до початкового. Сірі квадрати відповідають вже остаточно розміщеним словами; червоні — повинні залишатися порожніми; зелені — через них можуть бути додані нові слова. Стрілками показано в якому напрямку можна додавати нові слова.

In[19]:=

ConstructingCrosswordArrays_30.gif

Out[22]=

ConstructingCrosswordArrays_31.jpeg

In[23]:=

ConstructingCrosswordArrays_32.gif

Графік нижче показує деякі кроки процесу побудови масиву кросворду. Якщо уважно вивчити пристрій квадратів в кожному з малюнків (для кожної з опцій), стане набагато більш зрозуміло те, як влаштовані алгоритми, представлені вище.

In[25]:=

ConstructingCrosswordArrays_33.jpeg

Out[25]=

ConstructingCrosswordArrays_34.jpeg

Застосовуючи функцію Manipulate, ми можемо з легкістю створити інтерактивну версію алгоритму, яка дозволить нам простежити за його кроками наочно і просто. Наведена нижче інтерактивна версія алгоритму дозволяє простежити за 12 його першими кроками для різних значень опцій.

In[26]:=

ConstructingCrosswordArrays_35.jpeg

Out[26]=

ConstructingCrosswordArrays_36.jpeg

Тепер давайте розглянемо складність реалізованого методу. Зважаючи на те, що пошук поточного стану квадрата є майже постійною величиною (не залежить від кількості вже заданих квадратів), ми очікуємо лінійну складність O(n) в залежності від кількості слів. В якості тесту, ми знайдемо розміщення 500 слів Mathematica. Для візуалізації процесу обчислень ми будемо використовувати функцію Monitor.

In[27]:=

ConstructingCrosswordArrays_37.gif

Тепер зобразимо виміряні значення витраченого часу. Графік праворуч показує середній час на додавання певної кількості слів. Він росте лінійно з числом слів, які необхідно додати.

In[30]:=

ConstructingCrosswordArrays_38.jpeg

Out[30]=

ConstructingCrosswordArrays_39.jpeg

Таким чином, сумарний час формування масиву кросворду з n слів має складність порядку ConstructingCrosswordArrays_40.jpeg. Графік показаний нижче наочно демонструє це (чорний — витрачений час, червоний — знайдена модель виду ConstructingCrosswordArrays_41.jpeg).

In[31]:=

ConstructingCrosswordArrays_42.jpeg

Out[32]=

ConstructingCrosswordArrays_43.jpeg

Нижче представлений отриманий масив кросворду. Ми використовуємо невеликий розмір шрифту для того, щоб відобразити його тут повністю.

In[33]:=

ConstructingCrosswordArrays_44.jpeg

Out[33]=

ConstructingCrosswordArrays_45.jpeg

Завдяки значно більшій швидкості роботи цього підходу, заснованого на хешуванні для великої кількості слів (скажімо, тисяч), ми тепер можемо дуже швидко скласти кросворд, скажімо, з 250 слів. При цьому в якості списку цих слів візьмемо 250 обраних випадково вбудованих функцій мови Wolfram Language (системи Mathematica).

In[34]:=

ConstructingCrosswordArrays_46.gif

Out[38]=

<img src=«habrastorage.org/getpro/habr/post_images/d9a/7f2/18d/d9a7f218dad2ec599a95ce2b8333365b.png» alt=«ConstructingCrosswordArrays_47.jpeg» width=«159» висота=«21»/>

In[39]:=

ConstructingCrosswordArrays_48.jpeg

Out[39]=

ConstructingCrosswordArrays_49.jpeg

Графік, показаний нижче відображає порядок у якому слова були розташовані на площині (в таблиці). Червоні, високі стовпці відповідають словам, які були додані на початку, сині, низькі «башточки» — доданим пізніше.

In[40]:=

ConstructingCrosswordArrays_50.jpeg

Out[40]=

ConstructingCrosswordArrays_51.jpeg

Тепер побудуємо масив кроссорда, що складається з назв функцій (і їх опцій), пов'язаних з різними візуалізаціями в мові Wolfram Language.

In[41]:=

ConstructingCrosswordArrays_52.gif

Out[42]=

ConstructingCrosswordArrays_53.jpeg

In[43]:=

ConstructingCrosswordArrays_54.gif

In[47]:=

ConstructingCrosswordArrays_55.jpeg

Out[47]=

ConstructingCrosswordArrays_56.jpeg

Тепер створимо функцію потенціалу f для функції positionAWord. Ця функція буде використовуватися для визначення того, якого саме вже розташованому речі належить той чи інший символ.

In[48]:=

ConstructingCrosswordArrays_57.gif

Створимо тепер деяку варіацію функції makeCWPGrid, яка буде використовувати інформацію, пов'язану з функцією f для розфарбовування слів.

In[53]:=

ConstructingCrosswordArrays_58.jpeg

Результат представлений в таблиці нижче. Колір букв стоять на перетині слів змішується.

In[54]:=

ConstructingCrosswordArrays_59.jpeg

Out[54]=

ConstructingCrosswordArrays_60.jpeg

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

In[55]:=

ConstructingCrosswordArrays_61.jpeg

Побудований алгоритм може працювати з лубыми символами. В якості прикладу можна навести два способи скласти кросворд із всіх тризначних простих чисел.

In[56]:=

ConstructingCrosswordArrays_62.jpeg

Out[56]=

ConstructingCrosswordArrays_63.jpeg

Або ж можна створити кросворд з прізвищ усіх нобелівських лауреатів (громадян Росії та СРСР):

In[57]:=

ConstructingCrosswordArrays_64.gif

Out[58]=

ConstructingCrosswordArrays_65.jpeg

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.