«Виселицу» — популярную игру на угадывание слов — кто‑то упомянул в комментариях к предыдущему посту, о задаче про игру в «Гонки». Не очень в тему, конечно — но я подумал «а чего это у нас задачи про виселицу нет?»

Теперь есть!

Обычно под программированием этой игры подразумевается написать код который загадывает слово — а пользователь предлагает буквы (и это пользователь будет повешен в случае неудачи). Здесь же наоборот — нужно написать программу которая угадывает слово по правилам данной игры. И теперь уже программист старается избежать «повешенья».

Задача интерактивная — сервер загадывает слово — а наша программа должна HTTP‑запросами предлагать ему буквы и смотреть что получается. Я покажу как можно «поиграть» вручную прямо из командной строки, используя curl но сдать задачу «вручную» не получится, поскольку присутствует ограничение по времени — так что без программы не обойтись.

Организационные замечания

Для этой и подобных «интерактивных» задач используется отдельный HTTP‑сервер (некий бесплатный хостинг). Исторически это был Google App Engine, но с тех пор перекочевал куда‑то ещё. Актуальный адрес всегда есть в инструкции которая упомянута в тексте задачи.

Запросы POST должны содержать в теле одно или несколько полей со значениями — в частности токен и «ход» пользователя. При этом форматы поддерживаются разные — JSON, form‑data или text/plain. Подробности также в инструкции — мы для примера используем первый.

Токен для запросов мы получаем в качестве «входных данных» на странице задачи. В случае если игра выиграна наш «игровой сервер» даст нам второй токен — его нужно отправить как ответ задачи чтобы она была засчитана.

Такое взаимодействие с использованием HTTP кажется немного громоздким — но зато позволяет написать программу практически на любом языке (лишь бы умел запросы отправлять) — ну и заодно помогает освоиться с HTTP‑протоколом (конечно, это актуально больше для новичков и учащихся).

Итак, игра!

На странице задачи (по ссылке выше) вы залогинившись увидите кроме текста задачи ещё и поля входных данных и ответа, как для обычных задач:

Как сказано выше, в интерактивных задачах входными данными является просто токен для общения с сервером.

Для начала игры нужно отправить запрос с единственным полем — токеном (ведь угадывать пока нечего):

curl -HContent-Type: -d '{"token":"..."}' \
    http://codeabbey-games.atwebpages.com/hangman.php

Вместо многоточия естественно нужно указать токен (можно считать его аналогом session_id), а Content‑Type можно не указывать (как в данном примере) чтобы использовать автоопределение — но упомянуть его требуется иначе курл автоматически подставит «form‑url‑encoded» (по‑моему).

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

В общем, если все сделано правильно, должен прийти ответ в духе:

{"pattern":"___________","attempts":9,"words":7,"time":0}

тут четыре поля и вероятно все итак ясно, но разберем подробно:

pattern — текущее состояние угадываемого слова — здесь будут появляться угаданные буквы (а где ещё не угаданы — подчёркивания)
attempts — на каждое слово даётся 9 попыток, в соответствии с правилами игры они уменьшаются только если предложить неправильную букву, а удачные попытки как бы «продлевают ходы»
words — сколько слов осталось угадать (для решения требуется угадать все семь)
time — время от начала игры, в ручном режиме не обращайте внимания — но программа должна справиться за 120 секунд

Делаем следующий ход!

В соответствии с мистической фразой «Этаойн Шрдлу» предлагаем букву «E»:

curl -HContent-Type: -d '{"token":"...", "letter":"e"}' \
    http://codeabbey-games.atwebpages.com/hangman.php

Нам повезло, «есть такая буква в этом слове» — и сервер отвечает:

{"pattern":"_e_________","attempts":9,"words":7,"time":422}

Как видим, правильная буква сохраняет попытки. Продолжая в том же духе найдём ещё несколько букв. К моменту когда до меня дошло, какое слово сервер загадал на этот раз, ситуация выглядела вот так:

{"pattern":"te__ni_ally","attempts":6,"words":7,"time":601}

(А вы догадались?)

Специальной возможности «назвать слово целиком» не предусмотрено, поэтому мы предлагаем две оставшиеся буквы и сервер сразу переходит к следующему слову — шаблон снова «наполняется подчеркиваниями», попытки возвращаются к 9 а счетчик слов уменьшается:

{"pattern":"________","attempts":9,"words":6,"time":796}

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

О программе

Общий принцип понятен, алгоритм не очень сложный. Слова берутся из файла который добывается по ссылке упомянутой в задаче — так что в принципе зачитываем их, и дальше с каждой попыткой фильтруем список. Тут можно добавить некоторые интересные фишки основанные на том что распределение букв в языке — не вполне независимая вещь. Если в слове, особенно небольшом, например угаданы «e» и «a» то вероятность найти там ещё какие‑то гласные резко уменьшается и упомянутый Этаойн уже немного не к месту.

Если игра заканчивается — например из‑за исчерпания попыток на угадывание очередной буквы — то в ответе будет поле end — обычно с пояснением, что произошло:

{"end":"game is lost","message":"You failed to guess: helmsmen","pattern":"h_______","attempts":0,"words":6,"time":1279}

Если же игра закончилась потому что вы выиграли, в ответе найдётся секретный токен который вы сможете скормить на странице задачи чтобы она была засчитана.

Запросы при выполнении по отдельности могут занимать некоторое время — у меня сейчас курл выполняется по 3–5 секунд — по‑моему это происходит на уровне наших доблестных провайдеров — в программе вы обычно переиспользуете коннект и такой проблемы не происходит.

Игра «Виселица» — интерактивная задачка c HTTP-запросами