Вырываемся в top10. Бот для игры в телеграме

Вырываемся в top10. Бот для игры в Telegram


Предыстория


Все началось с того, что мне прислали ссылку на бота в Telegram с предложением поиграть.
Выглядит он примерно так.



После моей первой игры я заработал 28 балов, не сильно впечатляющий результат. Значит нужно всего ничего — программа, которая находит слова из букв исходного слова и база существительных русских слов.


Поехали


Для базы решил использовать sqlite3, он мобильный и для этой задачи самое то.


Структура базы выглядит так.


CREATE TABLE IF NOT EXISTS words (
    word VARCHAR(225) UNIQUE NOT NULL,
    length INTEGER NOT NULL
);

  • word — из название понятно, что это хранимое буквенное значение слова.
  • length — символьная длина.

Структура есть, для ее заполнения воспользовался списком существительных русских слов.


Заполнение базы и поиск слов было решено реализовать в одном коде, обработку разделить флагами.


Так же само создание файла базы и создание таблицы реализовываются в init()


func init() {
    var err error
    connection, err = sql.Open("sqlite3", "./words.db")
    if err != nil {
        log.Fatalf("Failed connection: %v", err)
    }
    _, err = connection.Exec(`CREATE TABLE IF NOT EXISTS words (word VARCHAR(225) UNIQUE NOT NULL, length INTEGER NOT NULL);`)
    if err != nil {
        log.Fatalf("Failed create database table words: %v", err)
    }
}

Функция insert()


При добавление слов необходимо помнить, что мы используем кириллицу, из-за чего обычная функция len() нам не подходит, воспользуемся utf8.RuneCountInString() для правильного подсчета длины слов.


Добавляем проверку на ошибку if err.Error() != "UNIQUE constraint failed: words.word" — необходима для возможности внедрения новых словарей, которые содержат в себе копию слов из базы.


func insert(word string) error {
    _, err := connection.Exec("INSERT INTO words (word,length) VALUES(?,?)", word, utf8.RuneCountInString(word))
    if err != nil && err.Error() != "UNIQUE constraint failed: words.word" {
        return err
    }
    return nil
}

Для поиска слов входящих в состав исходного, необходимо его разложить на буквы. В слове может содержаться несколько одинаковых букв, для учёта количества используем map[rune]int где int это количество найденых букв в слове.


func decay(word string) map[rune]int {
    var m = make(map[rune]int)
    for _, char := range word {
        m[char]++
    }
    return m
}

Сам поиск осуществляем в многопоточном режиме, количество gorutine = длине исходного слова, минус одна gorutine т.к. стартуем с поиска слов, состоящих из двух и более букв.


При таком подходе, программа работала слишком быстро и отправляла в чат к боту количество ответов = gorutine, хоть и в каждой gorutine был time.Sleap(1 * time.Second) — это привело к блокировке моего Telegram со всех устройств на 10 минут. Я это учел и в текущей версии поставил задержку на отправку, а саму ф-ю отправки вынес в отдельную gorutine, которая общается с остальными через общий канал. Поиск же осуществляется как и раньше.

Используем waitGroup{} как механизм окончания поиска всех слов из базы, после чего закрываем канал.


func findSubWords(word string) {
    list := decay(word)
    for length := 2; length <= utf8.RuneCountInString(word); length++ {
        wg.Add(1)
        go func(out chan<- string, length int) {
            search(out, list, length)
            wg.Done()
            fmt.Println("Done: ", length)
        }(out, length)
    }
    wg.Wait()
    fmt.Println("search done")
    close(out)
}

Функция поиска выбирает из базы все слова с искомой длиной и проходит по циклу проверяя подходит ли слово. Проверка осуществляется в несколько этапов. Из за использования map создаем новую копию каждый раз как завершаем проход по циклу. Копия map нам необходима для проверки на количество букв в слове, каждый раз при совпадении буквы мы декрементируем значение по ключу на единицу пока оно не уменьшится до нуля, после чего при совпадении такой буквы у которой значение = 0, мы присвоим переменной сontain=false и при завершении цикла слово не будет добавлено в канал.


func search(out chan<- string, wordRuneList map[rune]int, length int) {
    wordList, err := selects(length)
    if err != nil {
        log.Printf("fail length %v, error: %v", length, err)
    }
    for _, word := range wordList {
        var (
            wordCopyList = make(map[rune]int)
            contain      = true
        )
        for k, v := range wordRuneList {
            wordCopyList[k] = v
        }
        for _, r := range word {
            if _, ok := wordCopyList[r]; ok && wordCopyList[r] > 0 {
                wordCopyList[r]--
            } else {
                contain = false
                break
            }
        }
        if contain {
            out <- word
        }
    }
}

Осталось дело за малым, чтобы программа сама отправляла ответы в чат. Так как бот с другим ботом не может вести общение мне пришлось использовать свой личный аккаунт. Я решил воспользоваться клиентом с открытым исходным кодом.


Запустив его на порту :9090. Отправляем сообщения в чат к боту.


func send(in <-chan string) {
    conn, _ := net.Dial("tcp", "localhost:9090") // conncect to client telegram
    for word := range in {
        fmt.Fprintf(conn, "msg WordsGame-bot %v\n", word)
        time.Sleep(5 * time.Second)
    }
}

Команды для быстрого запуска telegram-cli на debian.


Установка необходимых библиотек.


sudo apt install libreadline-dev libconfig-dev libssl-dev lua5.2 liblua5.2-dev libevent-dev libjansson-dev libpython-dev libgcrypt20 libz-dev make git

Клонирование репозитория.


git clone --recursive https://github.com/vysheng/tg.git && cd tg

Выполнение конфигурации.


./configure
make

Запуск клиента на порту 9090


bin/telegram-cli -P 9090

Для того чтобы клиент нашел бота необходимо уже в клиенте выполнить команду search WordsGame-bot, после проверьте результат командой msg WordsGame-bot test, если после действий вы не написали боту в чат текст test, попробуйте сыграть с ним в игру лично.
Чтобы клиент начал работать не забываем авторизоваться, он сам предложит когда вы войдете в первый раз.

Вроде бы все готово. Программа может как и заполнять базу, так и вести игру с ботом, но только если вы сами будете запрашивать слова у бота.


Но все это медленно, а мы ведь хотим сразу занять первую строчку, а для этого нам нужно научить программу запрашивать слова у бота. Создадим подключение и отправим команду msg WordsGame-bot /play у бота есть задержка, поэтому ждем 5 сек. После чего запрашиваем последнее сообщение из истории с ботом history WordsGame-bot 1 это будет ответ, а точнее слово которое мы должны использовать в качестве исходного. Для чтения из conn создадим переменную reply = make([]byte, 512). После того как мы получили весь ответ с сonn он выглядит примерно так.


    history @manymanywords_bot 1
    ANSWER 58
    [16:10]  WordsGame-bot »»» дорабатывание

Создадим regexp.MustCompile("([аА-яЯ]{1,100})") для поиска слов из кириллицы. После чего, выбираем наше слово.


else if *god {
    go send(out)
    for {
        var (
            conn, _ = net.Dial("tcp", "localhost:9090") // conncect to client telegram
            reply   = make([]byte, 512)
            r       = regexp.MustCompile("([аА-яЯ]{1,100})")
        )
        fmt.Fprintln(conn, "msg WordsGame-bot /play")
        time.Sleep(5 * time.Second)
        fmt.Fprintln(conn, "history WordsGame-bot 1")
        time.Sleep(2 * time.Second)
        _, err := conn.Read(reply)
        if err != nil {
            log.Fatalf("failed read connection %v", err)
        }
        word := r.FindAllString(string(reply), 1)
        if len(word) <= 0 {
            log.Fatalf("somthing wrong %s", reply)
        }
        findSubWords(word[0])
        time.Sleep(5 * time.Minute)
    }

Но есть проблема, т.к. мы закрывали канал после того как нашли все слова. Чтобы исправить это нам нужна глобальная переменная GODMOD. Добавим в findSubWords условие. Теперь когда мы используем ключ -g переменная GODMOD переводится в true и канал не закрывается, а после завершения прохода по циклу мы запрашиваем новое слово.


    if !GODMOD {
        close(out)
    }

Теперь можно посмотреть на результат.



Полезные ссылки


Поделиться публикацией

Комментарии 12

    0
    Нигде не увидел ника из под которого бот участвует в рейтинге. Пропустил?
      0
      Я в статье тоже не нашел, но подозреваю, что это wenkaler.
        0
        Да в программе бот не указан т.к. я использовал свой личный аккаунт wenkaler.
        0
        Циклы для поиска слов? И ещё база данных? Вообще-то достаточно просто отсортировать буквы по алфавиту и засунуть их конкатенацию в хэш. По исходным буквам можно получить все слова за O(1) + O(длина слова), что можно считать за O(1). Для 100 тыс слов потребуется около 10–20 мб памяти. Написание занимает очень мало времени (явно меньше, чем в статье).
          0
          Если я вас правильно понял, вы хотите что-то в этом духе:

          Деградация — это предоставленное слово
          Это цельные слова:
          град
          грация

          Это отсортированные в алфавитном порядке + hex:

          аагддеирця → 6cd7f4281021ee8ba9eab8bfa5887c79
          агдр → 3f2697cbf7033e5343e93940cd2e2aac
          агдирця → 57d1624e7938d262a22a6d1a56d9930a

          Даже если предположить что мы разберём наше представленное слово на повторяющиеся буквы то есть для примера «грация»:
          агдирця
          агдирц
          агдир
          агди
          агд
          аг
          агдиря
          агди

          И так далее получается для каждого свой hex, но помимо этой проблемы существует ещё проблема с двойными буквами в слове как в исходном так и искомом.
          А на счёт базы данных, где вы предлагаете искать подходящие слова?
          Возможно я вас не правильно понял?
            0
            hex и 6cd7f4281021ee8ba9eab8bfa5887c79
            Под словом хэш имелась ввиду структура данных, а не хэш-функция.

            А у меня так:
            Города — если отсортить, получится агдор
            Дорога — если отсортить, получится агдор

            o['агдор'] = ['города', 'дорога']. По «агдор» мгновенно получаем весь список слов.

            Если нужно считать повторения, то будет «агдоор» (с двумя «о»).

            А на счёт базы данных, где вы предлагаете искать подходящие слова?
            В памяти программы. Вначале загрузить все данные из файла (или из базы, если так удобнее), а потом мгновенно отдавать результат. Можно обрабатывать порядка 20 млн запросов на поиск слов в секунду на одном ядре. Но пишется проще, чем у Вас.
              0
              тестомесилка
              1 — аееитклмосстт
              2 — аеитклмосстт
              3 — аееитклмосст
              4 — аееитклмостт
              5 — аеитклмостт
              6 — аееитклмост
              7 — аеитклмосст
              8 — аеитклмост
              И это только двойные буквы, но даже пусть так. Зачем мне скорость ещё быстрей? Если мне пришлось замедлить свою программу в 5 раз чтобы обойти блокировки. Хранить в памяти, тоже вариант для скорости, но как я уже сказал за ней я не гнался.
                0
                Двойные буквы мы либо учитываем, либо нет, как я понял. В обоих вариантах нам не надо заполнять 8 вариантов, а только 1.

                Зачем мне скорость ещё быстрей?
                Как я сказал, выше не только скорость, но и простота реализации. Глупо делать простые вещи сложнее и медленнее.
                  0
                  Я понял вашу идею, сейчас речь идёт о слове которое мы получаем во время хода игры. Получается что с ним нужно провести не просто сортировку, а ещё и выявить все возможные комбинации сочетания букв, в связи с этим фактом, мне интересна ваша реализация алгоритма нахождения всех возможных комбинаций букв с предоставленного слова. Можно просто псевдокодом.
                    0
                    Какие комбинации? Или Вы имеете ввиду, что можно использовать что ли не все буквы? Я просто не вчитывался в условие задачи (а Вы в статье его не указали). Если да, то неинтересная игра какая-то:
                    — Если в слове есть хотя бы одна «и» или одна «я», то уже можно составить слова «ИИ» и «я».
                    — Если есть «а», можно составить «ава», «ад», «фа» (нота), «мама», «папа».
                    — Если есть «е/ё», можно составить «дед», «ёж», «ре» (нота).
                    — Если есть «и», можно составить «ИИ».
                    — Если есть «о», можно составить «боб», «ВОВ», «до» (нота), «зоо», «око», «ом», «он», «ор», «сос».
                    — Если есть «у», можно составить «уж», «ум», «ус».
                    — Если есть «ы», можно составить «вы», «ты», «мы».
                    — Если есть «э», простых слов нет.
                    — Если есть «ю», можно составить «юг», «юз» (занос), «кю» (ранг), «ню», «мю» (буква).
                    — Если есть «я», можно составить «я».

                    В большинстве случаев лишь этих слов хватит, чтобы составить их из других слов.

                    Ну или расскажите уже в статье условие задачи, если я чего-то не понимаю. Я вначале подумал надо чтобы все буквы встретились. Правда не понял, должны ли одинаковые встречаться столько же раз, но для решения задачи это значения не имеет.
                      0
                      Правила игры озвучивает сам бот на скриншоте, «Вам необходимо из букв одного слова составить другие слова» и да буквы любой длины подходят, только вот однобуквенные слова я не проверял и исключил из поиска. По поводу решения я имел ввиду алгоритм разбора того слова которое нам дали. С поиском у меня не возникло вопросов, мне просто хотелось понять как вы предлагаете из того слова которое нам даёт игра найти подходящие. Нам нужно найти любые слова которые входят в состав представленного.
                        0
                        На скриншоте не озвучено формальных правил. Непонятно, нужно ли использовать все буквы или можно только некоторые (я вначале подумал первое). Непонятно, можно ли повторять буквы. Для игрока это всё не проблема, он быстро проверит, но у читателя статьи нет такой возможности.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое