Вы должны написать решатель Hangman. Тестирование по этому списку английских слов [1] , решатель, который решает наибольшее количество слов, побеждает, с количеством полных неверных догадок. Все слова в списке слов будут проверены в случайном порядке.
[1]: Этот список слов берется отсюда , затем удаляются цифры, затем удаляются слова длиной 1 или не алфавитными символами, а в качестве этого списка слов выбираются наиболее часто встречающиеся 4096 уникальных слов.
Детали:
Ваша программа будет взаимодействовать с игровой программой, которая выдаст вам через подчеркивание и правильно угаданные буквы. Ваша программа выдаст ваши догадки, и на основании входных данных она определит, было ли предыдущее предположение правильным или неправильным. После того, как вы ошиблись 6 раз, ваша программа проигрывает. Ваша программа должна быть готова к следующей игре после окончания каждой игры (после победы или поражения).
Длина вашего кода должна быть строго меньше 2048 байт, и ваша программа не должна использовать какие-либо внешние ресурсы (включая, но не ограничиваясь, доступ к списку слов в локальном хранилище или из Интернета).
Пример : ( >здесь вводу предшествует только пояснение - на самом деле его нет на входе)
>_______ // 7 underscores
a // Now you wait for input again
>_a___a_
e
>_a___a_ // Implies that your guess is wrong
>_____ // new round, this will be given ONLY IF you already have 6 losses
Предположим, что вы ошибаетесь 6 раз, вы получите окончательный результат, который подразумевает, что ваше предположение неверно, и ваша программа должна быть готова начать новый раунд (то есть сделать другой ввод).
Если вы выиграете,
>_angman
h
>hangman
>_____ // new round
Зная, что вы выиграли (потому что у ввода нет подчеркиваний), вы должны быть готовы принять следующий раунд.
Ваша программа должна завершиться, когда получит вход END.
Если ваша программа не является детерминированной (зависит от случайности, псевдослучайности, системного времени, температуры окружающей среды, моего настроения и т. Д.), Вы должны явно указать это в своем представлении, и ваш счет будет взят 10 раз (мной, если не указано иное) и в среднем.
Примечание : если вы используете такие языки, как python, пожалуйста, очищайте ваш стандартный вывод после каждого оператора печати.
Программа игры выглядит следующим образом (кредит nneonneo ):
import sys, random, subprocess
proc = subprocess.Popen(sys.argv[1:], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
def p(x):
proc.stdin.write(x+'\n')
proc.stdin.flush()
wordlist=[]
f=open('wordlist.txt', 'r')
for i in f:
wordlist.append(i[:-1] if i[-1]=='\n' else i)
# wordlist=[i[:-1] for i in f]
random.shuffle(wordlist)
score=0
totalerr=0
for s in wordlist:
s2=[]
for i in s:
s2.append('_')
err=0
p(''.join(s2))
while err<6 and '_' in s2:
c=proc.stdout.readline().strip()
nomatch=True
for i in range(0, len(s)):
if s[i]==c:
s2[i]=c
nomatch=False
if nomatch:
err+=1
totalerr+=1
p(''.join(s2))
if err<6:
score+=1
p('END')
sys.stderr.write('score is '+str(score)+', totalerr is '+str(totalerr)+'\n')Использование: python ./game.py [yoursolverprogram]
Пример: python ./game.py ruby ./solver.rb
Это должно работать как старая программа скоринга, но не зависит от именованных каналов, поэтому может работать на других платформах. Обратитесь к истории изменений, если вас интересует старая.
источник
subprocessвместо внешнего fifo для управления игрой? Таким образом, код будет работать для других ОС (например, Cygwin в Windows). Вот чтоgame.pyмодифицировано дляsubprocessзапуска программы, названной в командной строке: gist.github.com/nneonneo/d173f8888e1ea0c6fe37 . Используйте это какpython game.py <program> [args], напримерpython game.py python hangman.py.Ответы:
Python 2, оценка = 2111
Беги с
python -u. (Для тестирования с данным контроллеромpython ./game.py python -u ./solver.py.) Это 2044 байта кода + 1 для-u= 2045 байтов.Результат
Как это работает
Программа заменяет все
_s на1s в текущем состоянии, обрабатывает результат как целое число-36 и принимает его по модулю 1879, что дает нам грубую хеш-функцию. Он выбирает букву для угадывания путем индексации этого значения хеша в длинную строку букв. Если он уже угадал эту букву раньше, он уменьшает модуль на 6 (поэтому он всегда остается относительно простым до 36) и выбирает другую букву, повторяя, пока не найдет букву, которую он еще не угадал.Я разработал эту стратегию, чтобы иметь много настраиваемых переменных (отдельных букв длинной строки), большинство из которых независимо влияют на итоговую оценку небольшим количеством. Это делает его хорошо подходящим для оптимизации стиля восхождения на холм - я использовал Diversified Late Acceptance Search .
Python 2, оценка = 2854
Благодаря свободному использованию непечатаемых байтов и встроенному сжатию мы можем втиснуть гораздо больше информации.
Расшифровать с
xxd -rи запустить сpython -u. (Для тестирования с данным контроллеромpython ./game.py python -u ./solver.py.) Это 2047 байтов кода + 1 для-u= 2048 байтов.Результат
источник
Python: 2006 байт, оценка = 1501
1885 байт, оценка = 13371961 байт, оценка = 1207Вот мое представление:
Оценка результата:
Эта программа полностью детерминирована. Гигантский большой двоичный объект (который представляет собой блок
zlibсжатых данных в кодировке base-64 ) представляет собой список деревьев решений (одно дерево на длину слова). Каждое дерево решений кодирует полное двоичное дерево с глубиной от 2 до 5. Каждый внутренний узел является одним символом, и решение принимается на основе того, присутствует ли символ в слове палача.Каждый листовой узел двоичного дерева содержит оптимизированную таблицу частот, специфичную для этой ветви поиска в дереве. Таблица специально оптимизирована для того, чтобы способствовать завершению определенных слов, в то же время полностью игнорируя другие (которые не могут быть достигнуты из-за ограниченного бюджета «неудачи»). Таблица не оптимизирована для минимизации ошибок, и, следовательно, общее количество программ в программе высокое, несмотря на ее (относительно) хороший результат.
Оптимизатор, который не показан, использует недетерминированный нелинейный оптимизатор, использующий стратегию рандомизированного градиентного спуска для создания таблиц частот.
источник
range(4)можно заменить на[1]*4условии, что вам на самом деле не нужно использовать значениеi.decode('zip')вместоdecode('zlib')Рубин
Совместное представление от пользователя PragTob и меня.
Результат:
В нем 1672 символа, и он еще не в гольфе, поэтому у нас достаточно места для улучшения алгоритмов.
Сначала мы храним хэш символьных частот (вычисленных из списка слов), сгруппированных по длине слова.
Затем в каждом раунде мы просто сортируем все символы по частотам для текущей длины и пробуем их от наиболее распространенного к наименее распространенному. Используя этот подход, мы, очевидно, ошибаемся в каждом отдельном слове, которое имеет хотя бы средний общий характер.
источник
score is 625, totalerr is 23196еще актуален ваш обновленный алгоритм? Я попробовал подобный, и я получил только максимум 300.Обновление Используя метод, похожий на @nneonneo, я прихожу к этому коду, ровно 2047 символов .
Гол:
Код:
Старая запись
Результат:
Это не среднее значение, поскольку этот алгоритм является детерминированным, т. Е. Он всегда дает одинаковую оценку для любого перемешанного списка слов.
Вот моя запись в Python 2.7; игра в гольф (717 символов)
При этом используется идея, аналогичная @ m.buettner, для хранения упорядоченного списка букв, после которых будут сделаны предположения. Но это не использует данные о частоте напрямую, скорее, он просто пробует почти каждую возможную перестановку букв и моделирует игру, и, наконец, берет перестановку, которая дает лучший результат.
Эта версия оптимизирована с использованием первых 9 букв, поэтому для 2-буквенных и 3-буквенных слов перестановка уже является оптимальной в классе алгоритмов, где информация из предыдущего ввода игнорируется. В настоящее время я все еще использую код для топ-10 букв, оптимизирую слова из четырех букв (а также нахожу лучшее решение для более длинных слов).
неверный ввод
Для моего сравнения, вот код, который использует полное дерево решений, 11092 символа.
Гол:
Код:
источник
Perl, 1461 байт, оценка = 1412, итог = 21050
(Обратите внимание, что это 1461 байт после удаления небольшого количества необязательного пробела. Как напечатано, это на сто или более тяжелее, но все же намного меньше 2000).
Я попробовал кучу более «тонких» подходов, но этот в итоге побил их всех. Две строки данных - это просто ранжированные списки символов, которые наиболее вероятно следуют за каждым символом, и символы, которые наиболее вероятно предшествуют каждому символу (с орграфами, которые не встречаются в списке слов, вообще не представлен).
<и>используются для обозначения начала и конца слова. В качестве примера,"w[aiehonrlsdtkfy]"означает, что «wa» встречается чаще, чем «wi», встречается чаще, чем «мы» и т. Д.%d, Прямое отображение включает глобальное ранжирование, сохраняемое как$d{''}. Он используется для мест, где есть два неизвестных подряд или где исчерпаны все орграфы в списке слов (поэтому мы должны иметь дело со словом, не входящим в список слов).Для каждой неизвестной позиции в слове, он смотрит на предыдущий символ, дает каждому возможному следующему символу оценку, начиная с 180 для высшего ранга и уменьшая до 80 в конце списка; затем то же самое делается для следующего персонажа. Все баллы для всех персонажей суммируются, и выбирается тот, у кого самый высокий балл.
После того, как письмо угадано, оно удаляется непосредственно из таблиц ранжирования, поэтому его невозможно угадать снова (пока мы не начнем новое слово и не проинициализируем таблицы).
Обновление: набрал кучу очков, исправив ошибку (мы не удаляли буквы из обратной таблицы) и изменив способ сброса очков по мере продвижения по списку.
источник
Питон: 2046 байт, оценка = 1365
оценка 1365, итого 21343
Большая часть кода заимствована из представления Python от nneonneo (без которого я бы не получил это при ограничении в 2048 байт). Первоначально я думал, что это должно набрать еще около 200, но я обнаружил ошибку в своем инструменте создания строки данных. Теперь это исправлено, мой счет намного более разумный 1365.
Вместо того чтобы создавать двоичные деревья на основе длины, я создал одно двоичное дерево для хранения информации о частоте. Дерево не имеет одинаковой глубины, так как нет смысла хранить информацию о частоте для чего-то более глубокого, чем шесть неправильных догадок (но теоретически правильные догадки могут быть глубиной двенадцать для «значительно» и «неудобно»). Это неуклюжее дерево перемещается по факториальному коду (фактически используя комбинационную функцию). Чтобы сделать строку данных более сжимаемой, я добавил все неиспользуемые индексы с 's'.
Я использовал скрипт для вычисления хороших строк, которые нужно сохранить как d, и если кто-то может сыграть еще несколько символов из остальной части скрипта, то вот некоторые замены, которые должны привести к лучшим показателям. Верхняя строка - это строка, закодированная в программе выше.
Сценарий, который я использовал для генерации строк данных, находится здесь , на случай, если он кому-нибудь пригодится!
источник
distinct, ваша программа выводила по порядкуeitanogsuc, что означает, что она как-то перестает выдавать вывод, даже если она угадывает только 5 раз.Язык программирования D - мой инструмент выбора для этой задачи.
Просто стесняется ограничения в 2048 байт, хотя в некоторых частях он слегка приглушен, чтобы уменьшить счетчик байтов, все тяжелые подъемы остаются отлично читаемыми. Этот решатель не очень хорош в своей работе, и я ожидаю, что его легко одолеть, но это просто для того, чтобы мяч заработал. Начните, так сказать.
РЕДАКТИРОВАТЬ # 1 :
Как уже указывалось, первоначальный кодекс склонен умирать ужасной смертью, когда он исчерпывает все гласные. Поскольку он не работает должным образом, я заменил его более грубым подходом к случайным угадываниямРЕДАКТИРОВАТЬ # 2 : Исходный код был исправлен и теперь стоит.
Оценка :
25.7; totalerr: 24,529.9 (average of 10 tests).Как это работает
Этот решатель совершенно случайно. Даже случайность случайна, веселые времена!
Когда программа получает ввод, она отгадывает один случайный символ, который еще не угадал, и отправляет его в STDOUT.
Алгоритм угадывания работает так:
источник
./test.d(44): Error: cannot implicitly convert expression (uniform(0, Letters.length, rng)) of type ulong to int. Мне удалось это исправитьcast(int). После 10 пробежек ваш средний балл составляет 22,4 слова с 24529,1 неправильных догадок. Я перепроверю, если вы исправите более продвинутую версию :) ВеселитесьJAVASCRIPT + HTML Решение
источник