«Виселицу» — популярную игру на угадывание слов — кто‑то упомянул в комментариях к предыдущему посту, о задаче про игру в «Гонки». Не очень в тему, конечно — но я подумал «а чего это у нас задачи про виселицу нет?»
Обычно под программированием этой игры подразумевается написать код который загадывает слово — а пользователь предлагает буквы (и это пользователь будет повешен в случае неудачи). Здесь же наоборот — нужно написать программу которая угадывает слово по правилам данной игры. И теперь уже программист старается избежать «повешенья».
Задача интерактивная — сервер загадывает слово — а наша программа должна 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 секунд — по‑моему это происходит на уровне наших доблестных провайдеров — в программе вы обычно переиспользуете коннект и такой проблемы не происходит.