Блог Игоря Шевченко

Как писать интерфейсные надписи 10 сентября 2017

Представьте себе разработчика Петра, который с утра пришел на работу и увидел в Джире такую задачу:

Добавить на страницу с отчетом возможность отправить csv-версию отчета на почту текущему пользователю

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

Вопросы, о которых думает Петр во время работы над задачей, — как написать оптимальный SQL-запрос, как разрешить конфликт версий между библиотеками, как правильно настроить кодировку файла... Тексты только отвлекают от реальных задач Петра, поэтому он на них особо не останавливается. Если вы когда-нибудь видели в программах или на сайтах странные и непонятные надписи, то скорее всего, они появились в подобной ситуации.

В крупных компаниях вроде Фейсбука и Дропбокса в последние годы стали появляться специальные люди в роли UX-копирайтеров, которые пишут тексты для интерфейса. Но большинство программистов работает не в таких компаниях. Хорошо, если есть хотя бы дизайнер, но даже ходить к дизайнеру за каждым сообщением об ошибке слишком накладно. В итоге надписи приходится писать самим программистам.

Этот пост — конспект внутреннего доклада, в котором я собрал советы для себя и других разработчиков нашей компании о том, какими должны быть надписи. Эти принципы предназначены для тех текстов, которые обычно пишут программисты. У маркетологов, сеошников и авторов корпоративных блогов наверняка есть какие-то свои правила.

Надписи должны быть точными

Иногда тянет написать какой-то обобщенный текст и использовать его во всех возможных ситуациях. Например, для всех ошибок выводить сообщение «Что-то пошло не так».


Это скриншот интерфейса электронной регистрации на авиарейс из блога Артемия Лебедева. Если бы разработчики указали, в каком виде они хотят получить номер телефона, Артемий и другие пассажиры тратили бы намного меньше времени на попытки угадать формат.


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


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

Надписи должны быть полезными

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

Есть история об устройстве, которое при отсутствии электричества показывало сообщение: «Ошибка пониженного напряжения». В какой-то момент сообщение заменили другим: «Проверьте электрический кабель». Количество звонков в техподдержку уменьшилось, потому что теперь владельцы прибора сами понимали, что им нужно включить его в розетку.


Это сообщение появлялось при отправке твита через клиент для Мака. Программа говорит, что дело в приложенной картинке, но не дает никакого решения. Если не знать, что эта надпись выводится, когда картинка превышает ограничение по размеру, то невозможно догадаться сжать ее.


Ошибка авторизации в Мейлчимпе. Сайт точно указывает, в чем проблема — в несуществующем юзернейме или неправильном пароле. Но помимо этого, он сразу же предлагает пользователю следующее логичное действие и показывает прямо в сообщении ссылку на восстановление юзернейма или пароля.


Для транзакционных писем от сервисов существует принцип, согласно которому в письме должна быть всего одна ссылка или большая кнопка. Так получатель сразу увидит ее и, не теряя времени, нажмет. Письмо от Аэрофлота приходится внимательно читать, чтобы обнаружить в нем ссылку на онлайн-регистрацию.

Надписи должны быть человечными

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


Это канадский транспортный терминал. С точки зрения обычного человека, терминал нужен, чтобы класть деньги на карточку, а потом расплачиваться ею в автобусе. С точки зрения программистов, этот терминал делает запросы к биллинговому серверу, которые могут иметь статусы «Выполнен» и «Ошибка». Программисты понимают, что значит «Запрос выполнен», а для нормальных людей это сообщение не несет никакого смысла.


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


Удивительный факт: пользователи никогда не считают себя или других людей «пользователями». На сайте с митапами это понимают, поэтому пишут не просто «10 пользователей идут на это событие», а указывают, что это за люди. Например, на встречу клуба читателей собирается 21 книжный червь.


Ну и совсем плохо, если пользователь видит техническое сообщение вроде NullReferenceException was thrown. Такие сообщения помогают при отладке, но на продакшне их нужно отключать.

Надписи должны быть короткими

Стив Круг в книге «Не заставляйте меня думать» пишет, что пользователи обычно ведут себя очень хаотично. Они быстро и сфокусированно делают какие-то вещи, направленные на решение их задачи, и почти ничего не читают. Короткие надписи увеличивают вероятность, что пользователь всё-таки зацепит их взглядом и что-то поймет. Поэтому надписи должны быть максимально короткими — не для того, чтобы сэкономить время на чтение, а потому, что длинную надпись просто проигнорируют.


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

Надписи должны быть самодостаточными

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

В бюро Горбунова это называют «взглядом новичка». Каждое возможное состояние должно иметь смысл с точки зрения человека, который забыл всё, что видел до этого. Если какая-то надпись непонятна сама по себе, нужно добавить в нее больше контекста и информации.


Еще лучше, когда самодостаточны даже отдельные элементы на экране. Например, маковские гайдлайны требуют не писать на кнопках просто «Да», «Нет», «Ок», а указывать совершаемое действие: «Сохранить» или «Удалить». Тогда решение получится принять быстрее, а вероятность нажать не на ту кнопку будет меньше.

Надписи должны быть уместными

Об этой проблеме хорошо написано в статье «Опаньки! Я сломал вам жизнь :)» (цитата из перевода с Хабра):

Ещё не угасла надежда на слабый сигнал Wi-Fi в аэропорту, на заряд батареи, который вот-вот заставит ноутбук вырубиться — а розетку здесь найти та ещё задача — и на то, что письмо клиенту на миллион долларов вроде ушло. И в этот момент «пожалуйста, заработай» вылезает приводящее в шок сообщение: «Упс». Как в некоторые бросающие в дрожь моменты фильма «Американский психопат» это не очень различимое, бесстрастное сообщение от почты Gmail вонзает кинжал точно в моё сердце, мгновенно порождая отчаяние — что же пошло не так?

Сейчас модно вставлять в тексты микрокопию — небольшие забавные тексты, которые по задумке должны приятно удивить или повеселить пользователя. Например, сервис почтовых рассылок Мейлчимп хвалит пользователя, дописавшего письмо, говоря ему «High Fives!» и показывая гифку с обезьяньей рукой. А если попытаться зарегистрироваться в Тумблере под уже занятым именем, появится сообщение «That's a good one, but it's taken».

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

Нормальные места, чтобы вставить микрокопию — онбординг, экран загрузки, сообщение об успехе, пустое состояние. Но не надо специально напрягаться и что-то выдумывать. Обычное сдержанное сообщение подойдет к любой ситуации.

Надписи должны быть целостными


Это скриншоты из старого Дропбокса. История версий файла в трех местах называется по-разному, и это будет путать пользователя. Если он запомнил заголовок «Version History», то он будет искать его в меню, где вместо этого написано «Previous versions». Будьте в курсе терминологии вашей системы и везде используйте единые понятия.

Целостность важна не только в терминологии, но и в деталях. Если все валидационные сообщения заканчиваются точкой, не забудьте поставить ее в очередном валидационном сообщении. Лично я не люблю писать «Вы» с большой буквы, но если так пишут на всем остальном сайте, то я не буду поднимать бунт и писать свой отдельный текст по-другому.


У пользователей уже есть привычки, сформированные другими сайтами и приложениями. Они привыкли к определенным названиям. На скриншоте данные из гугл-трендов, с помощью которых дизайнеры Дропбокса определяли, что написать на кнопке входа.

Надписи должны быть грамотными

Это очевидно, но ошибки и опечатки встречаются у всех. Проверяйтесь. Хорошо, если ваши IDE или линтер умеют находить ошибки в текстах.

Иногда бывают сложные случаи. Например, когда я пишу что-то на английском, мне не всегда хватает знаний, чтобы проверить написанное. Приходится скидывать надпись англоговорящим коллегам и спрашивать, всё ли в ней правильно.

Отдельная проблема есть с динамическими сообщениями вроде «22 файлов отправлено». Чтобы они были формально корректными, в них часто меняют формулировку на что-нибудь вроде «Файлов отправлено: 22». Это звучит очень неестественно, лучше написать по-человечески, разобрав возможные случаи (это легко).

Надписи должны быть необходимыми

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

Делайте работу за пользователя. В примере с Артемием Лебедевым и форматом телефона на сайте авиакомпании можно было просто приводить номер к нужному виду внутри системы.

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

Домашнее задание

Повторю список правил еще раз, надписи должны быть:

  1. Точными
  2. Полезными
  3. Человечными
  4. Короткими
  5. Самодостаточными
  6. Уместными
  7. Целостными
  8. Грамотными
  9. Необходимыми

Чтобы они лучше запомнились, у меня есть для вас небольшое домашнее задание. Ниже я привел несколько надписей. Попробуйте улучшить их. Если нужен какой-то дополнительный контекст, можете придумать его самостоятельно.

  • Эта возможность доступна только платным подписчикам.
  • (при сбросе пароля) Ваш временный код уже использован или истек!
  • Duplicate entry "ivan@gmail.com" for key "ixemail"
  • Пост не может быть удален.
  • Ошибка авторизации: вы уже авторизованы.
5 комментариев

Быстрые напоминания в Слаке 15 марта 2017

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

В Слаке много удобных фишек, но самыми недооцененными мне кажутся быстрые напоминалки.  В списках советов для пользователей Слака им уделяется столько же внимания, сколько команде /shrug ¯\_(ツ)_/¯

Напоминалки прячутся под кнопкой Remind me about this возле каждого сообщения.

Слак предлагает готовые временные интервалы Слак предлагает готовые временные интервалы

Слакбот подтверждает установку напоминалки Слакбот подтверждает установку напоминалки

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

На мобильниках это тоже есть.

Если заданные временные интервалы не подходят, то напоминалку можно поставить через консольную команду. Пишем в любой чат: 

/remind [@имя или #канал или me] [о чем напомнить] [когда напомнить]

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

/remind me to fix the bug tomorrow at 10:00

Слакбот подтверждает установку напоминалки из консоли

Слакбот понимает все формулировки даты напоминания, которые я пробовал — in 1 hour, at 12:00, on Tuesday, next week, mar 28, every day at 4:20pm. На русском не понимает, но это не страшно.

Типичные сценарии использования:

  • Ставлю себе напоминалку на завтра о чужом сообщении, если кто-то из американской части команды просит меня что-то сделать, когда у меня уже кончился рабочий день.
  • Ставлю себе напоминалку на 1 час о чужом сообщении, если всплыла какая-то задача, а я сейчас занят чем-то другим и не хочу переключаться.
  • Ставлю себе напоминалку на завтра о своем сообщении, если писал кому-то из удаленной команды и хочу завтра пингануть его еще раз, если за ночь мне не ответят.
  • Ставлю себе консольную напоминалку на шесть часов вечера, чтобы обсудить какие-то вопросы с американскими коллегами, когда у них уже будет утро.
  • Ставлю себе консольные напоминалки вообще обо всём подряд.
  • Ставим напоминалку на канал о праздниках удаленной команды, чтобы заранее решить все вопросы, пока они еще на работе.

Можно ставить напоминалки для других пользователей, но я этим не пользуюсь. По-моему, слишком агрессивно, лучше написать самому.

По функциональности это обычный туду-лист. Но оверхед у встроенных напоминалок гораздо ниже. Не нужно открывать отдельное приложение. Не нужно писать описание задачи. Сроки напоминания подбираются автоматически и довольно разумно.

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

Нет комментариев

NaNoGenMo: как компьютеры пишут новеллы 4 ноября 2016

Ноябрь считается месяцем литературного творчества. Каждый год в интернете проходит мероприятие NaNoWriMo (National Novel Writing Month). Участники должны до конца месяца написать новеллу длиной не менее 50000 слов. За 17 лет в нем поучаствовали больше 20000 человек.

В 2013 году у программистов появилось аналогичное соревнование — NaNoGenMo (National Novel Generation Month). Задача NaNoGenMo — написать программу, которая сгенерирует новеллу длиной 50000 слов или больше. При этом требования к новелле довольно слабые — подойдет любой текст достаточной длины. Как вы увидите, это может быть сборник рассказов, пьеса, кулинарная книга, словарь или туристический путеводитель. На самом деле, произведение не обязано даже быть текстовым.

Графическая новелла «Сгенерированный детектив»

Сама по себе задача написать программу, которая сгенерирует текст из 50000 слов, проста. Для этого достаточно вот такого кода:

print 'мяу ' * 50000

С другой стороны, читать такую новеллу будет скучно уже начиная с третьего слова. Участники NaNoGenMo пытаются решить эту проблему. Они придумывают литературные и технические ходы, которые позволили бы удержать внимание читателя. Это уже гораздо сложнее. На практике, если можно с интересом прочитать хотя бы несколько страниц новеллы — это можно считать успехом.

В этом посте я хочу рассказать, какие приемы используют для алгоритмической генерации литературы, и поделиться самыми интересными работами за три года.

Марковские цепи

Цепи Маркова — классический способ генерации текста. Он хорошо описан здесь. У цепей Маркова есть проблема: если выбрать для N-грамм большое значение N (обычно 5 и больше), то в тексте проявляются большие куски исходного корпуса, если взять N меньше, то он получается откровенно бессмысленным.

Но эта проблема решаема: некоторые жанры произведений могут успешно скрывать от читателя свою бессмысленность. Например, реплики из диалогов Сократа и Аристотеля от yourpalal с первого взгляда трудно отличить от философских размышлений. Точно так же я бы не раздумывая принял сгенерированное лицензионное соглашение от greg-kennedy, если бы увидел его в установщике нужной мне программы.

Другие произведения, основанные на цепях Маркова: эротические рассказы от Agrajag-Petunia, речи Рейгана (с примесью работ Шопенгауэра) от VincentToups, автобиографии на английском 19 века от lizrush.

Расширение шаблонов

Чаще всего осмысленные фрагменты текста генерируют с помощью шаблонов. Представим, что у нас есть такая грамматика:

sentence = '<greeting>, <world_phrase>!'
greeting = ['Привет', 'Приветик', 'Здравствуй', 'Добрый день']
world_phrase = ['<happy_adj> мир', '<sad_adj> мир', 'мир']
happy_adj = ['прекрасный', 'светлый', 'добрый']
sad_adj = ['унылый', 'жестокий', 'мрачный']

На основе нее мы можем сгенерировать много разных предложений — «Привет, унылый мир!» или «Добрый день, прекрасный мир!». Чем богаче грамматика, тем более интересные тексты она выдает.

В «The Gamebook of Dungeon Tropes» от maetl с помощью шаблонов генерируются описания подземелий.

В «Атеистах, которые верят в Бога» от tra38 используются данные какой-то переписи населения США. Герои новеллы — люди, которые сказали, что они атеисты, но верят в Бога. Они один за другим читают шаблонные лекции, в которые подставлены ответы на вопросы из переписи.

Шаблоны используются в новелле «Где-то что-то» от BenKybartas, сборнике «5000 рассказов» от tinyworlds, эротической новелле «Оргазмотрон» от enkiv2 (простите, больше эротики не будет) и спортивном комментарии «Федерация лжеамериканского футбола» от creade.

Рекурсия

Шаблоны позволяют получить небольшой фрагмент читабельного текста. Но по правилам соревнования новелла должна быть не короче 50000 символов. Изящно нарастить объем помогает рекурсия.

Простой вариант: в «The transorbital anaphase provine biforn the pure-bred synostosis» от samcoppini берется одно предложение (оно вынесено в заголовок). А затем с помощью словаря дается определение некоторых слов. Для слов из определений тоже даются определения. И так пока не наберется пятьдесят тысяч.

«Гигант без сердца» от MichaelPaulukonis рассказывает вариации норвежской сказки о принце, который спас своих братьев от злого гиганта. Но в конце этот принц сам становится гигантом и похищает детей другого короля. И вся история повторяется, но уже немного по-другому.

Новелла «Надежды и воспоминания» от cpressey состоит из нескольких событий и диалога двух персонажей. По ходу новеллы они встречают вампира, зомби, дракона и других чудовищ. А всё остальное время они вспоминают свои встречи и предполагают, кого они увидят в будущем. А потом вспоминают, как вспоминали какую-то встречу, предполагают, будут ли они вспоминать, как предполагали другую встречу и так далее.

Похожа по структуре «Redwreath and Goldstar Have Traveled to Deathsgate» от erkyrath. Там тоже два персонажа ведут разговор. Они очень вежливые — спрашивают: «Могу ли я задать вопрос?» и «Правильно ли я понимаю, что...». И так пока в какой-то момент не доходит до такой реплики:

"You want to know whether I am asking whether you are asking whether you shall tell me whether you want to know whether I believe I can answer that?"

«Сто шестьдесят пять дней Рождества» от hugovk — это продолжение английской народной песни «Двенадцать дней Рождества», где продолжают дарить новые и новые подарки (и их количество тоже растет).

Переработка существующих произведений

Если литературное произведение находится в публичном достоянии, его можно использовать любым способом. В том числе и для генерации нового произведения на его основе. Самые интересные примеры:

Моби Дик на кошачьем языке от hugovk. Это одна из самых известных работ NaNoGenMo про которую писали The Guardian, Vox и The Atlanctic. Просто приведу цитату:

Meow me Meeeeow. Meow meeow mew--meoow meow mew meow meeeeooow--meeeow meeeow me me meeow me me meoow, mew meeeoow meeeooooow me meooooow me me meeow, M meeooow M meoow meow meoow m meooow mew mew mew meooow meow me mew meeow.

Сравните с оригиналом:

Call me Ishmael. Some years ago--never mind how long precisely--having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world.

«Приключения Шарлотты Холмс» от emdaniels. Автор поменяла пол всех персонажей в рассказах о Шерлоке Холмсе. Звучит не очень серьезно, но на самом деле это непростая лингвистическая задача. C которой автор справилась не до конца (поэтому пришлось придумать местоимение herr).

To Charlotte Holmes he is always THE man. I have seldom heard her mention him under any other name. In herr eyes he eclipses and predominates the whole of him sex. It was not that she felt any emotion akin to love for Ivan Adler.

«Гомерическое ультранасилие» от lilinx. Из текста Илиады выбрали все предложения, в которых есть слово «ударить» в одной из форм. Получилось описание длинной и жестокой бойни, в которой уже даже непонятно, кто с кем сражается.

«Моби Дик, или :whale:» от pteichman — еще один вариант Моби Дика, в котором некоторые слова заменили соответствующими эмодзи.

Другие произведения: «Приключениях Тома Сойера» с героями из романа про Конана от MrDrews, «Гамлет» от dkurth, пропущенный через несколько этапов машинного перевода, «Гордость и предубеждение» с лексикой из Твиттера от michelleful, «Превращение» Кафки, в котором каждое слово заменено более абстрактным, от jonkagstrom.

Не обязательно использовать только одно произведение. Например, сборник коротких рассказов, состоящих из шести слов, от hugovk.

А в «Нашем прибытии» (PDF) от aparrish из корпуса «Проекта Гутенберг» выбраны предложения, в которых описываются какие-то природные объекты или явления. Собранные вместе, они составляют дневник некой экспедиции. Получилось очень красиво, эта новелла занимает одно из мест в моем личном топе новелл с NaNoGenMo.

Переработка других данных

Не обязательно брать в качестве основы литературное произведение. moonmilk составил новеллу из твитов участников NaNoWriMo (PDF) (это то соревнование, где люди сами пишут новеллы), а jimkinsey — из вопросов, которые ученые задают в аннотациях статей (PDF):

In what sense is this a novel situation? Should conflicts in the private domain be exempted from public scrutiny in cases where individual are being deprived of their basic legal rights? How many students study abroad and where do they go? Furthermore if the existing policies are found to be ineffective, what all policy measures can be suggested to the Government to put an end to this evil practice? Who are user entrepreneurs?

Сгенерированные новостные отчеты о NaNoGenMo от enkiv2 трудно отличить от настоящих статей.

В «Словаре языка D'skuban» от samcoppini словам из выдуманного компьютером языка даны определения терминов из реального словаря.

Новелла «Искатель» (PDF) от thricedotted рассказывает о том, как компьютер учится делать всё, что делают люди, с помощью сайта wikiHow.

Симуляция

Хорошей новелле нужны сюжет и развитие событий. Один из способов добиться этого — симуляция. Автор программы создает некоторый мир и описывает правила, по которым он функционирует. А потом просто перечисляет события, которые в этом мире происходят. Если эти события интересные, сюжет тоже получается интересным. Похоже на компьютерную игру, но вы не играете в нее, а читаете лог.

Герои серии фэнтези-новелл от mattfister ходят по разным местам. Если у них кончается еда, они идут охотиться или рыбачить, а устав, они разбивают лагерь. Иногда им встречаются враги, с которыми приходится сражаться.

Похожим образом герои новеллы flexo бродят по арене и дерутся при встрече.

Кроме сражений, есть и другие симуляции. В «Вечере дождливого дня» от cpressey Алиса и Боб играют в карты. В новелле nothings Ханна решает задачу о Ханойской башне (для 50000 слов хватило двенадцати дисков). Во «Флоре и фауне» от amarriner ботаник ищет выход из лабиринта, встречая по пути животных и растения.

Иногда авторы симулируют перемещения по реальному миру. В «Вокруг света за X статей Википедии» от kevandotorg Филеас Фогг и Паспарту совершают кругосветное путешествие, рассказывая факты о местах, которые они посещают. «Книга Элизы» от greg-kennedy приводит подробный маршрут сорокалетнего путешествия Моисея по пустыне (даже есть карта!).

Высокоуровневая генерация сюжета

Другой подход к построению сюжета — сформировать основные сюжетные точки, а потом уже развернуть их в подробный текст. cpressey реализовал это во «Времени судьбы» и описал в посте, как работает его построение сюжета. Компилятор истории начинает с простой последовательности:

[ПредставлениеГероев, *, Развязка]

Вместо звездочки компилятор может вставлять любые события со своим началом и концом:

[ПредставлениеГероев, [СокровищаУкрадены, *, СокровищаНайдены, *], Развязка]

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

ПредставлениеГероев = [ПредставлениеДетектива, ПредставлениеГрабителя]
СокровищаУкрадены = [ГрабительБеретСокровища, ГрабительСбегает]
СокровищаНайдены = [ДетективЛовитГрабителя, ДетективЗабираетСокровища]
Развязка = [ДетективИдетДомой, ГрабительСбегает]

После этого остается превратить каждое событие в его итоговое описание в новелле.

Другие форматы

Иногда авторы отходят от формата новеллы. Я уже упоминал несколько подобных, но вот еще:

  • «Пустыни Запада» (PDF) от mewo2 — путеводитель по выдуманному миру, для которого специально генерируются карта и язык. И для карты, и для языка подробно описано, как именно они генерируются.
  • «Великая книга трансмутаций» (PDF) от TobiasWehrum — сборник алхимических рецептов. Чтобы подбирать ингридиенты, используется какой-то корпус связанных понятий.
  • Для «Обложки „И восходит солнце“» adregan взял изображение, а потом написал название цвета для каждого пикселя. Кстати, картинку потом смогли восстановить обратно.
  • В «Отправьте по телефону» от hugovk приведен диалог двух человек, один из которых диктует другому программу. «Эс как доллар», только еще хуже. Немного красивой рекурсии: программа, которую диктуют, и сгенерировала этот диалог.

Графические произведения

Не всегда авторы ограничиваются текстовыми новеллами. doldrumorchids для «Людей нет» берет картинки с гугл-панорам, распознает объекты на них, а потом вставляет описания подобных объектов из произведений с «Проекта Гутенберг».

«Серафимы» от lizadaly — это загадочный манускрипт с картинками, написанный на неизвестном языке (с символами из рукописи Войнича).

«Что-то, благодарение и ничего» от zachwhalen и «Сгенерированный детектив» от atduskgreg — графические новеллы (комиксы). В первой текста нет, во второй он есть. Но оба автора постарались над стилизацией картинок, и получилось атмосферно.

Нейронные сети

Немного о плохом. Нейронные сети за последнее время научились многому: побеждать в го, накладывать фильтры на фотографии и сортировать огурцы. Но с генерацией текстов у них, похоже, как-то не клеится. В 2015 было несколько произведений, написанных нейронками (переосмысление Лавкрафта от R-Gerard, переосмысление Жюля Верна от estayton и что-то графическое от spikelynch). Все они меня не впечатлили. Думаю, это значит, что у нейронных сетей всё впереди, и в будущем мы еще увидим что-то более осмысленное от них.

Что дальше

Новый NaNoGenMo начался несколько дней назад. Вот репозиторий для него. Если вы хотите в нем поучаствовать — создайте в нем issue с заголовком вроде «intent to participate». В самом issue вы сможете обсудить свои идеи с другими участниками, а после завершения работы туда надо будет выложить ссылку на код и сгенерированную новеллу. Желаю успеха всем, кто решится!

Ссылки

  1. Репозитории прошлых лет: 2013, 2014, 2015.
  2. Серия статей, из которой я узнал про NaNoGenMo: 1, 2, 3, 4. В этом посте я использовал некоторые примеры оттуда.
  3. Оригинал этого поста на Хабре
Нет комментариев

Конспект «Software Estimation: Demystifying the Black Art» 21 июля 2015

Каждый раз, когда начальник или заказчик обсуждает новую задачу с программистами, звучит вопрос: сколько времени потребуется на разработку? Ответить на него сложно. Часто разработчики с ходу дают оценку, которая оказывается неверной и приводит к проваленным срокам.

Software Estimation: Demystifying the Black Art

Об этом один из главных советов Стива Макконнелла в «Software Estimation: Demystifying the Black Art»: никогда не следует давать необдуманную оценку. Лучше взять время и дать хорошую оценку, по которой разработка будет спланирована более реалистично. В книге Макконнелл рассказывает, как правильно оценивать сроки и стоимость разработки и как обсуждать эти оценки. Некоторые из его идей я пересказываю ниже в своем конспекте.

Техники из «Software Estimation» рассчитаны скорее на небольшие и средние проекты. Оценке крупных проектов объемом в сотни человеко-лет посвящены более серьезные книги и статьи в научных журналах.

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

Определение оценки

Не путайте оценки, цели и обязательства:

  • Оценка — прогноз затрат времени или денег. (Проект с большой вероятностью может быть завершен в июне-июле.)
  • Цель — сформулированная бизнес-задача. (Программу нужно показать на выставке 1 сентября.)
  • Обязательство — обещание предоставить функциональность с заданным качеством к конкретной дате. (Проект будет сдан не позже 1 августа.)

Желаемые цели могут быть недостижимы, а взятые обязательства — включать запас времени или не укладываться в оценку. Результатом оценки должен быть точный прогноз, а не соответствие целям и обязательствам. По этой же причине следует разделять оценку и планирование, цель которого — достижение заданного результата, а не получение объективной информации о стоимости проекта.

Смешивание оценок, целей, обязательств и планов часто становится причиной конфликтов.

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

Когда цель и оценка расходятся в пределах 20%, руководитель проекта может достичь цели, меняя набор функциональности, размер группы, сроки и так далее. Если расхождение больше, незначительные изменения не помогут.

Вероятностные оценки

Точечная оценка (около двадцати недель) дает мало информации. Неясно, насколько вероятно получить такой результат. Лучше, чтобы оценка содержала вероятность (20 недель с вероятностью 70%) или выражалась в виде диапазона (от 16 недель в лучшем случае до 24 в худшем).

При этом оценщики обычно испытывают желание сузить диапазоны. Диапазоны с вероятностью 90% оказываются верными только в 60% случаев. Поэтому не стоит указывать вероятность оценки, если ее не подкрепляют численные методы.

При отсутствии явного указания диапазона в расчет будет браться четкость (precision), то есть количество значащих цифр. «1 год», «4 квартала», «13 месяцев», «392 дней» — одна оценка в разных форматах воспринимается по-разному. Поэтому четкость оценки должна соответствовать точности.

Точность оценки

Есть два вида ошибок оценки — переоценка и недооценка.

Опасность переоценки:

  • Закон Паркинсона — работа занимает всё отведенное время.
  • «Студенческий синдром» Голдратта — разработчики работают спустя рукава, а в конце начинается аврал.

Опасность недооценки:

  • Снижается эффективность планирования. Из-за недооценки можно ошибиться с размером группы или заставить одну группу простаивать в ожидании другой.
  • Уменьшается время, отводимое на постановку требований и проектирование. Плохая архитектура еще больше затягивает работу.
  • При переходе проекта в состояние «опоздания» приходится тратить время на дополнительные действия — встречи с начальством для обсуждения хода работы, подготовку новых оценок, общение с клиентами по поводу нарушения срока поставки, решение проблем с «костылями», вставленными из-за поджимающих сроков.

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

Но хотя переоценка и не так опасна, как недооценка, нужно стремиться к точности. Преимущества точной оценки:

  • Состояние проекта можно отслеживать, сравнивая оценку и текущй результат.
  • Не появляются ошибки и костыли из-за приближения дедлайна.
  • Улучшается координация разработки с тестированием, документированием, маркетингом и другими видами деятельности.
  • Увеличивается точность оценки бюджета.
  • Повышается доверие к группе разработчиков.
  • Появляется возможность заранее принять корректировочные меры при несоответствии оценки и целей. (Надо сделать за четыре месяца, а возможно только за шесть ⇒ урезаем функциональность.)

Источники ошибок оценки

Неопределенность в требуемой функциональности. По мере продвижения работы над проектом неопределенность уменьшается, и оценка улучшается. Это называется конусом неопределенности.

Конус неопределенности

Конус неопределенности отражает лучшую оценку, которую можно получить на этом этапе. Реальная оценка может быть только менее точной.

Единственный способ сокращения неопределенности в оценке — сокращение ее в проекте. Сжатие конуса происходит благодаря принятию решений.

При итеративной разработке небольшой конус появляется в начале каждой итерации.

Нестабильные требования. Они не дают конусу сузиться. При изменении требований на поздней стадии конус становится таким:

Конус неопределенности в условиях нестабильности

Нельзя оставлять оценку прежней, если требования меняются.

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

Можно заложить какое-то количество изменений в требованиях. Конус неопределенности с учетом 50%-ного роста требований:

Конус неопределенности с учетом роста требований

Плохое управление процессом разработки. Слабый анализ требований, плохое проектирование, недостаточная квалификация работников и так далее. Невозможно точно оценивать процесс, который нельзя контролировать. Важнее избавиться от хаоса в управлении, чем улучшать оценку.

Неучтенные задачи. Их три вида:

  • неучтенные функциональные и нефункциональные требования (программа-установщик, обеспечение безопасности);
  • неучтенные действия по разработке (настройка системы сборки, исправление багов);
  • неучтенные действия, не связанные с разработкой (болезни, решение технических проблем).

В книге есть большой список задач каждого вида. Использование его в качестве чеклиста улучшает оценку.

Необоснованный оптимизм. Оценки разработчиков обычно содержат допуск на оптимизм от 20% до 30%.

Субъективность. Часто на оценщиков давят, чтобы оценки соответствовали целям бизнеса.

Этапы оценки

Процесс оценки состоит из следующих этапов:

  1. Декомпозиция проекта на части.
  2. Оценка каждой части в промежуточных показателях (пункты ТЗ, строки кода).
  3. Переход к непосредственным показателям (времени, срокам или стоимости).

Для экономии времени можно положиться на экспертную оценку и пропустить первый или второй этап — оценивать сразу весь проект или сразу в человеко-днях. Но это даст менее точный результат.

Декомпозиция

Декомпозиция — это разделение оценки на фрагменты, и оценка фрагментов по отдельности. Размер фрагментов зависит от этапа работы над проектом: чем дальше, тем они могут быть меньше.

Work breakdown structure — подход к декомпозиции работы.

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

При получении сводной оценки вычисляются оценки лучшего и худшего случаев. Формулы для получения этих оценок с различной достоверностью приведены в книге.

Оценка в промежуточных показателях

Выбранные промежуточные показатели должны высоко коррелировать с размером проекта. Это могут быть требования, пользовательские истории, функциональные пункты, страницы сайта, диалоговые окна, таблицы БД, стандартные компоненты и так далее.

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

Показатели могут быть и абстрактными. Например, это может быть условный размер фрагмента — «очень малый», «малый», «средний», «большой», «очень большой». При этом смежные категории должны отличаться как минимум вдвое. Сюда же относятся абстрактные рейтинги, используемые в планировочном покере.

Переход к непосредственным показателям

Для преобразования опосредованных показателей (количество требований) в оценку нужны соответствующие данные (время реализации одного требования). Могут использоваться:

  • Среднеотраслевые данные — данные других организаций по аналогичным проектам.
  • Исторические данные — данные организации по прошлым проектам.
  • Проектные данные — данные, полученные ранее в ходе оцениваемого проекта.

Исторические данные конкретной организации повышают точность благодаря учету организационных факторов. Среднеотраслевые данные следует применять только когда их нет.

Проще всего собирать исторические данные по проекту (размер проекта, объем работы, время, баги) в процессе работы над ним. Данные текущего проекта также помогут отследить динамику работы над ним и уточнить оценку на поздних этапах.

При сборе данных требуется принять некоторые решения (учитывать ли комментарии в коде? учитывать ли праздничные выходные дни?). Само решение ни на что не влияет. Главное, чтобы при сборе для всех проектов использовался общий подход, а оценщики понимали этот подход. Например, если при сборе не учитывается большое количество сверхурочной работы, в следующие проекты тоже будут автоматически заложены овертаймы.

По закону Брукса, с ростом размера проекта объем работы растет нелинейно. Поэтому нельзя использовать данные значительно больших или меньших по размеру проектов.

Индивидуальные экспертные оценки

Для оценки компонентов программы как в промежуточных, так и в непосредственных показателях могут применяться индивидуальные экспертные оценки. Для этого используется методика PERT.

Эксперт дает для каждого компонета оценки для лучшего, наиболее вероятного и худшего случая. Согласно PERT, ожидаемый результат вычисляется по формуле:

ОжидаемыйСлучай = [ЛучшийСлучай + (4 × НаиболееВероятныйСлучай) + ХудшийСлучай] / 6

Иногда используют более пессимистичный вариант:

ОжидаемыйСлучай = [ЛучшийСлучай + (3 × НаиболееВероятныйСлучай) + (2 × ХудшийСлучай)] / 6

Чтобы улучшать оценки эксперта, нужно по результатам проекта проверять, вошел ли фактический результат в предсказанный диапазон, и вычислять величину относительной ошибки (MRE):

MRE = [(ФактическийРезультат – ОценкаРезультата) / ФактическийРезультат] × 100%

Уточнение оценки с помощью группового обсуждения

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

При групповом обсуждении выполняют три правила:

  1. Каждый оценивает по отдельности, а потом все встречаются для сравнения оценок.
  2. Разницу между результатами надо обсудить, нельзя просто принимать среднюю оценку.
  3. С итоговой оценкой должна согласиться вся группа.

Широкополосный дельфийский метод предлагает структуру для группового обсуждения.

Групповая оценка стоит дороже индивидуальной, потому что требует собраний и работы нескольких оценщиков. Обычно достаточно 3–5 человек.

Оценочные программы

Существуют программы, предназначенные для вычисления оценки (например, COCOMO II). Они могут лучше человека смоделировать разброс в оценке, дать вероятностный диапазон, учесть издержки масштаба, учесть непредвиденное расширение требований, вычислить плановые показатели. Программы дают возможность быстро пересчитать показатели с другими входными условиями.

Программы стоят дорого, иногда это объясняется наличием базы исторических данных. Но данные хотя бы по трем проектам, сделанным в этой же организации, гораздо полезнее.

Оценочные программы могут выдать неверный результат из-за неверных предположений, неверной калибровки, внесения смещения при помощи коэффициентов. Результат всё равно нужно проверять на соответствие здравому смыслу.

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

Сравнение альтернативных оценок

Используйте несколько альтернативных методов оценки и проанализируйте совпадение или расхождение результатов.

Если результаты различаются более, чем на 5%, нужно найти источник этого различия.

Уточнение оценки по ходу работы

Проводите повторную оценку на разных этапах проекта.

По мере продвижения работы можно переходить к более точным оценкам.

Если оценка пересчитывается в результате нарушения промежуточных сроков, новая оценка должна основываться на фактическом ходе проекта, а не на изначальном плане.

Заказчикам обычно не нравится увеличение оценки по ходу проекта. Лучше давать им оценку в виде диапазона, который будет постепенно уточняться.

Представление оценки

Важной частью оценки являются задокументированные предположения, которые легли в ее основу. К ним относятся: обязательные и необязательные функции программы, глубина проработки функций, доступность ключевых ресурсов, зависимость от третьих сторон, основные неизвестные факторы, качество оценки, назначение оценки. Если какие-то из этих предположений не сбудутся, это станет основанием для пересмотра оценки.

Если представить оценку в виде диапазона плюс/минус, то при прохождении по организации она может превратиться в точечную, иногда с усечением до минимума.

Можно сразу квантифицировать риски — указать, как изменится оценка при нарушении каждого предположения (не получилось использовать код предыдущего проекта ⇒ +1,5 месяца).

Оценки с коэффициентом достоверности можно представить в виде графика:

График достоверности оценки

Политика: как избежать проблем из-за сроков

Часто руководство беспокоится о внешних факторах, которые требуют сдать проект в указанный срок или уложиться в заданный бюджет. Нужно понимать эти факторы и показывать понимание.

Не нужно обсуждать оценки — они являются результатом анализа и не могут измениться. Обсуждайте обязательства, принимаемые на основе оценки.

Разработчики часто беспокоятся, что высокая оценка приведет к отклонению проекта. Это нормально. Занизив оценку, они заставят руководство принять неверное решение.

В ходе переговоров можно прийти к решениям, которые позволят достичь целей без взятия нереалистичных обязательств. Это может быть исключение некоторых функций, их приоритезация, привлечение дополнительных ресурсов. Разработчик должен предложить варианты планирования, поддерживающие цели организации.

Эти варианты должны быть продуманы заранее. В процессе обсуждения не следует давать необдуманных оценок.

Нет комментариев

Посёлок Абонентного Ящика 001, вам на 1 10 января 2014

Уже известно, что спастись от смерти на виселице можно с помощью жижи и цацки. Давайте попробуем узнать, как лучше играть в другую игру — в города.

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

По не до конца выясненным лингвистическим причинам многие города мира начинаются и/или заканчиваются на букву «А», в связи с чем можно предполагать, что выиграет игрок, знающий больше городов на эту букву (Анапа, Алушта, Аделаида и т. д.).

Для проверки этого утверждения потребуется список городов мира и немного кода на питоне.

Получение списка городов

Города — такая игра, в которую невозможно играть, не зная названий городов. Поэтому для анализа требуется словарь с городами на русском языке.

В интернете есть базы, которые в основном предназначены для использования на сайтах для указания города при регистрации. Но все они не понравились мне. Некоторые из них, обещая список полностью на русском языке, внезапно переходили на родной язык для городов из других стран. Для сайта это нормально, но играть в города так нельзя. А в остальных базах городов было слишком мало. Для проверки полноты я придумал «тест Аддис-Абебы», и ни одна из них его не прошла.

Пришлось вытаскивать названия из википедии. Там последней проблемы нет, и даже наоборот: уже на первой странице категории можно увидеть XVI Партсъезд и 25 км Железной Дороги Мончегорск-Оленья, а где-то дальше есть больше всего впечатливший меня Посёлок Абонентного Ящика 001. Но это не так страшно, удалить всегда можно.

И сразу же код.

import mwclient

def get_page_names():
    site = mwclient.Site('ru.wikipedia.org')
    category = site.Pages[u'Категория:Населённые пункты по алфавиту']
    return (page.name for page in category)

Для получения списка страниц категории будем обращаться к апи википедии, используя библиотеку mwclient.

def is_letter(c):
    return u'а' <= c.lower() <= u'я'


def starts_and_ends_with_letter(name):
    first = name[0]
    last = name[-1]
    return is_letter(first) and is_letter(last)

Так будем выбрасывать названия, которые начинаются или заканчиваются не на букву.

def remove_braces(name):
    return name.split('(')[0].strip()

Хорошее название для города придумать трудно, поэтому они иногда повторяются. В таких случаях в википедии пишут в скобках пояснение, о каком городе эта статья. Нас это не интересует, поэтому скобки и всё, что после них, будем обрезать.

def get_cities():
    used_cities = set()
    for name in get_page_names():
        city = remove_braces(name)
        if starts_and_ends_with_letter(city) and city not in used_cities:
            used_cities.add(city)
            yield city

Получим список городов, выбрасывая повторяющиеся и те, которые нам не подходят.

import codecs

with codecs.open('cities.txt', 'w', 'utf8') as f:
    for city in get_cities():
        f.write(city + '\n')

Этот список сохраним в файл.

Полностью скрипт получился таким.

Извлеченный словарь содержит 130 тысяч городов. В нем еще мог остаться какой-то единичный мусор, который общую картину менять не должен.

Анализ

В отличие от виселицы, где можно было полностью перебирать словарь, здесь так сделать не получится. Есть 130 тысяч вариантов первого хода, потом в среднем 4 тысячи вариантов второго, потом еще 4 тысячи третьего... Все эти числа надо перемножить, и в итоге получится совершенно астрономическое количество вариантов. Но самое обидное, что если даже получится построить оптимальные стратегии для всех игроков, они окажутся бесполезными для игры с другим словарем. А словари вообще у каждого человека разные. Поэтому самое полезное, что можно сделать, — вычислить букву, на которую стоит обратить особое внимание (как в википедии).

Начнем с упрощения модели. В названиях городов для нас значимыми являются только первая и последняя буквы. Так список из 130 тысяч городов уменьшается до маленького ориентированного графа. Вершинами его будут буквы, а ребро из x в y будет иметь вес, равный количеству названий, начинающихся с x и заканчивающимися на y.

Может быть, в графе уже можно решать полным перебором? Там же всего 30 вариантов начала, 30 вариантов второго хода, 30 вариантов третьего, четвертого, пятого, шестого... Нет, тоже многовато.

Просто сравнить сумму весов исходящих и входящих ребер? Если на какую-то букву начинается мало городов, а заканчивается ею много, то ее можно хорошо использовать против соперника. Но реальность игры в города сложнее: ведь надо учитывать, из каких вершин надо попадать в эту вершину, как попадать в них и так далее. Поэтому используем более хитрый алгоритм.

У каждой буквы будет рейтинг, который зависит от ее связей. Входящие ребра будут передавать часть рейтинга от вершины, из который они выходят, и часть этого рейтинга будет уходить дальше через исходящие ребра. Вычисляется такой рейтинг с помощью алгоритма PageRank, про который я однажды уже рассказывал.

Перейдем к коду.

def get_cities():
    with open('cities.txt') as f:
        for line in f:
            yield line.strip().decode('utf8').lower()

Достаем список городов из файла.

def get_edge(city):
    return city[0], city[-1]

Определяем функцию для получения из города ребра (то есть начальной и конечной вершин).

from collections import Counter

def get_weighted_edges(cities):
    counter = Counter(get_edge(city) for city in cities)
    return ((a, b, float(weight)) for (a, b), weight in counter.iteritems())

И еще одну, которая получает список городов и возвращает ребра в виде списка кортежей из начальной вершины, конечной вершины и веса. Здесь используется удобная способность контейнера Counter сразу же пересчитывать всё, что передается в него при инициализации.

import networkx as nx

def get_graph():
    cities = get_cities()
    edges = get_weighted_edges(cities)
    g = nx.DiGraph()
    g.add_weighted_edges_from(edges)
    return g

Создаем ориентированный граф из этих ребер с использованием уже известной библиотеки networkx.

def add_final_vertices(g):
    g.add_weighted_edges_from((v, v + u'_finish', 1.0) for v in g.nodes())

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

def evaluate_letters():
    g = get_graph()
    add_final_vertices(g)
    pr = nx.pagerank(g)

    for a, b in sorted(pr.items(), key=lambda x: x[1]):
        if a[1:] == '_finish':
            print a[0], b

Посчитаем пейджранки и выведем результат. Результат получился таким:

б 0.0047940481766
п 0.00479409201359
м 0.00479468124255
л 0.00479518712277
в 0.00479519556089
к 0.00479524573281
с 0.00479536849038
з 0.00479577419979
э 0.00479586689975
г 0.00479595151747
ч 0.00479598047734
д 0.00479609383531
т 0.00479638754244
ф 0.00479694481314
ш 0.00479694980713
х 0.0047970864409
ж 0.00479821870855
р 0.00479830237913
у 0.00480167551917
н 0.00480336443514
ю 0.00480600994751
ц 0.00480935947044
а 0.00480975757728
и 0.00481506621565
щ 0.00481612997918
о 0.00481980791183
я 0.00482062139306
е 0.00486013871912
й 0.00491924389476
ы 0.00593319978398
ь 0.0278309795176

Ой. Будем считать, что алгоритм прошел проверку на разумность: победил мягкий знак, на который некоторые города заканчиваются, но ни один не начинается. Поправим код, чтобы обрезать мягкий знак на конце слов. (А заодно и ы. Ыспарты и еще нескольких городов не достаточно, чтобы можно было нормально играть с ней.)

def get_edge(city):
    return city[0], city.strip(u'ъыь')[-1]


def get_weighted_edges(cities):
    counter = Counter(get_edge(city) for city in cities if not city.startswith(u'ы'))
    return [(a, b, float(weight)) for (a, b), weight in counter.iteritems()]

Полностью код выглядит так, и он выдал такой результат:

б 0.00450930556033
п 0.00450944258223
м 0.00451008313833
к 0.00451058888306
в 0.00451067983318
с 0.00451093647496
э 0.00451113552385
з 0.00451128722349
ч 0.00451135271873
г 0.00451146651546
д 0.0045119188442
х 0.00451228788221
т 0.00451237835021
ф 0.00451246102843
ш 0.0045125190597
л 0.00451323505599
ж 0.00451361765873
р 0.00451425487076
у 0.00451717313258
н 0.00451985073145
ю 0.00452106046281
а 0.0045266942414
щ 0.00453027578976
и 0.00453275391185
ц 0.00453579724983
о 0.00453796965795
я 0.00453843101065
е 0.00458125968474
й 0.00463979500792

Самой востребованной буквой оказалась й. На нее в использованном словаре заканчиваются 4093 слова, а начинаются с нее всего 187 слов.

Проблема длиннейшего сиритори

В ходе анализа я пытался найти чужие решения подобной задачи. За рубежом эта игра называется Geography и является частным случаем игры Word Chain. Но результаты нашлись только для японского названия — сиритори (не путать с упоротым авангардистом).

От него получила имя задача, которая называется проблемой длиннейшего сиритори: построить из заданного словаря как можно большую цепочку в соответствии с правилами игры. Есть несколько японских статей об этой задаче. Вот эта, например. Ничего, кроме абстракта не понятно, но по картинкам видно, что у них тоже какие-то графы.

К счастью, есть статья Даики Каваками (надеюсь, правильно транскрибировал) на английском, которая написана позднее и учитывает накопленный опыт по этому вопросу. Там предлагается интерактивный алгоритм, способный решить проблему длиннейшего сиритори.

Даики Каваками представляет словарь в виде такого же ориентированного графа, как у нас, а игру — как перемещение между вершинами с уменьшением веса использованного ребра на единицу. Решение задачи находится в процессе игры с использованием алгоритмов, называемых итераторами, которые оценивают текущее состояние и выбирают следующую вершину. В статье приводится три итератора:

  1. Первый выбирает вершину, в которую ведет самое тяжелое ребро.
  2. Второй выбирает вершину, для которой сумма исходящих весов максимальна (то есть заглядывает на один шаг вперед).
  3. Третий учитывает оба этих значения, складывая их с разными коэффициентами.

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

Полученная с его помощью цепочка содержала 50% словаря, тогда как более ранние методы могли покрыть словарь только на 46%. (Из этого почему-то сделали вывод, что проблему длиннейшего сиритори теперь можно считать решенной. Не очень понял, почему результат нельзя улучшить еще, заглядывая вперед на два шага, например, ну да ладно.)

Этот алгоритм предлагает самый альтруистичный вариант игры: ходить так, чтобы у соперника был максимальный выбор ходов. Нас же интересует противоположная стратегия, которую можно получить из этой. Начнем с реализации исходного алгоритма.

def get_out_weight(graph, vertex):
    return sum(d['weight'] for u, v, d in graph.out_edges(vertex, data=True))

Эта функция вычисляет вес всех ребер, исходящих из вершины.

def choose_next_vertex(graph, vertex):
    possible_moves = [n for n in graph.neighbors(vertex)
                        if graph[vertex][n]['weight'] > 0]
    if not possible_moves:
        return None
    scores = max((get_out_weight(graph, n), n) for n in possible_moves)
    return scores[1]

Эта функция выбирает следующую букву, используя алгоритм второго итератора.

def run_shiritori_algorithm():
    g = get_graph()
    current_letter = choice(g.nodes())
    i = 0
    while True:
        next_letter = choose_next_vertex(g, current_letter)
        if not next_letter:
            print current_letter, i
            break
        g[current_letter][next_letter]['weight'] -= 1
        i += 1
        current_letter = next_letter

И вот так происходит само моделирование: переходим от буквы к букве, пока не окажемся в тупике. Начальная буква выбирается случайно.

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

Теперь изменим стратегию так, чтобы выбиралась вершина, из которой ходов меньше всего. Для этого нужно всего лишь заменить max на min в функции choose_next_vertex. Полностью код можно посмотреть здесь.

Тогда игра будет заканчиваться после 372–373 городов. В букве й, конечно. Судя по тому, что длина цепочки в два раза больше количества городов, начинающихся с й (чуть меньше за счет Йенбая и Йосвайняя), вся игра представляла собой танцы вокруг этой буквы. То есть ничего примечательного в таком результате нет. Интересно, могут ли быть графы, в которых проблема кратчайшего сиритори решается не так скучно.

Итог

Как и википедия, я не могу объяснить лингвистические причины, из-за которых названий на букву й так мало, кроме того, что ее вообще считают ущербной. Зато городов, которые заканчиваются ею, достаточно много благодаря множеству топонимов-прилагательных. Список из четырех тысяч названий, грепнутый из использованного словаря, я выложил сюда. Выберите оттуда штук двести городов, которые вам понравятся, и запомните до следующего раза, когда будете играть в города. Больше вам, скорее всего, не понадобится.

3 комментария
← Раньше