Можете Ли Вы Разгадать Кроссворд С Регулярным Выражением?


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

Идея достаточно проста — создать головоломку в стиле кроссворда с регулярными выражениями, которые являются «подсказками». Если вы не знаете, что такое регулярное выражение — это способ указать, какие символы разрешены, используя символы подстановочных знаков и многое другое. Например, точка соответствует любому отдельному символу, и .* любое число (включая ноль) символов и так далее.

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

Например, первая строка содержит регулярное выражение

.*H.*H.*

что означает, грубо говоря, любые буквы, за которыми следует буква «Н», затем любые буквы, за которыми следует другая буква «Н», и любая последовательность букв, чтобы закончить. Другими словами, в строке есть по крайней мере два Hs. 

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

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

Посмотрите, сможете ли вы уйти очень далеко:

Скачать PDF

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

Если вы хотите увидеть решение, посетите: Обычное решение кроссворда

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

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

Кроме того, есть ли еще какие — либо головоломки программирования, которые мы не придумали- возможно, головоломка со скобками? 


Добавить комментарий