Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 12
Нигде не увидел ника из под которого бот участвует в рейтинге. Пропустил?
Циклы для поиска слов? И ещё база данных? Вообще-то достаточно просто отсортировать буквы по алфавиту и засунуть их конкатенацию в хэш. По исходным буквам можно получить все слова за O(1) + O(длина слова), что можно считать за O(1). Для 100 тыс слов потребуется около 10–20 мб памяти. Написание занимает очень мало времени (явно меньше, чем в статье).
Если я вас правильно понял, вы хотите что-то в этом духе:
Деградация — это предоставленное слово
Это цельные слова:
град
грация
Это отсортированные в алфавитном порядке + hex:
аагддеирця → 6cd7f4281021ee8ba9eab8bfa5887c79
агдр → 3f2697cbf7033e5343e93940cd2e2aac
агдирця → 57d1624e7938d262a22a6d1a56d9930a
Даже если предположить что мы разберём наше представленное слово на повторяющиеся буквы то есть для примера «грация»:
агдирця
агдирц
агдир
агди
агд
аг
агдиря
агди
…
И так далее получается для каждого свой hex, но помимо этой проблемы существует ещё проблема с двойными буквами в слове как в исходном так и искомом.
А на счёт базы данных, где вы предлагаете искать подходящие слова?
Возможно я вас не правильно понял?
Деградация — это предоставленное слово
Это цельные слова:
град
грация
Это отсортированные в алфавитном порядке + hex:
аагддеирця → 6cd7f4281021ee8ba9eab8bfa5887c79
агдр → 3f2697cbf7033e5343e93940cd2e2aac
агдирця → 57d1624e7938d262a22a6d1a56d9930a
Даже если предположить что мы разберём наше представленное слово на повторяющиеся буквы то есть для примера «грация»:
агдирця
агдирц
агдир
агди
агд
аг
агдиря
агди
…
И так далее получается для каждого свой hex, но помимо этой проблемы существует ещё проблема с двойными буквами в слове как в исходном так и искомом.
А на счёт базы данных, где вы предлагаете искать подходящие слова?
Возможно я вас не правильно понял?
hex и 6cd7f4281021ee8ba9eab8bfa5887c79Под словом хэш имелась ввиду структура данных, а не хэш-функция.
А у меня так:
Города — если отсортить, получится агдор
Дорога — если отсортить, получится агдор
o['агдор'] = ['города', 'дорога']. По «агдор» мгновенно получаем весь список слов.
Если нужно считать повторения, то будет «агдоор» (с двумя «о»).
А на счёт базы данных, где вы предлагаете искать подходящие слова?В памяти программы. Вначале загрузить все данные из файла (или из базы, если так удобнее), а потом мгновенно отдавать результат. Можно обрабатывать порядка 20 млн запросов на поиск слов в секунду на одном ядре. Но пишется проще, чем у Вас.
тестомесилка
1 — аееитклмосстт
2 — аеитклмосстт
3 — аееитклмосст
4 — аееитклмостт
5 — аеитклмостт
6 — аееитклмост
7 — аеитклмосст
8 — аеитклмост
И это только двойные буквы, но даже пусть так. Зачем мне скорость ещё быстрей? Если мне пришлось замедлить свою программу в 5 раз чтобы обойти блокировки. Хранить в памяти, тоже вариант для скорости, но как я уже сказал за ней я не гнался.
1 — аееитклмосстт
2 — аеитклмосстт
3 — аееитклмосст
4 — аееитклмостт
5 — аеитклмостт
6 — аееитклмост
7 — аеитклмосст
8 — аеитклмост
И это только двойные буквы, но даже пусть так. Зачем мне скорость ещё быстрей? Если мне пришлось замедлить свою программу в 5 раз чтобы обойти блокировки. Хранить в памяти, тоже вариант для скорости, но как я уже сказал за ней я не гнался.
Двойные буквы мы либо учитываем, либо нет, как я понял. В обоих вариантах нам не надо заполнять 8 вариантов, а только 1.
Зачем мне скорость ещё быстрей?Как я сказал, выше не только скорость, но и простота реализации. Глупо делать простые вещи сложнее и медленнее.
Я понял вашу идею, сейчас речь идёт о слове которое мы получаем во время хода игры. Получается что с ним нужно провести не просто сортировку, а ещё и выявить все возможные комбинации сочетания букв, в связи с этим фактом, мне интересна ваша реализация алгоритма нахождения всех возможных комбинаций букв с предоставленного слова. Можно просто псевдокодом.
Какие комбинации? Или Вы имеете ввиду, что можно использовать что ли не все буквы? Я просто не вчитывался в условие задачи (а Вы в статье его не указали). Если да, то неинтересная игра какая-то:
— Если в слове есть хотя бы одна «и» или одна «я», то уже можно составить слова «ИИ» и «я».
— Если есть «а», можно составить «ава», «ад», «фа» (нота), «мама», «папа».
— Если есть «е/ё», можно составить «дед», «ёж», «ре» (нота).
— Если есть «и», можно составить «ИИ».
— Если есть «о», можно составить «боб», «ВОВ», «до» (нота), «зоо», «око», «ом», «он», «ор», «сос».
— Если есть «у», можно составить «уж», «ум», «ус».
— Если есть «ы», можно составить «вы», «ты», «мы».
— Если есть «э», простых слов нет.
— Если есть «ю», можно составить «юг», «юз» (занос), «кю» (ранг), «ню», «мю» (буква).
— Если есть «я», можно составить «я».
В большинстве случаев лишь этих слов хватит, чтобы составить их из других слов.
Ну или расскажите уже в статье условие задачи, если я чего-то не понимаю. Я вначале подумал надо чтобы все буквы встретились. Правда не понял, должны ли одинаковые встречаться столько же раз, но для решения задачи это значения не имеет.
— Если в слове есть хотя бы одна «и» или одна «я», то уже можно составить слова «ИИ» и «я».
— Если есть «а», можно составить «ава», «ад», «фа» (нота), «мама», «папа».
— Если есть «е/ё», можно составить «дед», «ёж», «ре» (нота).
— Если есть «и», можно составить «ИИ».
— Если есть «о», можно составить «боб», «ВОВ», «до» (нота), «зоо», «око», «ом», «он», «ор», «сос».
— Если есть «у», можно составить «уж», «ум», «ус».
— Если есть «ы», можно составить «вы», «ты», «мы».
— Если есть «э», простых слов нет.
— Если есть «ю», можно составить «юг», «юз» (занос), «кю» (ранг), «ню», «мю» (буква).
— Если есть «я», можно составить «я».
В большинстве случаев лишь этих слов хватит, чтобы составить их из других слов.
Ну или расскажите уже в статье условие задачи, если я чего-то не понимаю. Я вначале подумал надо чтобы все буквы встретились. Правда не понял, должны ли одинаковые встречаться столько же раз, но для решения задачи это значения не имеет.
Правила игры озвучивает сам бот на скриншоте, «Вам необходимо из букв одного слова составить другие слова» и да буквы любой длины подходят, только вот однобуквенные слова я не проверял и исключил из поиска. По поводу решения я имел ввиду алгоритм разбора того слова которое нам дали. С поиском у меня не возникло вопросов, мне просто хотелось понять как вы предлагаете из того слова которое нам даёт игра найти подходящие. Нам нужно найти любые слова которые входят в состав представленного.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вырываемся в top10. Бот для игры в телеграме