Вот так, некогда популярная серия «Lua для игр и не только» ненадолго воскрешается в силу ряда причин. Во-первых, буквально в новогодние праздники мы засели с некоторыми читателями и специалистами по ИИ за виртуальным круглым столом (пообщались в чате), где обсудили направления развития серии «Популярно об ИИ». Как многие знают, новый сезон я стартовал с темы вероятностной логики. После чего многие начали спорить, потому как просили написать большей частью о генетических алгоритмах, или хотя бы совместить две темы в одну. В принципе, сами они немного близки:). Затем обратились студенты-читатели рубрики программирования, задав множество интересных вопросов, среди которых очень многие опять же пересекаются с генетическими алгоритмами. Люди, обучающиеся Lua, сказали, что соответствующая серия была интересной, но не полной, поскольку в ней не рассмотрено много насущных вопросов, таких как работа с внешними файлами, строками, подключение и взаимодействие с внешними API. И окончательно ситуацию «добил» один веселый читатель, который попросил у меня алгоритм для создания (генерации) кроссвордов на базе имеющегося словаря. В общем, все темы, так или иначе, пересекаются. Поэтому приступим.
Формируем первое задание
Перед тем как приступить к написанию генератора кроссвордов, мы захватим менее сложный пример, а именно в этом материале начнем создавать алгоритм преобразования слова «МУХА» в слово «СЛОН». Это стандартная детская головоломка, в рамках которой предлагается составить список промежуточных слов, в каждом из которых в отличие от предыдущего меняется только одна буква. Таким образом, создается некая взаимосвязанная цепочка. В данном случае мы рассмотрим основные методы, покажем наиболее оптимальный, параллельно захватим те области языка Lua, о которых еще не писалось.
Предварительная подготовка
Работать мы будем в программе Scite (бесплатно скачивается с http://scite.ruteam.ru), в нем уже имеется встроенный интерпретатор языка Lua версии 5.1. Дополнительно нам понадобится объемный словарь, включающий четырехбуквенные слова, который можно довольно быстро найти в интернете, пройдясь по сайтам кроссвордистов. Я нашел один такой вариант на ресурсе http://chyjik.narod.ru, там он получился на чуть меньше чем 4000 слов. Перенес я его в обычный текстовый файл (XML мы делать не будем). Итак, поехали.
Чтение из файла
Возможны два варианта работы с файлами. Первый — поиск мы можем осуществлять внутри них, то есть, не создавая дополнительных массивов (таблиц), второй — мы вгружаем файл в массив (таблицу), отсортировав все данные. У каждого случая есть свои плюсы и минусы, но в силу большей простоты и понятности реализации выберем второй вариант.
В текстовом файле, так получилось при копировании (Ctrl+C/Ctrl+V), что все четырехбуквенные слова стоят вначале строк, а через несколько пробелов идут их описания. Описания, в общем-то, нам тоже понадобятся, поэтому стоит задача построчного чтения с последующим разбиением строк. То есть, структурно это подразумевает написание двух простых функций (если не объединять их в одну), одна из которых производит построчное чтение, вторая — разбивает данные и заносит в массив.
Итак, даю следующий фрагмент кода:
--создаем пустую --таблицу
dtable = {}
--счетчик для нее kdt=1
--функция заполнения --массива словаря function split_dict(str) dtable[kdt]={} local cap = str:sub(1, 4) table.insert(dtable[kdt],cap) cap = str:sub(6, -1) table.insert(dtable[kdt], cap) kdt=kdt+1 end
--читаем текстовый файл for line in io.lines("E:\\dictionary.txt") do split_dict(line) end
Проверять все можно через команду print(), например, выведя весь словарь:
for i=1,kdt-1 do print (dtable[i][1], dtable[i][2]) end
Результат получится таким:
Вывод будет производиться с некоторой задержкой, но при этом стоит отметить, что она связана только с выводом, сама операция преобразования файлов в массив занимает очень мало времени (что опять же можно проверить строкой print(os.clock())).
Теперь небольшие пояснения к коду. Операция for line in io.lines(путь к файлу) do что-то там end является оптимальным вариантом автоматизации, в рамках которого открывается файл в режиме чтения, запускается цикл построчечного чтения, пока не встречается значение nil, после этого сам файл автоматически закрывается.
Функция split_dict получает на входе строку из текстового файла, автоматически создавая «второе измерение» для массива/таблицы dtable (строка dtable[kdt]={}) , и заполняет две, если говорить образно, колонки, в одну вносит первые четыре символа строки выделенные функцией str:sub(1, 4), во вторую (поскольку там несколько пробелов) с 6 символа до конца, что делается за счет функции str:sub(6, -1). Следует отметить, что если в качестве последнего символа указывается «-1», это обозначает конец строки.
Таким образом, мы быстро и оперативно заполнили наш массив. Движемся дальше.
Разбиение слов на буквы
Я рассматривал листинги некоторых программ (на Java, C++ и т.п.) и там нередко можно встретиться с тем, что сами слова не только разбиваются на символы, но и символы преобразуются в их кодовые значения ASCII. Целесообразность такового в плане Lua не совсем понятна, потому как слово «МУХА» всегда будет равно слову «МУХА», но не равно «МУЗА». Вопросы строчных/заглавных тоже можно решить быстрым конвертированием одних в другие и наоборот. То есть, единственное, что нам в данном случае нужно, — это просто разбиение слов на буквы.
Делаем мы его с помощью той же функции sub, но при этом создав двумерный массив/таблицу под названием result, и сделав для него отдельный счетчик. Все будет выглядеть так:
--таблица, содержащая --результаты разбиения --по буквам result = {}
--ее счетчик kr=-1
--функция разбиения function split_word(str) local bv result[kr]={} for i=1,4 do bv=str:sub(i,i) table.insert(result[kr], bv) end kr=kr+1 end
Теперь поясним, на входе функция split_word() получает слово, после чего открывает второе «измерение» таблицы/массива результатов, и заносит в нее четыре новых элемента — буквы, из которых состоит входное слово. Коэффициент kr мы приняли равным единице не спроста, поскольку -1-м и 0-м элементами у нас будут исходное и заключительное слова головоломки.
Мы можем их и сразу внести, дописав снизу строки:
split_word(«МУХА») split_word(«СЛОН»)
Этап завершен, двигаемся дальше.
Начало перебора
Итак, по правилам игры в слове при каждой итерации мы сможем изменять только одну букву. Соответственно, нам понадобятся отдельный массив из букв, а также функция сопоставления получившейся комбинации с теми, что есть в словаре. Иначе говоря, нам нужно вычленить только имеющие смысл слова. Делаем это так:
--задаем массив букв --по алфавиту alpha={"А","Б","В","Г","Д","Е","Ё","Ж","З","И","Й","К","Л","М","Н","О","П","Р","С","Т","У", "Ф","Х","Ц","Ч","Ш","Щ","Ы","Ь","Ъ","Э","Ю","Я"}
--массив уместных --слов slova = {} --его счетчик ksl=1
--функция сверки --со словарем function sootv_dict(str, str_ish) for i=1,kdt-1 do if dtable[i][1] == str and dtable[i][1]~=str_ish then slova[ksl]= dtable[i][1] ksl=ksl+1 print(dtable[i][1],dtable[i][2]) end end end
--функция добавления --одного символа function perebor() for i=1,33 do str_ish=result[-1][1]..result[-1][2]..result[-1][3]..result[-1][4] str4 = alpha[i]..result[-1][2]..result[-1][3]..result[-1][4] sootv_dict(str4,str_ish) str4 = result[-1][1]..alpha[i]..result[-1][3]..result[-1][4] sootv_dict(str4,str_ish) str4 = result[-1][1]..result[-1][2]..alpha[i]..result[-1][4] sootv_dict(str4,str_ish) str4 = result[-1][1]..result[-1][2]..result[-1][3]..alpha[i] sootv_dict(str4,str_ish) end end
perebor() print(ksl-1)
Итак, в рамках функции perebor() мы, во-первых, сохраняем исходное слово, для того, чтобы потом его исключить из вариантов, во-вторых, перебираем все варианты с изменением одного символа (буквы), совмещая символы с помощью операции конкатенации «..», после чего вызываем функцию сравнения со словарем. В ее рамках пока находится print(), распечатывающая все найденные варианты, также они заносятся в массив/таблицу slova. Из слова МУХА у нас получилось 11: - АУХА — Рыба семейства окуневых.
- МАХА — Один из видов полбы.
- МУЗА — Стихотворение А. Ахматовой.
- МУКА — 1) Пищевой продукт, полученный размолом зерна различных культур; основное сырье для хлебопекарного, макаронного и кондитерского производств. 2) Стихотворение русского поэта XIX века Кольцова.
- НУХА — Название города Шеки в Азербайджане до 1968 года.
- МУНА — Река в Якутии, левый приток Лены.
- МОХА — Город в Йемене, порт на Красном море.
- МУРА — Приток Ангары.
- МУСА — Исламский пророк.
- МУТА — Древнеримская нимфа, рассказавшая Юноне о любви Юпитера к Ютурне; за что Юпитер лишил ее дара речи.
- МУХУ — Остров в Балтийском море.
Дальше предлагаю подумать самостоятельно до следующей части статей этой серии
Итак, мы сейчас создали весь необходимый базис для дальнейших действий. Предлагаю на данном этапе остановиться и подумать, каким образом мы будем искать ветку преобразования от «МУХА» к «СЛОН». Большинство начинающих студентов склонится к варианту полного перебора. Поэтому, предлагаю вам попробовать реализовать все самостоятельным образом, а в продолжении материала опишу некоторые варианты решений. Естественно, блок перебора, отображенный сегодня — это просто затравка. Полный листинг сегодняшней программы дан внизу статьи под подписью.
Кристофер Перепечатка материалов или их фрагментов возможна только с согласия автора
Полный листинг предварительной программы
dtable = {} kdt=1 result = {} kr=-1 alpha={"А","Б","В","Г","Д","Е","Ё","Ж","З","И","Й","К","Л","М","Н","О","П","Р","С","Т","У", "Ф","Х","Ц","Ч","Ш","Щ","Ы","Ь","Ъ","Э","Ю","Я"} slova = {} ksl=1
function split_dict(str) --создаем второе измерение dtable[kdt]={} --вносим добавления local cap = str:sub(1, 4) table.insert(dtable[kdt],cap) cap = str:sub(6, -1) table.insert(dtable[kdt], cap) kdt=kdt+1 end
--читаем текстовый файл for line in io.lines("E:\\dictionary.txt") do split_dict(line) end
---------------------------------------------------------------
function split_word(str) local bv result[kr]={} for i=1,4 do bv=str:sub(i,i) table.insert(result[kr], bv) end kr=kr+1 end
split_word("МУХА") split_word("СЛОН")
--------------------------------------------------------------
function sootv_dict(str, str_ish) for i=1,kdt-1 do if dtable[i][1] == str and dtable[i][1]~=str_ish then slova[ksl]= dtable[i][1] ksl=ksl+1 print(dtable[i][1],dtable[i][2]) end end end
function perebor() for i=1,33 do str_ish=result[-1][1]..result[-1][2]..result[-1][3]..result[-1][4] str4 = alpha[i]..result[-1][2]..result[-1][3]..result[-1][4] sootv_dict(str4,str_ish) str4 = result[-1][1]..alpha[i]..result[-1][3]..result[-1][4] sootv_dict(str4,str_ish) str4 = result[-1][1]..result[-1][2]..alpha[i]..result[-1][4] sootv_dict(str4,str_ish) str4 = result[-1][1]..result[-1][2]..result[-1][3]..alpha[i] sootv_dict(str4,str_ish) end end
perebor() print(ksl-1)
|