Учитывая шаблон, представляющий список длин, и строку, представляющую эти длины, они совпадают?
Для тех, кто заинтересован, этот вопрос эквивалентен проверке правильности строки или столбца нонограммы . Тем не менее, я опустил все формулировки, относящиеся к нонограммам, чтобы сделать вопрос менее запутанным для тех, кто не знаком с этими головоломками.
вход
Две строки данных, разделенные новой строкой.
Первая строка будет разделенным пробелами списком целых чисел, например:
3 6 1 4 6
Эта строка описывает шаблон заполненных пробелов размером, равным целочисленному списку, разделенных пробелами неизвестной положительной длины, которым должна соответствовать вторая строка. Также могут быть пустые места в начале и в конце совпадающей строки.
Вторая строка будет строкой, которая может соответствовать или не соответствовать шаблону в первой строке. Она целиком состоит из
#
,x
и_
. Эта строка гарантированно будет по крайней мере такой же, как и сумма целых чисел в первой строке плюс количество различных целых чисел, минус 1, и может быть длиннее. Таким образом, вторая строка в этом случае гарантированно будет длиной не менее(3+6+1+4+6) + (5) - 1
24 символов. Вот пример строки из 24 символов, которая соответствует шаблону в первой строке:###_######_#_####_######
Значение символов:
#
Это представляет собой заполненную коробкуx
Это представляет поле, помеченное как «гарантированно будет пустым»_
Это представляет собой неизвестное / не помеченное поле.
Цель
Идея состоит в том, чтобы:
- Убедитесь, что вторая строка может быть допустимой строкой, которая соответствует шаблону первой строки.
- Вы должны напечатать однозначное сообщение об ошибке (как вы решите сделать это, зависит от вас; примеры ниже пишите,
ERROR
но это не обязательно должны быть те 5 символов), если неизвестные пробелы не могут быть заполнены либо,#
либоx
соответствовать первому линия.
- Вы должны напечатать однозначное сообщение об ошибке (как вы решите сделать это, зависит от вас; примеры ниже пишите,
- Печать нулевой индексированные показатели целых чисел , которые были полностью размещены в строке, через пробел. Если есть неопределенность, не печатайте индекс .
Примеры:
Input: | Output: | Reason:
--------------------------------------------------------------------------
3 6 1 4 6 | 0 1 2 3 4 | This is a complete string that
###x######x#x####x###### | | matches perfectly.
--------------------------------------------------------------------------
1 2 1 | 0 1 2 | There is no ambiguity which filled cells
#____xx___##__x_# | | correspond to which parts of the pattern.
--------------------------------------------------------------------------
1 2 1 | | I don't know whether the filled block is
____#___x | | part of the 1, 2, or 1, so output nothing.
--------------------------------------------------------------------------
1 2 1 | ERROR | The first unknown cell will create a block that
#_#x_# | | matches either 1 1 or 3, but not 1 2.
--------------------------------------------------------------------------
1 2 1 | 0 2 | Even though we know where all the filled cells
#____# | | must be, only 0 and 2 are actually filled here.
--------------------------------------------------------------------------
1 1 1 1 | | There are so many possible ways to do fill this,
__#_______#____ | | we don't know which indices are actually matched.
--------------------------------------------------------------------------
4 4 | | Again, we don't know WHICH 4 is matched here,
______x####________ | | so output nothing.
--------------------------------------------------------------------------
4 4 | 0 | However, here, there's no room for a previous 4,
__x####________ | | so the displayed 4 must be index 0.
--------------------------------------------------------------------------
3 | ERROR | We can't fit a 3 into a space before or after
__x__ | | the x, so this is impossible to match.
--------------------------------------------------------------------------
5 1 3 | 0 | While we can match the 5, we don't know whether
x#####x____#____ | | the single block matches the 1 or the 3.
--------------------------------------------------------------------------
3 2 3 | 1 | The two has been completely placed,
____##x##____ | | even though we don't know which it is.
Правила:
Вы можете написать программу или функцию , которая получает входные данные в виде строки с разделителями новой строки или из STDIN (или ближайшей альтернативы) и возвращает выходные данные в виде строки с разделителями пробелами или печатает их в STDOUT (или ближайшей альтернативе). При желании вы можете включить один завершающий символ новой строки в вывод.
Кроме того, стандартные лазейки, которые больше не смешны , запрещены .
источник
Ответы:
Perl, 134 байта
(включает 1 переключатель)
Принимает две строки ввода от STDIN. Должен быть повторно выполнен для каждого ввода.
Идея состоит в том, чтобы сначала извлечь все возможные шаблоны, которые соответствуют заданным длинам. Например, если у нас есть длина
1 2
и шаблон#_x_#_
, то соответствующие шаблоны(#, _#)
и(#, #_)
. Затем объедините соответствующие шаблоны для каждого индекса - для примера, результатом является список(##, _##_)
. Теперь напечатайте индексы всех строк в списке, которые имеют только символы «#».Я получил метод для извлечения всех возможных совпадений из регулярного выражения в Perl здесь .
источник